0% completed
How Maps Work Inside
On This Page
Groups, Slots, and Control Bytes
Tables and Growth
The Seed and Iteration Order
Map Elements and Addresses
Sizing with make
Memory After delete and clear
Comparable Key Types
Using This in an Interview
Key Takeaways
A map must find the value for a key without looking at every entry. It must also accept new keys at any time, and it must keep working when two different keys produce the same position. It must do all of this while the number of entries grows from a few to many millions.
Go meets these requirements with a hash table. A hash table is an array of storage locations, where a function of the key (the hash) chooses the location to check first. Since Go 1.24, the table follows a design called Swiss Tables, implemented in the package internal/runtime/maps. This description is true of Go 1.27, and the details can change between releases, because the language promises only how a map behaves.
Knowing the structure answers several practical questions: why the iteration order changes, why &m[k] does not compile, why a struct in a map cannot be changed in place, and what delete and clear do to memory.
Groups, Slots, and Control Bytes
A map value is a single pointer to a runtime struct, so it is 8 bytes on amd64. The entries are stored in groups. A group has 8 slots, each holding one key and one value. It also has a control word of 8 bytes, with one control byte per slot. A key or value larger than 128 bytes is stored elsewhere, and its slot holds a pointer to it (internal/abi/map.go).
The hash of a key is split into two parts. The lower 7 bits are called H2, and the remaining upper bits are called H1. Each control byte records whether its slot is empty, deleted, or in use, and a slot in use also stores the H2 of its key.
A lookup then works in four steps:
- Compute the hash of the key, using the seed of this map (a random number that is mixed into every hash).
- Use H1 to choose a group.
- Compare H2 with all 8 control bytes in one operation, which gives a short list of candidate slots.
- Compare the full key only for those candidates. If there is no match and the group has an empty slot, the key is not in the map. Otherwise, move to the next group in the probe sequence (the fixed order in which groups are tried).
The control bytes make this fast, because H2 excludes most slots without reading a single key. The source estimates a 1 in 128 chance of a false match per slot, and a false match costs only one extra key comparison.
Tables and Growth
A map that has never held more than 8 entries, and was not created with a larger hint, is a single group with no table around it. A larger map uses one or more tables, where each table is a complete hash table with its own groups. A table allows an average of 7 used slots per group (maxAvgGroupLoad in group.go), because a probe sequence ends only at a group with an empty slot.
When a table reaches that limit, the runtime grows it. Up to a capacity of 1,024 slots (maxTableCapacity in table.go), it replaces the table with one that has double the capacity, and it moves every entry at once. Beyond that size, it splits the table into two. The upper bits of the hash then select the table, through an array of table pointers called the directory, before the lookup steps above begin.
Splitting limits the cost of one insert. No single growth step copies more than one table. A map with millions of entries therefore never stops to move all of them at the same time.
The Seed and Iteration Order
Each map receives a random seed when it is created. Both clear and a delete that empties the map replace it. The seed goes into every hash, so two maps place the same keys differently. An attacker who sends chosen keys therefore cannot predict collisions. An iterator also picks a random starting offset (Iter.Init in table.go). That offset is why the order can change even between two loops over one unchanged map.
One possible output:
different orders seen in 200 loops: 5
Do not depend on the iteration order. For stable output, copy the keys and sort them, for example with slices.Sorted(maps.Keys(stock)).
Map Elements and Addresses
When a table grows, its entries move to new groups, so the address of an entry is not stable. If Go allowed a pointer to a map entry, that pointer could refer to an old location after the next insert. The Go specification therefore leaves map elements out of its list of addressable operands, and the compiler rejects the expression.
The same rule explains a second error. Changing a field of a struct in a map would need the address of the entry, so the compiler rejects that assignment too.
orders := map[int64]Order{1001: {ID: 1001}} p := &orders[1001] orders[1001].Paid = true _ = p
./main.go:10:8: invalid operation: cannot take address of orders[1001] (map index expression of struct type Order) ./main.go:11:2: cannot assign to struct field orders[1001].Paid in map
There are two repairs. Either copy the value out, change the copy, and store it back, or store pointers so that the map entry never needs to change.
Output:
true true
The second repair works because the assignment goes through a pointer read out of the map. The Order it points to does not move. This repair costs one allocation per order, which the first repair does not need.
Sizing with make
The second argument of make(map[K]V, n) is a hint, which the runtime uses to create enough groups for n entries at the start. A map with a hint skips the repeated growth steps, and each of those steps allocates new groups and moves entries.
One possible output:
no hint: 81 with hint: 34
The hinted map still allocates more than once, because this hint produces 16 tables. Each table needs a table struct and a group array, which makes 32 allocations, and the map and the directory add 2 more. Unlike a slice capacity, the hint is not a limit, because the map can grow past it.
Memory After delete and clear
Both delete and clear remove entries, and neither one returns the memory of the groups. The program below fills a map with 200,000 orders, removes them, and reads the heap size after a garbage collection.
One possible output:
full: 12 MB, len 200000 after delete: 12 MB, len 0 after clear: 12 MB, len 0 after nil: 0 MB
| Operation | Entries | Groups in memory | Other effects |
|---|---|---|---|
delete(m, k) | One removed | Kept | May leave a marker called a tombstone in a full group |
clear(m) | All removed | Kept | Zeroes the groups and picks a new seed |
m = nil or a new map | Old map no longer referenced | Freed by the garbage collector | Requires that nothing else refers to the old map |
A tombstone marks a slot as deleted so that a probe sequence continues past it. A later insert can reuse it, and the runtime removes the rest when the table runs out of room, either in place or by rebuilding the table. Both operations also zero the removed keys and values, so the garbage collector can free whatever those entries pointed to. Keeping the groups is useful when a map fills again, because the next round of inserts reuses them and allocates little or nothing. For a map that was once huge and will stay small, make a new map and copy the remaining entries into it.
Comparable Key Types
A key type must be comparable, meaning that == is defined for it, because the lookup ends by comparing keys. Slices, maps, and functions are not comparable, so the course's full Order type cannot be a key, because its Items field is a slice. The compiler rejects map[Order]bool with invalid map key type Order.
With an interface key, this check happens at run time. The type map[any]int compiles, but a key whose actual type at run time is not comparable causes a panic when it is hashed. The program below fails on its slice key.
panic: runtime error: hash of unhashable type []string
Using This in an Interview
Say that a Go map is a hash table split into tables and groups of 8 slots, where control bytes filter candidates before any key is compared. A random seed and a random iterator offset make the order unreliable by design. A likely follow-up asks why you cannot take the address of a map value. Entries move when a table grows, so such a pointer could become invalid.
Key Takeaways
- Since Go 1.24, a map uses Swiss Tables: groups of 8 slots with one control byte per slot.
- Part of the hash chooses the group, and the 7-bit H2 filters the slots before any key is compared.
- Tables double up to 1,024 slots and then split, so an insert into a large map moves at most one table.
- A random seed and a random iterator offset mean that iteration order must never be relied on.
- Entries move, so map elements are not addressable: copy, change, and store back, or store pointers.
deleteandclearremove entries but keep the groups; that memory is freed only when nothing refers to the map.
A Go map does not keep an entry at a stable location, and that choice allows fast lookups and growth in small steps. Nearly every rule that surprises engineers follows from that design, including the changing order, the missing &m[k], and the memory that stays after a clear. When those rules cause a problem, the repair is usually to store pointers, copy values out, or build a new map.
Reading Progress
0%
On This Page
Groups, Slots, and Control Bytes
Tables and Growth
The Seed and Iteration Order
Map Elements and Addresses
Sizing with make
Memory After delete and clear
Comparable Key Types
Using This in an Interview
Key Takeaways