codeloopback
Guide contents

Lesson 42 of 94

HashMap

HashMap<K, V> maps keys to values with average O(1) lookups. You met the basics in A First Look at String, Vec & HashMap; this lesson covers it in depth. The API will feel familiar, with two Rust-specific themes:

  • Ownership: inserting moves the key and value into the map. Reading gives you references.
  • The entry API: one lookup to "get or insert, then update", a single, borrow-checker-friendly tool.

HashMap lives in std::collections, so it needs a use line.

Operation Rust
Insert map.insert(k, v) (returns the old value as Option)
Look up map.get(&k) returns Option<&V>
Look up with a default map.get(&k).copied().unwrap_or(d)
Check for a key map.contains_key(&k)
Remove map.remove(&k) returns Option<V>
Insert lazily if missing map.entry(k).or_insert_with(f)
Count occurrences *map.entry(k).or_insert(0) += 1
Iterate over entries map.iter()
Build from literals HashMap::from([("a", 1)])
Sorted map BTreeMap: BTreeMap & BTreeSet

1. Creating a map and inserting

Rust
use std::collections::HashMap;

fn main() {
    let mut prices: HashMap<String, u32> = HashMap::new();
    prices.insert(String::from("apple"), 120);
    prices.insert(String::from("pear"), 95);
    prices.insert(String::from("kiwi"), 60);
    println!("{} products", prices.len());
    println!("pear costs {:?}", prices.get("pear"));
}
Output
3 products
pear costs Some(95)

2. get returns an Option

A missing key is None, never null, so you can't forget to handle it.

Rust
use std::collections::HashMap;

fn main() {
    let stock = HashMap::from([("apple", 3), ("pear", 0)]);
    for item in ["apple", "pear", "mango"] {
        match stock.get(item) {
            Some(0) => println!("{item}: sold out"),
            Some(n) => println!("{item}: {n} left"),
            None => println!("{item}: not sold here"),
        }
    }
    let mango = stock.get("mango").copied().unwrap_or(0);
    println!("mango count with default: {mango}");
}
Output
apple: 3 left
pear: sold out
mango: not sold here
mango count with default: 0

HashMap::from([...]) builds a map from an array of pairs. .copied() turns the Option<&i32> into an Option<i32>.

3. Indexing with map[key] panics on missing keys

map["key"] is convenient when a missing key would be a bug. For normal lookups, use get.

Rustpanics at runtime
use std::collections::HashMap;

fn main() {
    let config = HashMap::from([("host", "localhost"), ("port", "8080")]);
    println!("{}:{}", config["host"], config["port"]);
    println!("{}", config["timeout"]);
}
Output
localhost:8080

thread 'main' panicked at src/main.rs:6:26:
no entry found for key

4. Inserting moves owned keys and values

A String key is moved into the map. This is the ownership rule from Ownership, not a special map rule.

Rust✗ does not compile · E0382
use std::collections::HashMap;

fn main() {
    let mut sessions = HashMap::new();
    let user = String::from("ana");
    sessions.insert(user, 42);
    println!("inserted session for {user}");
}
Output
error[E0382]: borrow of moved value: `user`
 --> src/main.rs:7:37
  |
5 |     let user = String::from("ana");
  |         ---- move occurs because `user` has type `String`, which does not implement the `Copy` trait
6 |     sessions.insert(user, 42);
  |                     ---- value moved here
7 |     println!("inserted session for {user}");
  |                                     ^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
6 |     sessions.insert(user.clone(), 42);
  |                         ++++++++

Insert a clone if you still need the value, or use the key before inserting it. Keys of Copy types, like integers, are simply copied.

5. Looking up String keys with &str

A HashMap<String, V> can be queried with a &str, no allocation needed. This works through the Borrow trait: a String can be borrowed as a str, and get accepts any borrowed form of the key type.

Rust
use std::collections::HashMap;

fn main() {
    let mut users: HashMap<String, u32> = HashMap::new();
    users.insert(String::from("ana"), 34);
    let name = "ana";
    let owned = String::from("ana");
    println!("{:?} {:?} {:?}", users.get(name), users.get(&owned), users.get("zed"));
}
Output
Some(34) Some(34) None

6. insert returns the previous value

Inserting an existing key replaces the value and hands back the old one.

Rust
use std::collections::HashMap;

fn main() {
    let mut latest_version = HashMap::new();
    println!("{:?}", latest_version.insert("serde", "1.0.200"));
    println!("{:?}", latest_version.insert("serde", "1.0.210"));
    println!("{:?}", latest_version.get("serde"));
}
Output
None
Some("1.0.200")
Some("1.0.210")

