Maps in Go: the language contract, the Swiss Table, and four consequences of the design

What the language guarantees

Six operations, and there are no others:

scores := map[string]int{"alice": 10}
scores["mike"] = 12                 // write
score := scores["alice"]            // read
score, ok := scores["john"]         // read, checking presence
delete(scores, "alice")             // delete
n := len(scores)                    // how many entries
for k, v := range scores { }        // iterate

Reading a missing key does not panic — it gives the zero value of the element type. Hence the question the two-result form exists for: how do you tell an existing key whose value is 0 from a missing one? With the single-result form, you cannot.

A nil map reads but does not write: len, range and delete work, a write panics. The iteration order is unspecified and must not be relied on. Concurrent access with a write requires synchronisation — a rule absent from the map section of the spec entirely; it lives in the memory model.

Maps and goroutines. A runtime crash is not a protection mechanism: a run of bench/gomap/concurrent.go shows that two concurrent writes kill the process with fatal error: concurrent map writes, while a read concurrent with a write finishes with exit code 0 and not a single message. The race detector finds that same race every time. The cure is a mutex beside the map or ownership by one goroutine; sync.Map is built for two narrow cases, and its own documentation talks you out of it.

Everything below is the Go 1.24 implementation. It explains behaviour and guarantees nothing.

Why changes survive a function call

func add(m map[string]int) { m["x"] = 1 }          // visible outside
func grow(s []int)         { s = append(s, 42) }   // NOT visible outside

Passing a map to a function copies the map value, but it keeps referring to the same data structure — so changes to elements are visible to the caller. A slice copies a header carrying the length, and the new length stays in the copy. How a map value is represented inside is an implementation detail; it can be confirmed, but it should not carry an argument:

unsafe.Sizeof(map[int]int{})   // 8 — one word
unsafe.Sizeof([]int{})         // 24 — three

The mechanism: the control byte, one operation, and the stopping rule

The key's hash splits in two: the upper 57 bits choose a group of eight slots, the lower 7 are written into a byte tag for that slot. Eight such bytes lie next to each other and form one 64-bit control word.

Why are tags seven bits and not eight? Because the eighth distinguishes three states of a slot:

  empty    1 0 0 0 0 0 0 0
  deleted  1 1 1 1 1 1 1 0
  full     0 h h h h h h h     ← the seven tag bits

The top bit is an inverted occupancy flag: for a full slot it is clear. Hence "full", "empty or deleted" and "empty" are three tests on the same bit.

Now the point: the wanted tag can be compared against all eight slots at once with one operation on that word. It takes four steps: replicate the tag across every byte by multiplying by 0x0101010101010101; XOR — a matching byte becomes zero; subtract one from each byte — a zero byte borrows and its top bit lights up; keep those bits with the mask 0x8080808080808080.

v := uint64(g) ^ (bitsetLSB * uint64(h))
return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)

Seven bits are few, and a false match happens about once in 128, so after a match the key is compared in full. A non-match, though, rules the slot out for certain: the full comparison falls to one or two slots out of eight rather than all of them.

The second half of the mechanism is the stopping rule: a lookup ends only on finding a group with a free slot. The logic is simple: had the key existed, it would lie no further than the first free spot. A deleted slot does not count as free — otherwise deleting one key would hide its neighbour. That is what the byte's third state is for: a deleted slot is free for an insert but occupied for a lookup.

And hence: free slots must exist. So the map grows without waiting to be full — at 7/8. An eighth of the slots is kept empty on purpose, as the price of giving a lookup somewhere to stop.

Consequence one (lookup): a miss costs more than a hit

A hit stops on the key it found. A miss has to reach a free slot, and those are scarce.

The same rule explains the comparison with the old implementation — it is still there behind GOEXPERIMENT=noswissmap, so both can be measured on one machine:

On a hit the new one is twice as fast. On a miss it is 1.4 times slower, and the run ranges do not overlap. In the old map a miss looked at one bucket and ended there; in a Swiss Table it walks to a free slot. What makes a hit fast makes a miss long.

One shape of map was measured — map[int64]int, 100,000 entries, consecutive keys; the cost of a miss depends on the load factor.

Consequence two (iteration): the only rule is not to depend on the order

One sentence goes into your work: code must not depend on a map's iteration order. Everything below is a study of the implementation: it explains why buggy code can go unbroken for a long time, but the bug is no less of a bug for it.

A nine-entry map over two thousand iterations produces exactly nine distinct orders — not 362,880. All nine are rotations of one sequence, because the iterator contains

entryIdx := (it.entryIdx + it.entryOffset) & entryMask

and entryOffset is taken once for the whole iteration. After that the slots go in order — along the same table.

This is more dangerous than real randomness. Code depending on A coming before B would, under shuffling, fail in half the runs. Under rotation it fails only on the shifts that cut the tape between those keys, that is, far more rarely: it will pass the tests and break in production.

