Hash Tables

std::collections::HashMap<K, V, S> (and HashSet<T, S>) is an associative hash table that maps keys to values in $O(1)$ average time for lookup, insertion, and removal. Rust's standard HashMap is backed by hashbrown—a high-performance Rust port of Google's SwissTable open-addressed hash table that uses SIMD instructions to probe 16 control bytes in parallel!

SwissTable (`HashMap`) Flat Memory Layout:

  [ Control Bytes (1 Byte per Slot: `EMPTY`, `DELETED`, or 7-bit Hash `H2` Fingerprint) ]
  | h2_0 | h2_1 | EMPTY | h2_3 | ... (16 control bytes compared in 1 SIMD instruction!)
  +-------------------------------------------------------------------------------------+
  | (K0, V0) | (K1, V1) | uninit | (K3, V3) | ... (Key-Value pairs stored contiguously!)

Required Key Traits: Eq + Hash Consistency Invariant

Any key type K stored in a HashMap or HashSet must implement Eq and Hash (almost always via #[derive(PartialEq, Eq, Hash)]), and must obey the fundamental hash-table law:

$$k_1 == k_2 \implies \text{hash}(k_1) == \text{hash}(k_2)$$

Furthermore, a key's hash value must never change while the key is inside the map (which is why types with interior mutability like RefCell<T> or AtomicU64 do not implement Hash).

Borrowed Key Lookups Without Allocation (Borrow Trait)

Notice the signature of HashMap::get:

pub fn get<Q>(&self, k: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Because String implements Borrow<str> (and Vec<T> implements Borrow<[T]>), you can look up or remove a key in a HashMap<String, V> by passing a borrowed &str literal (map.get("alice")) with zero heap allocation!

Single-Lookup Upserts with the Entry API

Calling if map.contains_key(&k) { ... } else { map.insert(k, v); } hashes the key and probes the hash table twice. Using map.entry(key) hashes and probes the table exactly once, returning an Entry enum (Occupied or Vacant) that modifies the slot in place:

use std::collections::HashMap;

#[derive(Debug, Default, PartialEq, Eq)]
pub struct EndpointStats {
    pub requests: u64,
    pub bytes_sent: u64,
}

pub fn record_traffic(
    table: &mut HashMap<String, EndpointStats>,
    route: &str,
    bytes: u64,
) {
    // If the route is already in the table, looking up via `.get_mut(route)` avoids
    // allocating a `String` for `entry(route.to_string())` on hits!
    if let Some(stats) = table.get_mut(route) {
        stats.requests += 1;
        stats.bytes_sent += bytes;
    } else {
        table.insert(
            route.to_string(),
            EndpointStats {
                requests: 1,
                bytes_sent: bytes,
            },
        );
    }
}

fn main() {
    let mut metrics = HashMap::with_capacity(8);
    record_traffic(&mut metrics, "/v1/orders", 512);
    record_traffic(&mut metrics, "/v1/orders", 1024);

    // Classic Entry API for word frequency counting:
    let mut word_counts: HashMap<&str, u32> = HashMap::new();
    for word in ["rust", "fast", "rust", "safe", "rust"] {
        *word_counts.entry(word).or_insert(0) += 1;
    }

    assert_eq!(
        metrics.get("/v1/orders"), // Look up with `&str` without allocating a `String`!
        Some(&EndpointStats {
            requests: 2,
            bytes_sent: 1536,
        })
    );
    println!("Order route stats: {:?}", metrics.get("/v1/orders").unwrap());
    println!("Count of 'rust':   {}", word_counts["rust"]);
}

Order route stats: EndpointStats { requests: 2, bytes_sent: 1536 }
Count of 'rust':   3

Choosing a Hasher (SipHash vs FxHash / AHash)

By default, std::collections::HashMap uses SipHash 1-3 (RandomState), a cryptographically strong hash function seeded with random per-process keys to defend network servers against HashDoS collision attacks.

Hasher	HashDoS Resistant?	Speed on Small Integer / Short Keys	When to Use
RandomState (SipHash 1-3) (Std Default)	Yes	Baseline	Untrusted user/network keys (HTTP headers, JSON keys, query params).
rustc-hash (FxHashMap) / ahash	No (FxHash) / Partial (AHash)	2x–5x faster on u32/u64/pointer keys	Compilers, game engines, and internal algorithms where keys are trusted!