Hash Maps and Hash Sets

Average-Case and Worst-Case Complexity

HashMap<K, V> and HashSet<T> provide $O(1)$ expected average-case time for lookup, insertion, and removal, while their worst-case time is $O(n)$ when either a table resize (rehash) occurs or all keys collide into the same probe chain.

Complete Complexity Summary for HashMap<K, V> and HashSet<T>

($n$ = number of elements currently in the map/set; $c$ = allocated capacity.)

Operation Method Average Case Worst Case Cause of Worst Case
Lookup get(&k), contains_key(&k), contains(&x) $O(1)$ $O(n)$ All $n$ keys collide into a single probe chain
Insert insert(k, v), entry(k).or_insert(v) Amortized $O(1)$ $O(n)$ Table reaches $7/8$ load factor and rehashes all $n$ elements (or $n$-way collision)
Remove remove(&k), remove_entry(&k), take(&x) $O(1)$ $O(n)$ Probing past an $O(n)$ collision cluster (never shrinks table)
Clear clear() $O(n)$ (or $O(c)$ control reset) $O(c + n)$ Drops $n$ elements and resets control bytes to EMPTY
Iteration iter(), keys(), values(), retain() $O(c)$ $O(c)$ Scans control bytes across the allocated capacity $c$
Reserve reserve(additional) $O(n)$ (when resizing) $O(n)$ Allocates new table and re-inserts all $n$ elements

Why Iteration Is $O(\text{capacity})$ Rather Than $O(\text{len})$

Because open-addressed hash tables scatter elements across the allocated bucket array, iterating over a HashMap scans the control-byte array (16 bytes at a time via SIMD) to find occupied slots.

  • If a HashMap has len = 10 and capacity = 14, iteration is near-instantaneous.
  • However, if a HashMap grew to $1,000,000$ elements (capacity $\approx 1.8\text{M}$) and you removed $999,995$ elements via .remove(), its len() is 5 but its capacity() is still $1.8\text{M}$—making .iter() or .retain() scan $1.8\text{M}$ control bytes! Call map.shrink_to_fit() after massive removals if the map will be iterated repeatedly:
use std::collections::HashMap;

fn main() {
    let mut map: HashMap<u32, u32> = (0..1_000).map(|i| (i, i)).collect();
    println!("Peak:        len={:>4}, cap={:>4}", map.len(), map.capacity());

    // Remove 995 elements:
    map.retain(|&k, _| k < 5);
    println!("After prune: len={:>4}, cap={:>4} (still large!)", map.len(), map.capacity());

    // Shrink capacity so future `.iter()` calls scan only a tiny table:
    map.shrink_to_fit();
    println!("After shrink: len={:>4}, cap={:>4}", map.len(), map.capacity());
}

Peak:        len=1000, cap=1792
After prune: len=   5, cap=1792 (still large!)
After shrink: len=   5, cap=   7

Guaranteed Worst-Case Bounds: When to Prefer BTreeMap

In hard real-time systems or adversarial environments where even a single $O(n)$ rehash pause or custom-hasher collision spike is unacceptable, BTreeMap<K, V> and BTreeSet<T> guarantee a strict $O(\log n)$ worst-case bound on every single get, insert, and remove operation without ever performing a full-table rehash.