Fundamentals 16 min read

Why Go’s New Map Uses SwissTable: Inside the Faster Hash Table

This article explains how Go 1.24 rewrote its built‑in map with a SwissTable‑based hash table, compares it to Dolt’s SwissMap implementation, and details the underlying data structures, algorithms, and performance benefits.

Radish, Keep Going!

Jan 3, 2025

Why Go’s New Map Uses SwissTable: Inside the Faster Hash Table

Go 1.24 Map Reimplemented with SwissTable

This is an older article that discusses the recent change in Go 1.24 where the standard library map implementation was switched to a SwissTable‑based design. The author plans to compare Dolt’s SwissMap with Go’s swisstable and explain why it may become the new standard implementation.

Background

In 2022 ByteDance opened an issue suggesting that Go’s map should adopt SwissTable. In 2023 Dolt published a blog titled “SwissMap: A smaller, faster Golang Hash Table”, which attracted attention. The Go core team subsequently added parts of the swisstable design to the runtime, prompting a deeper dive into its principles and a comparison with the existing runtime map.

Traditional Hashtable Basics

Hash tables map a key to a value using a hash function that determines a slot position. Collisions are inevitable; common resolutions are chaining (linked lists) and linear probing.

Chaining

When multiple keys map to the same slot, they are stored in a linked list. Insertion and deletion are fast, but cache locality suffers because linked nodes are scattered in memory.

Linear Probing

On a collision, the algorithm scans forward slot by slot until an empty slot is found. This method is cache‑friendly but can suffer from clustering, higher memory usage, and degraded lookup performance.

Go Map Storage Model

Keys are hashed into multiple bucket s; each bucket holds a fixed number of slot s (8 key‑value pairs).

If a bucket fills, an overflow bucket is allocated.

Lookup computes the hash, finds the bucket, then scans its slots (including overflow buckets) for the key.

SwissTable: An Efficient Hashtable Implementation

SwissTable

improves linear probing by using a compact metadata array ( ctrl) that stores hash fingerprints (H2) and slot state flags. This metadata fits easily into CPU caches and enables SIMD‑accelerated batch comparisons, reducing unnecessary key equality checks.

Basic Structure

type Map[K comparable, V any] struct {
    ctrl      []metadata
    groups    []group[K, V]
    hash      maphash.Hasher[K]
    resident  uint32 // occupied slots
    dead      uint32 // tombstones
    limit     uint32 // resize threshold
}

type metadata [groupSize]int8

type group[K comparable, V any] struct {
    keys   [groupSize]K
    values [groupSize]V
}

The ctrl array holds one byte per slot, encoding whether the slot is empty, deleted, or contains the H2 fingerprint of the key. This tiny metadata allows the CPU to quickly filter candidates before accessing the actual slot data.

Adding Data

Split the hash into h1 (group index) and h2 (fingerprint).

Probe the group indicated by h1 and use metaMatchH2 to find matching H2 values.

If a matching key is found, update its value; otherwise, use metaMatchEmpty to locate a free slot and insert the new key‑value pair.

If the group is full, continue linear probing to the next group.

func (m *Map[K, V]) Put(key K, value V) {
    if m.resident >= m.limit {
        m.rehash(m.nextSize())
    }
    hi, lo := splitHash(m.hash.Hash(key))
    g := probeStart(hi, len(m.groups))
    for {
        matches := metaMatchH2(&m.ctrl[g], lo)
        for matches != 0 {
            s := nextMatch(&matches)
            if key == m.groups[g].keys[s] {
                m.groups[g].values[s] = value
                return
            }
        }
        matches = metaMatchEmpty(&m.ctrl[g])
        if matches != 0 {
            s := nextMatch(&matches)
            m.groups[g].keys[s] = key
            m.groups[g].values[s] = value
            m.ctrl[g][s] = int8(lo)
            m.resident++
            return
        }
        g++
        if g >= uint32(len(m.groups)) {
            g = 0
        }
    }
}

func metaMatchH2(m *metadata, h h2) bitset { return hasZeroByte(castUint64(m) ^ (loBits * uint64(h))) }

func nextMatch(b *bitset) uint32 {
    s := uint32(bits.TrailingZeros64(uint64(*b))
    *b &= ^(1 << s)
    return s >> 3
}

Advantages of SwissTable

Operations move from bulky slot s to tiny ctrl metadata, improving cache utilization.

Storing hash fingerprints reduces costly full key comparisons.

Batch processing of ctrl entries with SIMD yields higher throughput.

Memory layout and flag values are SIMD‑optimized, further boosting performance.

Large‑map benchmarks on a MacBook M1 (without SIMD) still show noticeable speedups for swisstable over traditional maps.

Conclusion

Go’s official runtime has not yet fully adopted swisstable, but community projects such as concurrent-swiss-map and swiss provide implementations. While swisstable may underperform on small maps compared to the existing runtime map, its performance on large maps and its modern design make it a promising direction for future Go hash tables.