The rule's boundary is 896 entries: maxTableCapacity (1024) times 7/8. Beyond that the map no longer fits in one table, the iterator gains a second offset over the table directory, and the number of orders grows: at 897 entries it is already 1174. The boundary was not tuned but computed from two constants — and then confirmed by running it.

If you need an order, sort: slices.Sorted(maps.Keys(m)).

Consequence three (growth): the entries move

At a load factor of 7/8 the table is rebuilt at twice the size and the entries are laid out afresh. Two consequences follow:

An element's address cannot be taken — a pointer taken before a growth would lead into somebody else's memory. The ban is at compile time. The way around it is map[K]*V: the pointer moves, the object stays put.

A size hint removes not bytes in the map but the intermediate tables:

The finished map is the same — second column. What halves is the garbage along the way: without a hint the map grows by doubling, and the sum of the tables thrown away is roughly the size of the final one.

Consequence four (memory): the table does not shrink

a million entries:               36.0 MB,  len = 1,000,000
after deleting every key:        36.0 MB,  len = 0
after clear(m):                  36.0 MB,  len = 0
after m = make(map[int]int):      0.1 MB

Only replacing the map frees anything. For a long-lived cache that is the difference between "the memory came back" and "it never will": it will hold memory at its historical maximum.

What the design does not explain

Two things live by their own rules and have to be known separately.

The key contract. float64 is comparable, but NaN != NaN — and a map looks keys up by ==. Five inserts of one NaN give five entries, a lookup finds none of them, delete stays silent. They can be removed only with clear or along with the map; filter them at the entrance with math.IsNaN. A nil map has a milder asymmetry: reading, len, range and delete work, only a write panics. And map[any]T defers the comparability check to run time: m[[]int{1}] = 1 gives hash of unhashable type []int, and int(1) and int64(1) are different keys there.

Concurrent access. A write from two goroutines is not a panic but a fatal error: recover will not help and the stack is not unwound. That is deliberate — a race on a multiword structure can corrupt memory, and failing loudly is safer. Cured with a mutex beside the map; sync.Map is built for two narrow cases, and its own documentation talks you out of it.

What costs what

• v, ok := m[k] is free: 18.43 against 17.83.
• A string key costs half again as much as an integer one — the hash is computed over the string's contents.
• Dense integer keys: a read from a map 15.55 ns, from a slice 1.12. Iterating a hundred thousand entries — 855,702 ns against 37,434. A map is not needed here.

The article has three parts, and their order is not accidental. First, what a map promises as a language construct: that is enough to write correct code, and there is not a word about internals in it. Then how lookup is built in Go 1.24. And only after that, the consequences that follow from the design — the ones that would otherwise have to be memorised.

Part I. What the language guarantees

Everything in this part is contract: it holds in any version of Go and does not depend on how a map is built inside.

A map in five minutes

Six operations, and there are no others:

scores := map[string]int{
    "alice": 10,
    "bob":   7,
}                                   // create
 
scores["mike"] = 12                 // write
score := scores["alice"]            // read
score, ok := scores["john"]         // read, checking presence
delete(scores, "bob")               // delete
n := len(scores)                    // how many entries
 
for name, s := range scores {       // iterate
    fmt.Println(name, s)
}

The specification defines a map like this:

The word unordered here is not about the order being random but about there being no such notion: a map promises no order, so there is nothing to rely on.

Of the key type the specification demands one thing — comparability:

Numbers, strings, booleans, pointers, channels, and also structs and arrays made of comparable parts will do. A slice, a map and a function will not, and that is a compile error. An interface will, with a caveat we return to in the edge cases.

And the nil map: its zero value is not an empty map but "there is no map".

var m map[string]int   // nil
fmt.Println(len(m))    // 0
fmt.Println(m["a"])    // 0
delete(m, "a")         // does nothing
for range m { }        // zero iterations
m["a"] = 1             // panic: assignment to entry in nil map

There is exactly one asymmetry here: only a write panics. So a forgotten make survives until the first insert — and fails somewhere other than where the mistake is.

A zero instead of an error: why the two-result form exists

Reading a missing key neither panics nor returns an error — it gives the zero value of the element type: 0 for an int, an empty string for a string, nil for a pointer.

Hence the question that is the whole point of this section:

How do you tell an existing key whose value is 0 from a missing key?

With the single-result form, you cannot: it returns zero in both cases. Only the two-result form tells them apart.

The rule is simple: v := m[k] when zero and absence mean the same thing (counters, sums, accumulators). v, ok := m[k] when they do not (caches, configuration, "does this user have a setting").

We will measure the price of that form later, in part three: it turns out to be practically nil — but first it must be clear why the form exists at all.

Why changes survive a function call

This is the most common practical difference between a map and a slice, and it is observable from the program:

func add(m map[string]int) { m["x"] = 1 }
 
func main() {
    m := make(map[string]int)
    add(m)
    fmt.Println(m["x"])   // 1
}

An append inside a function, meanwhile, is not visible outside:

