The problem with scanning lists
You're building a config loader for a game server. The config file has hundreds of settings: max players, map rotation, difficulty flags. You parse the file and store the settings. Later, the game loop asks for max_players. You don't want to scan the entire list of settings every time. Scanning is slow. You need instant lookup by name.
In Python, you'd reach for a dict. In JavaScript, an object or Map. In Rust, the tool is HashMap. It stores key-value pairs and retrieves values by key in constant time. You give it a key, it gives you the value. No scanning. No linear search. Just a direct jump to the data.
HashMap: keys, values, and the hash function
A HashMap is a dictionary. It maps keys to values. Keys must be unique. If you insert the same key twice, the second value overwrites the first. Values can be anything: integers, strings, structs, or even other collections.
The magic happens in the hash function. When you insert a key, HashMap runs the key through a hash function. This function turns the key into a number, called a hash. The hash determines which "bin" in the underlying array stores the value. When you look up a key, HashMap computes the hash again, jumps to that bin, and retrieves the value.
Think of a warehouse with numbered bins. The hash function is the rule that tells you which bin number a box goes in based on its label. You calculate the bin number, walk there, and grab the box. You don't check every bin.
Sometimes two keys produce the same hash. This is a collision. Rust handles collisions automatically using a probing strategy. If a bin is occupied, HashMap checks the next available bin. The lookup logic accounts for this, so collisions don't break correctness. They just add a tiny bit of overhead.
Rust's default hasher is SipHash. It includes a random salt to prevent hash-flooding attacks, where an attacker crafts keys to cause massive collisions. This makes HashMap safe for untrusted input. The trade-off is a small performance cost compared to simpler hashers. For most applications, SipHash is the right choice. If you control all keys and need raw speed, you can swap the hasher, but the default protects you from edge cases.
Minimal example
Create a HashMap with HashMap::new(). Insert pairs with insert. Retrieve values with get. The map must be mutable to insert or remove items. Retrieval works on immutable references.
use std::collections::HashMap;
fn main() {
// Create a mutable map. Insert requires &mut self.
let mut scores = HashMap::new();
// Insert key-value pairs. Keys are Strings, values are i32.
// If the key exists, the old value is overwritten.
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
// Look up a value. get returns Option<&V>.
// This handles missing keys safely without panicking.
let score = scores.get("Blue");
// copied() converts &i32 to i32. i32 implements Copy.
// unwrap_or(0) provides a default if the key is absent.
let blue_score = score.copied().unwrap_or(0);
println!("Blue score: {blue_score}");
// Check existence without retrieving the value.
if scores.contains_key("Red") {
println!("Red exists");
} else {
println!("Red is missing");
}
}
Don't fight the Option. get returns Option<&V> because the key might not exist. Handle the absence explicitly with unwrap_or, expect, or pattern matching. This forces you to consider missing data.
Keys must implement Hash and Eq
Not every type can be a key. The key type must implement two traits: Hash and Eq.
Hash provides the hash function. It turns the key into a u64. Eq provides equality checking. It confirms whether two keys are identical.
You need both because hash collisions exist. If two keys have the same hash, HashMap uses Eq to distinguish them. Without Eq, the map couldn't tell if a collision means the same key or a different key with the same hash.
Built-in types like String, &str, i32, and bool implement these traits. Custom structs need #[derive(Hash, Eq, PartialEq)]. Note that Eq implies PartialEq, so you must derive both.
use std::collections::HashMap;
// Derive Hash, Eq, and PartialEq for custom keys.
// Eq implies PartialEq, so both are required.
#[derive(Hash, Eq, PartialEq)]
struct UserId {
id: u64,
region: String,
}
fn main() {
let mut users = HashMap::new();
// Create a custom key.
let user = UserId {
id: 42,
region: String::from("US"),
};
// Insert using the custom key.
users.insert(user, "Alice");
// Look up with a matching key.
let lookup_key = UserId {
id: 42,
region: String::from("US"),
};
// get works because UserId implements Hash and Eq.
let name = users.get(&lookup_key);
println!("User: {:?}", name);
}
If you forget to derive the traits, the compiler rejects the code with E0277 (trait bound not satisfied). The error message tells you exactly which trait is missing. Add the derive macro and the error disappears.
Convention aside: When defining keys, keep them small. Large keys mean more data to hash and compare. If you have a large struct, consider hashing only the unique fields or using a smaller identifier as the key.
The entry API: update or insert in one pass
A common pattern is updating a value if the key exists, or inserting a default if it doesn't. A naive approach uses get followed by insert. This performs two lookups. It hashes the key twice. It's inefficient.
Rust provides the entry API to solve this. entry performs the lookup once. It returns an Entry enum that lets you chain operations. You can insert a default, modify an existing value, or remove the entry. The API guarantees the hash is computed only once.
use std::collections::HashMap;
fn count_words(text: &str) -> HashMap<String, usize> {
let mut counts = HashMap::new();
for word in text.split_whitespace() {
// entry API performs lookup once.
// or_insert_with provides a default if key is missing.
// The closure runs only if the key is absent.
let count = counts.entry(word.to_lowercase()).or_insert_with(|| 0);
// Increment the count.
*count += 1;
}
counts
}
fn main() {
let text = "Rust is fast. Rust is safe. Rust is fast.";
let counts = count_words(text);
// Print results.
for (word, count) in &counts {
println!("{word}: {count}");
}
}
The entry API is idiomatic Rust. You'll see it in standard library code and community crates. Use it whenever you need to update or insert conditionally. It saves a lookup and keeps the logic concise.
Another variant is and_modify. This lets you update an existing value without touching missing keys.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([
("Blue", 10),
("Yellow", 50),
]);
// Add points only if the team exists.
scores
.entry("Blue".to_string())
.and_modify(|score| *score += 5);
// Insert a new team with a default score.
scores.entry("Red".to_string()).or_insert(0);
println!("{:?}", scores);
}
The entry API saves you a lookup. Use it whenever you update or insert conditionally.
Iteration and ownership
HashMap provides several ways to iterate. The method you choose determines ownership and mutability.
iter() returns references to keys and values. It borrows the map. You can read data but not modify the map structure. keys() and values() return iterators over just keys or values. values_mut() gives mutable access to values, allowing in-place updates.
into_iter() consumes the map. It yields owned keys and values. Use this when you no longer need the map and want to move the data out.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([
("Blue", 10),
("Yellow", 50),
]);
// Iterate with references. Borrows the map.
for (team, score) in scores.iter() {
println!("{team}: {score}");
}
// Modify values in place.
for score in scores.values_mut() {
*score *= 2;
}
// Collect keys into a Vec.
// into_keys avoids cloning keys by consuming the map.
let teams: Vec<&String> = scores.keys().collect();
println!("Teams: {:?}", teams);
}
Convention aside: When collecting keys or values, prefer into_keys() and into_values() over keys().cloned(). The into_ variants consume the map and move the data, avoiding allocation and cloning. Use them when you're done with the map.
Iteration order is not guaranteed. HashMap does not preserve insertion order. The order depends on hash values and internal resizing. If you need stable order, use IndexMap or BTreeMap.
Pitfalls and compiler errors
The borrow checker catches common mistakes with HashMap. The most frequent issue is borrowing immutably while trying to mutate.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([("Blue", 10)]);
// get holds an immutable borrow of the map.
let score = scores.get("Blue");
// insert requires mutable access.
// This fails because the map is already borrowed.
scores.insert("Yellow", 50);
}
The compiler rejects this with E0502 (cannot borrow as mutable because it is also borrowed as immutable). The immutable borrow from get is still active when insert runs. Rust prevents this to avoid dangling references.
Fix the issue by cloning the value or restructuring the logic.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([("Blue", 10)]);
// Clone the value to release the borrow.
let score = scores.get("Blue").copied();
// Now the map is free to mutate.
scores.insert("Yellow", 50);
}
Another pitfall is using HashMap when order matters. If you iterate and expect insertion order, you'll get random results. The map reorders items during resizing. Switch to IndexMap if you need order.
Performance pitfall: HashMap allocates on the heap. Creating many small maps can fragment memory. If you're building maps in a tight loop, reuse a single map with clear() instead of allocating new ones.
The borrow checker protects you from self-referential messes. Clone the value or restructure the logic.
Choosing the right map
Rust offers several map types. Pick the one that matches your access pattern.
Use HashMap when you need O(1) lookups and iteration order is irrelevant. It's the fastest general-purpose map. Use BTreeMap when your keys must stay sorted or you need to query ranges of keys. It offers O(log n) lookups but maintains order. Use IndexMap when you need the speed of a hash map but also care about the order items were inserted. It preserves insertion order while keeping fast lookups. Use a Vec with binary search when the data is read-heavy, sorted, and you want to minimize memory overhead. It has no allocation overhead for the structure itself.
Pick the map that matches your access pattern. O(1) is great until you need order.