The High-Score Problem
You're building a high-score table for a game. Players submit scores in a chaotic stream. You need to store them and occasionally display the top ten. You grab a map to store PlayerName -> Score. When you print the map, the names come out in a random order. You sort them manually, but now every time a new score comes in, you're re-sorting or managing a separate list. There's a better way, but it depends on what you value more: raw insertion speed or keeping things tidy.
Rust gives you two main choices for key-value storage: HashMap and BTreeMap. They solve the same problem but with different trade-offs. HashMap prioritizes speed for lookups and inserts. BTreeMap prioritizes order and range queries. Picking the wrong one won't crash your program, but it can make your code slower or more complex than it needs to be.
Warehouse Bins vs Library Shelves
Think of HashMap like a warehouse with numbered bins. You take an item, run a quick calculation on its name to get a bin number, and drop it in. Retrieval is instant if you know the bin. Walking through the warehouse gives you items in a random order determined by those bin numbers. The calculation is a hash function. The bins are buckets. If two items hash to the same bin, the system handles the collision, but the goal is to spread items out so you rarely have to dig.
BTreeMap is like a library with alphabetical shelves. Finding a specific book requires walking down the aisles and checking signs, which takes a few steps. But the books are always sorted. If you want every book starting with "A", you just grab that section. No sorting needed. The structure is a balanced tree. It keeps data organized as you insert it. You pay a small cost on insert to maintain that order, but you get sorted iteration and range queries for free.
Minimal Example
Here's the basic usage. Both maps look similar when you insert and get values. The difference shows up when you iterate.
use std::collections::{HashMap, BTreeMap};
fn main() {
// HashMap: Fast lookups, arbitrary order.
let mut scores_hash = HashMap::new();
scores_hash.insert("Alice", 100);
scores_hash.insert("Bob", 200);
scores_hash.insert("Charlie", 150);
// Iteration order is not guaranteed. It may change between runs.
for (name, score) in &scores_hash {
println!("HashMap: {} -> {}", name, score);
}
// BTreeMap: Sorted keys, slightly slower lookups.
let mut scores_tree = BTreeMap::new();
scores_tree.insert("Alice", 100);
scores_tree.insert("Bob", 200);
scores_tree.insert("Charlie", 150);
// Iteration is always sorted by key.
for (name, score) in &scores_tree {
println!("BTreeMap: {} -> {}", name, score);
}
}
The HashMap output might print Alice, then Charlie, then Bob. The BTreeMap output will always print Alice, Bob, Charlie. If you run this program multiple times, the HashMap order might shuffle. The BTreeMap order stays fixed.
Under the Hood: Hashing and Trees
HashMap uses a hash table. When you insert a key, Rust computes a hash value. That value maps to an index in an internal array. Rust's HashMap implementation uses Robin Hood hashing with linear probing. This strategy tries to keep the distance from the ideal bucket short for all items. It reduces the variance in lookup time. The average case is O(1). The worst case is O(n), but that's extremely rare with good hash functions.
BTreeMap uses a B-Tree. This is a balanced tree where each node can hold multiple keys and values. The tree stays balanced automatically. Insertion and lookup are O(log n). The constant factors are higher than a hash table for point lookups, but the structure is predictable. There are no pathological cases where performance degrades unexpectedly.
The B-Tree structure also has wide nodes. Each node holds many keys. This reduces the number of pointer hops. It makes the structure more cache-friendly than a binary tree with one key per node. This matters for iteration performance.
The Cache Locality Surprise
Counter-intuitive but true: BTreeMap can be faster than HashMap for full iteration.
When you iterate a HashMap, the entries are scattered across memory in buckets. The CPU has to jump around, loading cache lines that might not be related. This causes cache misses. When you iterate a BTreeMap, the nodes are allocated in a way that keeps related data closer together. The iteration walks through the tree in order, which often aligns with memory layout. The CPU prefetches data more effectively.
If your workload involves iterating over the entire map frequently, BTreeMap might outperform HashMap despite the O(log n) lookup cost. The cache locality wins. This is a common "ah-ha" moment for Rust developers who assume HashMap is always faster. It's faster for random access. It's not always faster for sequential access.
Realistic Example: Range Queries
The killer feature of BTreeMap is range queries. You can efficiently find all keys within a range. HashMap has no equivalent. To do a range query on a HashMap, you'd have to iterate every entry and filter, which is O(n). BTreeMap does it in O(log n + k), where k is the number of results.
use std::collections::BTreeMap;
fn main() {
let mut inventory = BTreeMap::new();
inventory.insert("apple", 50);
inventory.insert("banana", 30);
inventory.insert("cherry", 20);
inventory.insert("date", 10);
inventory.insert("elderberry", 5);
// Range query: Get all fruits from "banana" up to but not including "date".
// This is efficient. It jumps to "banana" and stops at "date".
for (fruit, count) in inventory.range("banana".."date") {
println!("{}: {}", fruit, count);
}
}
This prints banana and cherry. The range method returns an iterator that yields only the matching entries. It doesn't scan the whole map. If you're building a database index, a calendar view, or anything that needs "give me everything between X and Y", BTreeMap is the tool. HashMap forces you to write a linear scan.
Pitfalls: Trait Bounds and Floating Point
Both maps require traits on keys, but different ones. HashMap requires Hash and Eq. BTreeMap requires Ord. If you define a custom struct and try to use it as a key without deriving these traits, the compiler rejects you.
use std::collections::HashMap;
struct User {
id: u32,
}
fn main() {
let mut map = HashMap::new();
// This fails because User doesn't implement Hash and Eq.
// error[E0277]: the trait bound User: Hash is not satisfied
map.insert(User { id: 1 }, "Alice");
}
The fix is to derive the traits. For HashMap, add #[derive(Hash, Eq, PartialEq)]. For BTreeMap, add #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]. Note that Ord implies PartialOrd, Eq, and PartialEq. You can derive all of them at once for BTreeMap keys.
Floating point keys are a trap. f64 does not implement Hash or Ord. The reason is NaN. NaN is not equal to itself, which breaks Eq. NaN is not comparable in a total order, which breaks Ord. If you need floating point keys, wrap them in a type that handles NaN, or use a different key type like a string or integer ID.
Convention aside: The Rust community defaults to HashMap. If you don't have a specific reason to use BTreeMap, use HashMap. It's the standard choice. BTreeMap is the specialist. Don't reach for BTreeMap just because you like sorted output. If you only need sorted output once, sort the HashMap keys. If you need sorted output constantly, or you need ranges, switch to BTreeMap.
Decision Matrix
Use HashMap when you need O(1) average lookups and insertion speed is the priority. Use HashMap when memory overhead per entry matters less than raw speed, as HashMap has higher constant factors but better asymptotic performance for point queries. Use HashMap when keys are complex objects where hashing is cheap but comparison is expensive. Use BTreeMap when you need to iterate over keys in sorted order without paying the cost of a separate sort. Use BTreeMap when you need range queries, such as finding all entries where the key falls between two values. Use BTreeMap when deterministic iteration order is required for reproducible tests or stable serialization formats. Use BTreeMap when your keys implement Ord but do not implement Hash.
If you find yourself sorting a HashMap's keys every time you print, switch to BTreeMap. Range queries on a HashMap are a code smell. Reach for BTreeMap.