Golang Maps: how Swiss Tables replaced the old bucket design

Introduction

Maps sit on the hot path of almost every non-trivial Go program: they power request routing, cache lookups, deduplication sets, aggregation pipelines, and a lot of the glue code we barely notice until it gets slow. Because they are so common, even small runtime-level improvements in map behavior can produce measurable gains across real systems.

Go 1.24 shipped one of the biggest map-internals changes in years: the classic bucket-plus-overflow implementation has been replaced by a Swiss Table-inspired design. The external API did not change - your code still writes map[K]V and calls make, indexing, delete, and range the same way as before. Under the hood, however, lookup and insert paths were reshaped around tighter metadata, flatter probing patterns, and much better cache locality.

The practical effect is straightforward: less pointer chasing, fewer cache misses, higher useful load factors, and faster common operations in many workloads. In microbenchmarks this can be dramatic, while full applications usually see smaller but still meaningful aggregate wins. Memory behavior also improves in many scenarios, especially where old overflow chains used to accumulate.

This post focuses on what changed specifically in Go's runtime design, why those choices matter, and where the trade-offs still show up. If you want a conceptual refresher on hash tables first, see Hash Map Deep Dive.

Go's Old Map Implementation (Pre-1.24)

Before Go 1.24, maps used a bucketed design that had been refined for years and worked well for a wide range of workloads. Each map owned an array of buckets. Each bucket held up to 8 key/value pairs, plus metadata used to speed up matching and track slot state. When a bucket filled up, the runtime allocated an overflow bucket and chained it to the original one.

At a high level, the layout looked like this:

// Conceptual shape, not the exact runtime source.
type hmap struct {
    // map header
    count     int
    B         uint8    // number of buckets is 1<<B
    buckets   *bmap
    oldbuckets *bmap   // previous bucket array during growth
}

type bmap struct {
    // bucket with 8 slots
    tophash [8]uint8
    keys    [8]K
    values  [8]V
    overflow *bmap
}

The key idea was simple and practical. Hash the key, use part of the hash to pick the bucket, then scan that bucket's entries. If no matching key was found and an overflow bucket existed, keep walking the chain until the key was found or the chain ended.

This design had real strengths: it was stable, battle-tested, and supported incremental growth so resize work did not arrive as one huge latency spike. During growth, the map kept both old and new bucket arrays for a while, and operations gradually evacuated old buckets into their new positions as the map was accessed.

The main cost was memory locality under pressure. Overflow chains introduced pointer chasing, and pointer chasing means cache misses. Once hot buckets started spilling into overflow, lookups and inserts could bounce across non-contiguous memory.

The implementation also had practical load-factor limits around 81% (roughly 6.5 filled slots per 8-slot bucket) before growth pressure and collision costs became harder to ignore.

So the old map was not a broken design waiting to be replaced, but an effective implementation with trade-offs that became more visible as modern CPUs, cache behavior, and high-throughput services pushed for tighter, flatter probe paths.

Swiss Tables: Core Design

Historically, Swiss Tables came out of Google's internal performance work on hash tables and were later documented and open-sourced through Abseil - Google's open-source C++ library collection - as flat_hash_map and related containers. The design notes are still the best primary reference for the model and its trade-offs.

Swiss Tables keep the same high-level hash-table contract, but reorganize the data path around two ideas: compact per-slot metadata and probe-friendly contiguous groups. The design has since been adopted across several runtimes and databases because it moves the common-case probe work onto a much more cache-efficient path.

The first thing to understand is that Swiss Tables do not start probing by reading full keys. They start by reading metadata bytes that are cheap to scan in bulk. Only candidates survive to full key comparison. This sounds small, but it changes where CPU time goes.

Hash split: one part for placement, one part for filtering

A key is hashed once, then split into two logical pieces:

• h1: used to choose the initial group index.
• h2: a short fingerprint stored in per-slot metadata.

