Sixteen Buckets at a Time: The SwissTable in Rust's HashMap

TL;DR: HashMap in Rust is a SwissTable: a power-of-two bucket array with a parallel array of control bytes, where the top 7 bits of each hash are stored in the control byte. A lookup loads 16 control bytes with one SSE2 instruction, compares them all at once, and uses movemask to find candidates — 16 comparisons for the price of one.

Note: HashMap in current Rust lives in library/std but the table implementation comes from the external hashbrown crate (hashbrown = "0.17.1" in library/std/Cargo.toml). The snippets below are from hashbrown-0.17.1.

Control bytes

rust
// hashbrown-0.17.1/src/control/tag.rs:7-49

impl Tag {
    /// Control tag value for an empty bucket.
    pub(crate) const EMPTY: Tag = Tag(0b1111_1111);

    /// Control tag value for a deleted bucket.
    pub(crate) const DELETED: Tag = Tag(0b1000_0000);

    /// Checks whether a control tag represents a full bucket (top bit is clear).
    #[inline]
    pub(crate) const fn is_full(self) -> bool {
        self.0 & 0x80 == 0
    }
    ...
    /// Creates a control tag representing a full bucket with the given hash.
    #[inline]
    pub(crate) const fn full(hash: u64) -> Tag {
        ...
        // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
        // value, some hash functions (such as FxHash) produce a usize result
        // instead, which means that the top 32 bits are 0 on 32-bit platforms.
        // So we use MIN_HASH_LEN constant to handle this.
        let top7 = hash >> (MIN_HASH_LEN * 8 - 7);
        Tag((top7 & 0x7f) as u8) // truncation
    }
}

The layout is a deliberate bit-budget:

the top bit distinguishes “special” (EMPTY or DELETED) from “full”;
the remaining 7 bits are h2, the top 7 bits of the hash.

That split is what makes the SIMD scan possible: “is this bucket free?” is “does the top bit of this byte have the high bit set?”, which movemask answers for 16 bytes at once.

The group scan

rust
// hashbrown-0.17.1/src/control/group/sse2.rs:46-116

/// Loads a group of tags starting at the given address.
#[inline]
pub(crate) unsafe fn load(ptr: *const Tag) -> Self {
    unsafe { Group(x86::_mm_loadu_si128(ptr.cast())) }
}
...
/// Returns a `BitMask` indicating all tags in the group which have
/// the given value.
#[inline]
pub(crate) fn match_tag(self, tag: Tag) -> BitMask {
    unsafe {
        let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(tag.0 as i8));
        BitMask(x86::_mm_movemask_epi8(cmp) as u16)
    }
}
...
/// Returns a `BitMask` indicating all tags in the group which are `EMPTY` or `DELETED`.
#[inline]
pub(crate) fn match_empty_or_deleted(&self) -> BitMask {
    unsafe {
        // A tag is EMPTY or DELETED iff the high bit is set
        BitMask(x86::_mm_movemask_epi8(self.0) as u16)
    }
}

#[inline]
pub(crate) fn match_full(&self) -> BitMask {
    BitMask(!self.match_empty_or_deleted().0)
}

Two movemask results: which of the 16 bytes equal my h2 tag, and which are free. One _mm_cmpeq_epi8 plus one _mm_movemask_epi8 does the work of 16 byte comparisons.

And the comment about AVX explains why the table stopped at SSE2:

rust
// hashbrown-0.17.1/src/control/group/mod.rs:8-23

// Use the SSE2 implementation if possible: it allows us to scan 16 buckets
// at once instead of 8. We don't bother with AVX since it would require
// runtime dispatch and wouldn't gain us much anyways: the probability of
// finding a match drops off drastically after the first few buckets.

Runtime dispatch for AVX would cost more than it saves, because the probability of finding a match drops off quickly.

The lookup loop

rust
// hashbrown-0.17.1/src/raw.rs:2007-2045

#[inline(always)]
unsafe fn find_inner(&self, hash: u64, eq: &mut dyn FnMut(usize) -> bool) -> Option<usize> {
    let tag_hash = Tag::full(hash);
    let mut probe_seq = self.probe_seq(hash);

    loop {
        let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };

        for bit in group.match_tag(tag_hash) {
            // This is the same as `(probe_seq.pos + bit) % self.num_buckets()` because the number
            // of buckets is a power of two, and `self.bucket_mask = self.num_buckets() - 1`.
            let index = (probe_seq.pos + bit) & self.bucket_mask;

            if likely(eq(index)) {
                return Some(index);
            }
        }

        if likely(group.match_empty().any_bit_set()) {
            return None;
        }

        probe_seq.move_next(self.bucket_mask);
    }
}

Three optimisations in twenty lines:

The h2 filter. The expensive key comparison (eq, which may call Eq::eq on a user type) only runs for buckets whose 7-bit tag matches — a 1/128 false-positive rate.
The empty short-circuit. Finding an EMPTY byte means the key is definitely not in the table, so the lookup ends there.
Mask instead of modulo. & self.bucket_mask replaces %, because the bucket count is a power of two.

Triangular probing

rust
// hashbrown-0.17.1/src/raw.rs:57-93

/// Primary hash function, used to select the initial bucket to probe from.
#[inline]
#[expect(clippy::cast_possible_truncation)]
fn h1(hash: u64) -> usize {
    // On 32-bit platforms we simply ignore the higher hash bits.
    hash as usize
}

