Collections · about 45 min

HashMap and BTreeMap

Why this matters

A list answers "what is at position 3?". Many questions are instead "what is the value for this key?": the phone number for a name, the count for a word, the configuration value for a setting. A map stores key-value pairs and finds a value by its key quickly. Rust's standard library has two: HashMap, the fast general-purpose choice, and BTreeMap, which keeps keys sorted. Word counting, grouping, caching and indexing are all a few lines with them.

HashMap basics

use std::collections::HashMap;

fn main() {
    let mut ages: HashMap<String, u32> = HashMap::new();
    ages.insert(String::from("Ada"), 36);
    ages.insert(String::from("Alan"), 41);
    ages.insert(String::from("Ada"), 37);

    println!("{:?}", ages.get("Ada"));
    println!("{:?}", ages.get("Grace"));
    println!("{}", ages.contains_key("Alan"));
    println!("{}", ages.len());
    if let Some(a) = ages.get_mut("Alan") {
        *a += 1;
    }
    println!("{}", ages["Alan"]);
    let removed = ages.remove("Ada");
    println!("{:?} {}", removed, ages.len());
}
Some(37)
None
true
2
42
Some(37) 1

How a hash map works

A HashMap is an array of buckets. To store a key, it computes a hash, a number derived from the key's bytes, and uses it to pick a bucket:

 hash("Ada")  = 0x9f3a...  -> bucket 5
 hash("Alan") = 0x11c0...  -> bucket 2

 buckets:  0     1     2           3     4     5          6     7
         [   ] [   ] [Alan:41]   [   ] [   ] [Ada:37]   [   ] [   ]

Lookup computes the same hash and goes straight to the bucket, so it takes about the same time whether the map has ten entries or ten million ("O(1) on average"). Collisions (two keys in one bucket) are handled internally; when the map gets too full it allocates a bigger array and redistributes everything, like a Vec growing.

Two consequences:

  1. Keys must be hashable and comparable: they implement the Hash and Eq traits. Strings, integers, char, bool and tuples of these do; f64 does not (NaN breaks equality). You can derive them for your own types (module 10).
  2. Iteration order is unspecified. It depends on hashes, and Rust randomizes the hash function per process (to defend against attackers who craft colliding keys). The same program can print a HashMap in a different order on every run. Never rely on HashMap order in output: sort first, or use a BTreeMap.

Ownership: the map owns its keys and values

insert moves the key and value into the map:

use std::collections::HashMap;

fn main() {
    let name = String::from("Ada");
    let mut m = HashMap::new();
    m.insert(name, 1);
    println!("{name}");
}
error[E0382]: borrow of moved value: `name`
 --> main.rs:7:15
  |
4 |     let name = String::from("Ada");
  |         ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
5 |     let mut m = HashMap::new();
6 |     m.insert(name, 1);
  |              ---- value moved here
7 |     println!("{name}");
  |               ^^^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
6 |     m.insert(name.clone(), 1);
  |                  ++++++++

Copy types like integers are copied as usual. References can be stored too (HashMap<&str, u32>), but then the map borrows from whatever owns those strings and cannot outlive it; owned String keys are the simple choice.

The entry API

The most common map operation is "update the value for this key, creating it if missing". The entry API does it with one lookup:

use std::collections::HashMap;

fn main() {
    let text = "one fish two fish red fish blue fish";
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    let mut sorted: Vec<_> = counts.iter().collect();
    sorted.sort();
    println!("{:?}", sorted);

    let mut by_len: HashMap<usize, Vec<&str>> = HashMap::new();
    for word in text.split_whitespace() {
        by_len.entry(word.len()).or_default().push(word);
    }
    println!("{:?}", by_len.get(&4));
}
[("blue", 1), ("fish", 4), ("one", 1), ("red", 1), ("two", 1)]
Some(["fish", "fish", "fish", "blue", "fish"])

map.entry(key) returns an Entry, a view of the slot for that key, occupied or vacant. or_insert(v) inserts v if vacant and returns a &mut V to the value either way, so *... += 1 updates it in place. or_default() inserts the type's default (0, empty Vec, empty String); or_insert_with(|| ...) computes the initial value only when needed. This is the idiom for counting and grouping.

BTreeMap: sorted keys

BTreeMap has nearly the same API but keeps entries sorted by key (keys implement Ord). Lookups take O(log n), slightly slower than hashing, and iteration is in key order, which makes output deterministic:

use std::collections::BTreeMap;

fn main() {
    let mut stock = BTreeMap::new();
    stock.insert("pear", 4);
    stock.insert("apple", 12);
    stock.insert("fig", 0);
    stock.insert("banana", 7);
    for (fruit, n) in &stock {
        println!("{fruit:<8}{n:>3}");
    }
    println!("{:?}", stock.first_key_value());
    let some: Vec<_> = stock.range("b".."g").collect();
    println!("{:?}", some);
}
apple    12
banana    7
fig       0
pear      4
Some(("apple", 12))
[("banana", 7), ("fig", 0)]

