Maps in Go: a group of eight, the 7/8 threshold, and a miss that costs more than a hit

What is actually being asked

The ladder is almost always the same, and the first two rungs decide more than they look like they do:

1. "What does m[k] return if the key is not there?" — the warm-up, which filters out everyone who expects an error.
2. "And how do you tell an absent key from a zero value?" — this is where the content starts.
3. "What happens if two goroutines write to it?" — checking whether you know this is not a panic.
4. "How does the lookup work?" — whether you name the hash and the group of slots or stop at the words "hash table".
5. "What happens when the map grows?" — whether you know the threshold and can name it as a number.
6. "What is the complexity?" — whether you separate the average from the worst case.
7. "Why is the iteration order random?" — a trick question: it is not random.

The lesson walks that ladder, and it walks it in one direction: first what a map promises, then how the implementation keeps that promise. The numbers come last — as a check on a prediction, not as a pile of surprising facts.

Base: what a map does

A map solves one problem: hold key-value pairs so that a key gets you its value directly instead of scanning everything. Hence the ordinary work with it: you store under a key, and you read back by the same key.

You may ask a map about any key — including one it does not hold. That is not an error: instead you get back the zero value of whatever type the map stores — zero for numbers, the empty string for strings. Nothing breaks, and that is the main subtlety at the entrance: did the zero come back because the key is absent, or because the value stored under it really is zero? By the value alone the two cases are indistinguishable. So reading has a second form — the one that returns not only the value but also the answer to "was the key there at all". Everything the lesson later calls comma-ok is that form.

Not everything can be a key. A map finds a key by comparison, so the key type has to support comparison for equality: numbers, strings and structs built of such fields qualify; a slice or another map does not.

You may range over a map, but no iteration order is promised: the language calls a map an unordered group of elements, and two ranges over the same map are free to hand back the entries differently.

And the last thing to know before any implementation detail: a map is not protected by anything. While one goroutine works with it all is well; the moment there are two and at least one of them writes, the synchronisation is yours to provide.

That is already enough to answer the basic interview question. What follows is why each of those rules is checkable and what exactly happens when one is broken — and, at the end, how the implementation manages to find a value in constant time and what it pays for that.

Mechanism 1: what a map promises

Now the same thing, but checked by a run and stated in the words of the specification. Start with what will not change with the Go version or the machine — the contract. Everything else in the lesson explains how the implementation keeps it, but the contract itself does not depend on the implementation.

An absent key is not an error, it is the zero value. A run of bench/gomap/contract.go:

scores["alice"]              10
scores["carol"]              0
scores["dave"]               0

Three lines, two different cases — and by value they are indistinguishable. carol has a key and her score really is zero; dave has no key at all. This is the first trap of the topic: if m[k] == 0 does not answer the question "is the key there".

What tells them apart is a second variable, the form known as comma-ok:

v, ok := scores["carol"]     0 true
v, ok := scores["dave"]      0 false

The rule is worth saying verbatim: ok answers the question of presence, the value answers the question of content, and the second must not stand in for the first. A bug from this neither crashes nor logs — it quietly treats an absent user as a user with zero.

A nil map can be read, ranged over and even deleted from — but not written to. The same run:

nilMap == nil                true
len(nilMap)                  0
nilMap["anything"]           0
_, ok := nilMap["anything"]  false
for range nilMap             0
delete(nilMap, ...)          ok
nilMap["anything"] = 1       panic: assignment to entry in nil map

Six operations work, the seventh crashes. The specification puts it in one sentence: A nil map is equivalent to an empty map except that no elements may be added.

The treachery is precisely in those first six lines. A nil map inside a struct somebody forgot to initialise behaves perfectly normally — until the first write, which may happen a week later and in different code.

Keys must be comparable, and the compiler checks it. bench/gomap/contract.sh tries to build a map with a slice key:

badkey.go:4:17: invalid map key type []int
--- go build exit code: 1

Structs and arrays are comparable element-wise and make fine keys; slices, maps and functions do not. What matters here is when this comes out: at build time, not in production. "A map with a slice key" is not a rare bug — it is a program that does not exist.

