HashMap<K, V> and BTreeMap<K, V>

HashMap and BTreeMap are Rust’s two primary map types. Both store key‑value pairs and expose an almost identical set of methods — insert, get, remove, contains_key — but their internal data structures solve two different problems. HashMap gives you the fastest possible lookups when you don’t care about the order of the keys. BTreeMap keeps the keys sorted at all times, which makes range queries and ordered iteration natural.

This deep‑dive assumes you’ve already met the basics in the earlier “Hash Maps (HashMap<K, V>)” section. Here we focus on the details that matter when you use these collections in real projects: the entry API, iteration patterns, performance characteristics, and the concrete trade‑offs that guide your choice.

Understanding the Two Maps

A HashMap is built on a hash table. When you call insert(key, value), the key is passed through a hash function — by default SipHash‑1‑3 — to produce a number. That number determines which “bucket” the entry goes into. Lookups work by hashing the search key and checking the corresponding bucket, which on average takes constant time regardless of how many elements are in the map.

A BTreeMap uses a B‑tree, a balanced search tree where each node holds a sorted array of keys and child pointers. Every lookup follows the tree from root to leaf, comparing the search key against the sorted keys in each node. This gives O(log n) behaviour, but because the keys are stored in order, you can efficiently ask questions like “give me all entries whose keys are between 10 and 20” or “what is the smallest key greater than 500?”.

HashMap<K, V>: The Hash Table Map

Use a HashMap when your primary need is associating arbitrary keys with values and you want the fastest average‑case lookups. The standard HashMap uses a hash table with open addressing and quadratic probing, which avoids the pointer‑heavy structure of older chaining designs and keeps elements close together in memory.

Basic Operations

Every operation follows the same ownership rules you see everywhere in Rust. Inserting moves the key and value into the map if they’re not Copy. Retrieving a value borrows the map and returns Option<&V>.

use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Red"), 25);
// get returns Option<&V>
match scores.get("Blue") {
    Some(v) => println!("Blue team score: {v}"),
    None => println!("No Blue team"),
}
// Access with a default if missing
let green_score = scores.get("Green").copied().unwrap_or(0);
// Overwrite an entry
scores.insert(String::from("Blue"), 15); // replaces old value

This example shows the standard lookup pattern. get borrows the map and returns an Option containing a reference to the value. Because the reference is tied to the borrow, you cannot mutate the map while you hold it — the compiler enforces this. The copied call turns Option<&i32> into Option<i32> when the value is Copy.

Counting with the Entry API

A common task is building a frequency map: each time you see a key, increment its count. Without the entry API you would do two lookups — one to check if the key exists, another to insert or update. The entry API fuses the check and the action into a single lookup.

use std::collections::HashMap;
let text = "the quick brown fox jumps over the lazy dog";
let mut word_counts = HashMap::new();
for word in text.split_whitespace() {
    let count = word_counts.entry(word).or_insert(0);
    *count += 1;
}
// "the" appears 2, all others 1

entry(word) returns an Entry enum — Vacant if the key is absent, Occupied if it’s present. or_insert(0) inserts the key with the given default only if vacant, and returns a mutable reference to the value. Because the lookup and the insertion happen under the same borrow, the compiler guarantees you never accidentally race yourself.

BTreeMap<K, V>: The Ordered Map

BTreeMap is the right tool when you need the keys in sorted order, or when you need to query ranges of keys efficiently. Because the data is stored in sorted B‑tree nodes, iterating over the map always visits entries in ascending key order. Operations that ask for neighbours — the smallest key, the largest key, or a contiguous range — work in O(log n) time.

Range Queries

The range method takes a range expression and returns an iterator over entries whose keys fall inside that range. This is not something HashMap can do at all.

use std::collections::BTreeMap;
let mut events: BTreeMap<u64, &str> = BTreeMap::new();
events.insert(1706745600, "Server started");
events.insert(1706745650, "Database connected");
events.insert(1706745700, "First request");
// All events between two timestamps
for (ts, description) in events.range(1706745640..1706745710) {
    println!("{ts}: {description}");
}
// Output: 1706745650: Database connected
//         1706745700: First request

