Hash Maps and Hash Sets

Hash Collisions

A hash collision occurs when two distinct keys (k1 != k2) map to the same 64-bit hash value (hash(k1) == hash(k2)) or map to the same bucket index modulo the table size (h1(k1) % num_buckets == h1(k2) % num_buckets).

Two Kinds of Collisions in a Hash Table

  1. Bucket-index collision (common): Two keys have different 64-bit hashes, but h1 % num_buckets lands in the same 16-slot SIMD probe group.
  2. Full 64-bit hash collision (rare with a good hasher): Two distinct keys produce the exact same u64 digest (h1 and h2 both match).

How HashMap Resolves Collisions (Open Addressing + Eq)

When HashMap inserts or searches for a key:

Lookup `key`:
  1. Compute 64-bit hash -> split into `h1` (57-bit group offset) and `h2` (7-bit tag)
  2. Probe 16-slot group at `h1 & bucket_mask` using SIMD compare against `h2`:
       ├── For each slot where `ctrl_byte == h2`:
       │     Compare `stored_key == key` via `Eq::eq`:
       │       ├── `true`  ──> Exact key match found! Return `&stored_val`
       │       └── `false` ──> Hash/h2 collision! Continue checking remaining matches
       ├── If any slot in the 16-byte group is `EMPTY`:
       │     Key is definitely not in the table ──> Return `None`
       └── If all 16 slots are `FULL` or `DELETED`:
             Advance by triangular step (`stride += 16`) to next group and repeat

Because HashMap always verifies candidate matches with Eq::eq (stored_key == query_key), hash collisions never cause incorrect lookups or silent overwrites—even if every single key in the table produces the exact same hash!

Demonstrating Correctness Under a Degenerate Constant Hasher

Even if a broken Hash implementation returns the same constant for every key, HashMap remains 100% functionally correct by falling back to PartialEq::eq comparisons along the probe sequence (degrading performance from $O(1)$ to $O(n)$):

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug, PartialEq, Eq)]
struct CollidingKey(u32);

impl Hash for CollidingKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Deliberately feeds the exact same constant for every key!
        0_u8.hash(state);
    }
}

fn main() {
    let mut map = HashMap::new();
    map.insert(CollidingKey(1), "one");
    map.insert(CollidingKey(2), "two");
    map.insert(CollidingKey(3), "three");

    // All three keys have identical hashes, yet `Eq` resolves each one accurately:
    println!("Key 1: {:?}", map.get(&CollidingKey(1)));
    println!("Key 2: {:?}", map.get(&CollidingKey(2)));
    println!("Key 3: {:?}", map.get(&CollidingKey(3)));
    println!("Len:   {}", map.len());
}

Key 1: Some(&"one")
Key 2: Some(&"two")
Key 3: Some(&"three")
Len:   3

Avoiding Accidental Collisions in Custom Hash Implementations

When writing a manual impl Hash:

  • Never combine fields with XOR ((self.x ^ self.y).hash(state)): XOR is symmetric and self-canceling, so (a, a) always hashes to 0 and (a, b) collides with (b, a) for every pair! Instead, call self.x.hash(state); self.y.hash(state); sequentially and let the Hasher mix them.
  • Include all fields compared by PartialEq::eq: Omitting distinguishing fields causes distinct keys to collide in the same bucket and forces linear Eq scans.