Map Internals: hmap, bmap Buckets, Hash High-Bits, Evacuation
- Last updated
- Prerequisites:
- Go map syntax and usage
- Understanding of hash tables and hashing
- go
- maps
- hmap
- bmap
- hash
- buckets
- grow
Read at your depth
The practical view
Go maps are hash tables: m := make(map[string]int); m["key"] = 1. Lookup, insert, and delete are amortized O(1). Maps grow automatically when they exceed a load factor: the runtime rehashes and doubles the bucket count. Important behaviors: map iteration order is RANDOM (not insertion order) — never rely on order; maps are reference types (passing a map shares it); reading a missing key returns the zero value (use v, ok := m[k] to distinguish); maps are not safe for concurrent use (use sync.RWMutex or sync.Map); you cannot take the address of a map element (m[k] is not addressable).
The same idea in other frameworks
N/A — Go runtime concern.N/A — Go runtime concern.N/A — Go runtime concern.N/A — Go runtime concern.Legacy vs modern
Slice lookup vs map lookup
A slice index is O(1) direct addressing; a map lookup is a hash + bucket scan with a per-map seed and possible growth.
m := make(map[int]string) // ❌ OLD: map where a slice would dos := make([]string, 1000) // ✅ NEW: direct addressingInterview gotchas
Context
This tests the map iteration semantics — interviewers want the hash-seed randomization and the runtime's intentional order scrambling that prevents programs from depending on order.
The mechanical answer
Go deliberately makes map iteration order random to prevent programs from depending on a specific order (which would break across versions and hide bugs). The mechanism: each map has a per-map random seed (hash0) chosen at creation, which affects the hash of every key and thus the bucket assignment — so the same keys map to different buckets across maps, making iteration order differ. Additionally, the runtime's mapiterinit picks a random starting bucket and offset within the iteration, so even iterating the SAME map twice can yield different orders. This is a correctness-by-design choice: the language spec explicitly says iteration order is not specified. If you need order, sort the keys yourself.
Trap
The naive answer is 'iteration order is undefined but usually insertion order'. It is deliberately randomized, not just unspecified. Another trap: assuming adding/removing keys doesn't change order — it can, because growth (evacuation) moves keys to different buckets. Candidates who mention the hash seed and random start position show real understanding.
Context
This probes the growth/evacuation mechanics — interviewers want the doubling + incremental evacuation design that keeps map growth latency bounded.
The mechanical answer
A map grows when the load factor exceeds ~6.5 elements per bucket, or when there are too many overflow buckets relative to the bucket count (for delete-heavy maps). Growth allocates a new bucket array (2x size) and sets oldbuckets to the previous array. Rather than moving everything at once (which would pause the program), Go evacuates INCREMENTALLY: on every subsequent insert/lookup/delete, a few buckets are moved from oldbuckets to the new array, tracked by the nevacuate counter. The 'growing' flag routes operations to check both arrays until complete. This bounds the latency of any single operation during growth. The trade-off is that lookup during growth may check two buckets (old and new), and the old array is retained until fully evacuated.
Trap
The naive answer is 'map growth is a stop-the-world rehash'. Go's is incremental. Another trap: assuming deleting keys shrinks the map — deletion marks slots but never shrinks the bucket array; memory is retained, and a delete-heavy workload triggers a growth to a larger array with many empty buckets unless you recreate the map. Candidates who describe incremental evacuation and the non-shrinking behavior show real depth.