func grow(s []int) { s = append(s, 42) }   // NOT visible outside

This is better phrased through observable behaviour than through internals: passing a map to a function copies the map value, but that value keeps referring to the same data structure, so changes to elements are visible to the caller. A slice copies a header carrying the length, and the new length stays in the copy.

Three practical consequences follow, all of them from the contract rather than the implementation: a map need not be returned from a function for changes to arrive; a map cannot be "copied" by assignment — an explicit walk is needed; and a nil map passed into a function stays nil for the caller even if make is assigned to it inside.

How a map value is represented in the runtime is an implementation detail. It can be confirmed, but it should not carry an argument:

unsafe.Sizeof(map[int]int{})   // 8 — one word
unsafe.Sizeof([]int{})         // 24 — three
unsafe.Sizeof("")              // 16 — two

What the language promises and what the implementation does

Control bytes, groups and measurements are coming, and they are easy to mistake for guarantees. The dividing line runs here, and it is worth holding to the end:

The language contract — always true, safe to build code on:

• the key must be comparable;
• a missing key gives the zero value, and the ok form reports presence;
• the iteration order is unspecified;
• a nil map reads but does not write;
• concurrent access with a write requires synchronisation.

The runtime implementation — true for one version; it explains behaviour but does not guarantee it:

• Swiss Table, groups of eight, H1 and H2, the control word;
• probing, tombstones, the 7/8 load factor;
• a directory of tables and a 1024-slot limit per table.

Measured observations — true for one machine, one version and one shape of data:

• 28.62 ns against 17.83 on a miss and a hit;
• nine iteration orders for a nine-entry map;
• 36.0 MB not released after clear.

From here on, every number says which of the three levels it belongs to.

Maps and goroutines

This topic sits here rather than at the end because it is needed before anything else: getting it wrong costs more than not knowing a thing about Swiss Tables.

A map may be read from any number of goroutines at once. As soon as even one writer joins them, the program itself must synchronise the access.

The first thing worth knowing about that rule: it is not in the language specification. The section on maps defines the key type, the behaviour of a nil map and growth — about goroutines it says nothing. The rule lives in the memory model:

A runtime crash is not a synchronisation mechanism

It is customary to say "you will get a fatal error", and from that people conclude that at least the bug is visible. That is wrong, and the difference is shown by a run of bench/gomap/concurrent.go in two modes.

Two goroutines writing — the runtime notices and kills the process:

fatal error: concurrent map writes

goroutine 8 [running]:
internal/runtime/maps.fatal(...)
	/usr/local/go1.24.7/src/runtime/panic.go:1058

The runtime checks a "write in progress" flag on entry to every operation, so there are three messages and they say what collided:

A goroutine reading while another writes — the same run, without the race detector:

the program printed only its own "finished" line and exited with code 0. No warning, no fatal error, nothing in the log. The very same code under the race detector:

==================
WARNING: DATA RACE
Write at 0x00c00009a0f0 by goroutine 7:
  runtime.mapassign_fast64()
Previous read at 0x00c00009a0f0 by goroutine 8:
  runtime.mapaccess1_fast64()

The point this measurement was made for: the runtime detecting concurrent access is not a contract but a check on luck. It fires when two goroutines happened to be inside the map at the same moment, and stays silent when they did not. Correctness is built on the memory model and on synchronisation, not on the hope of crashing.

And one more thing: recover does not help here. The run above has a defer with a recover in it — it printed nothing, because this is not a panic:

The difference is not cosmetic: panic unwinds the stack, runs deferred calls and can be recovered; fatal does none of that — beside it in the same file stands fatalthrow, "an unrecoverable runtime throw".

Why the severity. A map is a multiword structure, and a race on it corrupts not a value but consistency:

Stopping immediately is not strictness for its own sake but trading memory corruption for a crash visible in the log. As the run above showed, though, it does not always happen — and it cannot be relied on.

Three working models

First — a map under a mutex. The most common and almost always right. sync.RWMutex when readers clearly outnumber writers; a plain sync.Mutex otherwise. The same run under the race detector, with a mutex, finds nothing at all: all 160,000 writes land, there is no fatal error and the detector reports no findings.

Second — ownership by one goroutine. The map lives inside one goroutine and the others talk to it by messages over a channel. The synchronisation comes from the shape of the program rather than from locks, and there are no races by construction.

Third — sync.Map, and only for its own cases. Its own documentation talks you out of it:

Two cases are named: a cache that only grows, and disjoint sets of keys across goroutines. Everything else is a plain map with a mutex.

This has to be checked with the race detector

Neither the compiler nor a review will find a race on a map. -race will:

go test -race ./...
go run -race ./cmd/service

The detector slows the program several times over and raises its memory use, so it goes into tests and staging rather than production. More importantly, it finds a race only if one happened in that run. The memory model calls it exactly that — a reaction to something detected:

