Ordered Collections

Ordered vs. Unordered Collections

Rust provides parallel pairs of ordered (BTreeMap, BTreeSet) and unordered (HashMap, HashSet) associative collections with nearly identical method names, allowing you to trade $O(1)$ average hash lookups for $O(\log n)$ sorted order and range capabilities.

Comprehensive Comparison Matrix

Dimension Ordered (BTreeMap / BTreeSet) Unordered (HashMap / HashSet)
Underlying data structure Multi-element B-Tree ($B = 6$, up to 11 keys/node) SwissTable flat open-addressed hash table
Key trait bounds K: Ord K: Eq + Hash
Lookup / insert / remove (average) $O(\log n)$ $O(1)$
Lookup / insert / remove (worst case) $O(\log n)$ (guaranteed) $O(n)$ (rehash or full hash collision)
Iteration order Deterministic ascending Ord order Arbitrary / randomized per instance
Reverse iteration (.iter().rev()) Yes (DoubleEndedIterator) No
Min / Max access (first*, last*, pop_*) $O(\log n)$ Not supported ($O(n)$ full scan required)
Range queries (.range(a..=b)) $O(\log n + k)$ Not supported ($O(n)$ full scan required)
Pre-allocation (with_capacity, reserve) Not applicable (allocates per 6–11 keys) Supported (single contiguous table)
Implements Hash and Ord on the collection? Yes (BTreeSet can be a key in HashMap or BTreeSet) No (only implements PartialEq and Eq)
const fn new() Yes (static M: BTreeMap<...> = BTreeMap::new();) No (RandomState seeds at runtime)

When Ordered BTreeMap / BTreeSet Is Required

  1. Range, prefix, floor, and ceiling queries: Finding all timestamps in [t1, t2], all strings with a given prefix, or the largest key $\le x$.
  2. Double-ended priority queues: Repeatedly inspecting or popping both the minimum (pop_first) and maximum (pop_last) elements.
  3. Deterministic iteration and serialization: Producing byte-for-byte reproducible JSON/TOML/YAML outputs, cryptographic canonicalization, or compiler symbol dumps without sorting a temporary Vec on every read.
  4. Nested sets or maps as keys: Using a BTreeSet<T> or BTreeMap<K, V> as the key of another HashMap or BTreeMap.
use std::collections::{BTreeMap, HashMap};

fn main() {
    // A `BTreeMap` can serve as a key inside a `HashMap` because `BTreeMap: Eq + Hash`:
    let mut cache: HashMap<BTreeMap<&str, &str>, u32> = HashMap::new();

    let query_params_1 = BTreeMap::from([("page", "1"), ("sort", "asc")]);
    cache.insert(query_params_1, 200);

    // Insertion order into `BTreeMap` does not matter — canonical key order is identical:
    let query_params_2 = BTreeMap::from([("sort", "asc"), ("page", "1")]);
    println!("Canonical query cache hit: {:?}", cache.get(&query_params_2));
}

Canonical query cache hit: Some(200)