Standard Collections

HashMap vs. BTreeMap

Both HashMap<K, V> and BTreeMap<K, V> associate unique keys K with values V, but HashMap uses hash buckets for $O(1)$ average unordered lookup while BTreeMap uses sorted B-Tree nodes for $O(\log n)$ ordered lookup and range queries.

Feature and Complexity Comparison

Dimension HashMap<K, V> BTreeMap<K, V>
Required key trait bounds K: Eq + Hash K: Ord
Lookup / insert / remove (average) $O(1)$ $O(\log n)$
Lookup / insert / remove (worst case) $O(n)$ $O(\log n)$
Iteration order Arbitrary (nondeterministic per run) Sorted ascending by K: Ord
Range queries (map.range(a..=b)) Not supported ($O(n)$ full scan required) Supported in $O(\log n + k)$
Min / Max queries (first_key_value, last_key_value) Not supported ($O(n)$ full scan required) Supported in $O(\log n)$
Can the map itself be hashed or ordered (Map: Hash + Ord)? No (only PartialEq and Eq) Yes (BTreeMap<K, V>: Ord + Hash)

Comparing Unordered Lookup (HashMap) vs. Ordered Range Queries (BTreeMap)

use std::collections::{BTreeMap, HashMap};

fn main() {
    let pairs = [(200_u16, "OK"), (500, "Internal Error"), (404, "Not Found")];

    // 1. HashMap: fast O(1) exact lookup, arbitrary iteration order:
    let hash_map = HashMap::from(pairs);
    println!("HashMap lookup 404: {:?}", hash_map.get(&404));

    // 2. BTreeMap: sorted keys + range queries:
    let btree_map = BTreeMap::from(pairs);
    let client_and_server_errors: Vec<_> = btree_map.range(400..600).collect();

    println!("BTreeMap all keys sorted: {:?}", btree_map.keys().collect::<Vec<_>>());
    println!("BTreeMap 400..600 range:  {client_and_server_errors:?}");
}

HashMap lookup 404: Some(&"Not Found")
BTreeMap all keys sorted: [200, 404, 500]
BTreeMap 400..600 range:  [(404, &"Not Found"), (500, &"Internal Error")]

When to Choose Each Map

  • Choose HashMap<K, V> by default when you only need exact-key operations (get, insert, remove, entry) and do not care about key ordering. For integer or small string keys where SipHash overhead dominates and inputs are trusted, swapping the hasher (FxHashMap or AHashMap) makes HashMap even faster.
  • Choose BTreeMap<K, V> when you need deterministic sorted output (e.g., canonical serialization or reproducible compiler outputs), prefix/interval range queries (range(start..end)), finding the smallest/largest key (first_key_value / last_key_value), or using a map as a key inside another map or set.