A green run under -race means "no race showed up on these inputs", not "there is no race". So tests with concurrent access are worth writing so that the accesses actually overlap, rather than so that the code merely runs.

Part II. How lookup is built

From here to the end of part two is the Go 1.24 implementation. Everything here explains behaviour and guarantees nothing: in another runtime version the design may differ, while the contract from part one will not.

Why a map needs a hash: a fingerprint and a full comparison

The general idea is the same in every hash table, and it is not about Go.

The key goes through a hash function and produces a number. Part of that number says where to look — which region of the table to inspect. The trouble is that different keys land in the same region, so finding the place is not enough: you must also work out whether the right key is there.

The naive answer is to compare keys in full. It is correct and expensive: comparing a string or a struct costs noticeably more than comparing two numbers.

Hence the trick a Swiss Table rests on: a second, short part of the hash is kept beside the slot as a fingerprint. A fingerprint does not answer "this key" — it is short, and collisions across different keys are inevitable. But a non-match rules the slot out for certain, and the full comparison falls to a handful of candidates:

Everything that follows is Go's concrete answer to four questions: how to get a region out of the hash, how many slots to check at once, how many bits to give the fingerprint, and when to stop looking.

The table is an array of groups: where the index comes from

Before taking a group apart, we have to say what a table is — otherwise the word "group" stays an abstraction and "the hash picks a group" stays an incantation.

A group is eight slots and a control word alongside them. A table is an array of such groups, laid out end to end and numbered from zero. There is nothing else in it:

group 0   [control word: 8 bytes][slot 0][slot 1] … [slot 7]
group 1   [control word: 8 bytes][slot 0][slot 1] … [slot 7]
…
group 7   [control word: 8 bytes][slot 0][slot 1] … [slot 7]

That answers what "H1 named the group" means. It did not find the key, did not choose a slot and has not looked anywhere yet: it produced an index into that array — a number from 0 to N−1. The search starts afterwards, inside the named group, over its control word.

How H1 becomes an index

The number of groups in a table is always a power of two, and that decision pays for itself right here:

h1    = h >> 7            drop the 7 fingerprint bits
index = h1 & (N − 1)      take the low bits of what is left

The second line is the remainder of a division by the number of groups, written as a single AND. That works precisely because N is a power of two: for any other number & (N − 1) stops being a remainder.

It is best seen in bits. Here are the low 16 bits of the hash of four keys with eight groups, cut twice — the fingerprint on the right, the index next to it:

The middle three bits are the index: it is not computed, it is taken. The seven on the right are the fingerprint, bound for the control byte of whichever slot the key lands in. The six on the left are the rest of H1: they take no part in the index, but they do take part in the probe path if the named group turns out to be full.

Why the index comes from H1 and not from the whole hash

So that the index bits and the fingerprint bits do not overlap. The cost of overlapping can be counted. Take the index from the low bits — the very ones the fingerprint already occupies — and see how many distinct fingerprints can then occur inside a single group. Measured over 400,000 keys with eight groups:

• index from H1, as in Go — all 128 fingerprint values occur in a group;
• index from the low bits — 16.

The fingerprint loses three bits, false positives during lookup become roughly eight times more frequent, and each one is paid for with a full key comparison. Splitting the hash into non-overlapping parts is not tidiness; it is the condition under which the fingerprint filters anything at all.

A key has no group "of its own"

Without this, everything above misleads. The index is a function of the hash and of the table's current size. A key's hash never changes; the mask changes at every growth:

Doubling adds one bit to the mask, and that bit either leaves the key where it was or moves it forward by exactly the previous number of groups: k1 goes 1 → 9, k7 goes 0 → 16. Across 100,000 keys about half change index: 50.07% going from 4 groups to 8, and 49.97% from 32 to 64. Consequence three from part three follows from this: growth rebuilds the whole table, and so you cannot take the address of a map element.

Below, the whole path is played out step by step — from the 64-bit hash to a highlighted cell of the array — and the second tab shows the same unchanged hash landing on different indexes as the table grows:

Anatomy of a group: eight slots, eight bytes and three states

A hash table always has the same job: given a key, find its place fast. The hash gives a number, the number gives a position — but sooner or later two different keys give the same position, and something has to happen next.

The old Go map answered with chains: a position led to a "bucket" of eight pairs, and if that overflowed, to the next bucket by a link. A Swiss Table answers differently, and its whole design serves one goal: make eight candidates testable with one comparison rather than a loop of eight.

For that, a short summary of the eight slots lies next to them. The key's hash splits into two unequal parts:

• the upper 57 bits (H1) choose which group the search starts at;
• the lower 7 bits (H2) are written into a separate byte — the slot's tag.

What H1 does is unpacked in the section above: its low bits are the index of the group the search starts at. What matters here is the other half: that is where its work ends. H1 is not stored, is not written into any byte and is compared against nothing — what goes into the control byte is H2. The moment at which H1 drops out shows up not in the anatomy of a group but across a whole operation, and is unpacked below, on an insert.

