漫行记Wandering
Journal 10,582 字 36 分钟 Golang

Golang Map: A Deep Dive

Hash Table Architecture

Go maps are implemented as hash tables with separate chaining using arrays rather than traditional linked lists. This design choice provides significant performance benefits through better cache locality and memory access patterns.

The core structure is the hmap (hash map) in the Go runtime:

type hmap struct {
    count     int    // number of live cells (len())
    flags     uint8  // iterator flags, growing flag, etc.
    B         uint8  // log_2 of # of buckets (can hold up to 6.5 * 2^B items)
    noverflow uint16 // approximate number of overflow buckets
    hash0     uint32 // hash seed
    buckets   unsafe.Pointer // array of 2^B buckets
    oldbuckets unsafe.Pointer // previous bucket array during growth
    nevacuate  uintptr // progress counter for evacuation
    extra     *mapextra // overflow buckets and old overflow buckets
}

Why this structure? Each field serves a critical purpose:

  • count: Enables O(1) len() operations
  • B: Determines bucket array size as power of 2 for fast bit masking
  • hash0: Security feature preventing hash DoS attacks
  • buckets/oldbuckets: Dual arrays enable incremental growth without blocking

Bucket Structure

Each bucket can hold exactly 8 key-value pairs, and this isn’t arbitrary - it’s optimized for cache line efficiency:

type bmap struct {
    tophash [8]uint8    // high 8 bits of hash for each key
    // followed by 8 keys
    // followed by 8 values
    // followed by overflow pointer
}

The memory layout innovation: Keys and values are stored separately!

Traditional layout: [key1][val1][key2][val2][key3][val3]...
Go's layout:        [key1][key2][key3]...[val1][val2][val3]...

Why separate storage?

  1. Cache locality: When scanning for keys, we don’t load unnecessary values
  2. Alignment optimization: Values can be properly aligned regardless of key size
  3. SIMD potential: Multiple tophash values can be compared simultaneously

Hash Function Deep Dive

Hash Calculation Process

  1. Hash the key → get 64-bit hash value using type-specific hash function
  2. Split the hash strategically:
    • Lower B bits determine bucket index: bucket = hash & (1<<B - 1)
    • Top 8 bits become tophash: tophash = uint8(hash >> 56)
    • Middle bits used during growth for redistribution

Type-Specific Hash Functions

Go uses different hash functions based on key type for optimal performance

String Hashing (with AES optimization):

func stringHash(s string, seed uintptr) uintptr {
    if len(s) == 0 {
        return seed
    }

    // Use AES-based hash if CPU supports it (modern CPUs)
    if useAeshash {
        return aeshashstr(noescape(unsafe.Pointer(&s)), seed)
    }

    // Fallback to memhash for older CPUs
    return memhashString(s, seed)
}

Integer Hashing (multiplication-based with seed mixing):

func int64Hash(i uint64, seed uintptr) uintptr {
    // Mix the seed with the value
    i ^= uint64(seed)
    i ^= i >> 33
    i *= 0xff51afd7ed558ccd  // Large prime multiplier
    i ^= i >> 33
    i *= 0xc4ceb9fe1a85ec53  // Another large prime
    i ^= i >> 33
    return uintptr(i)
}

Others …

The Lookup Process

Here’s the actual lookup algorithm (simplified from Go runtime):

func mapaccess(h *hmap, key unsafe.Pointer) unsafe.Pointer {
    hash := h.hash(key)
    bucket := hash & (1<<h.B - 1)  // Extract lower B bits
    tophash := uint8(hash >> 56)   // Extract top 8 bits

    // Find the bucket in memory using pointer arithmetic
    b := (*bmap)(add(h.buckets, bucket*uintptr(h.bucketsize)))

    // Search bucket chain (main bucket + overflow buckets)
    for ; b != nil; b = b.overflow {
        for i := 0; i < 8; i++ {
            // Fast tophash comparison first!
            if b.tophash[i] == tophash && h.key_equal(key, b.key(i)) {
                return b.value(i)
            }
        }
    }
    return nil // Return zero value if not found
}

