Deep Dive into Go's Map Implementation: Hash Tables, Hash Functions, and Runtime Mechanics

Go's map (dictionary) is a specialized hash‑table implementation that enables fast lookup, insertion, modification, and deletion by mapping keys to values; the key type must support equality (operators == and != ), excluding function, map, and slice types.

A hash table stores records in an array indexed by a hash of the key; the hash function compresses arbitrary data into a fixed‑size fingerprint, and the array of buckets is called the hash table.

Hash functions should be deterministic, balanced, efficient, exhibit the avalanche effect, and be one‑way; they are used in many scenarios such as security, data validation, load balancing, distributed caching, and sharding.

Hash collisions occur when different keys produce the same hash value; common resolution methods are open addressing (linear probing, quadratic probing, double hashing) and chaining (linked lists). The article illustrates linear probing with example keys {89,18,49,58,69} and shows the probing sequence using images.

The core runtime structure of a Go map is hmap , which consists of fields like count , flags , B , noverflow , hash0 , buckets , oldbuckets , nevacuate , and an optional extra pointer. These fields track the number of live cells, bucket count (as a power of two), overflow buckets, hash seed, and pointers to the bucket arrays.

Additional structures include mapextra , which holds slices of overflow bucket pointers ( overflow and oldoverflow ) and a pointer to a free overflow bucket ( nextOverflow ), and bmap , which stores up to eight key/value pairs per bucket, a tophash array for quick hash‑byte comparison, and an overflow pointer.

During program start‑up, the runtime initializes the hash algorithm in alginit (called from schedinit ) which may select an AES‑based hash if the CPU supports the required instructions; otherwise it falls back to a software implementation. The relevant code is:

func alginit() {
    if (GOARCH == "386" || GOARCH == "amd64") && cpu.X86.HasAES && cpu.X86.HasSSSE3 && cpu.X86.HasSSE41 {
        initAlgAES()
        return
    }
    if GOARCH == "arm64" && cpu.ARM64.HasAES {
        initAlgAES()
        return
    }
    getRandomData((*[len(hashkey)*sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
    hashkey[0] |= 1
    hashkey[1] |= 1
    hashkey[2] |= 1
    hashkey[3] |= 1
}

Map creation is performed by two functions: makemap_small for small hints (≤ bucket count) and makemap for larger capacities. makemap_small simply allocates an hmap and sets a random hash seed:

func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

makemap performs more extensive work: it checks for memory overflow, computes the appropriate bucket exponent B based on the hint, allocates the bucket array, possibly creates overflow buckets, and returns the initialized hmap :

func makemap(t *maptype, hint int, h *hmap) *hmap {
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    return h
}

Go provides three common map initialization patterns: a literal, a declared variable followed by make , and direct make with optional capacity hint. Example literals:

m := map[string]string{"name": "张三丰", "grade": "一年级"}

Variable then make :

var m5 map[string]string
m5 = make(map[string]string)

Direct make with capacity:

m2 := make(map[string]string)
m3 := make(map[string]string, 1)
m4 := make(map[string]string, 8)

Key access differs between simple retrieval ( mapaccess1_faststr ) and the comma‑ok form ( mapaccess2_faststr ), which the compiler distinguishes during type checking and AST transformation.

Write and update operations are handled by runtime/mapassign , which checks for nil maps and inserts or updates the key/value pair; deletion uses runtime/mapdelete , which marks entries as empty without immediately freeing memory, relying on tophash states to manage space.

When the load factor exceeds 6.5 or overflow buckets exceed 2^15, the map triggers a resize. The runtime supports gradual, equal‑size, and incremental resizing strategies to maintain performance.

The article concludes that understanding Go's map internals involves grasping hash‑table theory, runtime initialization, and the interplay of various source files ( runtime/map.go , runtime/proc.go , runtime/alg.go ), and encourages further exploration of these mechanisms.