HashMap and BTreeMap

Two map types ship in the standard library, and the choice is decided by what your readers do with the data:

use std::collections::{HashMap, BTreeMap};

let mut scores: HashMap<&str, u32> = HashMap::new();
scores.insert("ada", 90);

let mut ranks: BTreeMap<&str, u32> = BTreeMap::new();
ranks.insert("ada", 90);

HashMap hashes keys into buckets: lookup, insert, and remove are O(1) average, degrading to O(n) only under adversarial collisions. The default hasher is randomized per process (RandomState), so two runs of the same program iterate in different orders — that randomization is deliberate, it is the defense against hash-flooding denial-of-service, and it is also why you must never depend on HashMap iteration order or write a test that asserts one. BTreeMap keeps keys in a balanced binary search tree: O(log n) for every operation, but iteration comes out sorted and range queries are first-class:

let mut prices: BTreeMap<String, f64> = BTreeMap::new();
// every operation O(log n)
for (sku, price) in prices.range("A000"..="B999") {   // ordered scan of a key window
    println!("{sku}: {price}");
}

HashMap has no range at all — a windowed query means iterating everything and filtering, O(n). The decision table:

Type bounds differ too, and they bite during refactors: a HashMap key needs Eq + Hash, a BTreeMap key needs Ord (which implies Eq). That is why f64 can never be a map key in either — f64 implements neither Hash nor Ord (NaN breaks reflexivity: NaN != NaN), so you wrap it in a newtype and hash the bits, or key by an integer. A newtype around an ID with #[derive(Hash, Eq, PartialEq)] is the standard fix for a domain key.