The terms come from the runtime itself:

Here is how that lies in memory. A control byte and a slot are one position, not two separate places: eight bytes run in a row, and behind them eight key–value pairs. Click the slots — below the diagram it says what each state means and what a lookup does on reaching it:

Now the part that usually gets skipped — and without which the mechanism does not come together. A byte has eight bits, a tag has seven. Where did the eighth bit go?

It is spent on letting one byte distinguish three states of a slot. The patterns are written out in the source verbatim:

  empty    1 0 0 0 0 0 0 0
  deleted  1 1 1 1 1 1 1 0
  full     0 h h h h h h h     ← the seven tag bits

The top bit is the occupancy flag, and an inverted one at that: for a full slot it is clear. That single convention yields three separate tests, each of them one operation on the same bit:

• the slot is full — the top bit is clear;
• the slot is empty or deleted — the top bit is set;
• the slot is empty — the top bit is set and the second-from-bottom is not (a deleted slot has it set, an empty one does not).

So the tag is seven bits not because "seven is enough" but because the eighth is given to the state. That price is what makes everything else possible.

How eight comparisons become one

The eight control bytes lie next to each other in memory and make up a single 64-bit number — the control word. Usually the explanation stops at "compares eight slots in one operation", and that sentence cannot be understood until you see what happens to the bytes. Here is what happens.

Step one — replicate the tag. The seven wanted bits are copied into all eight bytes, by multiplying by 0x0101010101010101. Now the comparison is not against a slot but against the whole word at once.

Step two — XOR. A byte becomes zero exactly where the two bytes matched. "Find the matching slots" has become "find the zero bytes", and that one is already solvable with arithmetic.

Step three — catch a zero byte with a borrow. One is subtracted from every byte: v - 0x0101010101010101. A zero byte has nothing to subtract from — it borrows and becomes 0xFF, so its top bit lights up. A non-zero byte does not light up this way; and if its top bit was set before the subtraction, the &^ v part clears it.

Step four — keep one bit per slot: & 0x8080808080808080. That is the finished answer: eight bits, one per slot.

In one line, this is the body of the runtime's function:

v := uint64(g) ^ (bitsetLSB * uint64(h))
return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)

Below, the same four steps run on real bytes — switch steps and tags. Every row of bits is printed by bench/gomap/controlword.go, which runs these formulas and cross-checks them against a plain eight-byte loop:

Three arithmetic operations on one number instead of a loop of eight comparisons. On amd64 one SIMD instruction does the same three steps, and the formula above is the portable variant for machines that have no such instruction.

Now for what a tag is not. Seven bits are 128 values, so two different keys sharing a tag is an everyday event. A tag answers not "this key" but "maybe this one": after a match the key is compared in full. A non-match, though, rules the slot out for certain, and that is where the saving is — the full comparison falls to one or two slots out of eight rather than all eight.

How much that imprecision costs is estimated in the runtime itself:

There is a second, rarer imprecision — in the formula itself. The borrow travels from a lower byte into a higher one, so once in a while an extra bit lights up. The comment in group.go names a concrete case: for the word 0x0302, searching for the tag 0x02, the formula reports slots 0 and 1 while an honest loop reports only slot 0. This costs no correctness precisely because a tag is not an answer anyway: an extra candidate costs one key comparison. The run of bench/gomap/controlword.go over two hundred thousand random groups confirms it: real matches missed — zero, extra ones reported — 0.03%.

The stopping rule: a free slot against a deleted one

The group is not always the one the hash chose: if there is no room in it, the search moves to the next one along the path. That path is neither random nor "just the next one" — the offset grows triangularly, p(i) = (i² + i)/2 + H1, and when the group count is a power of two such a sequence visits every group exactly once.

So a sign is needed for ending the search and saying "the key is not here". There is exactly one:

The logic is simple: had the key existed, an insert would have put it no further than the first free spot. Reach a free slot and there is no point looking further.

The subtlety is in the word free. A deleted slot does not count as free, and the source explains why:

This is what the byte's third state is for. A deleted slot is free for an insert but occupied for a lookup: an insert asks "empty or deleted", a lookup asks "empty". One bit tells the first apart, two bits tell the second, and both tests stay one operation on the word.

And the last piece of the picture: free slots must exist. Fill the table to the brim and a lookup has nowhere to stop, so a miss would have to search the whole table. That is why the map grows without waiting to be full: the threshold is 7/8. An eighth of the slots is kept empty on purpose, and it is not a safety margin but the price paid for the stopping rule.

An insert end to end: what H1 does, and what H2 does

Where the group index comes from is unpacked above; so is how many bits the fingerprint has and why the eighth is spent on state. One thing is left that neither section shows on its own: why there are two halves at all, and what the division of labour buys. The difference between H1 and H2 is not in what they look like — both are just pieces of one number — but in when they act: the first works once, before the table is looked at at all; the second works at every step and then stays in memory. That is visible only across a whole operation. Take an insert.

