Swiss table

Deep dive

How it works

In: a key (and a value on insert) · Out: the value or absent · State: a control-byte array (7-bit tag, EMPTY or DELETED per slot) plus a slot array, in one allocation · Cost: expected O(1); one SIMD compare per 16-slot group, about 2 cache misses on large tables

ctrl:  [h2][h2][E ][h2][D ][E ][h2][h2] | next group ...    E=EMPTY D=DELETED h2=0..127
slots: [k,v][k,v][  ][k,v][  ][  ][k,v][k,v]

1. h = hash(key); h2 = top 7 bits; start group = h1 & mask.
2. Load the group's control bytes. match_byte(h2) returns a bitmask of candidate slots; compare keys only there.
3. If the group contains an EMPTY byte, the key is absent: stop. Otherwise go to the next group in the probe sequence (triangular: +1, +2, +3 groups... visits every group once when the group count is a power of two).
4. Insert: same probe, remember the first EMPTY or DELETED slot, write h2 and the slot.
5. Delete: if the slot's group still has an EMPTY byte, no probe ever passed through it, so mark EMPTY; else mark DELETED (tombstone). Tombstones are purged on rehash.

Abseil uses kEmpty = 0x80, kDeleted = 0xFE, sentinel 0xFF; hashbrown uses EMPTY = 0xFF, DELETED = 0x80. Either way FULL bytes have bit 7 clear, so "empty or deleted" is just the top bit (movemask).

Code

