Inside SwissTable / hashbrown: H1/H2 Split & 1-Byte Control Metadata
Given a 64-bit hash $h = \text{hash}(k)$, SwissTable splits $h$ into two components:
H1(h) = h >> 7(57 bits): Selects the starting 16-slot Probe Group indexpos = H1(h) & mask.H2(h) = h & 0x7F(7 bits): A 7-bit fingerprint stored in the corresponding 1-byte Control Byte (ctrl[i]). Because the top bit (bit 7, the sign bit0x80) of every occupiedH2byte is strictly0(0b0xxxxxxx), the top bit1(0b1xxxxxxx) is reserved for special empty/deleted sentinels!
Look at the cleverness of the three sentinel byte encodings in hashbrown / Abseil:
OCCUPIED:0b0xxxxxxx(0x00to0x7F) — Bit 7 is0, bits[6..0]hold the 7-bitH2hash tag.EMPTY:0b11111111(0xFF, signed-1, or0x80-128in Abseil) — Bit 7 is1.DELETED(Tombstone):0b10000000(0x80inhashbrown/0xFE-2in Abseil) — Bit 7 is1.
Because both EMPTY and DELETED have their sign bit (bit 7) set to 1, a single x86 SSE2 instruction _mm_movemask_epi8(ctrl_group) extracts the MSB of all 16 control bytes simultaneously into a 16-bit integer mask of all non-occupied slots!
| Hash Map Implementation | Memory Overhead / Slot | Max Load Factor $\alpha$ | Buckets Checked per L1 Line | Full-Key False Compare Rate |
|---|---|---|---|---|
C++ std::unordered_map |
16–24B (next ptr + heap header) |
$1.00$ (Unbounded chains) | $1$ (Pointer chase per node) | Matches in bucket chain |
| Legacy Rust Robin Hood Map | 8B hash + alignment padding | $0.90$ | $2–4$ (hash, K, V) structs |
$2^{-64}$ |
Google Abseil flat_hash_map |
1 Byte (ctrl_t H2) |
$7/8 = 87.5\%$ | 64 Control Bytes (4 SIMD Groups) | $1 / 128 \approx 0.78\%$ |
Rust hashbrown::HashMap |
1 Byte (u8 H2) |
$7/8 = 87.5\%$ | 64 Control Bytes (4 SIMD Groups) | $1 / 128 \approx 0.78\%$ |
Formal Specification: The 16-Way SIMD Lookup State Machine
To find key with (h1, h2): start at group_idx = h1 & mask and step = 0. In each iteration:
- Load 16 control bytes starting at
ctrl + group_idxinto a 128-bit SIMD registerg = _mm_loadu_si128(...). - Match
H2:match_mask = _mm_movemask_epi8(_mm_cmpeq_epi8(g, _mm_set1_epi8(h2))). Iterate over set bits viatz = countr_zero(match_mask)andmatch_mask &= match_mask - 1. Only for those rare lanes where the 7-bitH2matches (false positive rate $1/2^7 = 0.78\%$) do we touch theslots[]data array to compareslots[idx].key == key! - Check
EMPTY:empty_mask = _mm_movemask_epi8(_mm_cmpeq_epi8(g, _mm_set1_epi8(EMPTY))). Ifempty_mask != 0, at least one slot in this 16-slot group has never been occupied, so the probe chain terminates immediately (return NOT_FOUND). - Triangular Group Advance: If all 16 slots are
OCCUPIEDorDELETED, advance to the next group via triangular probing:step += 16; group_idx = (group_idx + step) & mask.
Visualizing the 16-Byte SIMD Control Group & Bitmask Extraction
flowchart LR
H["h = hash(key)
h1 = h >> 7
h2 = h & 0x7F"] --> Load["Load 16B ctrl[pos..pos+15]
into SIMD XMM register"]
Load --> Match["mask = movemask(cmpeq(ctrl, h2))"]
Match --> Loop{"mask != 0 ?"}
Loop -- "Yes (tz = ctz(mask))" --> Cmp{"slots[pos+tz].key
== key ?"}
Cmp -- "Hit" --> Ret["Return &slots[pos+tz]"]
Cmp -- "7-bit Collision" --> Clear["mask &= mask - 1"] --> Loop
Loop -- "No" --> Emp{"movemask(cmpeq(ctrl, EMPTY))
!= 0 ?"}
Emp -- "Yes (Empty seen)" --> Miss["Return NOT_FOUND"]
Emp -- "No (All 16 full/del)" --> Step["step += 16
pos = (pos + step) & cap_mask"] --> Load
Open Addressing: Robin Hood PSL & SwissTable 16-Way SIMD Probe
Expected O(1) · SIMD H2
Compare Robin Hood Hashing (stealing slots from rich keys with lower Probe Sequence Length PSL to crush variance) and Google SwissTable / Rust hashbrown 16-byte H2 metadata SIMD bitmask probing.
Step 1 / 9
Timeline
Invariant & State
Robin Hood Invariant: ∀ slot i, PSL variance minimized; placed A at [1] with PSL=0
🧭 Live Hash Ring & Bucket Probe Telemetry — Open Addressing: Robin Hood PSL & SwissTable 16-Way SIMD Probe
Probe
Collision/Swap
Hit/Placed
[0]·
[1]Ah=1,PSL=0
[2]·
[3]·
[4]·
[5]·
[6]·
[7]·
Inserting
A (home=1)
Slot Index
[1]
Placed PSL
0
Max PSL in Table
0
[Step 1] Slot [1] was empty -> placed key A (home=1, PSL=0).
Hardware Reality: Portable 64-Bit SWAR Group Probing & Mirrored Tail Bytes
What if an unaligned probe group starts at index $m - 5$ near the end of the capacity-$m$ array? Instead of branching to wrap around the end of the ctrl array, SwissTable allocates $m + 16$ control bytes and mirrors the first 16 control bytes ctrl[0..15] at ctrl[m..m+15]! This allows _mm_loadu_si128(&ctrl[pos]) to execute an unbranched 16-byte load from any index pos in $[0, m-1]$. On targets without SSE2/NEON, SwissTable falls back to 8-byte SWAR (SIMD Within A Register) bit manipulation in a standard uint64_t.
Production C++20 Implementation: Portable 8-Way SWAR / SSE2 SwissTable Group Matcher
// C++20: SwissTable / hashbrown Control Group Matcher (8-Way SWAR + x86 SSE2)
#include <cstdint>
#include <cstring>
#include <bit>
#if defined(__SSE2__)
#include <emmintrin.h>
#endif
// Portable 8-Byte SWAR Group (Used by hashbrown on 64-bit targets without SIMD)
struct SwarGroup8 {
uint64_t ctrl; // 8 control bytes: 0x00..0x7F = H2, 0xFF = EMPTY, 0x80 = DELETED
explicit SwarGroup8(const uint8_t* ptr) noexcept {
std::memcpy(&ctrl, ptr, sizeof(uint64_t));
}
// Returns bitmask with bit (i*8 + 7) set for each byte matching h2 (0..127)
uint64_t matchByte(uint8_t h2) const noexcept {
constexpr uint64_t LO_BITS = 0x0101010101010101ULL;
constexpr uint64_t HI_BITS = 0x8080808080808080ULL;
uint64_t x = ctrl ^ (LO_BITS * h2);
return (x - LO_BITS) & ~x & HI_BITS;
}
// Returns bitmask with bit (i*8 + 7) set for each EMPTY (0xFF) or DELETED (0x80) byte
uint64_t matchEmptyOrDeleted() const noexcept {
return ctrl & 0x8080808080808080ULL;
}
static uint32_t trailingMatchedIndex(uint64_t bitmask) noexcept {
return static_cast<uint32_t>(std::countr_zero(bitmask) >> 3);
}
};
#if defined(__SSE2__)
struct Sse2Group16 {
__m128i ctrl;
explicit Sse2Group16(const uint8_t* ptr) noexcept {
ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(ptr));
}
uint32_t matchH2(uint8_t h2) const noexcept {
return static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(ctrl, _mm_set1_epi8(static_cast<char>(h2)))));
}
uint32_t matchEmpty() const noexcept {
return static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(ctrl, _mm_set1_epi8(static_cast<char>(0xFF)))));
}
};
#endifFailure Modes & Adversarial Pitfalls
- Pointer/Reference Invalidation on
flat_hash_mapInsert: Unlikestd::unordered_map, where node pointers remain valid across rehashes,absl::flat_hash_mapandhashbrown::HashMapstore(K, V)inline. Any insertion that triggers a resize invalidates all existing pointers and references! When pointer stability or large value types ($> 64$ bytes) are required, useabsl::node_hash_map. - Poor Low/High Bit Entropy in Custom Hash Functions: Because SwissTable uses the upper 57 bits (
H1) for bucket selection and the lowest 7 bits (H2) for the SIMD control byte, a custom hash function whose lowest 7 bits are constant (e.g., an unmixed aligned pointerreinterpret_cast<uintptr_t>(ptr)) setsH2 = 0for every single key—turning all 16 SIMD lanes into $100\%$ false positives! Always pass custom hashes through a finalizer mixer.