The range bounds follow Rust’s usual .. syntax. The returned iterator yields references in sorted order. There is no copying or re‑sorting — the tree structure directly supports this traversal.

First, Last, and Neighbour Operations

BTreeMap exposes methods that directly read from the ordered structure: first_key_value and last_key_value return the smallest and largest entries. pop_first and pop_last remove and return those entries, which is useful for priority‑queue‑style patterns.

let mut bmap = BTreeMap::from([(3, "three"), (1, "one"), (2, "two")]);
if let Some((key, val)) = bmap.first_key_value() {
    println!("Smallest: {key} -> {val}"); // 1 -> one
}
if let Some((key, val)) = bmap.pop_last() {
    println!("Removed largest: {key}");    // 3
}

These methods are O(log n), not O(1). In scenarios where you need to repeatedly extract the smallest or largest key, a BinaryHeap might be a better fit, but BTreeMap gives you the same capability while keeping the full map available for other queries.

Choosing Between HashMap and BTreeMap

The right choice depends on which question you ask most often: “what is the value for key X?” or “what keys are near X?”.

HashMap’s average O(1) makes it the default for caches, lookup tables, configuration maps, and any situation where you just need “give me the value for this key”. BTreeMap shines when the order of the keys matters: leaderboards, time‑series data, or any database‑like access pattern over sorted data.

The Entry API: Efficient Single Lookups

The entry API is so central to working with maps that it deserves its own section. Every call to entry returns an Entry value — either Entry::Vacant(entry) or Entry::Occupied(entry) — which lets you act on the presence or absence of a key with exactly one hash or tree traversal.

Inserting a Default Only If Missing

let mut map = HashMap::new();
map.entry("key1").or_insert(42);  // inserts 42
map.entry("key1").or_insert(99);  // key1 already exists, value stays 42

or_insert takes a value directly. It’s suitable for cheap, Copy defaults. For defaults that require computation (like allocating a Vec), use or_insert_with to pass a closure that is only called when the key is vacant.

let mut cache: HashMap<String, Vec<u8>> = HashMap::new();
let data = cache.entry("resource".to_string())
                .or_insert_with(|| expensive_load());

Modifying an Existing Value In‑Place

When you know the key already exists, and_modify lets you mutate the value without a separate lookup.

let mut scores = HashMap::from([("Alice", 10)]);
scores.entry("Alice").and_modify(|v| *v += 5);
// Alice is now 15

Chaining entry calls is idiomatic. For example, a more realistic frequency counter that also capitalises the first occurrence:

let mut word_count = HashMap::new();
for word in text.split_whitespace() {
    word_count.entry(word)
        .and_modify(|count| *count += 1)
        .or_insert(1);
}

If the key is absent, and_modify does nothing and or_insert fires. If present, and_modify fires and or_insert is skipped. The chain still incurs only one lookup.

Iteration Patterns

Iterating over a map is the same for both collections, but the order of elements is dramatically different.

Consuming vs Borrowing Iterators

All maps provide three main iteration methods:

• iter() — returns an iterator of (&K, &V); the map remains usable afterward.
• iter_mut() — returns (&K, &mut V); you can modify values but not keys.
• into_iter() — consumes the map and yields (K, V) owned pairs.

let mut hmap = HashMap::from([("a", 1), ("b", 2)]);
// Borrowed iteration — map still valid
for (key, val) in hmap.iter() {
    println!("{key}: {val}");
}
// Mutable borrow — modify values
for (_, val) in hmap.iter_mut() {
    *val *= 10;
}
// Consuming iteration — hmap is gone after this
let owned_pairs: Vec<(&str, i32)> = hmap.into_iter().collect();

For HashMap, the iteration order is arbitrary and can change between runs or even between insertions. For BTreeMap, the order is always ascending by key.