7. contains_key, remove, and remove_entry

Rust
use std::collections::HashMap;

fn main() {
    let mut carts = HashMap::from([(101, 3), (102, 1), (103, 7)]);
    println!("{}", carts.contains_key(&102));
    println!("{:?}", carts.remove(&102));
    println!("{:?}", carts.remove(&999));
    println!("{:?}", carts.remove_entry(&103));
    println!("{} carts left", carts.len());
}
Output
true
Some(1)
None
Some((103, 7))
1 carts left

8. Iteration order is not defined

Iteration order is effectively random, and Rust even randomizes it per program run to resist hash-flooding attacks. For stable output, sort the entries, or use a BTreeMap.

Rust
use std::collections::HashMap;

fn main() {
    let scores = HashMap::from([("ben", 71), ("ana", 92), ("cy", 85)]);
    let mut entries: Vec<(&&str, &i32)> = scores.iter().collect();
    entries.sort();
    for (name, score) in entries {
        println!("{name}: {score}");
    }
}
Output
ana: 92
ben: 71
cy: 85

Every other example in this lesson sorts before printing, so the output is the same on every run.

9. keys, values, and values_mut

Rust
use std::collections::HashMap;

fn main() {
    let mut balances = HashMap::from([("ana", 100), ("ben", 250), ("cy", 40)]);
    let total: i32 = balances.values().sum();
    let mut names: Vec<&str> = balances.keys().copied().collect();
    names.sort();
    println!("{:?} total {total}", names);

    for balance in balances.values_mut() {
        *balance += 10; // monthly bonus
    }
    let mut after: Vec<(&str, i32)> = balances.into_iter().collect();
    after.sort();
    println!("{:?}", after);
}
Output
["ana", "ben", "cy"] total 390
[("ana", 110), ("ben", 260), ("cy", 50)]

10. get_mut: change a value in place

Rust
use std::collections::HashMap;

fn main() {
    let mut inventory = HashMap::from([("widget", 10), ("gadget", 3)]);
    if let Some(qty) = inventory.get_mut("widget") {
        *qty -= 4;
    }
    match inventory.get_mut("gizmo") {
        Some(qty) => *qty -= 1,
        None => println!("gizmo not in inventory"),
    }
    println!("{:?}", inventory.get("widget"));
}
Output
gizmo not in inventory
Some(6)

11. The entry API: count occurrences

entry(key) looks the key up once and returns a handle to that slot. or_insert(v) inserts v if the slot is empty and returns a &mut to the value either way.

Rust
use std::collections::HashMap;

fn main() {
    let text = "the cat and the hat and the bat";
    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<(&str, u32)> = counts.into_iter().collect();
    sorted.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
    println!("{:?}", sorted);
}
Output
[("the", 3), ("and", 2), ("bat", 1), ("cat", 1), ("hat", 1)]

12. or_insert_with and or_default

or_insert_with(f) only runs f when the key is missing. or_default() inserts the type's default value (0, empty Vec, ...).

Rust
use std::collections::HashMap;

fn expensive_profile(user: &str) -> String {
    println!("  loading profile for {user}");
    format!("{user}-profile")
}

fn main() {
    let mut cache: HashMap<&str, String> = HashMap::new();
    for user in ["ana", "ben", "ana", "ana"] {
        let profile = cache.entry(user).or_insert_with(|| expensive_profile(user));
        println!("{profile}");
    }

    let mut totals: HashMap<&str, u64> = HashMap::new();
    for (region, amount) in [("eu", 10), ("us", 5), ("eu", 7)] {
        *totals.entry(region).or_default() += amount;
    }
    println!("eu={} us={}", totals["eu"], totals["us"]);
}
Output
  loading profile for ana
ana-profile
  loading profile for ben
ben-profile
ana-profile
ana-profile
eu=17 us=5

13. and_modify(...).or_insert(...)

Update the value if present, otherwise insert a starting value, in one lookup.

Rust
use std::collections::HashMap;

fn main() {
    let mut last_login: HashMap<&str, (u64, u32)> = HashMap::new(); // (timestamp, login count)
    for (user, time) in [("ana", 100), ("ben", 150), ("ana", 300)] {
        last_login
            .entry(user)
            .and_modify(|(t, count)| {
                *t = time;
                *count += 1;
            })
            .or_insert((time, 1));
    }
    let mut v: Vec<_> = last_login.into_iter().collect();
    v.sort();
    println!("{:?}", v);
}
Output
[("ana", (300, 2)), ("ben", (150, 1))]