There is one exception, and it is the dangerous one: in map[any]T the key type is formally comparable, so the check moves to run time. Put a slice in and you get a panic on the line that put it there.

Iteration order is not guaranteed. That too is part of the contract rather than a property of the implementation: you must not rely on the order, full stop. How that lack of guarantee is implemented is a detail that makes such bugs harder to catch with tests than you would think — the lesson returns to it under "Deeper".

Mechanism 2: maps and goroutines

This question comes second rather than last because it is about the safety of the contract, not about a subtlety: a map in Go is protected by nothing, and the cost of getting this wrong is higher than anything else in the lesson.

"What happens if two goroutines write to one map" tests one thing: whether you know this is not a panic.

fatal error: concurrent map writes

There are three messages, and they say what collided: concurrent map writes, concurrent map read and map write, concurrent map iteration and map write.

And recover will not help. The difference is not cosmetic: panic unwinds the stack, runs deferred calls and can be caught; fatal does none of that — the process stops where it is. The comment on fatal itself names racing map writes as the model case: fatal is equivalent to throw, but is used when user code is expected to be at fault for the failure, such as racing map writes.

Why stopping was chosen rather than "whatever happens". The Go memory model explains it outright: races on multiword data structures can lead to inconsistent values not corresponding to a single write — and goes on to arbitrary memory corruption. Failing loudly beats silently corrupting somebody else's data.

A separate note on the race detector. The check inside the map is not it: it runs always, in an ordinary build, without -race. But it is not a guarantee: two goroutines can miss each other, and then the program simply corrupts the table. go test -race finds such races more reliably, because it watches accesses rather than a flag.

The cure: an ordinary mutex beside the map. sync.Map looks like the ready-made answer, but it is tuned for a different profile — many reads and few writes — and loses to a mutex-guarded map on an even mix.

Mechanism 3: why changes are visible after passing to a function

Here the lesson moves from what a map promises to how the variable is built — and the first observation is usually noticed before its explanation.

A map passed into a function changes for the caller:

func fill(m map[string]int) { m["a"] = 1 }   // visible outside

The explanation is simple: map[K]V is a pointer to a runtime structure, not the structure itself. The pointer is copied; the table behind it is shared.

This differs from a slice in a more interesting way than it looks. With a slice a function can change the elements but cannot lengthen it — because the length lives in the copied header. With a map "lengthening" works too, because the size lives behind the pointer rather than beside it.

Note the direction of the reasoning. "A map is a pointer" explains nothing on its own and is easy to memorise wrong; it is useful precisely because two observable facts follow from it — the shared table after passing, and the ban on taking the address of an element.

A nil map can be read but not written. The specification puts it in one sentence: A nil map is equivalent to an empty map except that no elements may be added.

var m map[string]int
fmt.Println(m["missing"], len(m))   // 0 0 — works
m["present"] = 1                    // panic: assignment to entry in nil map

The trap here is that reading works: a nil map inside a struct somebody forgot to initialize behaves perfectly normally right up to the first write.

You cannot take the address of an element. &m[k] does not compile, and the reason is spelled out under "Deeper": on growth the entries physically move, and the address would stop being valid. With a slice you can take an address, because there the move is visible from outside through append; in a map it happens silently.

Mechanism 4: edge cases that cost a crash

The key must be comparable. The specification: The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice. For map[any]T this is checked at run time: put a slice in and you get a panic where you put it.

And the subtlest case: NaN. float64 is a comparable type, yet NaN != NaN. A map finds a key by comparison, so a write under NaN lands in the map but can never be found:

nan := math.NaN()
m := map[float64]int{}
m[nan] = 1
m[nan] = 2
// len(m) == 2 — TWO entries under one "key"
// m[nan] == 0 — neither can be found
// delete(m, nan) — deletes nothing

Entries that can be neither read nor deleted. The only way to be rid of them is to throw the map away. In an interview this is an excellent answer to "can a key be present and still unreachable".

Deeper: how a map is built inside

