The leaderboard dilemma
You're building a leaderboard for a multiplayer game. Players join, scores update, and you need to display the top ten. You also need to check a specific player's score instantly when they request it. You grab a map to store the data. Now you have a choice. Do you use HashMap or BTreeMap?
The choice changes how your code behaves, how fast it runs, and whether your output looks random or sorted. Picking the wrong one can turn a fast lookup into a sorting nightmare, or force you to pay for ordering you never use.
Hash maps vs tree maps
HashMap is the default choice for most Rust code. It uses a hash function to scatter keys across buckets. You calculate the hash, jump straight to the bucket, and find the value. Lookups are O(1) on average. The keys are scattered. There is no order. Iterating over a HashMap gives you keys in a random sequence that can change between runs.
BTreeMap keeps keys sorted. It stores data in a balanced tree structure. To find a key, you compare it to the middle node, go left or right, and repeat. Lookups are O(log n). The keys are always ordered. Iterating gives you keys from smallest to largest. You get deterministic output and range queries for free.
Think of HashMap like a locker room where lockers are scattered based on a code. You know the code, you find the locker instantly. You don't know where locker 5 is relative to locker 6. Think of BTreeMap like a library index card catalog. You follow a path. Left or right. You always find things in order.
Minimal example
use std::collections::{HashMap, BTreeMap};
/// Compare iteration order and basic usage.
fn main() {
// HashMap: fast lookups, random iteration order.
let mut scores_hash = HashMap::new();
scores_hash.insert("alice", 100);
scores_hash.insert("bob", 200);
scores_hash.insert("charlie", 50);
// BTreeMap: sorted keys, slightly slower lookups.
let mut scores_btree = BTreeMap::new();
scores_btree.insert("alice", 100);
scores_btree.insert("bob", 200);
scores_btree.insert("charlie", 50);
// HashMap iteration order is non-deterministic.
// Don't rely on the order of this loop.
for (name, score) in &scores_hash {
println!("HashMap: {} -> {}", name, score);
}
// BTreeMap iteration is always sorted by key.
// This loop runs alice, bob, charlie every time.
for (name, score) in &scores_btree {
println!("BTreeMap: {} -> {}", name, score);
}
}
Speed comes at the cost of chaos. If you need order, HashMap won't give it to you.
Under the hood
When you insert into a HashMap, Rust hashes the key. The hash determines the bucket index. If two keys hash to the same bucket, the map handles the collision using probing. The map grows when the load factor gets too high. This resizing keeps lookups fast. HashMap requires keys to implement Hash and Eq.
When you insert into a BTreeMap, Rust compares the key to existing nodes. It walks down the tree. Left if smaller, right if larger. It maintains balance by rotating nodes. This keeps the tree height logarithmic. BTreeMap requires keys to implement Ord. The Ord trait implies PartialOrd, Eq, and PartialEq. If your type implements Ord, you can use it as a BTreeMap key.
BTreeMap has higher constant factors than HashMap. The tree structure means more pointer chasing and more comparisons. HashMap wins on raw speed for random access. BTreeMap wins when you need sorted access or range queries.
Sorting is free with BTreeMap. You pay for it in slightly slower lookups, but you get range queries and determinism for free.
Range queries: the BTreeMap superpower
BTreeMap supports range queries. You can ask for all keys in a range. HashMap cannot do this. You would have to iterate the entire map and filter.
use std::collections::BTreeMap;
/// Demonstrate range queries with BTreeMap.
fn main() {
let mut scores = BTreeMap::new();
scores.insert("alice", 100);
scores.insert("bob", 200);
scores.insert("charlie", 150);
scores.insert("dave", 50);
// Find all players with scores between 100 and 200 inclusive.
// BTreeMap::range uses the sorted structure to find the start quickly.
let range = scores.range(100..=200);
// Iterate only the matching entries.
// This is O(log n + k) where k is the number of results.
for (name, score) in range {
println!("{}: {}", name, score);
}
}
Range queries are O(log n + k). You pay the log n cost to find the start, then linear cost for the results. HashMap would be O(n) for the same operation. If you need ranges, BTreeMap is the only standard library option.
Realistic example: building the view
In a leaderboard, you often update scores frequently and display the ranking occasionally. You can use HashMap for the hot path and BTreeMap for the display path.
use std::collections::{BTreeMap, HashMap};
/// Manage a leaderboard where we need top-N and fast updates.
fn main() {
// Use HashMap for the hot path: updating scores.
// O(1) updates are crucial when players submit scores rapidly.
let mut active_scores: HashMap<String, u32> = HashMap::new();
active_scores.insert("player_1".to_string(), 1500);
active_scores.insert("player_2".to_string(), 1200);
active_scores.insert("player_3".to_string(), 1800);
// Use BTreeMap for the display path: sorted ranking.
// O(log n) insert is acceptable when building the view.
let mut leaderboard: BTreeMap<u32, Vec<String>> = BTreeMap::new();
// Invert the map: score -> list of players.
// BTreeMap sorts by score automatically.
for (player, score) in &active_scores {
// Entry API avoids double lookup.
// or_insert_with creates the Vec only if the key is missing.
leaderboard
.entry(*score)
.or_insert_with(Vec::new)
.push(player.clone());
}
// Iterate from highest score to lowest.
// BTreeMap::iter gives ascending order, so reverse it.
for (score, players) in leaderboard.iter().rev() {
for player in players {
println!("{}: {}", player, score);
}
}
}
Convention aside: use entry API when you need to insert a default value if the key is missing. It avoids double hashing and keeps the code clean. Also, BTreeMap iteration is ascending. Reverse it for leaderboards.
Don't sort if you don't need to. Don't hash if you need order.
Pitfalls and compiler errors
BTreeMap requires Ord. If you try to use a type that doesn't implement Ord, the compiler rejects you with E0277 (trait bound not satisfied). The error tells you the type doesn't implement Ord. You need to derive Ord or implement it manually.
HashMap requires Hash and Eq. If you have Eq but no Hash, you get a similar bound error. A common trap is using f64 as a key. Floating point equality is tricky. NaN is not equal to NaN. Hashing floats can be unstable across platforms. Stick to integers, strings, or tuples of hashable types.
Another pitfall is assuming HashMap iteration order is stable. It is not. The order can change between runs and between Rust versions. If you need deterministic output, use BTreeMap.
If you need insertion order, neither HashMap nor BTreeMap gives it to you. Use IndexMap from the indexmap crate. It preserves insertion order and supports O(1) lookups.
Decision matrix
Use HashMap when you need the fastest average-case lookups and insertions. Use HashMap when key order doesn't matter and you only care about finding values by key. Use HashMap when you are building a cache, a frequency counter, or a lookup table where performance is the priority.
Use BTreeMap when you need keys sorted or deterministic iteration order. Use BTreeMap when you need range queries, like finding all keys between A and Z. Use BTreeMap when you need to find the nearest key, such as the floor or ceiling of a value. Use BTreeMap when your keys don't implement Hash but do implement Ord.
Use IndexMap when you need insertion order preservation. Use IndexMap when you need fast lookups like HashMap but also want to iterate in the order items were added.
Pick the tool that matches your access pattern. The compiler will force you to be honest about what you need.