The claim everything else follows from:

An insert is a lookup that failed. Not "found a free spot and put it there". The map is obliged to establish that the key is absent first, and only then take a slot. Otherwise the same line m["a"] = 1 run twice would produce two entries.

Here is the whole path, step by step.

Step 0. The hash is cut at the seventh bit. h1 = h >> 7, h2 = h & 0x7f. No bit plays both roles: a tag match says nothing about the group, and a group number says nothing about the tag.

Step 1. H1 is applied — exactly once. h1 & (number of groups − 1) gives the starting group, and it also seeds the triangular probe sequence. That is all; H1 takes part in no comparison after that. It is not stored, not checked, and past this step it is not needed.

Step 2. H2 enters — and acts at every step. In each group along the path, the group's control word is compared against the tag in a single operation. It is also the only part that stays in memory: when the key lands in a slot, the control byte gets H2.

Step 3. Inside a group, the search is for the KEY, not for a spot. A tag match produces candidates, and every candidate is checked by a full key comparison. If one matches, the value is overwritten in place: no new slot appears, the control byte does not change, len stays as it was. Insert and update are the same operation, parting ways on the last comparison.

Step 4. The key is not in this group — is this the end of the path? The question from the previous section. The group is completely full — step to the next one. There is a free slot — the path is over, the key is definitely not in the table. But if the first non-occupied slot is a deleted one, the spot is remembered and the path continues.

Step 5. The write. If a deleted slot was remembered along the way, the key goes into it rather than where the path stopped — and it costs nothing from the growth budget, having already been accounted for. If there is no growth budget left, the table is rebuilt first.

Step five is the least obvious and the most useful. The price follows from it:

Inserting a new key costs a full miss lookup. Not "found a hole and filled it" — until a free slot turns up, there is no telling whether the key is further along the path, so the first available spot cannot simply be taken.

Below, those same five scenarios are played out step by step. Two things are worth watching: the moment H1 stops taking part, and which slot the write actually goes to in the last scenario:

One detail remains, and it is the one that makes these two halves easiest to confuse. In group.go the pattern for an occupied slot is annotated like this:

full: 0 h h h h h h h  // h represents the H1 hash bits

The comment says H1 — while the code beside it writes H2 into the control byte. Both lines come from the same package:

seq := makeProbeSeq(h1(hash), t.groups.lengthMask) // H1 sets the path
g.ctrls().set(i, ctrl(h2(hash)))                   // H2 goes into the byte

And above the h2 function itself, map.go says it outright:

So the control byte holds H2; the comment in group.go has drifted from the code. Checked on go1.24.7 — and it is worth keeping in mind while reading the sources: the names H1 and H2 come from Abseil, and so does the confusion in that comment.

The design is now described whole: table → groups of eight → H1 picks the starting group → the H2 tag in the control word → one operation instead of eight comparisons → stopping at a free slot → a 7/8 load factor. Four consequences follow, each checked by measurement.

Part III. Consequences of the design

Everything from here on follows from part two, and each item is backed by a measurement. The numbers here belong to the third level of the split above: one machine, one version, one shape of map. What is stable in them is not the value but the direction.

Consequence one (lookup): a miss costs more than a hit

A hit stops on the key it found — on average in the very first group. A miss has to walk to a group with a free slot, and by construction those are scarce: the load factor is 7/8.

Measured on a map of a hundred thousand entries:

That is the exact opposite of the expectation — "a miss found nothing, so it must be faster". The mechanism says otherwise, and the practical consequence is direct: if _, ok := m[k]; !ok costs more than reading an existing key, and in a hot loop where misses are frequent that shows.

The same cause is visible against the previous implementation

Go 1.24 makes an honest comparison possible — the old implementation is still there behind a build flag:

A rare opportunity: one compiler, one machine, one benchmark, exactly one build flag different. The runs were interleaved — on a virtual machine the clock drifts, and two consecutive runs would show a difference that is not there.

The ranges across four rounds do not overlap on any row — this is not noise.

The miss row is explained by the same stopping rule, seen from the other side. In the old map a miss looked at one bucket — eight tophash bytes — and ended there if no overflow chain existed. In a Swiss Table a miss must walk the probe sequence to a free slot. What makes a hit fast makes a miss long.

The Go team's blog does make the caveat about regressions, without naming a case:

Here is one such case, and it does not look like an edge: checking whether a key exists is an ordinary operation. A caveat is owed to the measurement too: this is one shape of map (map[int64]int, a hundred thousand entries, consecutive keys), and the cost of a miss depends on the load factor and on how the keys are laid out.

Consequence two (iteration): the only rule is not to depend on the order

From this whole section, one sentence goes into your work, and here it is:

Code must not depend on a map's iteration order. A map promises no order, and the observed order is not a contract.

Everything below is a study of the implementation. It explains why buggy code can go unbroken for a long time, and that is its whole value: the bug does not become less of a bug for it.