You can think of h2 as a fast pre-check. If a slot's fingerprint does not match, there is no reason to touch that slot's key bytes at all. Most probes end up rejecting many slots at this metadata stage, which is much cheaper than repeatedly loading and comparing full keys.

Group-oriented layout

Instead of treating each slot as an isolated unit, Swiss Tables organize slots into fixed-size groups. In Go's design, that group size is 8 slots, which aligns with compact metadata handling and practical cache behavior. Each group stores:

• a control word (one metadata byte per slot, packed together),
• 8 key slots,
• 8 value slots.

Conceptually:

group i:
  ctrl: [c0 c1 c2 c3 c4 c5 c6 c7]
  keys: [k0 k1 k2 k3 k4 k5 k6 k7]
  vals: [v0 v1 v2 v3 v4 v5 v6 v7]

Control bytes encode slot state (empty, deleted, occupied) and, for occupied slots, include the h2 fingerprint bits. Because those 8 control bytes are contiguous, the runtime can inspect all slot states for a group in one tight operation.

Probe sequence: filter first, compare keys second

Lookup becomes a two-stage loop:

1. Read the current group's control bytes.
2. Find control-byte positions whose fingerprints match h2.
3. For those positions only, compare real keys.
4. If no match, advance to the next group in the probe sequence.
5. Stop when an empty slot proves the key is absent.

Simplified pseudocode:

g = startGroup(h1)
for {
    matches = matchFingerprint(ctrl[g], h2)
    for each pos in matches {
        if keys[g][pos] == key {
            return vals[g][pos]
        }
    }
    if hasEmpty(ctrl[g]) {
        return not found
    }
    g = nextGroup(g)
}

The hasEmpty(ctrl[g]) check is key. In open addressing, an empty slot means probing can terminate: if the key had ever been inserted along this sequence, the probe would have encountered it before the first truly empty slot.

Insertion and the role of deleted slots

Insert follows the same probe path used by lookup, but it tracks the first reusable position it sees. Reusable can mean either:

• an empty slot, or
• a deleted slot (tombstone), depending on policy and probe progress.

When lookup fails to find the key, insert writes into the best reusable slot discovered so far. This preserves probe invariants while limiting uncontrolled cluster growth.

Deletion does not usually compact the cluster immediately. Instead, it marks metadata as deleted. Immediate compaction would make single deletes expensive and can break probe continuity guarantees. The trade-off is that too many tombstones can lengthen future probes, so implementations need cleanup behavior during growth or reorganization phases.

Why this maps well to modern CPUs

Swiss Tables are often described as "SIMD-friendly," but the broader point is locality plus branch behavior:

• Contiguous metadata scan: a group's control bytes are read together, reducing scattered memory touches.
• Fewer full key loads: most slots fail at fingerprint stage, so key comparisons are sparse.
• Predictable hot loop: probe steps are simple and repetitive, helping branch prediction.
• Better cache residency: metadata and nearby slots are packed to favor cache lines.

Even without architecture-specific vector instructions, this shape tends to perform better than pointer-heavy traversals once maps reach realistic production sizes.

Load factor and practical ceiling

The old bucket-overflow model had to balance overflow growth costs relatively early. Swiss-style open addressing tolerates denser occupancy before performance degrades sharply, because probe work remains mostly linear scans over compact metadata and nearby slots. In practice, this pushes useful load factors upward into the high-80% range (often discussed around 87.5% for 8-slot group designs). The exact threshold is implementation-dependent, but the key result is consistent: denser tables are possible before lookups and inserts become too expensive.

Higher usable density means less memory overhead per stored entry and fewer growth events for the same number of elements - both effects that show up directly in heap profiles and allocation rates.

The trade-offs do not disappear

