skip to content

BTreeMap and BTreeSet

BTreeMap keeps keys sorted in a cache-friendly B-tree, which gives ordered iteration and range queries. Interviewers ask when it beats HashMap.

on this pageshow

questions

6

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?

level: juniorimportance: must knowfreq 60%

answer

  1. where the order comes from
  2. which comparison trait the methods need
  3. the bound sits on insert, not new
  4. f64 keys and E0277
  5. a randomly seeded hasher

basics

~20 s

BTreeMap 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 s

A `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 lines
rust
use 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

for a junior

Recall that BTreeMap iterates in ascending key order and needs Ord keys, while HashMap order is arbitrary and needs Hash plus Eq.

for a middle

Explain that the Ord bound lives on insert, get and range rather than on new, and read the E0277 that a float key produces.

for a senior

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.

for a principal

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.
open as a page

For a Rust order book in a BTreeMap<u64, u32>, how do you query a price band with range, and when does range panic?

level: middleimportance: must knowfreq 50%

basics

~20 s

Call range with any RangeBounds value (a..b, ..=b, a.., or a Bound tuple like (Excluded(a), Unbounded)) to iterate only those keys, in order, from either end. It panics when start exceeds end, or when equal bounds are both Excluded.

open as a page

In a Rust leaderboard stored as BTreeMap<u32, String> keyed by score, why do tied players vanish, and how do you read the top and bottom?

level: middleimportance: should knowfreq 42%

basics

~20 s

Each key holds one value, so inserting a second player with an equal score replaces the first. Store unique (score, player) tuples in a BTreeSet instead, then read last() for the top, first() for the bottom, and pop_first() to evict the lowest.

open as a page

In a Rust order book held as BTreeMap<u64, u32>, how do you remove empty or out-of-band price levels without hitting E0502?

level: middleimportance: should knowfreq 35%

basics

~20 s

Removing inside a for loop over &map fails with E0502. Use retain for a predicate over every entry, split_off to cut the map at a key, or extract_if, stable since Rust 1.91, to remove and collect matches inside one key range.

open as a page

A Rust BTreeSet holds keys whose Ord reads a Cell, and one key is changed in place; why do lookups start missing, and is it undefined behaviour?

level: seniorimportance: should knowfreq 30%

basics

~20 s

The tree placed the key by its old ordering and never re-sorts, so searches for either value take the wrong path and miss. std calls this a logic error: results are unspecified (wrong answers, panics, leaks, non-termination) but never undefined behaviour.

open as a page

Why is Rust's std BTreeMap built as a B-tree with multi-key nodes rather than a binary search tree, and when does HashMap still beat it?

level: seniorimportance: should knowfreq 38%

basics

~20 s

A binary tree allocates one node per entry and risks a cache miss at every comparison. std's B-tree currently packs up to 11 keys per node in contiguous arrays and scans them linearly. HashMap still wins on large, lookup-only workloads with costly-to-compare keys.

open as a page