Contents
Dig101: dig more, simplify more, know more
Maps are everywhere in Go. They hide hashing, collision chains, growth, and compaction. Below is the runtime layout (Go 1.14beta1 on macOS) without a line-by-line source dump.
Quick picture of the hash table layout before the details.
0x01 Internal structures

A map is an hmap pointing at buckets. Each bucket (bmap) holds up to 8 key/value slots.
Lookups hash the key, pick a bucket, and compare via tophash (top 8 bits of the hash).
Collisions after 8 slots chain through overflow buckets.
noverflow, oldbuckets, nevacuate, oldoverflow participate in growth (later).
1 | // runtime/map.go — map header |
Compiler-generated bucket layout (reflect.go):
1 | type bmap struct{ |
hmap.B — bucket count is 2^B so hash % n becomes hash & (2^B-1) (BucketMask) and doubling is B++.
Keys/elems layout — keys in one array, values in another (better alignment, e.g. map[int64]int8).
Types larger than 128 bytes use indirect storage (indirectkey, indirectelem).
hmap.extra — when overflow must be uintptr so the bucket has no pointers (GC noscan), mapextra keeps overflow buckets reachable.
See Type-unsafe pointers for why bare uintptr is risky.
0x02 Hashing
1 | var m = map[interface{}]int{} |
Call chain:
1 | hash := t.hasher(key, uintptr(h.hash0)) |
Each key type gets its own hasher. Slices are not comparable → not hashable.
Non-comparable kinds (ANOEQ in alg.go): func, map, slice; arrays/structs containing them.
0x03 Growth
You cannot take the address of a map element; you cannot mutate inner fields of struct/slice values in place — only replace the whole value. Incremental growth moves entries.
1 | m0 := map[int]int{} |
Two growth modes:
sameSizeGrow — too many overflow buckets; rebuild at same
B, drop excess overflows (noverflowvs1<<B, cap logic atB>15).biggerSizeGrow — load factor
count/2^B > 6.5(overLoadFactor); double buckets; incremental migrate on assign/delete (hashGrow,growWork,evacuate).
Growth hooks (comments from runtime):
1 | // mapassign — decide whether to grow when inserting |
evacuate picks old bucket half x vs new half y using hash & newbit. NaN keys (key != key) get special handling — NaN keys are useless anyway:
1 | n1, n2 := math.NaN(), math.NaN() |
0x04 Initialization
Nil map is unusable. make builds the hmap.
small (
makemap_small) — no hint or hint ≤8: allocatehmap+hash0on heap.large (
makemap) — pickBsohint/2^B ≈ 6.5, preallocate bucket array; ifB>4, reserve extra overflow buckets and wirenextOverflow.
0x05 Lookup
mapaccess1 / mapaccess2 / mapaccessk (iterator after grow). Hash, bucket index, maybe old bucket during evacuation, walk bucket + overflow chain, match tophash and key equality; indirect keys/elems dereferenced; missing key → zero value.
0x06 Assign
mapassign: hash, growWork if growing, scan chain — empty slot, update equal key, or new overflow bucket; set tophash, bump count, maybe trigger hashGrow.
0x07 Delete
Same search as assign; clear slot. Coalesce emptyOne → emptyRest backward so iterators skip trailing empty runs (bucketloop breaks on emptyRest).
0x08 Iteration
mapiterinit picks random startBucket (fastrand) → random iteration order.
mapiternext follows buckets; during grow, migrated buckets use new storage.
Design highlights
Bas log2 bucket count — fast mask, easy double.- Per-map
hash0— spread collisions. - Type-specific hashers.
- Split key/elem arrays; big KV as pointers.
tophashbyte filter + overflow lists.mapextra+uintptroverflow when bucket must be pointer-free.- Incremental evacuation on writes/deletes.
- Load factor 6.5 vs same-size overflow compaction.
makemaphints vsmakemap_small.- Random walk start — unordered iteration.
flagsdetects concurrent map read/write.
Worth another pass through runtime/map.go while this is fresh.
Further reading (other Go versions; same ideas):
Code: NewbMiao/Dig101-Go
Questions? Leave a comment below or email: newbvirgil@gmail.com![]()
