Standard Collections

HashMap<K, V>

HashMap<K, V, S = RandomState> (std::collections::HashMap) is an unordered key-value associative table backed by a SwissTable open-addressed flat hash table (hashbrown), providing $O(1)$ average-case lookup, insertion, and removal for keys implementing Eq + Hash.

Memory Layout and Default Hasher

Stack (`HashMap<K, V>`)
+------------------------+
| table_ptr              | ──> Heap Allocation (Contiguous Control Bytes + (K, V) Buckets)
| hasher (SipHash-1-3)   |     +-----------------------------------------------------+
+------------------------+     | Control Bytes (1 byte/slot: empty, deleted, or h2)  |
                               +-----------------------------------------------------+
                               | Inline (K, V) slots: [ (K0, V0), (K1, V1), ... ]    |
                               +-----------------------------------------------------+
  1. SIMD-accelerated probing: Each slot has a 1-byte control tag holding a 7-bit fingerprint of the key's hash (h2), allowing the CPU to probe 16 slots in parallel using a single SIMD instruction.
  2. HashDoS resistance: By default (RandomState), HashMap uses SipHash-1-3 seeded with per-instance random keys so attackers cannot craft colliding keys to degrade $O(1)$ lookups into $O(n)$.

Essential HashMap<K, V> Operations

Operation Method Return Type
Insert or overwrite map.insert(k, v) Option<V> (Some(old_v) if k already existed)
Lookup by key reference map.get(&q) / map.get_mut(&q) Option<&V> / Option<&mut V>
Check key presence map.contains_key(&q) bool
Remove key and return value map.remove(&q) Option<V>
Insert-or-modify in 1 lookup map.entry(k).or_insert(default) &mut V 
use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::from([("alice", 10), ("bob", 20)]);

    // 1. Overwrite existing key (returns old value `Some(10)`):
    let old = scores.insert("alice", 15);
    println!("Old score for alice: {old:?}");

    // 2. Borrowed key lookup (`&str`):
    println!("Bob's score: {:?}", scores.get("bob"));

    // 3. Single-lookup insert-or-increment via Entry API:
    for player in ["alice", "carol", "alice"] {
        *scores.entry(player).or_insert(0) += 5;
    }

    println!(
        "Final scores -> alice: {}, bob: {}, carol: {}",
        scores["alice"], scores["bob"], scores["carol"]
    );
}

Old score for alice: Some(10)
Bob's score: Some(20)
Final scores -> alice: 25, bob: 20, carol: 5

Note that iteration order over a HashMap<K, V> is nondeterministic across runs; if you need deterministic or sorted key order, use BTreeMap<K, V>.