Hash Tables 101

Introduction: The Quest for the "Instant" Lookup

In our quest for performance, we often pursue the elusive goal of software engineering: the "instant" lookup. In algorithmic terms, we call this O(1), or constant time. It promises that finding a specific needle in the haystack will take the same effort, no matter how much data we generate. However, as any systems engineer will explain, this dream constantly clashes with the physical limits of computer memory. We operate in a world where application data spaces seem infinite, yet our hardware has strict boundaries.

A hash table is not just a storage tool; it is a complex mathematical compromise. It connects a vast universe of possible keys and the small, sequential arrays our CPUs can actually process. Creating a hash table means addressing a key question: How do we fit an infinite world of data into a tiny, finite array without everything falling apart?

If you work in Go, this compromise is made concrete in the runtime. The built-in map type is a practical example of these trade-offs. Since Go 1.24 (released February 11, 2025), the default implementation of Go maps is based on Swiss Tables with extendible hashing. That modern design replaces the older bucket/overflow-chain implementation as the default; the legacy bucket code is retained only as an opt-out fallback (via GOEXPERIMENT=noswissmap). This post explains what the Swiss-table design means for Go programmers, the runtime guarantees you can rely on, and the practical caveats you must respect — across Go 1.24, 1.25, and the current Go 1.26 release.

The Speed King: Why O(1) Changes Everything (and the caveats)

The appeal of the hash table lies in its outstanding efficiency. While balanced trees or sorted lists involve navigating through comparisons and jumps — paths that grow longer with our data — a well-designed hash table skips the search altogether. When implemented and used properly, hash tables deliver expected O(1) average-case insertions, deletions, and lookups.

But "on average" hides failure modes:

• Hash collisions: Bad or attacker-controlled hash inputs can create many collisions and long probe sequences. Go mitigates hash-flooding by using a per-map random seed that perturbs hashing so crafted inputs can't reliably cause worst-case collisions across maps or program runs.

• Memory layout and GC pressure: Storing large structs directly in a map causes copies and more GC pressure than storing pointers. Storing pointers avoids copying but introduces pointer-chasing and additional GC scan work.

• Resizing is unavoidable. When a map grows, Go migrates entries incrementally to a larger internal structure. This avoids a single long pause but means some operations pay extra work while migration is in progress.

• Iteration order is randomised and intentionally unstable between runs and between modifications — don't rely on it.

• Maps are not safe for concurrent mutation. Concurrent read+write or concurrent writes cause the runtime to detect the race and terminate the program. Use sync.RWMutex or sync.Map for concurrent access.

• A map's zero value is nil. Reading from a nil map returns the zero value for the element type; assigning to a nil map panics.

Swiss Tables in Go: the current default (Go 1.24–1.26)

Since Go 1.24, the default Go map is a Swiss table with extendible hashing. Here is what that means concretely:

Structure: groups, not overflow chains

The table is organised into groups of 8 slots. This grouping is chosen for CPU-friendly operations (e.g., vectorised comparisons) and cache efficiency.

Each group holds a control region: one control byte per slot. Each control byte contains a small "fingerprint" of the key's hash (called h2,a 7-bit hash fragment) plus a 1-bit status marker (empty / deleted/ occupied). The control bytes let the runtime quickly rule out non-matching slots without fetching full keys — analogous to the legacy tophash, but laid out for efficient parallel comparison.

Open addressing, not overflow chains

The table uses open addressing rather than chained overflow buckets. Insertions and lookups probe groups following a probe sequence defined by the hash and the table's addressing scheme. This improves memory locality and removes the pointer-chasing overhead of the old overflow-chain design.

Note: The legacy bucket-based implementation — 8-slot buckets, a per-slot tophash byte, overflow chains, the hmap.hash0 seed field — is still present in the source tree as a noswiss fallback (src/runtime/map_noswiss.go). It is not the default for any release since Go 1.24.

Extendible hashing for growth

A map may hold one or more table objects. A single Swiss table is capped at 128 groups (1,024 slots). Beyond that cap, Go uses extendible hashing: the map is split into multiple independent sub-tables that cover different partitions of the key space, identified by leading bits of the hash. Migration of entries to a larger sub-table is done incrementally to bound pause times and spread resize cost across operations — rather than a single stop-the-world rehash.

Why Swiss Tables were chosen

Reported improvements in Go 1.24: lookups in large maps ~30% faster, assignment into pre-sized maps ~35% faster, iteration ~10–60% faster depending on load, with reduced memory footprint for most workloads.

Go's map implementation — a practical primer

Per-map hash seed

Each map uses a per-map random seed (called seed in the Swiss-table implementation; hash0 in the legacy code) to randomise internal hashing. This prevents an attacker from crafting key sets that reliably cause pathological probe sequences across maps or program runs (hash-flooding mitigation).

Incremental growth

Maps grow incrementally. The runtime migrates entries to larger sub-tables in a controlled fashion to avoid large pause times on resize operations. Individual sub-tables grow (roughly doubling group count, up to the 128-group cap) and are then replaced; beyond the cap, the map splits into more sub-tables via extendible hashing.