14. Matching on Entry::Occupied and Entry::Vacant

For full control, match on the entry itself.

Rust
use std::collections::HashMap;
use std::collections::hash_map::Entry;

fn main() {
    let mut usernames: HashMap<String, u32> = HashMap::new();
    for (name, id) in [("ferris", 1), ("gopher", 2), ("ferris", 3)] {
        match usernames.entry(name.to_string()) {
            Entry::Vacant(slot) => {
                slot.insert(id);
                println!("registered {name} as user {id}");
            }
            Entry::Occupied(existing) => {
                println!("'{name}' is taken by user {}", existing.get());
            }
        }
    }
}
Output
registered ferris as user 1
registered gopher as user 2
'ferris' is taken by user 1

15. Why the entry API exists

The "check, then insert" pattern fights the borrow checker: the reference returned by get is still alive when you try to insert.

Rust✗ does not compile · E0499
use std::collections::HashMap;

fn get_or_create<'a>(map: &'a mut HashMap<String, Vec<u32>>, key: &str) -> &'a mut Vec<u32> {
    if let Some(v) = map.get_mut(key) {
        return v;
    }
    map.insert(key.to_string(), Vec::new());
    map.get_mut(key).unwrap()
}

fn main() {}
Output
error[E0499]: cannot borrow `*map` as mutable more than once at a time
 --> src/main.rs:7:5
  |
3 | fn get_or_create<'a>(map: &'a mut HashMap<String, Vec<u32>>, key: &str) -> &'a mut Vec<u32> {
  |                  -- lifetime `'a` defined here
4 |     if let Some(v) = map.get_mut(key) {
  |                      --- first mutable borrow occurs here
5 |         return v;
  |                - returning this value requires that `*map` is borrowed for `'a`
6 |     }
7 |     map.insert(key.to_string(), Vec::new());
  |     ^^^ second mutable borrow occurs here

This is the loop-return limitation from Fixing Borrow Checker Errors. The entry API does it in one lookup, and compiles:

Rust
use std::collections::HashMap;

fn get_or_create<'a>(map: &'a mut HashMap<String, Vec<u32>>, key: &str) -> &'a mut Vec<u32> {
    map.entry(key.to_string()).or_default()
}

fn main() {
    let mut orders: HashMap<String, Vec<u32>> = HashMap::new();
    get_or_create(&mut orders, "ana").push(1001);
    get_or_create(&mut orders, "ana").push(1002);
    println!("{:?}", orders.get("ana"));
}
Output
Some([1001, 1002])

16. Grouping values: HashMap<K, Vec<V>>

Rust
use std::collections::HashMap;

fn main() {
    let orders = [("ana", 30), ("ben", 12), ("ana", 7), ("cy", 50), ("ben", 3), ("ana", 9)];
    let mut by_customer: HashMap<&str, Vec<u32>> = HashMap::new();
    for (customer, amount) in orders {
        by_customer.entry(customer).or_default().push(amount);
    }
    let mut rows: Vec<(&str, Vec<u32>)> = by_customer.into_iter().collect();
    rows.sort();
    for (customer, amounts) in rows {
        let total: u32 = amounts.iter().sum();
        println!("{customer}: {:?} total {total}", amounts);
    }
}
Output
ana: [30, 7, 9] total 46
ben: [12, 3] total 15
cy: [50] total 50

17. Building a map with collect

An iterator of pairs collects into a HashMap. Later duplicates overwrite earlier ones.

Rust
use std::collections::HashMap;

fn main() {
    let users = [(1, "ana"), (2, "ben"), (3, "cy")];
    let by_id: HashMap<u32, &str> = users.iter().copied().collect();
    let name_lengths: HashMap<&str, usize> = users.iter().map(|&(_, n)| (n, n.len())).collect();
    println!("{:?} {:?}", by_id.get(&2), name_lengths.get("cy"));

    let with_duplicates: HashMap<&str, i32> = [("x", 1), ("x", 2)].into_iter().collect();
    println!("{:?}", with_duplicates);
}
Output
Some("ben") Some(2)
{"x": 2}

18. Custom struct keys

Any type implementing Eq and Hash can be a key. Derive them, as in Deriving Standard Traits.

Rust
use std::collections::HashMap;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Cell {
    row: i32,
    col: i32,
}