Performance optimizations in this code:

  1. Bit masking instead of modulo: hash & (1<<h.B - 1) is much faster than hash % bucket_count
  2. Tophash pre-filtering: 8-bit comparison before expensive key comparison
  3. Pointer arithmetic: Direct memory access without array bounds checking
  4. Cache-friendly traversal: Linear scan through bucket slots

Growth and the Evacuation Algorithm

This is where Go maps get truly sophisticated. The challenge: How do you resize a hash table without blocking all operations?

Growth Triggering Conditions

Load Factor Calculation:

func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    // where bucketCnt = 8, loadFactorNum = 13, loadFactorDen = 2
    // So threshold = 6.5 * 2^B
}

Why 6.5? This comes from extensive hash table research:

  • Below 6.5: Wastes memory with mostly empty buckets
  • Above 6.5: Too many collisions, performance degrades exponentially
  • 6.5: Sweet spot balancing memory usage and lookup performance

Growth is triggered when EITHER condition is met:

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(h)  // Trigger growth: B = B + 1
}

Too Many Overflow Buckets:

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    // If B >= 15: threshold = 2^15 overflow buckets
    // If B < 15: threshold = 2^B overflow buckets
    if B > 15 {
        return noverflow >= uint16(1)<<15
    }
    return noverflow >= uint16(1)<<B
}

The B Value Determination Algorithm

func makemap(t *maptype, h *hmap, hint int) *hmap {
    // Calculate optimal B based on expected size
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++  // Keep increasing until load factor ≤ 6.5
    }

    // B now represents log₂(optimal_bucket_count)
    h.B = B
    h.buckets = newarray(t.bucket, int(bucketShift(B)))
}

The Incremental Evacuation Algorithm

The Problem: Naive approach would rehash everything at once:

// BAD: Would cause massive pause
func naiveGrow(h *hmap) {
    newBuckets := allocate_new_buckets(2 * current_size)
    for each key-value in old buckets {
        newBucket := hash(key) & new_mask
        insert into newBuckets[newBucket]
    }
    // PAUSE: Could take milliseconds for large maps!
}

Go’s Solution: Incremental evacuation during normal operations:

func evacuate(h *hmap, oldbucket uintptr) {
    // Get the old bucket to evacuate
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(h.bucketsize)))
    newbit := h.noldbuckets() // This is 2^B - the new bit that determines split

    // Two destination buckets for the split
    var x, y evacDst  // x = lower half, y = upper half
    x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(h.bucketsize)))
    y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(h.bucketsize)))

    // Process all key-value pairs in the old bucket chain
    for ; b != nil; b = b.overflow(t) {
        k := add(unsafe.Pointer(b), dataOffset)      // Pointer to first key
        v := add(k, h.bucketsize-h.valuesize*8)     // Pointer to first value

        for i := 0; i < bucketCnt; i++ {
            if b.tophash[i] == emptyOne || b.tophash[i] == emptyRest {
                continue  // Skip empty slots
            }

            // THE MAGIC: Recalculate hash to determine new bucket
            hash := h.hash(k)

            // Use the new bit (bit B) to decide destination
            var dst *evacDst
            if hash&newbit == 0 {
                dst = &x  // Stays in lower half (same index)
            } else {
                dst = &y  // Moves to upper half (index + 2^B)
            }

            // Move key-value to destination
            dst.b.tophash[dst.i] = b.tophash[i]
            typedmemmove(h.keytype, dst.k, k)
            typedmemmove(h.valuetype, dst.v, v)

            // Advance destination pointers
            dst.i++
            dst.k = add(dst.k, h.keysize)
            dst.v = add(dst.v, h.valuesize)

            // If destination bucket full, allocate overflow bucket
            if dst.i == bucketCnt {
                dst.b = h.newoverflow(dst.b)
                dst.i = 0
                dst.k, dst.v = dst.b.keys(), dst.b.values()
            }
        }

        // Move to next key-value pair in current bucket
        k = add(k, h.keysize)
        v = add(v, h.valuesize)
    }

    // Mark old bucket as evacuated
    b.tophash[0] = evacuatedX // or evacuatedY depending on bucket type
}

