In Rust, why does printing a BTreeMap<&str, usize> list keys in sorted order when a HashMap does not, and what must its key type implement?
answer
- where the order comes from
- which comparison trait the methods need
- the bound sits on insert, not new
- f64 keys and E0277
- a randomly seeded hasher
basics
~20 sBTreeMap keeps entries sorted by key, so iteration and Debug output walk them in ascending order, and its key type must implement Ord. HashMap places entries by a randomly seeded hash, so its order is arbitrary, and it needs Hash + Eq instead.
solid answer
~40 sA `BTreeMap<K, V>` is an ordered map. Every insert puts the key at its sorted position, and `iter`, `keys`, `values`, `into_iter` and the `{:?}` output all yield entries in ascending key order, on every run. That is why its methods carry a `K: Ord` bound: `insert`, `get`, `range` and `entry` all compare keys. `BTreeMap::new` has no bound, so a float key fails at the first `insert` with E0277 ("the trait bound `f64: Ord` is not satisfied"). A `HashMap` needs `Hash + Eq` and uses a randomly seeded hasher, so its order is arbitrary and can change between runs. Choose `BTreeMap` for sorted output, range queries or reproducible iteration in snapshot tests and diffs. As a bonus, `BTreeMap` and `BTreeSet` implement `Hash` and `Ord` themselves, so they can serve as keys, which `HashMap` cannot.
code
rust · 17 linesuse std::collections::{BTreeMap, HashMap};
fn main() {
let words = ["pear", "apple", "fig", "kiwi", "banana"];
let mut hashed: HashMap<&str, usize> = HashMap::new();
let mut sorted: BTreeMap<&str, usize> = BTreeMap::new();
for w in words {
hashed.insert(w, w.len());
sorted.insert(w, w.len());
}
// Order depends on this map's random hasher seed: can differ run to run.
println!("{hashed:?}");
// Always ascending by key, because &str implements Ord.
println!("{sorted:?}");
}go deeper
Recall that BTreeMap iterates in ascending key order and needs Ord keys, while HashMap order is arbitrary and needs Hash plus Eq.
Explain that the Ord bound lives on insert, get and range rather than on new, and read the E0277 that a float key produces.
Show when determinism matters in production: snapshot tests, serialized diffs and reproducible logs, and why a hashed map's order must never be relied on.
Frame the choice as an API decision: exposing a BTreeMap gives callers ordering and hashability, which becomes part of the contract you cannot quietly withdraw.
## What "ordered" means for `BTreeMap` A **`BTreeMap<K, V>`** (in `std::collections`) is an **ordered map**. Every `insert` places the key at its sorted position, so the map is always ordered by key. Whatever order you insert in, these all yield entries in **ascending key order**: - `iter`, `iter_mut`, `keys`, `values` and `into_iter`; - a `for (k, v) in &map` loop, which calls `iter` under the hood; - the `{:?}` output, because the `Debug` impl walks the same iterator. The std docs state that these iterators produce items in key order. That is why a `BTreeMap<&str, usize>` printed twice gives the same output on every run and every machine. **`BTreeSet<T>`** is the same structure with keys only: its `iter` yields elements in ascending order. ## The `Ord` bound and where rustc enforces it To keep keys sorted, the map has to compare any two of them and get a definite `Ordering` (`Less`, `Equal` or `Greater`). That is what the **`Ord`** trait promises: a total order. So the methods that place or find a key carry a `K: Ord` bound. That includes `insert`, `get`, `contains_key`, `remove`, `entry` and `range`. One detail surprises people: **`BTreeMap::new` has no bound** (it is even a `const fn`). The error appears at the first call that needs to compare: ```rust let mut prices = BTreeMap::new(); prices.insert(19.99_f64, "widget"); // error[E0277]: the trait bound `f64: Ord` is not satisfied ``` rustc points at the `K: Ord` clause on `BTreeMap::insert`. Floats are the classic case because `NaN` breaks a total order, so `f64` implements only `PartialOrd`. How to order such a type is covered with the comparison traits. For a price, the usual fix is an integer number of cents or ticks. ## Why `HashMap` prints in a different order A **`HashMap<K, V>`** needs `K: Hash + Eq`, not `Ord`. It files each entry under a bucket chosen from the key's hash. By default the hasher is `RandomState`, which is seeded randomly, so two maps holding the same keys can lay them out differently. The std docs describe its iterators as visiting entries in **arbitrary order**. The order can change between runs of the same program; two runs of one binary printed the same map's keys in two different orders. How the hasher works and why it is randomised belongs with the hash map material. ## Choosing between them | Need | `BTreeMap` | `HashMap` | |---|---|---| | Key bound | `Ord` | `Hash + Eq` | | Iteration order | ascending by key, every run | arbitrary, may differ per run | | Range queries (`range`) | yes | no | | Smallest or largest key | `first_key_value`, `last_key_value` | a full scan | | Map usable as a key itself | yes: it implements `Hash` and `Ord` | no: no `Hash` impl | | Hasher to choose or tune | none | `RandomState` by default | Reach for `BTreeMap` when: 1. output must be **sorted** (a report, a CLI listing, a config dump); 2. you need **reproducible iteration**: snapshot tests, diffs of serialized state, deterministic logs; 3. you query **ranges** or the **ends** of the key space; 4. the map itself must be **hashed or compared**, for example a `BTreeSet<u32>` stored inside a `HashSet`. For plain lookups by key, with no need for order, a `HashMap` is the common default. ## The same rules for `BTreeSet` `BTreeSet<T>` wraps a `BTreeMap` whose values are a zero-sized placeholder, a set of keys with nothing attached, and it follows the same rules: - `insert` requires `T: Ord` and returns `true` only when the value was not already present; - `iter` and the `{:?}` output are in ascending order, so `BTreeSet::from([3, 1, 2])` prints `{1, 2, 3}`; - set operations such as `union`, `intersection` and `difference` also yield their results in sorted order. That makes a `BTreeSet` the quickest way to get a **sorted, deduplicated** list of values, such as tags, user ids or file names, without a separate sort and dedup pass. ## Mistakes interviewers listen for - Thinking `BTreeMap` keeps **insertion order**. It keeps key order. Insertion order needs something else, such as a `Vec` of keys kept alongside the map. - Assuming a `HashMap` with integer keys prints sorted. It may look sorted on a small map by accident, and that proves nothing. - Expecting `BTreeMap::new()` itself to reject a non-`Ord` key. The bound sits on the methods. - Believing `BTreeMap` needs `Hash`. It never hashes anything.
- How do you key a Rust BTreeMap by a price when f64 does not implement Ord?The usual fix is to store the price as an integer, such as cents or exchange ticks in a `u64`. Exact integer keys are what money needs anyway. If you must keep the float, wrap it in a newtype whose `Ord` uses `f64::total_cmp`. Writing that impl correctly is covered with the comparison traits.
- Why can a BTreeSet<u32> be an element of a HashSet when a HashSet<u32> cannot?`BTreeSet<T>` implements `Hash` (when `T: Hash`) and `Ord`. Its elements always iterate in sorted order, so equal sets feed the hasher the same sequence. `HashSet` and `HashMap` implement neither `Hash` nor `Ord`, so using one as a key fails with a missing-trait error. A sorted set is the standard way to key by a set of values.
- BTreeMap keeps keys in the order they were inserted.
- A BTreeMap key only needs Eq, the same as a HashMap key.
- BTreeMap::new() refuses to compile when the key type lacks Ord.
- A HashMap with integer keys always iterates in ascending order.
- BTreeMap hashes its keys, so they must implement Hash.