Dig101 — map internals (hmap, buckets, growth, iteration)

Contents

  1. 1. 0x01 Internal structures
  2. 2. 0x02 Hashing
  3. 3. 0x03 Growth
  4. 4. 0x04 Initialization
  5. 5. 0x05 Lookup
  6. 6. 0x06 Assign
  7. 7. 0x07 Delete
  8. 8. 0x08 Iteration

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

Go map hmap and bucket layout

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// runtime/map.go — map header
type hmap struct {
count int // len(map)
flags uint8
// iterator=1 — may iterate buckets
// oldIterator=2 — may iterate oldbuckets during grow
// hashWriting=4 — concurrent write detection
// sameSizeGrow=8 — same-size bucket compaction
B uint8 // log2 of bucket count; capacity ~ loadFactor * 2^B
noverflow uint16 // overflow count (~approx above 2^15-1)
hash0 uint32 // per-map hash seed

buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr

extra *mapextra
}

type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}

const (
BUCKETSIZE = 8
MAXKEYSIZE = 128
MAXELEMSIZE = 128
)

type bmap struct {
tophash [bucketCnt]uint8
}

Compiler-generated bucket layout (reflect.go):

1
2
3
4
5
6
type bmap struct{
topbits [8]uint8
keys [8]keytype
elems [8]elemtype
overflow otyp // *bmap or uintptr if map has no pointers
}

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
2
3
var m = map[interface{}]int{}
var i interface{} = []int{}
println(m[i]) // panic: hash of unhashable type []int

Call chain:

1
2
3
4
5
6
7
8
hash := t.hasher(key, uintptr(h.hash0))
// reflect.go builds hasher per key type; slices use interhash
func interhash(...) {
t := (*iface)(p).tab._type
if t.equal == nil {
panic("hash of unhashable type " + ...)
}
}

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
2
3
4
5
6
m0 := map[int]int{}
_ = &m0[0] // error

m := make(map[int][2]int)
m[0] = [2]int{1, 0}
m[0][0] = 1 // error — assign whole value only

Two growth modes:

  • sameSizeGrow — too many overflow buckets; rebuild at same B, drop excess overflows (noverflow vs 1<<B, cap logic at B>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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// mapassign — decide whether to grow when inserting
if !h.growing() &&
(overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
}

bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}

// growWork — at most two buckets per call
func growWork(t *maptype, h *hmap, bucket uintptr) {
evacuate(t, h, bucket&h.oldbucketmask())
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}

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
2
3
4
n1, n2 := math.NaN(), math.NaN()
m := map[float64]int{}
m[n1], m[n2] = 1, 2
println(n1 == n2, m[n1], m[n2]) // false 0 0

0x04 Initialization

Nil map is unusable. make builds the hmap.

  • small (makemap_small) — no hint or hint ≤8: allocate hmap + hash0 on heap.

  • large (makemap) — pick B so hint/2^B ≈ 6.5, preallocate bucket array; if B>4, reserve extra overflow buckets and wire nextOverflow.

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

  • B as log2 bucket count — fast mask, easy double.
  • Per-map hash0 — spread collisions.
  • Type-specific hashers.
  • Split key/elem arrays; big KV as pointers.
  • tophash byte filter + overflow lists.
  • mapextra + uintptr overflow when bucket must be pointer-free.
  • Incremental evacuation on writes/deletes.
  • Load factor 6.5 vs same-size overflow compaction.
  • makemap hints vs makemap_small.
  • Random walk start — unordered iteration.
  • flags detects 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