Portable SWAR version (8 control bytes in a u64, like hashbrown's non-SSE path). Groups are aligned, which makes the "EMPTY in my group" delete rule exact.

const GROUP: usize = 8;
const EMPTY: u8 = 0xFF; // hashbrown encoding
const DELETED: u8 = 0x80;
const LO: u64 = 0x0101_0101_0101_0101;
const HI: u64 = 0x8080_8080_8080_8080;

fn hash(k: u64) -> u64 { // splitmix64 finalizer
    let mut x = k.wrapping_add(0x9E37_79B9_7F4A_7C15);
    x = (x ^ (x >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    x ^ (x >> 31)
}
// Bit 7 of byte i set => ctrl byte i may equal h2. False positives are always FULL slots; keys get compared anyway.
fn match_byte(g: u64, h2: u8) -> u64 { let x = g ^ (LO * h2 as u64); x.wrapping_sub(LO) & !x & HI }
fn match_empty(g: u64) -> u64 { g & (g << 1) & HI } // 0xFF: bits 7 and 6 set; DELETED has bit 6 clear
fn first(m: u64) -> usize { m.trailing_zeros() as usize / 8 }

pub struct SwissMap<V: Copy + Default> { ctrl: Vec<u8>, slots: Vec<(u64, V)>, mask: usize, items: usize, growth_left: usize }

impl<V: Copy + Default> SwissMap<V> {
    pub fn with_buckets(n: usize) -> Self {
        assert!(n.is_power_of_two() && n >= GROUP);
        SwissMap { ctrl: vec![EMPTY; n], slots: vec![(0, V::default()); n], mask: n - 1, items: 0, growth_left: n / 8 * 7 }
    }
    fn group(&self, pos: usize) -> u64 { u64::from_le_bytes(self.ctrl[pos..pos + GROUP].try_into().unwrap()) }
    fn start(&self, h: u64) -> usize { h as usize & self.mask & !(GROUP - 1) }

    fn find(&self, k: u64) -> Option<usize> {
        let h = hash(k);
        let (mut pos, mut stride) = (self.start(h), 0);
        loop {
            let g = self.group(pos);
            let mut m = match_byte(g, (h >> 57) as u8);
            while m != 0 {
                let i = pos + first(m);
                if self.slots[i].0 == k { return Some(i); }
                m &= m - 1;
            }
            if match_empty(g) != 0 { return None; }
            stride += GROUP; // triangular probing over groups
            pos = (pos + stride) & self.mask;
        }
    }
    pub fn get(&self, k: u64) -> Option<V> { self.find(k).map(|i| self.slots[i].1) }

    pub fn insert(&mut self, k: u64, v: V) {
        if let Some(i) = self.find(k) { self.slots[i].1 = v; return; }
        if self.growth_left == 0 { self.resize(); }
        let h = hash(k);
        let (mut pos, mut stride) = (self.start(h), 0);
        loop {
            let free = self.group(pos) & HI; // EMPTY or DELETED
            if free != 0 {
                let i = pos + first(free);
                if self.ctrl[i] == EMPTY { self.growth_left -= 1; } // reusing a tombstone is free
                self.ctrl[i] = (h >> 57) as u8;
                self.slots[i] = (k, v);
                self.items += 1;
                return;
            }
            stride += GROUP;
            pos = (pos + stride) & self.mask;
        }
    }

    pub fn remove(&mut self, k: u64) -> Option<V> {
        let i = self.find(k)?;
        let g = self.group(i & !(GROUP - 1));
        // A group that still has an EMPTY byte never stopped a probe from passing, so no tombstone needed.
        self.ctrl[i] = if match_empty(g) != 0 { self.growth_left += 1; EMPTY } else { DELETED };
        self.items -= 1;
        Some(self.slots[i].1)
    }

    fn resize(&mut self) {
        let cap = self.mask + 1;
        let n = if self.items * 16 >= cap * 7 { cap * 2 } else { cap }; // mostly tombstones: rehash in place size
        let old = std::mem::replace(self, Self::with_buckets(n));
        for (i, &c) in old.ctrl.iter().enumerate() {
            if c & 0x80 == 0 { self.insert(old.slots[i].0, old.slots[i].1); }
        }
    }
}

Complexity and constants

• Expected probe length at 87.5 % load: about 1-1.5 groups for hits; misses stop at the first group with an EMPTY byte.
• False key compares per group: order of 16/128 = 0.125 with 16-wide groups.
• Memory: cap × (1 + sizeof(K,V)) bytes; average fill is order of 60-70 % over a growing table's life.
• Hit latency in L1/L2: order of 5-20 ns including hashing. Tables much larger than LLC: about 2 cache misses (control bytes, slot), order of 100-200 ns; prefetching the slot address while comparing helps.
• Resize: O(n) rehash, typically order of 5-20 ns/element.

Efficiency

• Cost: a hit takes order of 5-20 ns in L1/L2 including hashing; tables much larger than the LLC take about 2 cache misses (control bytes, then slot), order of 100-200 ns. A false key compare happens 1 time in 128 per slot. Memory is cap × (1 + sizeof(K,V)) bytes with load up to 7/8. Resize rehash costs order of 5-20 ns per element. Bound: memory latency, then hashing.
• Levers:
  • 1-byte tags compared 16 at a time with SSE2 — 16 slots filtered per instruction (Abseil, hashbrown) — x86; NEON uses 8-byte groups
  • good hash with strong high and low bits — H2 stays informative, no long runs (fast hash functions) — always
  • reserve before bulk load — avoids about log2(n) full rehashes — known sizes
  • prefetch the slot while comparing tags (order of) — hides the second miss — large tables, batched lookups
  • control and slots in one allocation — a miss touches only control bytes — absent-key-heavy workloads
• Naive → standard → state of the art:
  • chained table (std::unordered_map) · pointer chase per probe
  • linear probing / Robin Hood · one run scan, 70-90 % load
  • Swiss table with SIMD tags · one group compare, up to 7/8 load

Implementation notes

• x86: _mm_cmpeq_epi8(group, _mm_set1_epi8(h2)) then _mm_movemask_epi8 gives a 16-bit mask; iterate with tzcnt and blsr. ARM NEON has no movemask; hashbrown and Abseil use 8-byte groups with the NEON compare narrowed into a 64-bit mask.
• Unaligned probing (Abseil, hashbrown) starts at any byte, so the control array has GROUP-1 mirrored bytes at the end to make wrap-around loads valid. The delete rule then looks both ways: mark DELETED only if the run of non-EMPTY bytes around the slot is at least GROUP long (some probe window could have been all-full); otherwise EMPTY.
• Separate control and slot arrays in one allocation (Abseil: ctrl first, then slots) so a miss usually touches only the control bytes.
• The hash must have good high bits (H2) and low bits (H1). Identity hashing of integers breaks it; hashbrown and Abseil always mix.
• Iteration scans control bytes 16 at a time with the "full" mask; it is fast but proportional to capacity, not size.

Pitfalls

• Many deletes then inserts: tombstones fill groups, misses probe long. Count tombstones toward the load factor (as growth_left does) and rehash in place.
• Weak hash (e.g. hash(x) = x): H2 becomes constant within a run of keys and every group compare matches.
• Iterating while erasing and reinserting the same keys can loop forever or rehash repeatedly.
• reserve before bulk loading; doubling from small sizes rehashes everything ~log2(n) times.
• Huge values make the table sparse in bytes; store large values out of line.

Variants and alternatives

In production

• Language runtimes: Rust std::collections::HashMap (hashbrown), Go maps since Go 1.24 (Go blog).
• C++ libraries used across infrastructure code: Abseil flat_hash_map/flat_hash_set (from Google), Folly F14 (Meta), Boost.Unordered flat containers.
• Only language-runtime and library uses are sourced; no per-field production use was verified.

Implementations

Sources

• Matt Kulukundis, Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step, CppCon 2017. talk
• Abseil, Swiss Tables Design Notes, abseil.io. docs
• Amanieu d'Antras, hashbrown crate source (raw/mod.rs, control/group/generic.rs). code
• Michael Pratt, Faster Go maps with Swiss Tables, The Go Blog. post
• Folly, F14 hash tables. docs