HashMap Structure

Rust's std::collections::HashMap<K, V, S> is backed by hashbrown, a Rust port of Google's SwissTable flat, open-addressed hash table that uses SIMD instructions to probe 16 buckets in parallel.

SwissTable Memory Layout

Unlike chained hash tables that allocate a linked list node on the heap for every inserted key-value pair, HashMap allocates a single contiguous heap buffer divided into two arrays:

1. Control bytes (u8 metadata array): 1 byte per bucket slot tracking whether the slot is EMPTY (0b1111_1111), DELETED (0b1000_0000 tombstone), or FULL (0b0xxx_xxxx, storing the 7-bit h2 fingerprint of the key's hash).
2. Data buckets ((K, V) array): Contiguous inline storage for the (K, V) pairs themselves,with zero pointer indirection.

Stack (`HashMap<K, V>`, 48 bytes)
+----------------------------------+
| bucket_mask: usize (cap_raw - 1) |
| ctrl:        NonNull<u8>        -+──┐
| growth_left: usize               |  │
| items:       usize (len)         |  │
| build_hasher: RandomState (16 B) |  │
+----------------------------------+  │
                                      ▼
Single Contiguous Heap Allocation (Power-of-Two Slots, e.g., 16 Slots):
+---------------------------------------------------------------------+
| Data Buckets:  ... | (K2, V2) | (K1, V1) | (K0, V0) |               |
+---------------------------------------------------------------------+
| Control Bytes: [ h2_0 | h2_1 | EMPTY | h2_2 | DELETED | EMPTY ... ] |
+---------------------------------------------------------------------+
                  ▲ (ctrl pointer points here; 16 control bytes = 1 SIMD register)

How Lookup Works in SwissTable

When you call map.get(&key):

1. key is hashed to a 64-bit integer h, which is split into a 57-bit primary position h1 = h >> 7 and a 7-bit fingerprint h2 = (h & 0x7F) as u8.
2. The starting group index is h1 & bucket_mask. The CPU loads 16 consecutive control bytes starting at that position into a 128-bit SIMD register (SSE2 on x86_64, NEON on Apple Silicon / ARM64).
3. A single SIMD equality instruction compares all 16 control bytes against h2 simultaneously:
   • For any slot whose control byte matches h2, the table checks bucket.key == key (only a ~1 in 128 chance of a false positive!).
   • If the 16-byte control group contains at least one EMPTY byte and no match was found, the search terminates immediately in 1 cache-line read.
   • Otherwise, quadratic triangular probing advances to the next 16-slot group.

Observing Stack Size and Power-of-Two Capacity

Because SwissTable maintains a maximum 87.5% (7/8) load factor inside a power-of-two raw bucket array, a raw table of 8 slots has a usable .capacity() of 7 elements (8 * 7 / 8 = 7), and a raw table of 16 slots has a usable .capacity() of 14 elements:

use std::collections::HashMap;
use std::mem::size_of;

fn main() {
    println!(
        "Stack size of HashMap<String, i32>: {} bytes",
        size_of::<HashMap<String, i32>>()
    );

    let mut map = HashMap::new();
    println!("Empty capacity:          {}", map.capacity());

    map.insert("a", 1);
    println!("After 1st insert (cap):  {} (7/8 of 4 or 8 raw slots)", map.capacity());

    map.reserve(10);
    println!("After reserve(10) (cap): {} (7/8 of 16 raw slots)", map.capacity());
}

Stack size of HashMap<String, i32>: 48 bytes
Empty capacity:          0
After 1st insert (cap):  3 (7/8 of 4 or 8 raw slots)
After reserve(10) (cap): 14 (7/8 of 16 raw slots)