Iteration order is randomised

The runtime randomises the iteration start point and order. Code must not rely on map iteration order for correctness — this is intentional and guaranteed by the language specification.

Concurrency

Concurrent writes or concurrent read/write without synchronisation cause the runtime to detect the race and issue a fatal error (the program is terminated; this cannot be recovered with recover()). Do not mutate maps from multiple goroutines without proper synchronisation.

Nil-map semantics

var m map[string]int // nil map
fmt.Println(m["x"]) // prints 0 (zero value), no panic
m["x"] = 1          // panic: assignment to entry in nil map

Reading from a nil map is safe and returns the zero value. Writing to a nil map panics.

Practical Go (1.26) examples

Below are concise examples you can run in a playground or local file to observe the behaviours described above.

Basic map usage (lookups and inserts)

package main

import "fmt"

func main() {
    m := make(map[string]int)
    m["apple"] = 5
    v, ok := m["apple"]
    fmt.Println(v, ok) // 5 true

    _, ok = m["banana"]
    fmt.Println(ok) // false
}

Nil maps: reads allowed; writes panic

var m map[string]int // nil
fmt.Println(m["x"]) // 0, no panic
// m["x"] = 1 // uncommenting causes panic: assignment to entry in nil map

Concurrent mutation: will cause a fatal error (unsafe)

package main

import "sync"

func main() {
    m := make(map[int]int)
    var wg sync.WaitGroup

    for i := 0; i < 4; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            for j := 0; j < 10000; j++ {
                m[j] = id // concurrent writes -> runtime fatal error
            }
        }(i)
    }

    wg.Wait()
}

Mutex-protected map (safe concurrency)

var (
    mu sync.RWMutex
    m  = make(map[int]int)
)

func write(k, v int) {
    mu.Lock()
    m[k] = v
    mu.Unlock()
}

func read(k int) (int, bool) {
    mu.RLock()
    v, ok := m[k]
    mu.RUnlock()
    return v, ok
}

sync.Map (concurrent map from stdlib)

sync.Map is a separate concurrent map-like API optimised for specific access patterns (stable key sets with many readers, or disjoint per-goroutine key sets). It has different performance characteristics from a mutex-guarded built-in map and is not a drop-in replacement.

var sm sync.Map
sm.Store("x", 42)
v, ok := sm.Load("x") // ok == true, v == 42
sm.Delete("x")

// Additional methods: LoadOrStore, LoadAndDelete, Range, Swap,
//                     CompareAndSwap, CompareAndDelete, Clear

Go 1.24 note: sync.Map was internally reimplemented in Go 1.24 as a wrapper around a concurrent hash-trie (internal/sync.HashTrieMap). The public API and semantics are unchanged; performance for disjoint-key workloads is significantly improved.

Iteration order is randomised (observe different orders)

package main

import "fmt"

func main() {
    m := map[int]string{1: "a", 2: "b", 3: "c", 4: "d"}
    for i := 0; i < 3; i++ {
        var order []int
        for k := range m {
            order = append(order, k)
        }
        fmt.Println(order) // likely different each run/iteration
    }
}

Incremental growth (illustrative)

package main

import "fmt"

func main() {
    m := make(map[int]int)
    for i := 0; i < 1<<20; i++ {
        m[i] = i
        if i%(1<<18) == 0 {
            fmt.Printf("inserted %d entries\n", i)
        }
    }
}

As the map grows, Go allocates larger sub-tables and incrementally migrates entries; inserts during that phase pay a small extra cost to advance migration.

Memory layout and GC trade-offs (values vs pointers)

type Big struct{ a [1024]byte }

func main() {
    // Value type: copies ~1KB into the map slot on each insert
    m1 := make(map[int]Big)
    m1[1] = Big{}

    // Pointer type: avoids the copy, but adds pointer indirection and GC scan work
    m2 := make(map[int]*Big)
    m2[1] = &Big{}
}

Choose value or pointer depending on whether copy cost or GC/pointer-chasing overhead is the dominant concern for your workload.

Conclusion

Hash tables aim for constant-time operations by pairing clever hashing with compact memory layout. Go's built-in map, from Go 1.24 onwards through the current Go 1.26, is backed by a Swiss-table design with extendible hashing: 8-slot groups with compact per-slot control bytes, open addressing, per-map random seeds, and incremental growth via extendible hashing across multiple sub-tables. These choices deliver excellent average-case performance and real improvements over the legacy bucket/chain implementation — but they impose practical constraints you must still respect: choose your key and value types wisely, pre-size maps when possible (make(map[K]V, hint)), never assume iteration order, and always synchronise concurrent access.

Understanding those trade-offs turns the map from a mysterious "magic" container into a predictable, efficient tool you can reason about and use safely.

References:

• Go 1.24 release notes — Swiss Tables adoption

• Faster Go maps with Swiss Tables — official Go blog

• pkg.go.dev/sync — sync.Map