The Binary Split Mathematics

The brilliant insight: When growing from 2^B to 2^(B+1) buckets:

Old hash: [remaining bits][B bits for bucket]
New hash: [remaining bits][new bit][B bits for bucket]

The new bit determines redistribution:

  • New bit = 0: Key stays at same bucket index
  • New bit = 1: Key moves to bucket index + 2^B

Concrete Example (B=2 growing to B=3):

Old: 4 buckets (indices 0,1,2,3)
New: 8 buckets (indices 0,1,2,3,4,5,6,7)

Old bucket 0 → New bucket 0 (new bit=0) or 4 (new bit=1)
Old bucket 1 → New bucket 1 (new bit=0) or 5 (new bit=1)
Old bucket 2 → New bucket 2 (new bit=0) or 6 (new bit=1)
Old bucket 3 → New bucket 3 (new bit=0) or 7 (new bit=1)

Evacuation Triggering and Progress

func mapassign(h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ... hash calculation and bucket finding ...

    if h.growing() {
        growWork(h, bucket)  // Evacuate during normal operations!
    }

    // ... continue with assignment ...
}

func growWork(h *hmap, bucket uintptr) {
    // Evacuate the bucket we're working on
    evacuate(h, bucket&h.oldbucketmask())

    // Make additional progress - evacuate one more bucket
    if h.nevacuate < h.noldbuckets() {
        evacuate(h, h.nevacuate)
        h.nevacuate++  // Track progress
    }
}

Key Properties:

  • Every map operation evacuates 1-2 buckets during growth
  • nevacuate counter tracks which buckets have been evacuated
  • Growth completes when nevacuate == noldbuckets()
  • Amortized O(1) - growth work spread across many operations

Lookup During Evacuation - The Tricky Part

The challenge: Some buckets are evacuated, others aren’t. Lookups must work correctly:

func mapaccess(h *hmap, key unsafe.Pointer) unsafe.Pointer {
    hash := h.hash(key)
    bucket := hash & (1<<h.B - 1)  // New bucket index

    if h.growing() {
        oldbucket := bucket & h.oldbucketmask()  // Corresponding old bucket
        b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(h.bucketsize)))

        if !evacuated(b) {
            // Old bucket not evacuated yet - search there!
            return searchBucket(b, key, hash)
        }
    }

    // Search in new buckets (either not growing or bucket evacuated)
    b := (*bmap)(add(h.buckets, bucket*uintptr(h.bucketsize)))
    return searchBucket(b, key, hash)
}

Hash Seed (hash0) - Security Through Randomness

Seed Generation and Lifecycle

Generation Process:

func makemap(t *maptype, h *hmap, hint int) *hmap {
    // ... other initialization ...
    h.hash0 = fastrand()  // Generated ONCE, never changes!
}

fastrand() Implementation:

// Each goroutine has its own random state
type g struct {
    // ... other fields ...
    rand uint64  // Per-goroutine random state
}

func fastrand() uint32 {
    gp := getg()  // Current goroutine
    // Linear Feedback Shift Register (LFSR) algorithm
    gp.rand = gp.rand*1103515245 + 12345
    return uint32(gp.rand >> 32)
}

Security Properties and Hash DoS Prevention

Without Random Seed (Vulnerable):

// Predictable hash function allows targeted attacks
func badHash(key string) int {
    return simpleHash(key) % bucketCount
}

// Attacker crafts keys that all collide:
// "evil1", "evil2", "evil3"... all hash to bucket 0
// Creates O(n) lookup time instead of O(1)

With Random Seed (Protected):

func goodHash(key string, seed uint32) int {
    return complexHash(key, seed) % bucketCount
}

// Attacker cannot predict bucket distribution
// Maintains O(1) average performance

Real-world Attack Example:

// Without randomization, attacker could send HTTP POST data:
// field1=hash_to_0&field2=also_hash_to_0&field3=still_hash_to_0...
// Causing server map operations to degrade to O(n)

Seed Immutability

// CORRECT: Seed never changes after map creation
m := make(map[string]int)  // hash0 = 0x12345678
m["hello"] = 42            // Uses 0x12345678
// ... map grows, keys redistribute ...
value := m["hello"]        // Still uses 0x12345678 - finds key!

