skip to content

How does Go's Swiss-table map layout differ from the old bucket-and-overflow-chain design?

level: middleimportance: nice to knowfreq 30%

answer

  1. eight slots share one summary word
  2. a few hash bits per slot, checked together
  3. probe onward instead of chaining
  4. large maps are a directory of tables
  5. semantics unchanged, cost changed

basics

~20 s

Since Go 1.24 a map stores entries in groups of eight slots, each slot summarised by a control byte carrying part of its key's hash. One word-sized comparison tests all eight at once, replacing walks down chains of overflow buckets.

solid answer

~50 s

The old implementation put eight key/value pairs in a bucket alongside an array of hash prefixes, and when a bucket filled it allocated an overflow bucket and chained it on — so a crowded map degraded into pointer chasing. Since Go 1.24 the runtime uses Swiss tables: part of the hash picks a group of eight slots, and seven more bits of the hash go into that group's control word, one byte per slot. A single word-sized operation on the control word says which slots could possibly match, so a lookup usually does one key comparison and a miss often touches no key at all. A full group probes on to the next group instead of chaining. A large map is a directory of bounded-size tables, so growth rehashes one table rather than the whole map. Visible semantics did not change: order is still randomised, elements are still unaddressable, the map still never shrinks.

code

go · 13 lines
go
func BenchmarkFill(b *testing.B) {
	const n = 100_000
	for b.Loop() {
		m := make(map[int]int, n) // presized: filling does no growth
		for i := range n {
			m[i] = i
		}
	}
}

// go test -bench=Fill -benchmem reports ns/op, B/op and allocs/op.
// Dropping the size hint raises B/op and allocs/op, because the map
// grows repeatedly while it fills.

go deeper

for a junior

You are not expected to know the internals. Know that a Go map is a hash table with amortised constant-time lookup, and that its implementation was replaced without changing how you write map code.

for a middle

Describe groups of eight slots with a control word of hash bits tested together, and say why that beats walking a chain of overflow buckets, especially for lookups that miss.

for a senior

Tie the layout to numbers you have measured: presize with make when the size is known, keep keys small and cheaply hashable, and read allocs/op from a -benchmem run before claiming a map change helped.

for a principal

Judge when map internals deserve anyone's attention at all. Most services are not map-bound, and the call is whether an engineer's week goes here or into the allocation, query or timeout that actually dominates the profile.

## The problem a hash table has to solve Look up a key: hash it, go where the hash says, and check whether what is there is actually your key. Everything interesting is in how collisions — two keys landing in the same place — are handled, and how the table grows when it fills. ## The old design (Go 1.0 through 1.23) A map was an array of **buckets**. Each bucket held up to eight key/value pairs plus a small array of `tophash` bytes — the top eight bits of each key's hash, used as a cheap filter so the runtime could skip a slot without comparing the full key. The low bits of the hash chose the bucket. If all eight slots were taken and a ninth key landed there, the runtime allocated an **overflow bucket** and chained it to the first. Lookups walked the chain. That works, but it has two costs: each overflow bucket is a separate allocation reached through a pointer, and an unlucky hash distribution turns a constant-time lookup into a walk down a linked list, with a cache miss at each hop. Growth doubled the bucket array. To avoid a long pause, the runtime kept the old array alive and **evacuated incrementally**: every write moved a bucket or two across, so for a while the map had entries in two places and every operation had to consider both. ## The Swiss-table design (Go 1.24 onward) Go 1.24 replaced this with an adaptation of the Swiss table, a design popularised by Abseil's flat hash map. The unit is a **group of eight slots**, and beside the group sits a **control word**: eight bytes, one per slot. Each control byte holds either a marker meaning empty or deleted, or seven bits taken from that slot's key hash. A lookup splits the hash: one part selects the group, the other seven bits become the value to search for. The runtime then compares those seven bits against **all eight control bytes at once** using ordinary 64-bit arithmetic on the control word (or a vector instruction where one is available). The result is a small bitmask of candidate slots. Typically that is one candidate, and one full key comparison confirms it. If the mask is empty and the group has a free slot, the key is definitively absent — the runtime answered a miss without reading a single key or value. When a group is full and the key is not there, the search **probes on** to another group rather than allocating an overflow bucket. There is no chain and no per-overflow allocation. ## Growth without a whole-map rehash A small map — up to eight entries — is a single group with no indirection at all, which is the common case in a lot of Go code and is now very cheap. Larger maps are organised as a **directory of tables**, in the manner of extendible hashing. Each table is itself groups of eight and is capped at a bounded size (on the order of a thousand entries in the current implementation). When one table fills, only that table is grown or split, and only its entries are rehashed; every other table in the directory is untouched. The consequence for you: the worst-case cost of a single insert is bounded by one table's size rather than by the size of the whole map, and there is no long tail of writes paying an evacuation tax after a growth event. ## What this changed for your code, and what it did not Changed: lookups, especially misses, got faster; memory overhead per entry went down; the pathological chained-overflow case is gone; small maps got cheaper. **Not** changed — and this is the part interviewers probe: - Iteration order is still randomised on every loop. - Map elements are still not addressable; `&m[k]` is still a compile error. - A map still **never shrinks**; deleting entries does not return the table storage. - Keys must still be comparable, and the same key type behaviour applies. - `make(map[K]V, n)` still matters: the size hint allocates enough groups and tables up front so filling n entries does no growth at all. ## How to talk about it without overclaiming The defensible summary is short: *groups of eight slots with a control word of hash bits, tested in parallel, open addressing instead of overflow chains, and a directory of bounded tables so growth is localised.* Precise internal constants (exact load thresholds, exact probe sequence) are implementation details that have already changed once and may change again — quoting them confidently is a small risk with no upside. The better move in an interview is to pivot from the mechanism to what you do with it: presize maps whose final size you know, keep key types small and cheaply hashable, and measure with a benchmark rather than reason from the layout. Reading `allocs/op` and `B/op` from a `-benchmem` run across a growing key count tells you more about your workload than any structural argument does.

  • How does a large Swiss-table map grow?
    It is a directory of independently allocated tables, each capped at a bounded size. When one table fills, only that table is grown and only its entries are rehashed; the rest of the directory is untouched. So the worst-case cost of one insert is bounded by a single table rather than by the size of the whole map.
  • Why is a lookup for a key that is absent cheaper than before?
    The control word summarises eight slots with a few hash bits each. If no control byte matches and the group has a free slot, the key cannot be there, and the runtime returns without reading any key or value — versus the old design, which could walk a chain of overflow buckets checking hash prefixes.
  • Does make(map[K]V, n) still matter with Swiss tables?
    Yes. The size hint allocates enough groups and tables up front, so filling n entries triggers no growth and no rehashing. Run the fill with and without the hint under -benchmem and the difference shows directly in allocs/op and B/op as n rises.
  • Did the change alter anything you can observe from Go code?
    Nothing semantic. Iteration order is still randomised per loop, elements are still unaddressable, the map still never shrinks, and keys must still be comparable. Only speed and memory footprint moved, which is precisely why the runtime team could make the swap at all.

Each group of eight slots carries a one-line index card summarising all eight; you read the card in a single glance instead of opening every drawer, and a crowded shelf sends you to the next shelf rather than bolting an annexe onto this one.

saying these in an interview costs you the question

  • Says a Go map is a tree or keeps keys sorted
  • Thinks the new implementation gave maps a defined iteration order
  • Claims every slot in a group is key-compared on each lookup
  • Says the change made maps shrink when entries are deleted
  • Believes overflow buckets are still chained in current Go