HashMap & BTreeMap

A phone book links names to numbers, a shop links items to stock levels, an election links cities to vote counts. Whenever you look things up by a key rather than by position, you want a map. Rust's standard library has two: HashMap, the fast general-purpose choice, and BTreeMap, which keeps its keys sorted.

In this lesson you will create maps, read and update values safely, use the entry API to count and group data, and learn the one rule that trips up everyone: a HashMap has no fixed order.

Creating and using a HashMap

HashMap is not in the prelude, so import it with use std::collections::HashMap;. Keys must all have one type and values another:

use std::collections::HashMap;

fn main() {
    let mut stock: HashMap<String, u32> = HashMap::new();
    stock.insert(String::from("rice"), 40);
    stock.insert(String::from("dal"), 25);
    stock.insert(String::from("atta"), 18);

    println!("Items: {}", stock.len());
    println!("Rice: {:?}", stock.get("rice"));
    println!("Sugar: {:?}", stock.get("sugar"));

    stock.insert(String::from("dal"), 30);         // replaces 25
    if let Some(qty) = stock.get_mut("atta") {
        *qty -= 3;
    }
    let removed = stock.remove("rice");
    println!("Removed rice: {removed:?}");
    println!("Has rice? {}", stock.contains_key("rice"));

    let mut items: Vec<_> = stock.iter().collect();
    items.sort();
    println!("{items:?}");
}

Items: 3
Rice: Some(40)
Sugar: None
Removed rice: Some(40)
Has rice? false
[("atta", 15), ("dal", 30)]

• get returns an Option, because the key may be missing. Even though the keys are String, you can look them up with a plain &str such as "rice".
• insert with an existing key replaces the old value. get_mut gives a mutable reference for changing a value in place.
• remove returns the removed value in an Option.
• Inserting a String key or value moves it into the map; the map owns its contents.
• HashMap::from([("rice", 40), ("dal", 25)]) builds a small map in one line.

HashMap order is random

A HashMap stores entries according to a hash of each key (a number calculated from the key), and Rust deliberately mixes a random seed into that calculation to protect servers against attackers who send many keys with colliding hashes. As a result, looping over a HashMap gives the entries in an order that can change from run to run.

Never rely on that order and never show it to users. In the example above we collected the entries into a vector and sorted it before printing. Another common pattern is to sort the keys:

// stock as above
let mut names: Vec<&String> = stock.keys().collect();
names.sort();
for name in names {
    println!("{name}: {}", stock[name]);
}

atta: 15
dal: 30

stock[name] reads a value directly; like vector indexing, it panics if the key is missing, so use it only for keys you know exist. If you need sorted output often, use a BTreeMap instead.

BTreeMap: always sorted by key

A BTreeMap has almost the same methods as a HashMap, but it keeps its keys in sorted order, so iteration and printing are predictable. Here it counts votes with the entry API:

use std::collections::BTreeMap;

fn main() {
    let votes = ["Pune", "Jaipur", "Pune", "Kochi", "Jaipur", "Pune"];
    let mut tally: BTreeMap<&str, u32> = BTreeMap::new();

    for city in votes {
        *tally.entry(city).or_insert(0) += 1;
    }

    println!("{tally:?}");
    for (city, count) in &tally {
        println!("{city:<8}{count}");
    }
}

{"Jaipur": 2, "Kochi": 1, "Pune": 3}
Jaipur  2
Kochi   1
Pune    3

entry(city) looks up the key once and returns an Entry. or_insert(0) inserts 0 if the key is new, and either way returns a mutable reference to the value, which *... += 1 increases. This replaces the clumsy "check with contains_key, then insert or update" pattern, and it does only one lookup.

More entry API: grouping and updating

The entry API has more helpers. or_default() inserts the type's default value (0, an empty Vec, an empty String), and and_modify changes an existing value:

use std::collections::BTreeMap;

fn main() {
    let students = [("Aarav", 'A'), ("Isha", 'B'), ("Kabir", 'A'), ("Meera", 'C'), ("Rohan", 'B')];
    let mut by_section: BTreeMap<char, Vec<&str>> = BTreeMap::new();
    for (name, section) in students {
        by_section.entry(section).or_default().push(name);
    }
    println!("{by_section:#?}");

    let mut fees: BTreeMap<&str, u32> = BTreeMap::new();
    fees.insert("Aarav", 5000);
    for name in ["Aarav", "Isha"] {
        fees.entry(name).and_modify(|f| *f += 500).or_insert(4500);
    }
    println!("{fees:?}");
}

{
    'A': [
        "Aarav",
        "Kabir",
    ],
    'B': [
        "Isha",
        "Rohan",
    ],
    'C': [
        "Meera",
    ],
}
{"Aarav": 5500, "Isha": 4500}

For each student, entry(section).or_default() returns the vector for that section, creating an empty one the first time, and push adds the name. In the fees loop, Aarav already had a fee, so and_modify added 500 to it; Isha was new, so and_modify did nothing and or_insert(4500) created her entry. The |f| *f += 500 part is a closure that receives a mutable reference to the existing value.

Sets and custom keys

HashSet and BTreeSet are maps with keys only: use them to keep unique values or to test membership quickly (insert returns false when the value was already there). For your own key types, derive the traits the map needs:

use std::collections::HashSet;

#[derive(Debug, PartialEq, Eq, Hash)]
struct Seat {
    coach: char,
    number: u8,
}

fn main() {
    let mut booked = HashSet::new();
    println!("{}", booked.insert(Seat { coach: 'B', number: 12 }));
    println!("{}", booked.insert(Seat { coach: 'B', number: 12 }));
    println!("Seats booked: {}", booked.len());
}

true
false
Seats booked: 1

Common mistakes

• Printing a HashMap directly in output that users or tests see. The order changes between runs. Sort first or use a BTreeMap.
• Using map[key] for keys that may be missing. It panics; use get.
• Checking contains_key and then inserting. That is two lookups and more code. Use entry.
• Using f64 as a key. Floats implement neither Hash nor Ord. Store amounts as integers (paise) if they must be keys.

Key points

• HashMap<K, V> maps keys to values; get returns an Option, insert replaces, remove returns the old value.
• A HashMap's iteration order is unpredictable; sort the entries or use BTreeMap for ordered output.
• BTreeMap keeps keys sorted and supports ranges; keys need Ord instead of Hash.
• The entry API (entry().or_insert(), or_default(), and_modify()) counts, groups and updates with one lookup.
• Maps own their keys and values; custom key types derive PartialEq, Eq and Hash (or Ord for B-trees).

use std::collections::BTreeMap;

fn main() {
    let text = "the quick fox and the lazy dog and the cat";
    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();

    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }

    for (word, n) in &counts {
        println!("{word}: {n}");
    }

    let mut best = ("", 0);
    for (word, n) in &counts {
        if *n > best.1 {
            best = (*word, *n);
        }
    }
    println!("Most frequent: {} ({} times)", best.0, best.1);
}

and: 2
cat: 1
dog: 1
fox: 1
lazy: 1
quick: 1
the: 3
Most frequent: the (3 times)