Why immutability is crucial:

// CATASTROPHIC if this happened:
m := make(map[string]int)
m["hello"] = 42  // Stored with seed A in bucket 3

// Imagine seed changed to B:
value := m["hello"]  // Looks with seed B in bucket 7 - KEY NOT FOUND!

Flags Field - Runtime State and Race Detection

Flag Definitions and Usage

const (
    iterator     = 1 // there may be an iterator using buckets
    oldIterator  = 2 // there may be an iterator using oldbuckets
    hashWriting  = 4 // a goroutine is writing to the map
    sameSizeGrow = 8 // current growth is compaction, not expansion
)

Concurrent Access Detection (Best-Effort)

func mapassign(h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // Check for concurrent write
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")  // Runtime panic!
    }

    h.flags ^= hashWriting  // Set writing flag (XOR toggle)

    // ... perform map modification ...

    h.flags &^= hashWriting  // Clear writing flag (AND NOT)
    return result
}

The Race Condition in Flag Operations

Flag operations are not atomic, which creates a window for concurrent access.

// RACE WINDOW EXISTS:
if h.flags&hashWriting != 0 { ... }  // ← Read operation
h.flags ^= hashWriting                // ← Write operation (NOT ATOMIC!)

Problematic sequence:

  1. Goroutine A: reads flags, sees hashWriting = 0 ✓
  2. Goroutine B: reads flags, sees hashWriting = 0 ✓
  3. Goroutine A: sets hashWriting = 1
  4. Goroutine B: sets hashWriting = 1 (overwrites A’s flag)
  5. Both proceed to modify map concurrently!

Why Go Doesn’t Use Atomic Operations

  1. Performance First: Atomic operations add overhead to every single map operation, even in single-threaded programs.
  2. Best-Effort Detection: Go’s approach is “best-effort race detection” rather than “foolproof race detection”. The goal isn’t to make maps thread-safe, but to catch common mistakes during development.

Iterator Safety Flags

func mapiterinit(h *hmap, it *hiter) {
    // Detect concurrent modification during iteration
    if h.flags&hashWriting != 0 {
        throw("concurrent map iteration and map write")
    }

    // Mark that iterator exists
    h.flags |= iterator
    if old := h.oldbuckets; old != nil {
        h.flags |= oldIterator  // Iterator needs to see old buckets too
    }
}

Growth Type Tracking

func hashGrow(h *hmap) {
    bigger := uint8(1)  // Default: double the buckets

    if !overLoadFactor(h.count+1, h.B) {
        // Same-size growth (compaction due to overflow buckets)
        bigger = 0
        h.flags |= sameSizeGrow
    }

    // Allocate new bucket array
    oldbuckets, buckets := h.buckets, newarray(t.bucket, int(bucketShift(h.B+bigger)))
    // ...
}

Memory Management and Performance Optimizations

Bucket Array Allocation

// Buckets allocated as single contiguous memory block
bucketsize = unsafe.Sizeof(bmap{}) + keysize*8 + valuesize*8 + ptrsize
buckets = newarray(buckettype, 1<<B)  // 2^B buckets in one allocation

// Benefits:
// - Better cache locality
// - Reduces memory fragmentation
// - Enables fast pointer arithmetic for bucket access

Overflow Bucket Management

type mapextra struct {
    overflow    *[]*bmap  // Overflow buckets in use
    oldoverflow *[]*bmap  // Old overflow buckets during growth
    nextOverflow *bmap    // Next free overflow bucket
}

// Overflow buckets are pooled and reused to reduce allocations

Cache-Friendly Design Decisions

Separate Key-Value Storage:

// Cache-friendly for key scanning:
for i := 0; i < 8; i++ {
    if tophash[i] == target_tophash {
        // Only load key if tophash matches
        // Avoids loading unnecessary values
    }
}

Reference: Faster Go Maps With Swiss Tables

← 随笔

漫行记 · Wandering © 2026

旅行随笔关于

人生海海，山山而川，不过尔尔