Deep Dive into Go's map Implementation: Structure, Operations, and Performance

Go's map is a key/value collection implemented as a hash table where each bucket ( bmap ) holds up to eight entries. The top-level header ( hmap ) contains metadata such as element count, flags, bucket count exponent B , hash seed, and pointers to the bucket array and overflow structures.

The runtime chooses a hash function at program start: if the CPU supports AES, an AES‑based hash is used; otherwise the generic memhash is applied. The low B bits of the hash select the bucket, while the high 8 bits (the topHash ) identify the slot within the bucket.

Map initialization can be performed via a nil declaration, make with an optional capacity hint, or a literal. During creation the makemap function validates the key type, computes an appropriate B based on the load‑factor threshold (6.5), allocates the bucket array, and seeds the hash.

Lookup uses two runtime functions, mapaccess1 (no existence flag) and mapaccess2 (returns a bool). Both compute the hash, locate the bucket, compare the stored topHash , and then compare the actual keys. If the map is growing, the old bucket is consulted before migration completes.

Insertion is handled by mapassign. After checking for concurrent writes, it computes the hash, finds a free slot (or updates an existing key), and may trigger growth if the load factor exceeds the threshold or overflow buckets become excessive. The growth process allocates a new bucket array, links the old one via oldbuckets , and migrates entries incrementally using growWork and evacuate , moving at most two buckets per write.

Deletion is performed by mapdelete . It validates concurrency, locates the key, clears the key/value memory (taking pointer presence into account), marks the slot as empty, and decrements the element count.

Iteration is deliberately nondeterministic: a random start bucket and offset are chosen via fastrand , ensuring that each for range map yields a different order. This prevents developers from relying on any implicit ordering.

Because maps are not thread‑safe, concurrent reads and writes must be protected. The article shows two solutions: a sync.RWMutex guarding a regular map, and the built‑in sync.Map which provides its own concurrency safety.

All code excerpts from the original source are preserved below, each line wrapped in ... tags to retain exact syntax.

// A header for a Go map.
type hmap struct {
count     int                  // 元素个数
flags     uint8
B         uint8                // 2^B 为 bucket 数量
noverflow uint16               // 溢出的 bucket 个数
hash0     uint32               // hash seed
buckets    unsafe.Pointer      // buckets 数组指针
oldbuckets unsafe.Pointer      // 旧 buckets（扩容时）
nevacuate  uintptr             // 搬迁进度
extra *mapextra                // 扩容辅助结构
}
type mapextra struct {
overflow    *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}
type bmap struct {
tophash [bucketCnt]uint8        // 每个 bucket 最多 8 个槽
}
const (
bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits
)

func makemap(t *maptype, hint int, h *hmap) *hmap {
// ... boundary checks, hash seed generation, B calculation ...
// allocate bucket array and overflow structures
return h
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ... hash calculation, bucket lookup, top‑hash compare ...
return unsafe.Pointer(&zeroVal[0])
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ... concurrency checks, bucket selection, possible growth ...
// find insertion slot or update existing entry
// write key/value, increment count
return val
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
// ... locate key, clear memory, mark slot empty, decrement count ...
}

func hashGrow(t *maptype, h *hmap) {
// allocate new bucket array, link oldbuckets, reset flags
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
// incremental migration of old buckets to new ones
}

type TestMap struct {
M    map[int]string
Lock sync.RWMutex
}
func main() {
// concurrent read/write example using RWMutex
}

m := sync.Map{}
m.Store(1, 1)
m.Load(1)