Key and Value Iterators

Sometimes you only need the keys or only the values. keys() and values() return iterators without the other half, saving you from destructuring when you don’t need it.

let bmap = BTreeMap::from([(2, "two"), (1, "one")]);
for k in bmap.keys() {
    println!("Key: {k}");
}
// Prints 1 then 2

Because BTreeMap is sorted, keys() gives you the natural ordering for free. With HashMap, keys() yields an arbitrary order.

Capacity, Performance, and Hashing

Both maps manage memory automatically, but understanding how they grow helps you avoid invisible performance costs.

HashMap Capacity

HashMap maintains a capacity — the number of elements it can hold before needing to reallocate. When the map exceeds its load factor, it allocates a larger table and re‑hashes every key. That occasional O(n) copy can cause latency spikes if you are building the map in a hot loop. When you know the final size, pre‑allocation eliminates this cost entirely.

let mut map = HashMap::with_capacity(10_000);
for i in 0..10_000 {
    map.insert(i, i * 2);
}
// No reallocation happened — all inserts were O(1) without spikes

with_capacity is the most direct way to pre‑allocate. For an existing map, reserve(additional) ensures enough room for at least that many more insertions.

The default hasher, SipHash‑1‑3, is designed to be resistant to HashDoS attacks — a malicious user cannot craft keys that all collide to degrade performance to O(n). The trade‑off is that SipHash is slower than some non‑cryptographic hash functions. For workloads that are purely internal and trust their inputs, you can swap in a faster hasher like FxHash from the rustc-hash crate by using HashMap::with_hasher. This is an advanced tweak; for most programs, the default is the right choice.

BTreeMap Performance

BTreeMap does not have a capacity concept — it allocates a new tree node for every B‑1 to 2B‑1 entries. The allocation pattern is more granular, but the tree depth remains small because each node holds many entries. This data layout is cache‑friendly: comparing against a node’s sorted array accesses memory sequentially, unlike the pointer‑chasing of a binary search tree.

Operations are reliably O(log n) regardless of the distribution of keys. There is no notion of a worst‑case “collision storm” — two keys that are close together simply land near each other in the sorted structure.

Using Custom Key Types

Both maps work seamlessly with any type that implements the required traits. For most structs, you can derive everything.

HashMap Keys

A HashMap key needs Hash and Eq (plus PartialEq). The standard derive macros handle this correctly, ensuring that two equal values produce the same hash.

use std::collections::HashMap;
#[derive(Hash, Eq, PartialEq, Debug)]
struct UserId {
    tenant: String,
    id: u64,
}
let mut sessions = HashMap::new();
let uid = UserId { tenant: "acme".into(), id: 12345 };
sessions.insert(uid, "session_abc123");

BTreeMap Keys

A BTreeMap key needs Ord (and PartialOrd, Eq). When deriving Ord, the fields are compared in declaration order.

use std::collections::BTreeMap;
#[derive(Ord, PartialOrd, Eq, PartialEq, Debug)]
struct Version {
    major: u32,
    minor: u32,
    patch: u32,
}
let mut releases = BTreeMap::new();
releases.insert(Version { major: 2, minor: 0, patch: 0 }, "First 2.0 release");
releases.insert(Version { major: 1, minor: 5, patch: 3 }, "Security fix");
// Iteration visits keys in ascending order: 1.5.3 then 2.0.0

Summary

HashMap and BTreeMap answer two different performance questions. HashMap gives you the fastest key‑value lookups when order does not matter, making it the default for caches, counters, and associative arrays. BTreeMap keeps the keys sorted at all times, which turns range queries and ordered iteration into first‑class operations. The entry API unifies both maps under a safe, single‑lookup pattern for inserting, updating, or modifying entries, and iter, keys, and values make traversal straightforward.

The decision chain is short: if you need sorted output or range queries today, pick BTreeMap; otherwise, start with HashMap. Because their public interfaces are nearly identical, changing your mind later is painless.