That iteration order is unspecified is common knowledge. The runtime goes further than not guaranteeing it — it randomizes deliberately:

Implementation detail: why buggy code can go unbroken for a long time

What goes unsaid is how it is randomized. And here the table comes in again: iteration walks it in order, and only the starting point is random.

One and the same nine-entry map, iterated two thousand times, produces exactly nine distinct orders. Not 362,880. And all nine are rotations of one sequence. The reason is a single line in the iterator:

entryIdx := (it.entryIdx + it.entryOffset) & entryMask

entryOffset is taken once, when the iterator is created. After that the slots are walked in order. So the sequence is one and only its shift is random. The sequence itself differs per program run — the map seeds its hash at startup; what is constant is that within one run the orders differ only by a shift.

Why that is more dangerous than real randomness. Code that accidentally depends on key A coming before key B would, under real shuffling, fail in roughly half the runs and be caught on day one. Under rotation it fails only on the shifts that cut the tape between those two keys — and the closer the keys lie, the fewer those are. So it passes the tests, passes review, and breaks in production when the map changes slightly.

The rule's boundary is computed from constants — the same table again

Everything above holds while the map fits in one table. The table's limit is maxTableCapacity = 1024, and it fills to 7/8, that is to 896 entries. Beyond that the map splits into several tables, the iterator gains a second independent offset — over the table directory (it.dirOffset) — there is more than one tape, and they are shuffled among themselves.

Measured exactly where the constants predict: at 896 entries there are 896 distinct orders, at 897 already 1174.

That is a good check that the mechanism was understood correctly: the boundary was not found experimentally, it was computed from two runtime constants and then confirmed by running it.

The practical conclusion is the old one: if you need an order, collect the keys and sort them. slices.Sorted(maps.Keys(m)) does it in one line.

Consequence three (growth): the entries move

When the load factor reaches 7/8 the table is not "extended" — it is rebuilt at twice the size and every entry is laid out afresh. Two practical consequences follow, usually learned separately.

An element's address cannot be taken.

p := &m["a"]        // cannot take the address of m["a"]
m["a"].field = 2    // cannot assign to struct field

This is not a compiler whim: a pointer taken before a growth would lead into somebody else's memory. The ban is at compile time rather than left to "be careful". The way around it is map[K]*V: then the pointer moves and the object stays put.

And a caveat back to the iteration section. A map larger than maxTableCapacity = 1024 is stored not as one table but as several — and then it grows one table at a time: only the entries of the table that overflowed are moved. The table remains the unit of growth here too; what changes is that there is now more than one of them. That is exactly why the boundary of the iteration-order rule falls at 896 entries.

A size hint removes not bytes in the map but the intermediate tables. Here the expectation is disappointed in the other direction. A million entries:

The finished map is the same — that is the last column. What is saved is not bytes inside it but the tables thrown away along the way: without a hint the map grows by doubling, and the sum of all intermediate tables is roughly the size of the final one. Hence exactly twice.

So a hint helps the garbage collector's workload, not memory consumption. If you were told otherwise, now there is something to check it with.

Consequence four (memory): the table does not shrink

Growth goes by tables — and so does release. A million map[int]int entries, live heap:

a million entries:                36.0 MB,  len = 1,000,000
after deleting every key:         36.0 MB,  len = 0
after clear(m):                   36.0 MB,  len = 0
after m = make(map[int]int):       0.1 MB

Neither delete nor clear gives memory back: the table stays the same size, just empty. Only replacing the map itself frees it.

This is not an optimization but the difference between a working service and a leak. A cache that lives long and is cleaned on a schedule will hold memory at its historical maximum — forever.

There is exactly one cure: m = make(map[K]V) instead of clear(m) when cleaning means "start from nothing".

That is the end of the four consequences of the design. What follows are two topics that do not derive from it and live by their own rules.

What this means when choosing

The design is covered; what remains are practical prices that do not follow from it directly but are needed when choosing between options.

The comma-ok form costs nothing. v, ok := m[k] — 18.43 ns against 17.83 for v := m[k]; on a miss 28.44 against 28.62, that is, in the other direction. The difference is inside the run-to-run spread, and both numbers of each pair come from one block of measurements — otherwise comparing them would not be allowed. The compiler emits the same runtime call and simply takes the second return value in the second case.

A string key costs half again as much as an integer one — 28.19 against 18.06. That is not the map's doing: a string's hash is computed over its contents, while an int64's is computed over eight bytes. A composite [2]int64 key of the same width costs 24.95: the runtime has separate fast paths for integers and strings (map_fast64_swiss.go, map_faststr_swiss.go), while everything else goes through the general code.

If the keys are a dense range of integers, a map is not needed. One read by a key already at hand: 15.55 ns from a map against 1.12 from a slice. Those two numbers compare with each other but not with the 18.06 above: there the key was still being fetched from a slice of keys. Iterating a hundred thousand entries: 855,702 ns against 37,434. Fourteen times and twenty-three times.