The Hash + Eq contract deserves its own sentence because violating it is the classic map bug: if two keys are equal, they must produce the same hash. Derive both together (#[derive(PartialEq, Eq, Hash)]) and never hand-write Eq in a way that disagrees with Hash. Break it and entries become unreachable — inserted under one hash, looked up under another, silently None, no error anywhere.

When performance claims matter: HashMap with SipHash (the default) trades speed for DoS resistance; a HashMap<K, V, BuildHasherDefault<...>> or the fxhash/ahash crates speed up integer-heavy workloads when all keys are trusted. BTreeMap nodes allocate per entry and compare keys log n times per operation — for small maps (a few dozen entries) the difference is noise, which is exactly when a BTreeMap's deterministic order is worth taking. In interviews, "when would you pick BTreeMap over HashMap?" is answered with order and ranges, not with speed.

Two API details that round out the choice: BTreeMap exposes range, range_mut, first_key_value, last_key_value, and pop_first/pop_last (ordered extraction — a min-heap workload without a heap), while HashMap offers none of those but adds try_fold-style iteration and cheap retain. Both provide Default, Extend<(K, V)>, and FromIterator, so collect() builds either from a tuple iterator identically — swapping containers rarely changes the pipeline, only the capabilities.

The counting bug every language has:

let mut counts: HashMap<String, u32> = HashMap::new();
for word in text.split_whitespace() {
    if let Some(n) = counts.get_mut(word) {   // lookup #1
        *n += 1;
    } else {
        counts.insert(word.to_string(), 1);   // lookup #2 (hash again, find slot again)
    }
}

Two hash computations and up to two probes per word, plus an allocation of the key in the miss branch that the entry API lets you defer. The same loop with entry:

for word in text.split_whitespace() {
    *counts.entry(word.to_string()).or_insert(0) += 1;
}

One lookup, one code path. entry takes the key by value and returns an Entry enum that has already located the slot:

or_insert_with matters the same way unwrap_or_else does — the closure defers an allocation or a computation to the branch that needs it:

let start = cache
    .entry(key.clone())
    .or_insert_with(|| expensive_load(key));   // not called on a hit

For control flow beyond "insert if missing," match on the entry:

match logs.entry(request_id) {
    Entry::Occupied(mut e) => { e.get_mut().push(line); }
    Entry::Vacant(e) => { e.insert(vec![line]); }
}

That is and_modify + or_insert spelled out — useful when the two arms need real statements rather than expressions.

The other half of the double-lookup story is insert, which returns the previous value: if let Some(old) = map.insert(k, v) { ... } tells you an overwrite happened, so detecting collisions (a key you assumed unique) costs nothing extra. Pair it with contains_key only when you need to test without writing — and when you truly need "get, and if absent, compute and store," entry still wins because it does the locate once.

Two details that make entry feel native rather than exotic. First, the API is identical on BTreeMap — same entry, or_insert*, and_modify methods, only the path differs (std::collections::btree_map::Entry) — so switching containers never rewrites your update logic. Second, entry hands back &mut V directly, so a simple policy stays one expression, and anything with real statements in both branches grows into a match on the entry instead of a nested conditional:

*hits.entry(path.to_string()).or_insert(0) += 1;      // one lookup, one expression

// both branches carry statements:
match counters.entry(user) {
    Entry::Occupied(mut e) => { *e.get_mut() = (*e.get_mut()).max(1); }
    Entry::Vacant(e) => { e.insert(1); }
}

Grouping is the canonical real-world use — one pass over records, no intermediate Vecs:

let mut by_tenant: HashMap<String, Vec<Order>> = HashMap::new();
for o in orders {
    by_tenant.entry(o.tenant.clone()).or_default().push(o);   // or_default(): Vec::new() on miss
}

or_default() on a HashMap<String, Vec<_>> inserts an empty Vec only when the tenant is new, and push then hits an existing (or fresh) bucket. The clone of o.tenant is the one allocation the entry API cannot avoid — because the key must be owned by the map — and it is exactly the kind of cost you accept once, per grouping, instead of per comparison.

Micro-note worth knowing: entry consumes the key, so counts.entry(word.to_string()) allocates the String even when the key is already present — for hot paths over borrowed data, pre-check with get_key_value (it returns (&K, &V) so you can clone the existing key instead of allocating a new one) or keep keys as &str borrowed from an arena. The map-side cost is one probe either way; the allocation is what you can avoid.

A HashMap<String, u32> can be queried with a plain &str without building a String — and understanding why prevents the "why doesn't this compile" week:

let mut ages: HashMap<String, u32> = HashMap::new();
ages.insert("ada".to_string(), 36);

let n = ages.get("ada");                     // works: get<Q: ?Sized>(&self, k: &Q)
                                             // where String: Borrow<Q>, Q: Hash + Eq

The Borrow bound is the contract: String: Borrow<str> (and Borrow<String>), so get, contains_key, remove, and entry accept &str for a String-keyed map — hashing the borrowed form must agree with hashing the owned form, which is exactly the same "consistent hash" requirement from the previous chapter. Consequences: lookups over &str never allocate, and a HashMap<String, _> you only read can be built from borrowed slices (HashMap<&str, _> where the source strings outlive it — the lifetime rules from the reference topics apply unchanged).

Removal has three shapes, each with a different return:

let v: Option<u32> = ages.remove("ada");           // just the value
let kv: Option<(String, u32)> = ages.remove_entry("ada");  // value AND the owned key back
ages.retain(|_k, v| *v >= 18);                     // bulk filter, one pass
let leftover: HashMap<String, u32> = std::mem::take(&mut ages);  // move the whole map out

remove_entry is the one people miss — when the key is expensive to reconstruct (a parsed identifier, a joined path), getting it back out with the value avoids re-deriving it. retain mirrors Vec::retain: one pass, no intermediate allocation. And std::mem::take (or mem::replace) moves the map out while leaving an empty one in place, which is how you hand a buffer of state to a worker without cloning.

Iteration deserves a warning regardless of which map you chose:

for (k, v) in &map { }        // borrows: map still usable
for (k, v) in map { }         // consumes: pairs are moved out (keys and values)
map.iter_mut()                // &mut V, mutate values in place (keys are immutable by design)

Mutating keys is impossible through iteration because that would break the map's own invariants — the key's position depends on its hash or its sort order. To change a key, remove the old entry and insert under the new one; this is a design statement, not a limitation: &mut K would let an entry become unfindable. Inserting while iterating has the same borrow-conflict shape you met with Vec — collect your additions first, or use extend after the loop.

Two value-update shapes, and when each is right: get_mut when the key is known to exist (a loop over a pre-populated config) — it is a plain lookup with a mutable borrow; entry when existence is genuinely unknown — it is the lookup-plus-decision in one call. Mixing them up costs either a redundant contains_key (with get_mut) or a redundant probe (with entry), and only one of those is visible in a profile.

Borrowed keys are the other everyday design choice, and lifetimes make the trade explicit:

let words: Vec<&str> = text.split_whitespace().collect();
let mut counts: HashMap<&str, usize> = HashMap::new();
for w in words { *counts.entry(w).or_insert(0) += 1; }
// `counts` borrows from `text` — it cannot outlive the buffer it indexes into

Keying by &str means zero allocations for keys, and the compiler enforces the data's lifetime: the moment text would be dropped, counts becomes a borrow error. That is usually what you want for short-lived aggregation; when the map must outlive its source — cached parsed names, a struct's field — clone the keys into Strings at insert time and pay one allocation per distinct key, once.

Finally, capacity: HashMap::with_capacity(n) reserves buckets up front (load factor ~0.75 means it reserves a bit more than n), and reserve(additional) avoids rehashing inside a bulk-load loop. A HashMap that grows during a 100k-element import rehashes log-wise several times; one with_capacity call turns that into a single allocation. This is the same reallocation discipline as Vec and Dynamic Arrays, one level up.