It also supports range queries (range(a..b)), first and last entries, and ordered traversal, which a HashMap cannot do.

Iterating a map

use std::collections::BTreeMap;

fn main() {
    let mut m = BTreeMap::from([("a", 1), ("b", 2), ("c", 3)]);
    for (k, v) in &m {
        print!("{k}={v} ");
    }
    println!();
    for v in m.values_mut() {
        *v *= 10;
    }
    let keys: Vec<_> = m.keys().collect();
    println!("{:?} {:?}", keys, m);
    let total: i32 = m.values().sum();
    println!("{total}");
}
a=1 b=2 c=3 
["a", "b", "c"] {"a": 10, "b": 20, "c": 30}
60

&map yields (&K, &V) pairs, &mut map yields (&K, &mut V) (keys can never be changed in place, since that would break the map's organization), and map by value yields owned (K, V) pairs. keys(), values() and values_mut() iterate one side.

Choosing

Common mistakes

Recap

Going further: read the docs for std::collections (the module page), which compares all the collections and their costs in a table.

Exercises

Exercise 1 · write code

Count words

Read all of stdin, split it into words with split_whitespace, lowercase each word, and count how often each occurs using a HashMap<String, usize> and the entry API. Print the words sorted by count (highest first), breaking ties alphabetically, one per line as word count:

the 3
cat 2
a 1
sat 1

for the input The cat sat the CAT the a. (Punctuation is not handled: sat. would count as its own word.)

File: main.rs

Starting point

use std::collections::HashMap;
use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut counts: HashMap<String, usize> = HashMap::new();
}

Example

input

The cat sat the CAT the a

expected output

the 3
cat 2
a 1
sat 1

Example

input

b a
c b
a b

expected output

b 3
a 2
c 1
Hint 1

*counts.entry(word.to_lowercase()).or_insert(0) += 1; counts one word.

Hint 2

HashMap order is unpredictable: collect into a Vec<(String, usize)> and sort it.

Hint 3

pairs.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0))) sorts by count descending, then word ascending.

Reference solution
use std::collections::HashMap;
use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut counts: HashMap<String, usize> = HashMap::new();
    for word in input.split_whitespace() {
        *counts.entry(word.to_lowercase()).or_insert(0) += 1;
    }
    let mut pairs: Vec<(String, usize)> = counts.into_iter().collect();
    pairs.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
    for (w, c) in pairs {
        println!("{w} {c}");
    }
}

Exercise 2 · write code

Group by key with BTreeMap

Input lines are name score (score an integer). A student can appear several times. Using a BTreeMap<String, Vec<u32>>, collect all scores per student, then print the students in alphabetical order with their scores in input order and their average (one decimal):

ada: [90, 80] avg 85.0
bob: [70] avg 70.0

for the input lines bob 70, ada 90, ada 80.

File: main.rs

Starting point

use std::collections::BTreeMap;
use std::io;

fn main() {
    let mut scores: BTreeMap<String, Vec<u32>> = BTreeMap::new();
    for line in io::stdin().lines() {
        let line = line.unwrap();
        let (name, score) = line.trim().split_once(' ').unwrap();
        let score: u32 = score.parse().unwrap();
    }
}

Example

input

bob 70
ada 90
ada 80

expected output

ada: [90, 80] avg 85.0
bob: [70] avg 70.0

Example

input

zed 1
zed 2
zed 4
amy 100

expected output

amy: [100] avg 100.0
zed: [1, 2, 4] avg 2.3
Hint 1

scores.entry(name.to_string()).or_default().push(score); creates an empty Vec on first sight and appends.

Hint 2

A BTreeMap iterates in key order, so for (name, list) in &scores is already alphabetical.

Reference solution
use std::collections::BTreeMap;
use std::io;

fn main() {
    let mut scores: BTreeMap<String, Vec<u32>> = BTreeMap::new();
    for line in io::stdin().lines() {
        let line = line.unwrap();
        let (name, score) = line.trim().split_once(' ').unwrap();
        let score: u32 = score.parse().unwrap();
        scores.entry(name.to_string()).or_default().push(score);
    }
    for (name, list) in &scores {
        let sum: u32 = list.iter().sum();
        let avg = sum as f64 / list.len() as f64;
        println!("{name}: {:?} avg {:.1}", list, avg);
    }
}

Exercise 3 · quiz

Choosing a map

Which statements are true? Select all that apply.

Answer

  • HashMap lookups take about the same time regardless of the number of entries (on average)

  • BTreeMap iterates its entries sorted by key

  • map.insert(key, value) takes ownership of both key and value

HashMap gives average O(1) lookups but an unspecified iteration order that can change between runs (Rust randomizes the hash seed). BTreeMap keeps keys sorted, with O(log n) operations. Inserting moves the key and value into the map. Indexing with map[&key] panics on a missing key; use get for an Option.