Edge cases worth knowing

Everything below is rare, but every item of it has cost somebody a working day at least once. It adds nothing to the basic model of a map, and it is worth reading last.

The key contract: comparable does not mean reflexive

The specification states the requirement on the key type through operators:

The requirement looks exhaustive, but between "the operators are defined" and "the map behaves as expected" there is a gap, and three cases fall into it.

NaN: an entry that can be neither found nor deleted

float64 satisfies the requirement: the operators are defined for it. But definedness is not reflexivity, and a map looks a key up by == precisely:

What comes of that is visible by running it (bench/gomap/nankey.go):

after m[nan] = 1 → len(m) = 1
after m[nan] = 2 → len(m) = 2
after m[nan] = 3 → len(m) = 3
after m[nan] = 4 → len(m) = 4
after m[nan] = 5 → len(m) = 5

m[nan]        → value 0, found false
len before delete: 5
len after two deletes: 5

Five assignments with the same variable as the key produced five entries. An ordinary key would have produced one: an assignment overwrites the key it found, and NaN cannot be found. The lookup does not find it; delete does not find it and stays silent, because there is nothing for it to remove. The entries are there all along: iteration sees them, they hold their values, they occupy memory. They are unreachable only by key.

This is not a side effect but known behaviour, written down in the runtime:

The runtime softens the consequence — handing NaN values a random hash so they do not gather into one chain — but does not remove it. And the map implementation states what can be done with such an entry at all:

Verified: clear(m) removes them all and returns len to zero. There is no other supported way.

The practical conclusion. NaN cannot be written as a literal — the compiler rejects the constant 0.0/0.0 with invalid operation: division by zero. NaN arrives from data: dividing zero variables (var z float64; z/z), math.Sqrt(-1), parsing the string "NaN". A map whose keys are numbers from an external source grows on such values without limit, and not one of those entries is ever reused. They must be filtered at the entrance with math.IsNaN: afterwards they can only be removed along with the whole map.

And a control, so as not to over-generalize: on other numbers the map shows no strangeness. +0.0 and -0.0 are equal under IEEE 754, and the map honestly treats them as one key — the second insert overwrote the first, len stayed

1. What breaks is exactly the place where == stops being reflexive, and that is only NaN.

An interface key defers the check to run time

map[any]T is the one place where a non-comparable key is not caught by the compiler:

m := map[any]int{}
m[[]int{1}] = 1   // panic: runtime error: hash of unhashable type []int

And in the same place: int(1) and int64(1) are different keys, because the type takes part in the comparison.

A nil map: where exactly this fires

The rule itself is covered in part one: everything reads, only a write panics. What matters here is where it shows up in practice — and it always shows up late.

A struct field. A struct with an undeclared map inside is created without error, reads fine and fails on the first write — sometimes much later than it was created, and in another package. The cure is a constructor that makes every map in the struct.

A function's return. func load() map[string]int may well return nil on the error branch, and a caller that only reads will notice nothing. The trap springs on the next caller, who decides to add an entry.

An assignment inside a function. A func fill(m map[string]int) that does m = make(...) changes nothing for the caller: the map value is copied, and the new map stays in the copy. A map that must be created is returned.

A key larger than 128 bytes moves out of the slot

internal/abi sets SwissMapMaxKeyBytes = 128. Measured on ten thousand entries:

Two things happen past the threshold, and they point in opposite directions: there is now one allocation per every key, while the bytes go down. The second is not a typo: all eight slots in a group are reserved whether occupied or not, while a key moved out is allocated at exactly its size.

How to reproduce the numbers

The measurements are bench/gomap/layout.go (layout) and bench/gomap/cost_test.go (cost). bench/gomap/nankey.go measures no time at all: it prints len, lookup results and delete for a NaN key. Table growths are caught by bench/gomap/growth.go. The bit arithmetic of the control word is run step by step and cross-checked against a plain loop by bench/gomap/controlword.go — it measures no time either, it prints the bits themselves. The whole insert path is played out by bench/gomap/insert.go, and the split of a hash into a group index and a fingerprint by bench/gomap/groupindex.go; both port the runtime's rules line by line and check themselves rather than asking to be taken on trust. This is a separate Go module, so they run from inside it:

go run bench/gomap/layout.go          # works from the repo root too
go run bench/gomap/growth.go
go run bench/gomap/controlword.go
go run bench/gomap/insert.go
go run bench/gomap/groupindex.go
cd bench/gomap
go test -run '^$' -bench . -benchmem .
./ab.sh                               # the old implementation against the new

layout.go prints observations without a single time measurement. ab.sh alternates builds with and without GOEXPERIMENT=noswissmap and prints a cpu: line for each run: if it differs between rounds, the round should be discarded rather than counted.

Published run: go1.24.7 linux/amd64, Intel Xeon 2.10 GHz, August 2026. Times depend on the machine; the B/op and allocs/op columns do not.