HashMap and BTreeMap
A map stores a value under a key: HashMap hashes the key and BTreeMap keeps it in order. Both need a key type with the right traits, and both return an Option from a lookup, which is the type from Option doing its job.
The lesson covers insert and get, the entry API that counts without a second lookup, a word count, the ordered map, and the error for a key of the wrong type. Iteration order of a HashMap is not specified, so the programs sort before printing.
insert and get
insert takes the key and the value, and get takes a reference to a key and returns an Option of a reference to the value. Inserting a key that exists replaces the value and returns the old one.
The program stores two scores, prints the length, and looks up a key that exists and one that does not. The second lookup prints None.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::new();
scores.insert(String::from("ada"), 36);
scores.insert(String::from("alan"), 41);
println!("{}", scores.len());
println!("{:?}", scores.get("ada"));
println!("{:?}", scores.get("grace"));
}
rustc --edition 2024 insert.rs
./insert
2
Some(36)
None
The lookup borrows the map, so the map is still usable afterwards. The lesson on borrowing explains why the key is passed by reference.
The entry API
entry(key).or_insert(0) looks the key up once and returns a mutable reference to the value, inserting the default when the key is absent. That single call replaces the if contains and insert pair and counts in one pass.
The program counts three letters and prints the counts for two of them. The reference is written through, which is why the count changes.
use std::collections::HashMap;
fn main() {
let mut counts = HashMap::new();
for word in ["a", "b", "a", "a"] {
let count = counts.entry(word).or_insert(0);
*count += 1;
}
println!("{:?}", counts.get("a"));
println!("{:?}", counts.get("b"));
}
rustc --edition 2024 entry.rs
./entry
Some(3)
Some(1)
The entry type has other methods for the absent case, such as or_default and and_modify. The standard word count is the next section.
Counting words
A word count is the entry API in a loop over split_whitespace. The map keys are string slices borrowed from the text, and the values are the counts.
The program counts the words of a sentence, copies the pairs into a vector and sorts them, because the iteration order of a HashMap is not the insertion order. The output is alphabetical with the count of each word.
use std::collections::HashMap;
fn main() {
let text = "the quick brown fox jumps over the lazy dog the end";
let mut counts = HashMap::new();
for word in text.split_whitespace() {
*counts.entry(word).or_insert(0) += 1;
}
let mut pairs: Vec<(&&str, &i32)> = counts.iter().collect();
pairs.sort();
for (word, count) in pairs {
println!("{word} {count}");
}
}
rustc --edition 2024 word_count.rs
./word_count
brown 1
dog 1
end 1
fox 1
jumps 1
lazy 1
over 1
quick 1
the 3
The keys borrow the sentence, so the map cannot outlive it. The lesson on text files reads the sentence from a file and keeps the same shape.
BTreeMap keeps the order
A BTreeMap has the same API and keeps the keys sorted, so iteration is deterministic without a sort. The price is a logarithm per operation instead of a constant, and the keys must implement Ord.
The program inserts three names in a scrambled order and prints them. The output is alphabetical because the map keeps the order.
use std::collections::BTreeMap;
fn main() {
let mut ages = BTreeMap::new();
ages.insert("grace", 85);
ages.insert("ada", 36);
ages.insert("alan", 41);
for (name, age) in &ages {
println!("{name} {age}");
}
}
rustc --edition 2024 btree.rs
./btree
ada 36
alan 41
grace 85
The choice between the two is the one from the C++ page: a hash map for lookups and a tree for ordered reports. The lesson on sets makes the same choice.
A key of the wrong type
The key type is part of the map type, and insert checks it. A map from strings to integers cannot take an integer key, and the compiler reports E0308 with the expected type.
The program inserts an integer into a map declared with string keys. The note points at the map type, and the fix is a conversion or a different map.
use std::collections::HashMap;
fn main() {
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(1, 36);
println!("{:?}", scores.get("ada"));
}
rustc --edition 2024 key_type_err.rs
error[E0308]: mismatched types
--> key_type_err.rs:5:19
|
5 | scores.insert(1, 36);
| ------ ^ expected `String`, found integer
| |
| arguments to this method are incorrect
|
note: method defined here
--> /rustc/31fca3adb283cc9dfd56b49cdee9a96eb9c96ffd/library/std/src/collections/hash/map.rs:1328:11
help: try using a conversion method
|
5 | scores.insert(1.to_string(), 36);
| ++++++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0308`.
A type used as a key needs Hash and Eq for a HashMap, which is why a float cannot be one: the next lesson shows the same rule for sets.
Exercises
- Build a map from names to ages and print the age of one name, handling the missing case.
- Count the letters of a word with the entry API and print the counts in alphabetical order.
- Use a BTreeMap for the same count and compare the loop that prints it.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
getreturn for a missing key?Answer
None
The lookup is fallible, so the result is an Option.
-
What does
entry(key).or_insert(0)do?Answer
Looks the key up once and inserts the default when it is absent
The entry API gives a mutable slot, inserting the fallback only when needed.
-
Why is a HashMap iteration order not reliable?
Answer
The hashing decides the bucket order
The order follows the hash buckets, which is why the program sorts before printing.
-
What does a BTreeMap require of its keys?
Answer
Ord
The tree keeps the keys in order and needs a comparison to do it.
-
What does this program print?
use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert(String::from("ada"), 36); scores.insert(String::from("alan"), 41); println!("{}", scores.len()); println!("{:?}", scores.get("ada")); }Answer
2 / Some(36)
Both keys are stored, and the lookup returns the value in an Option.
-
What does this program print?
use std::collections::HashMap; fn main() { let mut counts = HashMap::new(); for word in ["a", "b", "a", "a"] { let count = counts.entry(word).or_insert(0); *count += 1; } println!("{:?}", counts.get("a")); println!("{:?}", counts.get("b")); }Answer
Some(3) / Some(1)
The first word appears three times and the second once.
-
What does this program print?
use std::collections::BTreeMap; fn main() { let mut ages = BTreeMap::new(); ages.insert("grace", 85); ages.insert("ada", 36); for (name, age) in &ages { println!("{name} {age}"); } }Answer
ada 36 / grace 85
The tree keeps the keys sorted, so ada comes before grace whatever the insertion order.
-
What does this program print?
use std::collections::HashMap; fn main() { let mut map = HashMap::new(); map.insert("a", 1); let old = map.insert("a", 2); println!("{:?} {:?}", old, map.get("a")); }Answer
Some(1) Some(2)
The second insert replaces the value and returns the old one.
-
What is the first line of the compiler output for this program?
use std::collections::HashMap; fn main() { let mut scores: HashMap<String, i32> = HashMap::new(); scores.insert(1, 36); println!("{:?}", scores.get("ada")); }Answer
error[E0308]: mismatched types
The map wants a String key and the insert passes an integer.
-
What does this program print?
use std::collections::HashMap; fn main() { let text = "a b a"; let mut counts = HashMap::new(); for word in text.split_whitespace() { *counts.entry(word).or_insert(0) += 1; } println!("{}", counts.len()); println!("{:?}", counts.get("a")); }Answer
2 / Some(2)
There are two distinct words, and the first one appears twice.
The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev