HashMap & BTreeMap

HashMap offers fast average lookups. BTreeMap keeps keys sorted for range queries and deterministic iteration.

Recipe

use std::collections::HashMap;
 
fn count_words(text: &str) -> HashMap<&str, u32> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    counts
}

When to reach for this: Frequency tables, indexes, caches - pick BTreeMap when order or range scans matter.

Working Example

use std::collections::BTreeMap;
 
fn top3(scores: BTreeMap<&str, i32>) -> Vec<(&str, i32)> {
    let mut v: Vec<_> = scores.into_iter().collect();
    v.sort_by(|a, b| b.1.cmp(&a.1));
    v.truncate(3);
    v
}

What this demonstrates:

BTreeMap iterates keys in order
Convert to Vec for custom sort by value
entry API avoids double lookup in counts example

Deep Dive

HashMap needs BuildHasher (default RandomState). BTreeMap needs Ord keys. entry returns OccupiedEntry / VacantEntry.

Gotchas

Non-Ord key in BTreeMap - floats without wrapper fail. Fix: OrderedFloat or integer key.
HashDoS - Default hasher ok for apps; consider ahash/fxhash for perf (crates).
Iterating while mutating - Use entry not get+insert separately.
Key borrowing lookup - map.get("str") for String keys via Borrow.
Capacity - HashMap::with_capacity(n) reduces realloc.

Alternatives

Alternative	Use When	Don't Use When
`IndexMap`	Insertion order	Std only policy
`DashMap`	Concurrent map	Single-threaded
`Vec` of pairs	Tiny n	Large lookup tables

FAQs

entry or_insert?

Insert default if vacant.

and_modify?

Update occupied in chain.

range BTreeMap?

range((Bound, Bound)).

hash key own?

Keys owned unless &str with lifetime.

serde map?

JSON object maps.

eq keys?

Requires Eq + Hash for HashMap.

swap_remove Vec?

Not maps - remove on HashMap O(1) avg.

raw_entry?

Advanced entry API unstable/experimental paths.

no_std hash?

hashbrown in alloc ecosystems.

profile?

Count realloc in hot maps.

Stack versions: This page was written for Rust 1.97.0 (edition 2024), Tokio 1.x, Axum 0.8, serde 1.0, sqlx 0.8, clap 4, and Polars 0.46+.

Recipe

use std::collections::HashMap;
 
fn count_words(text: &str) -> HashMap<&str, u32> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    counts
}

When to reach for this: Frequency tables, indexes, caches - pick BTreeMap when order or range scans matter.

Working Example

use std::collections::BTreeMap;
 
fn top3(scores: BTreeMap<&str, i32>) -> Vec<(&str, i32)> {
    let mut v: Vec<_> = scores.into_iter().collect();
    v.sort_by(|a, b| b.1.cmp(&a.1));
    v.truncate(3);
    v
}

What this demonstrates:

BTreeMap iterates keys in order
Convert to Vec for custom sort by value
entry API avoids double lookup in counts example

Deep Dive

HashMap needs BuildHasher (default RandomState). BTreeMap needs Ord keys. entry returns OccupiedEntry / VacantEntry.

Gotchas

Non-Ord key in BTreeMap - floats without wrapper fail. Fix: OrderedFloat or integer key.
HashDoS - Default hasher ok for apps; consider ahash/fxhash for perf (crates).
Iterating while mutating - Use entry not get+insert separately.
Key borrowing lookup - map.get("str") for String keys via Borrow.
Capacity - HashMap::with_capacity(n) reduces realloc.

Alternatives

Alternative	Use When	Don't Use When
`IndexMap`	Insertion order	Std only policy
`DashMap`	Concurrent map	Single-threaded
`Vec` of pairs	Tiny n	Large lookup tables

FAQs

entry or_insert?

Insert default if vacant.

and_modify?

Update occupied in chain.

range BTreeMap?

range((Bound, Bound)).

hash key own?

Keys owned unless &str with lifetime.

serde map?

JSON object maps.

eq keys?

Requires Eq + Hash for HashMap.

swap_remove Vec?

Not maps - remove on HashMap O(1) avg.

raw_entry?

Advanced entry API unstable/experimental paths.

no_std hash?

hashbrown in alloc ecosystems.

profile?

Count realloc in hot maps.

Stack versions: This page was written for Rust 1.97.0 (edition 2024), Tokio 1.x, Axum 0.8, serde 1.0, sqlx 0.8, clap 4, and Polars 0.46+.

HashMap & BTreeMap

Search Documentation

HashMap & BTreeMap