Inside Google’s Swiss Table: A High-Performance Hash Table Explained

Swiss Tables:A Modern, High-Performance Hash Table

Swiss Table is a high-performance hash table design introduced by Google engineers in 2017. It has since inspired many standard-library implementations across languages, including:

• Go 1.24 ships its map with this design (up to 60% faster)
• Rust’s standard HashMap has also moved from Robin Hood hashing to a Swiss Table-inspired layout.
• Datadog reported as much as 70% memory savings after migrating to Swiss Table

Open Addressing, Briefly

An open addressing hash table is one of the implementation methods for hash tables. Unlike separate chaining — which uses external data structures such as linked lists or trees — open addressing implements the entire hash table as a single contiguous array.

In an open addressing hash table, when a hash collision occurs, the algorithm probes other empty slots within the table to find a location where the key can be placed.

Typical examples of open addressing strategies include:

• Linear Probing: Move one slot (j) at a time from the original hash position (i)
• Quadratic Probing: Move j² slots from the original hash position (i)

Control Bytes

Each slot carries a 1-byte metadata called a control byte that speeds up lookups and inserts. Control bytes help you quickly spot empty slots, and the short H2 fingerprint gives fast first-pass matches so each probe does less work.

Control byte states:

Grouped SIMD Scans

Modern hash table implementations actively leverage modern hardware to maximize performance. They often use SIMD vector operations to optimize bit operations on control bytes.

The control byte array is processed in chunks the size of the SIMD register VL (e.g., 128 bits). This chunk is called a control byte group (Group). It is not a physically separate structure—just a logical processing unit.

Typical bit split (assuming 64-bit hash):

• H1: upper 57 bits → group index
• H2: lower 7 bits → fingerprint in the control byte

For 32-bit hashes, a split like 25/7 also works.

How it works:

1. Hash the key and split into H1 and H2.
2. Use H1 to pick the starting control-byte group.
3. SIMD-compare the group’s control bytes with H2 (the fingerprint).
4. On a match, confirm the actual key; stop if an Empty is found.
5. Otherwise, advance to the next group and repeat.

References

• https://www.youtube.com/watch?v=ncHmEUmJZf4
• https://abseil.io/about/design/swisstables
• https://go.dev/blog/swisstable
• https://dev.to/huizhou92/swisstable-a-high-performance-hash-table-implementation-1knc
• https://attractivechaos.wordpress.com/2018/10/01/advanced-techniques-to-implement-fast-hash-tables/