Everything above is the contract: it does not depend on the Go version and will not change. What follows is a different kind of claim — the layout of today's implementation. It explains numbers that would otherwise look arbitrary, but it is not a rule of the language: before Go 1.24 a map was built differently, and it will be built differently again.

What a map needs a hash for

Now the implementation begins, and it is worth taking in two passes. First the ordinary hash table as any textbook describes it: without it, groups of eight and control bytes have to be memorised rather than understood.

A map has one job: find a value by its key in constant time. Scanning is out — that is linear. So the position of the value has to be computed rather than searched for.

Three consequences follow immediately, and they explain everything after:

• The hash must be fast, or the saving on the lookup is eaten by computing it. Which is why a key has to be comparable and hashable — a type whose hash cannot be computed does not belong in a map.
• Different keys can produce the same index. That is a collision, and it is not rare but normal: there are always fewer buckets than possible keys. So the bucket must also hold the key itself, and compare it.
• A full table works badly. The fewer free slots, the longer the probe chains, so the table has to grow ahead of time.

That is the classical model. Now the specifics: Go 1.24 implements it as a Swiss Table, and three decisions of that design — groups, the control byte and the stopping rule — explain the measurements that would otherwise look arbitrary.

A group of eight and the stopping rule

The key's hash splits in two: the high bits pick a group, the low seven go into a control byte — a short tag for the slot.

A group is eight slots and eight control bytes laid out next to each other. A lookup compares the wanted tag against all eight at once — one instruction, not a loop. A matching tag does not yet mean a matching key (seven bits are few), but a non-match rules the key out for certain, so the full key comparison happens only for tags that matched.

The important part is the stopping rule, and it is what produces the unexpected consequence. The lookup walks groups until it finds the key or meets a group with a free slot. A free slot means "there would have been nowhere further to put this key, so it is not here".

Hence a prediction worth making before looking at any numbers: a miss should cost more than a hit. A hit stops on the key it found. A miss must walk to a free slot — and free slots are scarce, because the map runs at a load factor of 7/8.

Nearly everyone expects the opposite: "a miss found nothing, so it must be faster". The mechanism says otherwise, and a measurement below checks it.

How a map grows

"When does a map grow" almost always gets "when it fills up". That is wrong, and the number is known: at a load factor of 7/8.

The growths can be caught — by jumps in the allocation count. Here are the sizes at which they happened:

9  15  29  57  113  225  449

Check it yourself: 7/8 of 16 is 14, and the growth happened on the fifteenth entry. 7/8 of 32 is 28, growth on the twenty-ninth. And so on. The rule: growth at "seven eighths of capacity plus one", with the table doubling.

Why 7/8 rather than completely full. This is not a safety margin or a tuned constant — it is the direct price of the stopping rule from the previous part. Fill the table completely and no free slots remain, so a miss would have to be searched across the whole table. An eighth of empty slots is what buys the lookup somewhere to stop.

Here is the chain worth saying out loud in an interview: groups of eight give a fast tag comparison; stopping on a free slot makes a miss cost more than a hit; and for the sake of that stop the map holds a load factor of 7/8, that is, deliberately spends an eighth of its memory. Three facts, and they are not independent.

What it costs

Now that the mechanism has been laid out, the numbers stop being truisms and become a check on a prediction.

The prediction from the stopping rule holds. Measured on a map of a hundred thousand entries:

A miss costs half again as much as a hit — precisely because it has to reach a free slot. This is the case where the mechanism lets you predict the result before it is shown; if it still looks surprising, go back to the stopping rule.

Complexity, and what hides behind the average

The right answer is O(1) on average. But, as with slices, two different claims stand behind it, and the second usually gets lost.

The average O(1) rests on the hash spreading keys across groups evenly, so the lookup path length does not depend on the map size. It is the evenness, not "hash table magic": with a poor hash the whole thing degrades.

The worst case of a single operation is O(n). An insert that lands on a growth rebuilds the entire table: the new table is twice the size and every entry is rehashed. On a latency chart that is an outlier, and the bigger the map the bigger it is. For a service with a p99 budget, a map that grows under load is a known source of tails.