fn main() {
    let mut board: HashMap<Cell, char> = HashMap::new();
    board.insert(Cell { row: 0, col: 0 }, 'X');
    board.insert(Cell { row: 1, col: 1 }, 'O');
    board.insert(Cell { row: 0, col: 2 }, 'X');
    println!("{:?}", board.get(&Cell { row: 1, col: 1 }));
    println!("{:?}", board.get(&Cell { row: 2, col: 2 }));
    println!("{} pieces placed", board.len());
}
Output
Some('O')
None
3 pieces placed

19. Floats can't be keys

f64 is not Eq (because of NaN) and not Hash, so it can't be a key. Store an integer representation, such as cents or a scaled value.

Rust✗ does not compile · E0599
use std::collections::HashMap;

fn main() {
    let mut by_price: HashMap<f64, &str> = HashMap::new();
    by_price.insert(9.99, "book");
}
Output
error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied
 --> src/main.rs:5:14
  |
5 |     by_price.insert(9.99, "book");
  |              ^^^^^^
  |
  = note: the following trait bounds were not satisfied:
          `f64: Eq`
          `f64: Hash`

20. retain: remove entries matching a condition

Rust
use std::collections::HashMap;

fn main() {
    let mut sessions = HashMap::from([("s1", 100), ("s2", 950), ("s3", 400), ("s4", 1_200)]);
    let now = 1_000;
    let ttl = 500;
    sessions.retain(|_, &mut last_seen| now - last_seen.min(now) < ttl);
    let mut alive: Vec<&str> = sessions.keys().copied().collect();
    alive.sort();
    println!("{:?}", alive);
}
Output
["s2", "s4"]

21. Merging two maps

extend inserts every pair from another map, overwriting existing keys. For combining values, use the entry API.

Rust
use std::collections::HashMap;

fn main() {
    let defaults = HashMap::from([("theme", "light"), ("lang", "en"), ("tz", "UTC")]);
    let user_prefs = HashMap::from([("theme", "dark"), ("tz", "Europe/Lisbon")]);
    let mut effective = defaults.clone();
    effective.extend(user_prefs);
    let mut v: Vec<_> = effective.into_iter().collect();
    v.sort();
    println!("{:?}", v);

    let q1 = HashMap::from([("eu", 100), ("us", 80)]);
    let q2 = HashMap::from([("us", 50), ("apac", 30)]);
    let mut year = q1.clone();
    for (region, sales) in q2 {
        *year.entry(region).or_insert(0) += sales;
    }
    let mut v: Vec<_> = year.into_iter().collect();
    v.sort();
    println!("{:?}", v);
}
Output
[("lang", "en"), ("theme", "dark"), ("tz", "Europe/Lisbon")]
[("apac", 30), ("eu", 100), ("us", 130)]

22. Inverting a map

Rust
use std::collections::HashMap;

fn main() {
    let country_of = HashMap::from([("Lisbon", "PT"), ("Porto", "PT"), ("Berlin", "DE"), ("Munich", "DE"), ("Paris", "FR")]);
    let mut cities_in: HashMap<&str, Vec<&str>> = HashMap::new();
    for (&city, &country) in &country_of {
        cities_in.entry(country).or_default().push(city);
    }
    let mut v: Vec<(&str, Vec<&str>)> = cities_in.into_iter().collect();
    v.sort();
    for (country, cities) in &mut v {
        cities.sort();
        println!("{country}: {:?}", cities);
    }
}
Output
DE: ["Berlin", "Munich"]
FR: ["Paris"]
PT: ["Lisbon", "Porto"]

23. Nested maps

Rust
use std::collections::HashMap;

fn main() {
    let mut permissions: HashMap<&str, HashMap<&str, bool>> = HashMap::new();
    permissions.entry("ana").or_default().insert("deploy", true);
    permissions.entry("ana").or_default().insert("billing", false);
    permissions.entry("ben").or_default().insert("deploy", false);

    let can = |user: &str, action: &str| -> bool {
        permissions.get(user).and_then(|p| p.get(action)).copied().unwrap_or(false)
    };
    println!("{} {} {} {}", can("ana", "deploy"), can("ana", "billing"), can("ben", "deploy"), can("zed", "deploy"));
}
Output
true false false false

24. Capacity

Like Vec, a map grows automatically. with_capacity avoids rehashing when you know the size.

Rust
use std::collections::HashMap;

fn main() {
    let mut index: HashMap<u32, String> = HashMap::with_capacity(1_000);
    let before = index.capacity();
    for i in 0..1_000 {
        index.insert(i, format!("item-{i}"));
    }
    println!("capacity held: {}", index.capacity() == before);
    println!("{:?}", index.get(&999));
}
Output
capacity held: true
Some("item-999")

