HashMap & BTreeMap

When you need to look things up by key rather than position, you reach for a map. Rust's workhorse is HashMap<K, V>, with BTreeMap as the sorted alternative.

HashMap basics

HashMap<K, V> stores key-value pairs with average O(1) lookup. insert adds or replaces; get returns an Option<&V> — the key might be absent, so Option appears again. Keys must be hashable and comparable, which most standard types are out of the box.

The entry API

The killer feature is entry: map.entry(key).or_insert(0) gives you a mutable reference to the value, inserting a default if the key is missing. It's the clean way to do 'increment a counter' or 'append to a list per key' without a get-check-insert dance. entry is one of the most-loved methods in the standard library.

entry().or_insert() is the counting idiom. To tally occurrences, *map.entry(word).or_insert(0) += 1; handles both 'first time seen' and 'seen before' in one line and one lookup. Reaching for a manual if contains_key check is the beginner tell — it does two lookups and reads worse.

HashMap vs BTreeMap

HashMap is unordered and fast. BTreeMap keeps keys sorted (so iteration is in order) at a small lookup cost. Choose HashMap by default; reach for BTreeMap when you need sorted iteration or range queries. Same API shape, different ordering guarantee.

Code

Word frequency with the entry API·rust

use std::collections::HashMap;

fn main() {
    let text = "the cat the dog the bird";
    let mut counts: HashMap<&str, u32> = HashMap::new();

    // The entry idiom: insert-or-increment in one line
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }

    // get returns Option — the key might not exist
    println!("the: {:?}", counts.get("the"));   // Some(3)
    println!("fish: {:?}", counts.get("fish")); // None
}

Exercise

Count word frequencies in a sentence using HashMap and the entry().or_insert() idiom. Then swap HashMap for BTreeMap and iterate — notice the keys now come out sorted. When would the sorted iteration of BTreeMap be worth its slightly slower lookups?

Hint

Use BTreeMap when you need deterministic, sorted output (a leaderboard, a report, range queries like 'all keys between A and M'). Use HashMap when you just need fast lookup and order doesn't matter.

HashMap basics

The entry API

HashMap vs BTreeMap

Code

External links

Exercise

Progress

Comments 0