What is the difference between HashMap and BTreeMap?
Short answer: a BTreeMap keeps entries sorted by key — iteration, ranges and the map’s ends
come in order — while a HashMap keeps no order and answers lookups faster. The choice is about
the order, not the speed: ordering is the one thing a HashMap cannot be given.
Mostly the same map
Section titled “Mostly the same map”Both live in std::collections, and most code cannot tell them apart: insert, get, remove,
len and iter exist on both with the same shapes, the entry API from the previous article
included. Swapping one for the other is usually a one-line change.
HashMap<K, V> |
BTreeMap<K, V> |
|
|---|---|---|
| Keys need | Hash + Eq |
Ord |
| Iteration order | arbitrary | sorted by key |
A float implements neither set, so both maps refuse it; a struct key earns Ord from
#[derive(PartialEq, Eq, PartialOrd, Ord)]. The
f64 key article covers the HashMap half.
Sorted iteration
Section titled “Sorted iteration”A BTreeMap hands back entries in key order whatever order they arrived in; a HashMap hands them
back in whatever order its table holds them. Stable output is free on a BTreeMap; on a HashMap
it takes a collect-and-sort detour.
BTreeMap-only calls
Section titled “BTreeMap-only calls”A few calls exist only on a BTreeMap and do not compile against a HashMap:
range("bravo".."delta") yields the entries in a key range, end exclusive; first_key_value() and
last_key_value() give the ends; and the iterators are double-ended, so keys().rev() walks
backwards.
What the speed costs
Section titled “What the speed costs”The standard library’s cost table puts HashMap lookups, inserts and removes at O(1) expected
and every BTreeMap operation at O(log n). Measured on one machine (release build, Rust
1.99.0, integer keys, random probes), HashMap lookups stayed in the tens of nanoseconds from a
thousand keys to a million; BTreeMap lookups climbed into the hundreds. The numbers move with the
machine; the shape does not. Outside a hot loop, the gap is noise.
Related
Section titled “Related”- Which collection should you use? — the decision table for the whole chapter
- How to handle missing keys with the entry API — the previous article, and the API both maps share
Next in this chapter: how to check whether a collection contains a value.