/// Probe sequence based on triangular numbers, which is guaranteed (since our
/// table size is a power of two) to visit every group of elements exactly once.
///
/// A triangular probe has us jump by 1 more group every time. So first we
/// jump by 1 group (meaning we just continue our linear scan), then 2 groups
/// (skipping over 1 group), then 3 groups (skipping over 2 groups), and so on.
///
/// Proof that the probe will visit every group in the table:
/// <https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/>
#[derive(Clone)]
struct ProbeSeq {
    pos: usize,
    stride: usize,
}

impl ProbeSeq {
    #[inline]
    fn move_next(&mut self, bucket_mask: usize) {
        // We should have found an empty bucket by now and ended the probe.
        debug_assert!(
            self.stride <= bucket_mask,
            "Went past end of probe sequence"
        );

        self.stride += Group::WIDTH;
        self.pos += self.stride;
        self.pos &= bucket_mask;
    }
}

The stride grows by the group width (16 on SSE2) each step, so the probe visits every group exactly once — triangular numbers mod 2ⁿ are a permutation. Note this is not robin-hood hashing and not triple hashing; it is group-wise quadratic probing with a triangular stride.

The load factor

rust
// hashbrown-0.17.1/src/raw.rs:104-191

// Otherwise require 1/8 buckets to be empty (87.5% load)
//
// Be careful when modifying this, calculate_layout relies on the
// overflow check here.
let adjusted_cap = cap.checked_mul(8)? / 7;
...
// Returns the maximum effective capacity for the given bucket mask, taking
// the maximum load factor into account.
#[inline]
fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
    if bucket_mask < 8 {
        // For tables with 1/2/4/8 buckets, we always reserve one empty slot.
        // Keep in mind that the bucket mask is one less than the bucket count.
        bucket_mask
    } else {
        // For larger tables we reserve 12.5% of the slots as empty.
        ((bucket_mask + 1) / 8) * 7
    }
}

87.5% maximum load: the slack keeps probe chains short, and the empty-slot reservation is what makes the “found an empty ⇒ absent” shortcut valid.

The backwards data layout

rust
// hashbrown-0.17.1/src/raw.rs:660-687

/// Returns pointer to one past last `data` element in the table as viewed from
/// the start point of the allocation.
...
pub(crate) fn data_end(&self) -> NonNull<T> {
    //                        `self.table.ctrl.cast()` returns pointer that
    // points here (to the end of `T0`)
    //                          ∨
    // [Pad], T_n, ..., T1, T0, |CT0, CT1, ..., CT_n|, CTa_0, CTa_1, ..., CTa_m
    //                           \________  ________/
    //                                    \/
    //       `n = buckets - 1`, i.e. `RawTable::num_buckets() - 1`
    //
    // where: T0...T_n  - our stored data;
    //        CT0...CT_n - control bytes or metadata for `data`.
    //        CTa_0...CTa_m - additional control bytes, where `m = Group::WIDTH - 1` (so that the search
    //                        with loading `Group` bytes from the heap works properly, even if the result
    //                        of `h1(hash) & self.bucket_mask` is equal to `self.bucket_mask`). See also
    //                        `RawTableInner::set_ctrl` function.
    self.table.ctrl.cast()
}

Elements are stored backwards relative to the control bytes, so that data_end() is simply “the control pointer” — one allocation, and the control array sits at the end where the group loads can over-read safely (the extra CTa_* bytes are the padding that makes a group load at the last position legal).

The iterator then walks the control bytes forward and subtracts to walk the data backwards:

rust
// hashbrown-0.17.1/src/raw.rs:460-471

#[inline]
unsafe fn next_n(&self, offset: usize) -> Self {
    let ptr = if T::IS_ZERO_SIZED {
        // invalid pointer is good enough for ZST
        invalid_mut(self.ptr.as_ptr() as usize + offset)
    } else {
        unsafe { self.ptr.as_ptr().sub(offset) }
    };

This backwards layout is also why HashMap’s iteration order is arbitrary: it is the raw bucket order, deliberately unspecified.

The random seed, once per thread

rust
// library/std/src/hash/random.rs:41-78

pub fn new() -> RandomState {
    // Historically this function did not cache keys from the OS and instead
    // simply always called `rand::thread_rng().gen()` twice. In #31356 it
    // was discovered, however, that because we re-seed the thread-local RNG
    // from the OS periodically that this can cause excessive slowdown when
    // many hash maps are created on a thread. To solve this performance
    // trap we cache the first set of randomly generated keys per-thread.
    //
    // Later in #36481 it was discovered that exposing a deterministic
    // iteration order allows a form of DOS attack. To counter that we
    // increment one of the seeds on every RandomState creation, giving
    // every corresponding HashMap a different iteration order.
    thread_local!(static KEYS: Cell<(u64, u64)> = {
        Cell::new(hashmap_random_keys())
    });

    KEYS.with(|keys| {
        let (k0, k1) = keys.get();
        keys.set((k0.wrapping_add(1), k1));
        RandomState { k0, k1 }
    })
}

The OS entropy is fetched once per thread (a getrandom syscall is ~1µs; creating a HashMap must not cost a syscall), while the seed is bumped per map so two maps in the same thread still have different iteration orders.

Where it lives

hashbrown-0.17.1/src/control/tag.rs — the control byte encoding.
hashbrown-0.17.1/src/control/group/sse2.rs — the SIMD group scan.
hashbrown-0.17.1/src/raw.rs — probing, growth, the backwards layout.
library/std/src/hash/random.rs — RandomState.

Takeaway

The SwissTable’s core idea is that a hash table’s expensive part is key comparison, and you can avoid most of it by storing a cheap fingerprint (next to the data) and comparing those in bulk with SIMD. Sixteen candidates at a time, with a 1/128 false-positive rate, is a very good trade — and it is the reason Rust’s HashMap is competitive with C++’s unordered_map.