Swiss Tables are not universally faster in every corner case. At high tombstone density or under specific delete-heavy patterns, probe lengths can regress until cleanup or growth restores table quality. Extremely adversarial hash distributions still hurt any open-addressing design, even with strong metadata filtering. The improvement comes from moving the common case onto a much more cache-efficient path, not from eliminating all hard cases. That is why the shift matters so much for Go: maps are used everywhere, and the common case is where most CPU cycles are spent.

Go-Specific Adaptations

If this were only a straightforward port of Abseil-style Swiss Tables, the runtime work would have been simpler. Go maps, however, have constraints that come from language behavior, GC integration, and long-standing expectations around latency and iteration. The interesting part of Go 1.24 is not just adopting Swiss-style probing, but adapting it so those constraints still hold.

Growth without long stop-the-world style spikes

Classic open-addressing tables are often resized by allocating a larger table and reinserting everything in one large migration step. That is fine in some systems, but Go maps are used on hot request paths where single-operation latency matters. A resize strategy that occasionally performs a full-table rehash can create exactly the kind of long tail the runtime tries to avoid.

Go's adaptation avoids that monolithic jump by spreading growth across smaller units. Instead of treating the map as one giant table that doubles and fully rehashes at once, the runtime can split work so expansion happens incrementally. Operationally, this keeps mutation costs more stable because a single insert is less likely to inherit the full cost of moving every existing element. The practical effect is similar in spirit to the old map's gradual evacuation model: growth still happens, but migration work is amortized across normal operations rather than concentrated into one expensive event.

Multiple independent tables and directory-style routing

One of the key Go-specific choices is to organize storage as multiple smaller Swiss-style tables rather than one ever-growing monolith. A higher-level directory (conceptually similar to extendible hashing) routes keys to a specific table segment, and only the segment under pressure needs to split. Keeping growth local means hot key regions can expand without forcing a global rebuild, and bounding memory movement to the splitting segment improves latency predictability under write-heavy bursts.

At a conceptual level, insertion looks like this:

1. Hash key
2. Use high bits to select table segment
3. Probe within that segment's Swiss groups
4. If segment exceeds thresholds, split that segment and update directory

That directory update is much cheaper than rebuilding every segment, and it composes well with Go's preference for incremental runtime work.

Preserving Go's range semantics while tables change

One of the hardest constraints is preserving Go's map iteration behavior while inserts, deletes, and growth are happening. In Go, iterating with range over a map has deliberately loose ordering guarantees, but it still has safety and consistency expectations. The runtime cannot expose torn state, lose reachability to entries that should still be visible under the language rules, or let relocation mechanics violate iterator correctness.

With segmented Swiss-style storage, this means iterators must understand that entries may move as segments split or internal probe layouts change. The runtime therefore couples iteration state to map-internal versioning and traversal metadata so the iterator can continue safely even while structure evolves. The implementation details are complex, but the user-visible result is simple: for k, v := range m keeps working while the runtime earns better cache locality and denser storage under the hood.

GC and write-barrier friendliness

Go cannot treat table entries as purely mechanical bytes. Keys and values may contain pointers, and pointer movement interacts with garbage collection and write barriers. Any redesign of map internals must preserve accurate pointer visibility and barrier behavior during insert, delete, grow, and iterator transitions. Segmented growth helps here too. Smaller relocation steps are easier to integrate with barriered writes and reduce the size of any single pointer-moving operation. This does not remove complexity, but it narrows blast radius and keeps runtime bookkeeping more tractable.

Swiss-style metadata probing delivers the raw algorithmic win, but Go-specific adaptations - segmented growth, iterator-safe migration, and GC-barrier integration - are what make that win usable at scale in a garbage-collected, latency-sensitive runtime. The performance numbers in the next section reflect both layers working together.

Performance & Memory Analysis (Deeper Dive)

The easiest way to get misled by map benchmarks is to look only at a single synthetic test and assume that number transfers directly to production. For Swiss maps in Go, the public data tells a more nuanced story: the micro-level wins are real and often large, the application-level aggregate win is smaller but still positive.