And the worst case of a lookup is O(n) too — if all keys land in one group. Go does not let that happen from outside: the map's hash is seeded with a random number at process start, so keys that all collide cannot be chosen in advance. This is protection against an algorithmic denial-of-service attack: back when there was no seeding, "send a hundred thousand keys with the same hash" took down web servers in other languages.

Hence a practical conclusion worth naming: if the final size is known, say it in make. Not for lookup speed — that will not change — but so that there are no growths at all. What exactly that saves is below.

delete, clear and the size hint

Three neighbouring questions, and intuition gets all three wrong.

delete does not return memory. Measured on a map of two hundred thousand entries:

A map in Go does not shrink. The table stays the size it grew to; delete only marks the slot and clear zeroes the entries without touching the size. The only way to give memory back is to build a new map and drop the old one.

The practical consequence shows up in design questions: a cache in a map that once grew to peak load stays that size forever. The cure is not delete but rebuilding the map on a schedule.

A size hint shrinks not the map but the garbage. The same measurement, two maps of two hundred thousand entries:

The finished map is the same. What differs by a factor of two is the work along the way: without the hint the runtime allocates and discards every intermediate table, which is exactly a doubling of allocated bytes. What is saved is the collector's work, not the map's memory.

Iteration order: the contract and the observation

Mechanism 1 said the iteration order is not guaranteed — that is the contract. This is about how the lack of guarantee is implemented, and the difference between those two statements costs bugs in production.

"Map iteration order is random" is common knowledge. The claim is incomplete, and incomplete in the dangerous direction.

Iteration starts at a random point and from there walks the table in order. So there are as many distinct orders as there are entries — these are rotations of one sequence, not permutations of it. For a nine-entry map there are nine orders, not 362,880.

Why that is more dangerous than real randomness. Code that accidentally depends on key A coming before B would, under real shuffling, fail in roughly half of runs — and be caught on day one. Under rotation it fails only on the rotations that cut the tape between those two keys. That does not survive tests — it passes them, and breaks in production.

The right interview answer: "order is not guaranteed and must not be relied on; that non-guarantee is implemented with a random starting point rather than shuffling — which is why a dependency on order is caught by tests far less often than you would think".

How to answer in an interview

Short answer: a map holds key-value pairs addressed by key, and an absent key gives you not an error but the zero value; the v, ok := m[k] form is what tells it apart from a genuine zero. Add as a second sentence what gets asked straight after: the variable holds a pointer to a runtime structure, which is why a map passed into a function changes for the caller, and why a nil map can be read but not written.

That is enough for a correct answer. What follows is what you add when the interviewer digs.

If the interviewer digs deeper

Describe the structure as a chain, not a list — and say out loud that this is how the current implementation is built, not a rule of the language. Groups of eight → tag compared against all eight at once → stop on a free slot → hence a miss costs more than a hit → and for that stop the load factor is held at 7/8. A chain shows understanding; a list of facts shows memorization.

Name the number. "On go1.24 it grows at 7/8 and the table doubles" weighs more than "when it fills up". If you remember, add that growths happen at 9, 15, 29, 57 entries: that is visible in a measurement and sounds like "I checked this".

Split the complexity. "O(1) on average; an insert that lands on a growth is O(n) because the whole table is rebuilt; the worst case of a lookup is O(n) too, but random hash seeding protects against chosen keys."

Do not call the iteration order random. Say "not guaranteed", and add that it is implemented with a random starting point, which is why a dependency on order passes tests. That is the answer people remember.

On concurrent access, say "not a panic". fatal error, recover does not help, cured with a mutex. Half of candidates answer "it will panic" — and that is exactly the difference the question is testing.

Next they ask

Common misconceptions

Practice

Two tasks. Answer first, then check against the real output: in both, the correct answer is taken from a script run rather than assigned.

nan := math.NaN()
m := map[float64]int{}
m[nan] = 1
m[nan] = 2
fmt.Println(len(m))
fmt.Println(m[nan])
delete(m, nan)
fmt.Println(len(m))

2
0
2

1
2
0

2
2
1

1
0
1

Knowledge check