HashMap and HashSet

Why a map?

Looking up a student's marks in a Vec of pairs means checking every pair until you find the name: slow for a big class. A hash map stores values by key, so lookup is about the same speed whether it holds 10 items or 10 million. A key is what you search by (a roll number, a city name); the value is what you get back.

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("rice"), 35);   // replaces 40

    println!("{:?}", stock.get("rice"));      // Some(35)
    println!("{:?}", stock.get("ghee"));      // None
    println!("{}", stock.len());              // 2
}

Hashing means turning a key into a number that tells the map where to store the value. You do not need the details; just know that keys must support hashing and equality (types like String, integers, char and bool do).

Ownership in maps

insert moves owned values like String into the map; the map now owns them. Copy values like u32 are copied. get gives back a reference to the value inside the map, so the map keeps ownership.

The entry API: insert or update

A very common job is "if the key exists, update it; otherwise insert a starting value". The entry API does this in one step. entry(key) looks up the key, or_insert(start) inserts the start value if missing, and both return a mutable reference to the value.

use std::collections::HashMap;

fn main() {
    let text = "chai samosa chai jalebi chai samosa";
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    println!("{:?}", counts.get("chai"));   // Some(3)
}

Looping and order

for (item, qty) in &stock {
    println!("{item}: {qty}");
}

Other useful methods

HashSet: unique items

A HashSet<T> is like a HashMap with keys only. It stores each value once and answers "is this in the set?" quickly. insert returns false if the value was already there, which is handy for spotting duplicates.

use std::collections::HashSet;

fn main() {
    let mut seen = HashSet::new();
    for phone in ["98", "97", "98", "96"] {
        if !seen.insert(phone) {
            println!("duplicate: {phone}");    // duplicate: 98
        }
    }
    let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
    let b: HashSet<i32> = [2, 3, 4].into_iter().collect();
    let common: HashSet<_> = a.intersection(&b).collect();
    println!("{}", common.len());              // 2
}

Common mistakes

• Forgetting use std::collections::HashMap;. The compiler error suggests the import.
• Expecting insertion order when printing. Use BTreeMap or sort the keys.
• Writing two steps (get, then insert) to update a count. Use entry(...).or_insert(...).
• Using f64 as a key. Floats cannot be hashed in std because NaN is not equal to itself; use integers (like paise) or strings.