HashMap
HashMap<K, V>
Section titled “HashMap<K, V>”HashMap<K, V> maps keys of type K to values of type V. It uses a hash function internally to achieve O(1) average-case insertion and lookup.
use std::collections::HashMap;
let mut scores: HashMap<String, u32> = HashMap::new();Keys must implement Eq and Hash. Common key types — String, &str, integers — already do.
Inserting and Reading Values
Section titled “Inserting and Reading Values”use std::collections::HashMap;
let mut scores: HashMap<String, u32> = HashMap::new();scores.insert(String::from("Alice"), 100);scores.insert(String::from("Bob"), 85);
// get returns Option<&V>if let Some(score) = scores.get("Alice") { println!("Alice: {}", score);}
// index syntax — panics if key is missinglet bob_score = scores["Bob"];Prefer .get(key) in production code so you handle the missing-key case gracefully.
Looking Up a String Key with &str — Borrow at Work
Section titled “Looking Up a String Key with &str — Borrow at Work”scores.get("Alice") above passes a &str literal to look up a HashMap<String, u32> — no String allocation needed for the lookup. This works because HashMap::get is generic over any type the stored key can borrow as, via the standard library’s Borrow trait: String implements Borrow<str>, so any method that only needs to compare/hash the key (get, contains_key, remove) accepts &str directly instead of forcing you to build an owned String just to ask a question.
use std::collections::HashMap;
fn main() { let mut scores: HashMap<String, u32> = HashMap::new(); scores.insert(String::from("alice"), 100); let key: &str = "alice"; // borrowed, no allocation println!("lookup by &str: {:?}", scores.get(key));}What the Compiler Says: Not Every Type Can Be a Key
Section titled “What the Compiler Says: Not Every Type Can Be a Key”HashMap keys must implement Eq (a total, reflexive equality) and Hash (equal values must hash identically). f64 implements neither on purpose — NaN != NaN breaks Eq’s reflexivity, and rounding makes hash-stability unreliable — so the compiler rejects it at the method call, not at the HashMap declaration:
// @expect-error E0599use std::collections::HashMap;
fn main() { let mut m: HashMap<f64, &str> = HashMap::new(); m.insert(1.5, "one and a half"); println!("{:?}", m.get(&1.5));}error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied --> src/main.rs:5:7 |5 | m.insert(1.5, "one and a half"); | ^^^^^^ | = note: the following trait bounds were not satisfied: `f64: Eq` `f64: Hash`
error[E0599]: the method `get` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied --> src/main.rs:6:24 |6 | println!("{:?}", m.get(&1.5)); | ^^^ method cannot be called on `HashMap<f64, &str>` due to unsatisfied trait bounds | = note: the following trait bounds were not satisfied: `f64: Eq` `f64: Hash`
error: aborting due to 2 previous errors
For more information about this error, try `rustc --explain E0599`.HashMap<f64, V> compiles fine as a type — the error only appears once you call a method (insert, get) that actually needs Eq/Hash. If you need to key by a floating-point-like value, key by a type that has real equality instead: round to an integer representation (cents instead of dollars, for example), or wrap it in a newtype with a custom Eq/Hash that documents how you define “equal” for your use case.
The Entry API
Section titled “The Entry API”The entry API provides a clean way to insert a value only if the key is absent, avoiding a double-lookup:
use std::collections::HashMap;
let mut scores: HashMap<String, u32> = HashMap::new();scores.insert(String::from("Alice"), 100);scores.insert(String::from("Bob"), 85);
// Insert 70 for "Dave" if "Dave" is not yet presentscores.entry(String::from("Dave")).or_insert(70);
// Increment a counter — insert 0 first if absent, then add 1let count = scores.entry(String::from("Eve")).or_insert(0);*count += 1;or_insert returns a &mut V pointing at the value, so you can update it in place.
or_insert_with — a Lazy Default
Section titled “or_insert_with — a Lazy Default”or_insert(v) always evaluates v, even when the key is already present and v gets thrown away. or_insert_with(f) takes a closure and only calls it when the key is actually absent — essential when the default is expensive to build (an allocation, a fresh Vec, a computed value):
use std::collections::HashMap;
fn main() { // or_insert_with(f): f only runs if the key is absent (lazy default) let mut groups: HashMap<String, Vec<i32>> = HashMap::new(); for n in [1, 2, 3, 4, 5, 6] { let key = if n % 2 == 0 { "even" } else { "odd" }; groups .entry(key.to_string()) .or_insert_with(Vec::new) .push(n); } let mut keys: Vec<&String> = groups.keys().collect(); keys.sort(); for k in keys { println!("{}: {:?}", k, groups[k]); }}even: [2, 4, 6]odd: [1, 3, 5]Grouping like this — entry(key).or_insert_with(Vec::new).push(item) — is one of the most common real uses of the entry API: build up a HashMap<K, Vec<V>> in a single pass with no separate “does this key exist yet” branch.
Iteration Order Is Random — Proven, Not Just Stated
Section titled “Iteration Order Is Random — Proven, Not Just Stated”HashMap does not guarantee any iteration order, and it is not merely “insertion order that looks scrambled” — Rust seeds its default hasher (SipHash) randomly per process, specifically to make hash-flooding denial-of-service attacks impractical. The same program, compiled once, prints a different order almost every run:
use std::collections::HashMap;
fn main() { let mut m: HashMap<&str, i32> = HashMap::new(); m.insert("alpha", 1); m.insert("bravo", 2); m.insert("charlie", 3); m.insert("delta", 4); for (k, v) in &m { print!("{}:{} ", k, v); } println!();}Two real runs of the exact same compiled binary — not two different programs:
$ ./a.binalpha:1 delta:4 bravo:2 charlie:3
$ ./a.bincharlie:3 delta:4 alpha:1 bravo:2When output order matters (tests, learning playgrounds, logging), sort the keys first:
use std::collections::HashMap;
let mut scores: HashMap<String, u32> = HashMap::new();scores.insert(String::from("Alice"), 100);scores.insert(String::from("Bob"), 85);
let mut keys: Vec<&String> = scores.keys().collect();keys.sort();for k in keys { println!("{}: {}", k, scores[k]);}BTreeMap<K, V> — When You Want Order for Free
Section titled “BTreeMap<K, V> — When You Want Order for Free”If you need sorted iteration every time, reach for BTreeMap<K, V> instead of sorting a HashMap’s keys yourself. It stores entries in a balanced tree ordered by key (K: Ord required), so iteration is always sorted with no extra step — at the cost of O(log n) operations instead of HashMap’s O(1) average:
use std::collections::BTreeMap;
fn main() { let mut m: BTreeMap<&str, i32> = BTreeMap::new(); m.insert("delta", 4); m.insert("alpha", 1); m.insert("charlie", 3); m.insert("bravo", 2); // BTreeMap iterates in sorted key order, always, no sorting needed for (k, v) in &m { print!("{}:{} ", k, v); } println!();}alpha:1 bravo:2 charlie:3 delta:4Every run of this program prints the same order — sorted by key — because BTreeMap does not use hashing at all.
Removing Entries
Section titled “Removing Entries”use std::collections::HashMap;
let mut scores: HashMap<String, u32> = HashMap::new();scores.insert(String::from("Alice"), 100);scores.insert(String::from("Bob"), 85);
scores.remove("Bob");println!("Bob present: {}", scores.contains_key("Bob"));flowchart TD
A["entry(key)"] --> B{Key already present?}
B -->|Yes| C["or_insert / or_insert_with: return &mut V to the existing value, default not evaluated"]
B -->|No| D["or_insert_with(f): call f() now, insert result"]
D --> E["or_insert(v): v was already evaluated eagerly, insert it"]
C --> F[Caller mutates *value in place]
E --> F use std::collections::HashMap;
fn main() { let mut scores: HashMap<String, u32> = HashMap::new(); scores.insert(String::from("Alice"), 100); scores.insert(String::from("Bob"), 85); scores.insert(String::from("Carol"), 92);
// entry API: insert if absent scores.entry(String::from("Dave")).or_insert(70); // Alice already exists — or_insert does nothing scores.entry(String::from("Alice")).or_insert(0);
// get returns Option<&V> if let Some(score) = scores.get("Alice") { println!("Alice scored {}", score); }
// deterministic iteration: sort keys let mut keys: Vec<&String> = scores.keys().collect(); keys.sort(); for k in keys { println!("{}: {}", k, scores[k]); }
// remove scores.remove("Bob"); println!("Bob present: {}", scores.contains_key("Bob"));}Compiling…
Mental Model
Section titled “Mental Model”A HashMap is a bucket array plus a hash function: insert/get/remove all start by hashing the key to pick a bucket, so their cost does not grow with the number of entries (on average) — but the bucket layout has nothing to do with insertion order, so “iterate the buckets in order” produces whatever order the hash function happened to scatter keys into, re-randomized every process start. BTreeMap is a completely different data structure with a completely different guarantee: it is a balanced tree, so “iterate in order” is “iterate the tree in-order traversal” — sortedness is structural, not incidental.
Trade-offs
Section titled “Trade-offs”HashMap wins on raw lookup speed (O(1) average) and has no requirement beyond Eq + Hash on the key. BTreeMap gives you sorted iteration and range queries (.range(a..b)) for free, at O(log n) per operation and an additional Ord requirement. entry(k).or_insert(v) is simpler to write but always evaluates v; entry(k).or_insert_with(f) costs one extra closure call but never builds a default value you are going to throw away.
Common Misconceptions
Section titled “Common Misconceptions”- “HashMap iteration order is insertion order, just not obviously so.” It is not insertion order at all — it is derived from a hash seed that is randomized fresh every process start, specifically as a defense against hash-flooding attacks. The same source code, recompiled or just rerun, gives a different order.
- “You can put an
f64in aHashMapkey as long as you’re careful withNaN.” The compiler does not let you try —f64implements neitherEqnorHashat all (not evenEqfor the “careful” cases), soHashMap<f64, V>fails at the first method call that needs those bounds, not at some runtime edge case. - “BTreeMap is strictly slower, so only use it for debugging output.” It is a completely valid production choice whenever you need range queries (
.range(low..high)) or predictable ordering as a correctness requirement, not just a debugging convenience — the O(log n) cost is the price of a real feature, not overhead you’re paying for nothing.
Reading AI-generated Code
Section titled “Reading AI-generated Code”AI-generated code often iterates a HashMap directly in output-sensitive code — a report, a test assertion, a snapshot — without ever considering that the order is not stable.
🐛 Spot the bug
fn format_report(scores: &std::collections::HashMap<String, u32>) -> String { let mut out = String::new(); for (name, score) in scores { out.push_str(&format!("{}: {}\n", name, score)); } out}Show the answer
This function’s output order depends on HashMap’s randomized hash seed — two runs of the exact same program, with the exact same data, can print scores in a different order. Any test that does assert_eq!(format_report(&scores), "alice: 100\nbob: 85\n") will pass or fail depending on that run’s random seed, which makes the test flaky rather than wrong. The fix: sort the keys before formatting (let mut names: Vec<_> = scores.keys().collect(); names.sort();), or switch the underlying map to BTreeMap if callers always want sorted output.