Hash Maps and Hash Sets

Hashing Fundamentals

Hashing transforms a key of arbitrary size or structure (such as a String, struct, or tuple) into a fixed-size 64-bit integer (u64) so that a hash table can map the key directly to a storage bucket in $O(1)$ average time.

The Three Components of Hashing in std::hash

Rust separates hashing into three distinct traits in std::hash:

Trait Role Implemented By
Hash Feeds the structural bytes of a key into a Hasher (key.hash(&mut hasher)) Domain key types (String, i32, #[derive(Hash)] structs)
Hasher Stateful streaming algorithm that mixes fed bytes and produces a u64 digest (hasher.finish()) Hashing algorithms (DefaultHasher / SipHash-1-3, FxHasher, AHasher)
BuildHasher Factory stored inside HashMap<K, V, S> that creates fresh Hasher instances (build_hasher()) RandomState (seeded per map), BuildHasherDefault<H> 
Key (e.g., "user_42")
  │
  ▼  1. map.hasher().build_hasher() creates a new Hasher state
+-----------------------------------+
| H: Hasher (SipHash-1-3 state)     |
+-----------------------------------+
  │  2. key.hash(&mut hasher) feeds bytes + length prefix
  ▼
  │  3. hasher.finish() returns a 64-bit hash digest
  ▼
u64 Digest (e.g., 0x8a3f_c901_44b2_19d7)
  ├── Upper 57 bits (h1) ──> Selects initial bucket group (`h1 % num_buckets`)
  └── Lower  7 bits (h2) ──> Stored in 1-byte SIMD control tag for fast filtering

Computing a 64-Bit Hash Manually

You can observe the exact u64 digest produced for any T: Hash by feeding it into std::hash::DefaultHasher:

use std::hash::{DefaultHasher, Hash, Hasher};

fn compute_hash<T: Hash>(value: &T) -> u64 {
    let mut hasher = DefaultHasher::new();
    value.hash(&mut hasher);
    hasher.finish()
}

fn main() {
    let h1 = compute_hash(&"rust-2024");
    let h2 = compute_hash(&"rust-2024");
    let h3 = compute_hash(&"rust-2021");

    println!("Hash of 'rust-2024' (1): 0x{h1:016x}");
    println!("Hash of 'rust-2024' (2): 0x{h2:016x} (deterministic per hasher seed)");
    println!("Hash of 'rust-2021':     0x{h3:016x} (avalanche effect)");
}

Hash of 'rust-2024' (1): 0x5c36c0f489993524
Hash of 'rust-2024' (2): 0x5c36c0f489993524 (deterministic per hasher seed)
Hash of 'rust-2021':     0x2015a78529e3b98e (avalanche effect)

Fundamental Properties of a Good Hash Function

  1. Determinism within a table: Feeding two equal keys (k1 == k2) into identically seeded Hasher instances must always produce the exact same u64 output.
  2. Uniform distribution (Avalanche effect): Flipping a single bit in the input key changes roughly 50% of the output bits, spreading similar keys ("id_1", "id_2", "id_3") evenly across all buckets.
  3. Prefix-collision resistance: Variable-length types like str and [T] write a terminator byte (0xFF in str::hash) or their length (slice.len()) into the Hasher so that ("ab", "c") and ("a", "bc") do not produce identical byte streams.