25. Realistic example: memoized Fibonacci

Rust
use std::collections::HashMap;

fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n <= 1 {
        return n;
    }
    if let Some(&cached) = memo.get(&n) {
        return cached;
    }
    let value = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, value);
    value
}

fn main() {
    let mut memo = HashMap::new();
    println!("fib(90) = {}", fib(90, &mut memo));
    println!("memo holds {} values", memo.len());
}
Output
fib(90) = 2880067194370816120
memo holds 89 values

Without the memo, fib(90) would take around 10¹⁸ calls. With it, each value is computed once.

26. Realistic example: an inventory system

Rust
use std::collections::HashMap;

#[derive(Debug)]
enum StockError {
    Unknown(String),
    Insufficient { sku: String, wanted: u32, have: u32 },
}

struct Inventory {
    stock: HashMap<String, u32>,
}

impl Inventory {
    fn receive(&mut self, sku: &str, qty: u32) {
        *self.stock.entry(sku.to_string()).or_insert(0) += qty;
    }

    fn ship(&mut self, sku: &str, qty: u32) -> Result<u32, StockError> {
        let have = self.stock.get_mut(sku).ok_or_else(|| StockError::Unknown(sku.to_string()))?;
        if *have < qty {
            return Err(StockError::Insufficient { sku: sku.to_string(), wanted: qty, have: *have });
        }
        *have -= qty;
        Ok(*have)
    }

    fn low_stock(&self, threshold: u32) -> Vec<(&str, u32)> {
        let mut low: Vec<(&str, u32)> = self.stock.iter().filter(|&(_, &q)| q <= threshold).map(|(s, &q)| (s.as_str(), q)).collect();
        low.sort();
        low
    }
}

fn main() {
    let mut inv = Inventory { stock: HashMap::new() };
    inv.receive("KB-1", 10);
    inv.receive("MS-2", 3);
    inv.receive("KB-1", 5);
    println!("{:?}", inv.ship("KB-1", 12));
    println!("{:?}", inv.ship("MS-2", 5));
    println!("{:?}", inv.ship("XX-9", 1));
    println!("low stock: {:?}", inv.low_stock(3));
}
Output
Ok(3)
Err(Insufficient { sku: "MS-2", wanted: 5, have: 3 })
Err(Unknown("XX-9"))
low stock: [("KB-1", 3), ("MS-2", 3)]

27. Realistic example: grouping anagrams

The key is each word's letters in sorted order, so all anagrams share a key.

Rust
use std::collections::HashMap;

fn main() {
    let words = ["listen", "silent", "enlist", "google", "inlets", "banana", "gogole", "cat", "act"];
    let mut groups: HashMap<String, Vec<&str>> = HashMap::new();
    for w in words {
        let mut letters: Vec<char> = w.chars().collect();
        letters.sort_unstable();
        let key: String = letters.into_iter().collect();
        groups.entry(key).or_default().push(w);
    }
    let mut result: Vec<Vec<&str>> = groups.into_values().filter(|g| g.len() > 1).collect();
    result.sort();
    println!("{:?}", result);
}
Output
[["cat", "act"], ["google", "gogole"], ["listen", "silent", "enlist", "inlets"]]

28. Realistic example: a per-user rate limiter

Each user has a list of recent request timestamps. Requests older than the window are dropped before checking the limit.

Rust
use std::collections::HashMap;

struct RateLimiter {
    window_ms: u64,
    max_requests: usize,
    history: HashMap<String, Vec<u64>>,
}

impl RateLimiter {
    fn allow(&mut self, user: &str, now_ms: u64) -> bool {
        let times = self.history.entry(user.to_string()).or_default();
        times.retain(|&t| now_ms - t < self.window_ms);
        if times.len() < self.max_requests {
            times.push(now_ms);
            true
        } else {
            false
        }
    }
}

fn main() {
    let mut limiter = RateLimiter { window_ms: 1_000, max_requests: 3, history: HashMap::new() };
    let requests = [("ana", 0), ("ana", 100), ("ben", 150), ("ana", 200), ("ana", 300), ("ana", 1_050), ("ana", 1_120)];
    for (user, t) in requests {
        println!("t={t:>5} {user}: {}", if limiter.allow(user, t) { "allowed" } else { "429 Too Many Requests" });
    }
}
Output
t=    0 ana: allowed
t=  100 ana: allowed
t=  150 ben: allowed
t=  200 ana: allowed
t=  300 ana: 429 Too Many Requests
t= 1050 ana: allowed
t= 1120 ana: allowed

