A SwissTable hash map with direct SSE2 SIMD — works on stable Rust.

• Direct SSE2 intrinsics on x86_64, scalar fallback on other architectures
• KeyExtract trait — store only values when the key is embedded in the value
• Pluggable BuildHasher — default AutoHasher (FxHash for ints, buthash for byte slices), swap for any hasher
• Custom allocator support via allocator-api2 (stable polyfill for the Allocator API)
• Zero-cost empty table — new() does not allocate; first insert triggers allocation
• SIMD-accelerated iterator — scans 16 control bytes per group via bitmask
• Bulk memcpy clone for Copy types
• 87% load factor with linear group probing

use probemap::{KeyExtract, SwissTable, PairExtract};

// Simple (K, V) usage — like HashMap<K, V>
type MyMap = SwissTable<PairExtract<u64, String>>;
let mut map = MyMap::new();
map.insert((42, "hello".to_string()));
assert_eq!(map.get(&42).unwrap().1, "hello");

// key_from_value pattern — key embedded in value
struct User { id: u64, name: String }

struct UserById;
impl KeyExtract for UserById {
    type Key = u64;
    type Value = User;
    fn extract(value: &User) -> &u64 { &value.id }
}

let mut users = SwissTable::<UserById>::with_capacity(64);
users.insert(User { id: 1, name: "Alice".into() });
assert_eq!(users.get(&1).unwrap().name, "Alice");

use probemap::{SwissTable, PairExtract, FxBuildHasher};
use std::collections::hash_map::RandomState;

// Use FxHash only (no buthash)
let map = SwissTable::<PairExtract<u64, u64>, FxBuildHasher>::with_hasher(FxBuildHasher);

// Use SipHash (DoS-resistant)
let map = SwissTable::<PairExtract<String, u64>, RandomState>::with_hasher(RandomState::new());

Both probemap and hashbrown implement the same SwissTable algorithm and use the same SSE2 intrinsics. The performance difference comes from how the surrounding code is structured.

Monomorphized key comparison vs dyn FnMut. hashbrown's inner lookup (find_inner) takes the key comparator as &mut dyn FnMut(usize) -> bool — a trait object. This means every key comparison in the probe loop is an indirect call through a vtable pointer. The CPU cannot predict it, and LLVM cannot inline through it. This is a deliberate trade-off in hashbrown to reduce binary size from monomorphization. probemap calls E::extract(slot) == key directly — the compiler monomorphizes the comparison for each concrete type and inlines it into the probe loop, eliminating the indirect call overhead entirely. This is likely the single biggest contributor to the ~30% lookup speedup.

Forward slot layout. hashbrown stores slots in reverse order relative to control bytes (base.sub(index)). probemap uses forward order (slots.add(index)). Modern CPUs prefetch forward; reverse indexing works against the hardware prefetcher.

Flatter data path. hashbrown has four layers: HashMap -> HashTable -> RawTable -> RawTableInner. RawTableInner type-erases the value to *u8 and reconstructs Bucket<T> through pointer arithmetic. probemap is a single struct with inline methods — no type erasure, no Bucket wrapper, no intermediate layers.

Linear group probing. hashbrown uses triangular probing (stride += 16; pos += stride) — two additions and an extra field per step. probemap uses linear probing with mirrored control bytes: pos = (pos + 16) & mask — one add, one and. The mirror (first 16 control bytes duplicated at the end of the array) lets unaligned SIMD loads wrap around without sentinel bytes or branches.

insert_assume_unique during grow. When rehashing into a fresh table, there can be no duplicates. probemap skips the h2 match + key comparison loop and only scans for empty slots. hashbrown also optimizes this path but carries extra bookkeeping (growth_left updates) in the hot loop.

SIMD iterator with match_full(). The iterator loads 16 control bytes, extracts a bitmask of occupied slots with _mm_movemask_epi8, and pops bits with trailing_zeros. Empty groups are skipped in one branch. The struct is flat — (table, group_pos, bitmask).

Bulk memcpy clone. clone_table() checks needs_drop::<V>() at compile time. For Copy types the entire slots array is a single memcpy — no per-element loop, no rehash.

• Rust edition 2024 (1.85+)
• Stable toolchain (no nightly features required)
• SSE2 SIMD on x86_64, scalar fallback on other architectures

Apache License