Swiss Tables: SIMD-Metadata Flat Hash Maps

The problem: pointer-chasing kills hash-map performance

The textbook hash map — separate chaining, as in C++'s std::unordered_map or Java's HashMap — stores each entry in a heap-allocated node and links collisions into a list. Every lookup hashes the key, indexes into a bucket array, then chases pointers through nodes scattered across the heap. On modern CPUs, where a main-memory access costs ~100 ns (hundreds of cycles) and an L1 hit costs ~1 ns, each pointer dereference that misses cache dominates the runtime. The actual comparison work is trivial; the memory stalls are the cost.

Swiss Tables attack this directly. They use open addressing: all entries live in one contiguous array, so there are no per-node allocations and no linked lists. To keep probing cheap, they add a second small array of one-byte control tags. The insight is that you rarely need the full key to reject a slot — a few bits of hash suffice. By packing 7 hash bits per slot into a dense byte array, the search phase touches a tiny, cache-resident metadata region and only reads the (larger) key/value payload when a byte-level match makes a real compare worthwhile.

How it works: control bytes, H1/H2, and 16-wide group scans

For a key, compute a 64-bit hash h and split it into two parts:

• H1 = the upper 57 bits → selects the starting group (position in the table).
• H2 = the low 7 bits → stored in the control byte, used as a fast filter.

Each control byte is one of four states:

EMPTY    = 0b1000_0000  (0x80)   // slot never used
DELETED  = 0b1111_1110  (0xFE)   // tombstone
SENTINEL = 0b1111_1111  (0xFF)   // end-of-table marker
FULL     = 0b0hhh_hhhh           // top bit 0, low 7 bits = H2

A lookup loads a group of 16 control bytes into an SSE2 register, then does _mm_cmpeq_epi8 against a byte broadcast of H2 and _mm_movemask_epi8 to get a 16-bit mask of candidate matches — a handful of instructions to screen all 16 slots. For each set bit, compare the actual key. If none match and the group has an EMPTY slot, the key is absent (probing stops). Otherwise advance to the next group via quadratic probing over triangular numbers (+16, +32, +48 …), which is guaranteed to visit every group of a power-of-two-sized table. Platforms without SSE2 use a SWAR fallback that packs 8 slots into a 64-bit word and finds matches with bit arithmetic.

Complexity and a worked lookup trace

Time is standard for a well-behaved open-addressing table:

• Lookup / insert / delete: O(1) average, O(1) amortized for insert including resizes, O(n) worst case (adversarial or pathological hashing).
• Space: O(n) payload plus 1 control byte per slot. At the default max load factor of 7/8 (87.5%), that is roughly 1.14 metadata bytes per live key.

The load-factor invariant α ≤ 7/8 guarantees each group almost always contains an EMPTY slot, so probe chains stay short. Because H2 filtering rejects ~1/128 of non-matching slots by chance, false byte-matches are rare and full key compares are few.

find("cat"): h = 0x…A5
  H1 -> group index 3
  H2 = 0x25 (low 7 bits)
  load control bytes [3..19)  (16-wide)
  mask = cmpeq(bytes, broadcast 0x25) = 0b0000_0000_0100_0000
  bit 6 set -> compare slot 9's key == "cat"?  yes -> return value
  (if mask==0 and group has EMPTY) -> "cat" not present, stop

The whole hot path typically touches one cache line of control bytes plus one of payload — hence the ~1-cache-miss claim that makes Swiss Tables so fast in practice.

Where it's used in real systems

Swiss Tables are among the most widely deployed data structures written in the last decade:

• Abseil (C++): absl::flat_hash_map / flat_hash_set (values stored inline) and node_hash_map (stable pointers). This is the reference implementation, used pervasively across Google's C++ codebase.
• Rust: the standard library's std::collections::HashMap is a Swiss Table via the hashbrown crate (a Rust port of the design). std defaults to the DoS-resistant SipHash-1-3 hasher; hashbrown standalone defaults to AHash.
• Go: as of Go 1.24 (2025), the built-in map type is implemented with Swiss Tables, replacing the older bucketed design.
• Databases / analytics engines and many performance-sensitive services adopt Abseil's map for hash joins, aggregations, and symbol tables.

The common thread: workloads dominated by point lookups and inserts on medium-to-large maps, where cache behavior — not asymptotics — decides throughput.

Compared to the alternatives — and the tradeoff

Against chaining (std::unordered_map): Swiss Tables win decisively on lookup speed and memory density (no per-node allocations, no next-pointers), at the cost of losing reference stability — a resize or rehash moves entries, invalidating pointers/iterators. Abseil offers node_hash_map when stable addresses are required.

Against Robin Hood / plain linear probing: those are also flat and fast, but they compare full keys (or full hashes) while probing; Swiss Tables' 7-bit control-byte filter plus SIMD lets them reject 16 slots at once, so probe sequences resolve with fewer payload touches.

Against cuckoo hashing: cuckoo offers a hard O(1) worst-case lookup (at most two probe locations), attractive for real-time systems, but it needs lower load factors or multi-way variants and can fail to insert (triggering a rehash). Swiss Tables give better average throughput and cache behavior at high load, trading the worst-case guarantee.

The core tradeoff: Swiss Tables optimize the common case ruthlessly — great average latency, high load factor, tiny metadata — but accept O(n) worst case and unstable references to get there.

Pitfalls, failure modes, and significance

Real-world gotchas to respect:

• Hash quality matters a lot. Open addressing amplifies clustering. A weak or attacker-controlled hash can drive probe chains long and collapse performance to O(n) — the basis of hash-flooding DoS attacks. This is why Rust's std uses a random-seeded SipHash by default.
• Tombstones accumulate. Deletions leave DELETED control bytes that still cost probe steps. Delete-heavy churn degrades lookups until a rehash/resize sweeps them; some implementations rehash in place when the tombstone ratio grows.
• Reference instability. Do not hold pointers/iterators across insertions that can trigger a grow — a classic use-after-move bug. Use node_hash_map (or box the values) if you need stable addresses.
• Non-SIMD platforms fall back to the 8-wide SWAR path — still fast, but the headline vectorization advantage narrows.

Its significance is architectural: Swiss Tables reframed hash-map design around the memory hierarchy and SIMD rather than pure asymptotics, and the design's rapid adoption across C++, Rust, and Go made it the de facto modern general-purpose hash map.

Swiss Table vs. common hash-map strategies (average-case, in-memory)

Property	Swiss Table (open addr + SIMD)	std::unordered_map (chaining)	Robin Hood / linear probing	Cuckoo hashing
Memory layout	Flat, one array + control bytes	Node per entry, pointer-linked	Flat array	Two flat arrays
Lookup (avg)	O(1), ~1 cache miss	O(1), 2+ cache misses (chase)	O(1)	O(1), ≤2 probes
Worst-case lookup	O(n)	O(n) (or O(log n) if treeified)	O(n)	O(1) guaranteed
Max load factor	~87.5% (7/8)	Often ~1.0 (chains grow)	~90%	~50% (2-table) / higher w/ 4-way
Deletion	Tombstone control byte	Unlink node	Backward-shift / tombstone	Direct clear
SIMD-friendly	Yes (core design)	No	Partial	No