A search index maps each word to the set of documents containing it. A query intersects the lists.

Rust
use std::collections::HashMap;

fn build_index<'a>(docs: &[(u32, &'a str)]) -> HashMap<String, Vec<u32>> {
    let mut index: HashMap<String, Vec<u32>> = HashMap::new();
    for &(id, text) in docs {
        for word in text.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty()) {
            let ids = index.entry(word.to_lowercase()).or_default();
            if ids.last() != Some(&id) {
                ids.push(id);
            }
        }
    }
    index
}

fn search(index: &HashMap<String, Vec<u32>>, query: &str) -> Vec<u32> {
    let mut result: Option<Vec<u32>> = None;
    for word in query.split_whitespace() {
        let ids = index.get(&word.to_lowercase()).cloned().unwrap_or_default();
        result = Some(match result {
            None => ids,
            Some(prev) => prev.into_iter().filter(|id| ids.contains(id)).collect(),
        });
    }
    result.unwrap_or_default()
}

fn main() {
    let docs = [
        (1, "Rust ownership explained"),
        (2, "Borrowing and ownership in Rust"),
        (3, "Java garbage collection"),
        (4, "Rust iterators, fast and lazy"),
    ];
    let index = build_index(&docs);
    for q in ["rust", "rust ownership", "java", "go"] {
        println!("{q:<15} -> {:?}", search(&index, q));
    }
}
Output
rust            -> [1, 2, 4]
rust ownership  -> [1, 2]
java            -> [3]
go              -> []

30. Realistic example: a two-level cache with statistics

Rust
use std::collections::HashMap;

struct PriceCache {
    by_sku: HashMap<String, u64>,
    hits: u32,
    misses: u32,
}

impl PriceCache {
    fn price(&mut self, sku: &str, fetch: impl FnOnce(&str) -> u64) -> u64 {
        if let Some(&p) = self.by_sku.get(sku) {
            self.hits += 1;
            return p;
        }
        self.misses += 1;
        let p = fetch(sku);
        self.by_sku.insert(sku.to_string(), p);
        p
    }
}

fn main() {
    let mut cache = PriceCache { by_sku: HashMap::new(), hits: 0, misses: 0 };
    let catalog = HashMap::from([("KB-1", 12_900), ("MS-2", 3_900)]);
    let mut total = 0;
    for sku in ["KB-1", "MS-2", "KB-1", "KB-1", "MS-2", "XX-0"] {
        total += cache.price(sku, |s| {
            println!("  fetching {s} from catalog service");
            catalog.get(s).copied().unwrap_or(0)
        });
    }
    println!("total {total}, hits {} misses {}", cache.hits, cache.misses);
}
Output
  fetching KB-1 from catalog service
  fetching MS-2 from catalog service
  fetching XX-0 from catalog service
total 46500, hits 3 misses 3

31. Realistic example: finding pairs that sum to a target

The classic "two sum" problem: a map from each value to its index turns an O(n²) search into O(n).

Rust
use std::collections::HashMap;

fn two_sum(prices: &[i64], budget: i64) -> Option<(usize, usize)> {
    let mut seen: HashMap<i64, usize> = HashMap::with_capacity(prices.len());
    for (i, &p) in prices.iter().enumerate() {
        if let Some(&j) = seen.get(&(budget - p)) {
            return Some((j, i));
        }
        seen.insert(p, i);
    }
    None
}

fn main() {
    let gift_prices = [2_500, 1_200, 4_300, 800, 3_700];
    println!("{:?}", two_sum(&gift_prices, 4_900));
    println!("{:?}", two_sum(&gift_prices, 100));
}
Output
Some((1, 4))
None

Summary

  • HashMap<K, V> needs keys that are Eq + Hash. Derive them for your own key types; floats can't be keys.
  • insert moves owned keys and values in and returns the old value. get, get_mut, remove, and contains_key take a reference to the key, and String keys can be looked up with &str.
  • map[key] panics on a missing key; get returns an Option.
  • The entry API (entry(k).or_insert(v), or_insert_with, or_default, and_modify) does "find or create, then update" in one lookup.
  • Iteration order is unspecified. Sort for display, or use BTreeMap for ordered keys.
  • Common patterns: counting, grouping (HashMap<K, Vec<V>>), caching, indexing, and inverting.

Next: HashSet.