Skip to content
Learn Rust
Theme

Maps

Data · Lesson 27

HashMap<K, V> stores values by key. Looking up a key gives back an Option, because the key might be missing.

Coming from GoHashMap<K, V> is your map[K]V, and its iteration order is also arbitrary, but you import it with use std::collections::HashMap. get returns an Option instead of a zero value, and *counts.entry(k).or_insert(0) += 1 does what counts[k]++ does.

Coming from KotlinHashMap<K, V> is like hashMapOf, and get returns an Option where Kotlin gives Int?. Kotlin's mutableMapOf remembers insertion order, but a Rust HashMap does not, and its order can differ from one run to the next.

Coming from PythonHashMap<K, V> is your dict, and get returns an Option like dict.get returns None. map["zed"] on a missing key panics like a KeyError, and the iteration order is arbitrary, not insertion order.

Coming from TypeScriptHashMap<K, V> is your Map<K, V>, with insert for set. get returns an Option instead of undefined, and the order you get when you loop over it is arbitrary, not insertion order.

Coming from JavaHashMap<K, V> is Java's HashMap, but get returns Option<&V> instead of a value that may be null, so a missing key can't slip through as a null. entry(k).or_insert(0) does the job of merge and computeIfAbsent.

Coming from C#HashMap<K, V> is Dictionary<K, V>, and get returns an Option like TryGetValue does, just as one value. map[&k] reads like the indexer and panics on a missing key, but it only reads: you can't assign through it.

Coming from CThe C standard library has no map; HashMap<K, V> is a full hash table in Rust's standard library. get returns an Option, so the "pointer or NULL" check you would write by hand is required by the compiler.

Coming from C++HashMap<K, V> is std::unordered_map, and get is find with an Option instead of comparing with end(). Unlike operator[], Rust's map[&k] only reads and panics on a missing key; entry(k).or_insert(0) is how you insert on purpose.

The quick comparison

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut ages: HashMap<String, u32> = HashMap::new();
    ages.insert(String::from("ana"), 30);
    ages.insert(String::from("bo"), 25);


    // get returns Option: Some(&value) or None
    match ages.get("ana") {
        Some(age) => println!("ana is {age}"),
        None => println!("no ana"),
    }


    // a default on purpose: 0 when the key is missing
    let zed = ages.get("zed").copied().unwrap_or(0);
    println!("zed is {zed}");


    // count words: entry() means "get it, or insert it first"
    let mut counts: HashMap<&str, u32> = HashMap::new();
    for word in "a b a c a".split(' ') {
        *counts.entry(word).or_insert(0) += 1;
    }
    println!("a appears {} times", counts["a"]);
}
$ cargo run
ana is 30
zed is 0
a appears 3 times
package main


import (
  "fmt"
  "strings"
)


func main() {
  ages := map[string]int{}
  ages["ana"] = 30
  ages["bo"] = 25


  if age, ok := ages["ana"]; ok {
    fmt.Println("ana is", age)
  } else {
    fmt.Println("no ana")
  }


  zed := ages["zed"] // 0 when missing
  fmt.Println("zed is", zed)


  counts := map[string]int{}
  for _, word := range strings.Split("a b a c a", " ") {
    counts[word]++
  }
  fmt.Println("a appears", counts["a"], "times")
}
$ go run main.go
ana is 30
zed is 0
a appears 3 times
fun main() {
    val ages = mutableMapOf<String, Int>()
    ages["ana"] = 30
    ages["bo"] = 25


    val ana = ages["ana"]           // Int? : null when missing
    println(if (ana != null) "ana is $ana" else "no ana")


    val zed = ages["zed"] ?: 0
    println("zed is $zed")


    val counts = mutableMapOf<String, Int>()
    for (word in "a b a c a".split(" ")) {
        counts[word] = (counts[word] ?: 0) + 1
    }
    println("a appears ${counts["a"]} times")
}
$ kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
ana is 30
zed is 0
a appears 3 times
from collections import Counter


ages: dict[str, int] = {}
ages["ana"] = 30
ages["bo"] = 25


# get returns None when the key is missing
age = ages.get("ana")
if age is not None:
    print(f"ana is {age}")
else:
    print("no ana")


# a default on purpose: 0 when the key is missing
zed = ages.get("zed", 0)
print(f"zed is {zed}")


counts = Counter("a b a c a".split(" "))
print(f"a appears {counts['a']} times")
$ python3 main.py
ana is 30
zed is 0
a appears 3 times
const ages = new Map<string, number>();
ages.set("ana", 30);
ages.set("bo", 25);


// get returns number | undefined
const ana = ages.get("ana");
if (ana !== undefined) {
  console.log(`ana is ${ana}`);
} else {
  console.log("no ana");
}


// a default on purpose: 0 when the key is missing
const zed = ages.get("zed") ?? 0;
console.log(`zed is ${zed}`);


// count words: read the old count (or 0) and store the new one
const counts = new Map<string, number>();
for (const word of "a b a c a".split(" ")) {
  counts.set(word, (counts.get(word) ?? 0) + 1);
}
console.log(`a appears ${counts.get("a")} times`);
$ tsc --strict --module nodenext --types node main.ts && node main.js
ana is 30
zed is 0
a appears 3 times
import java.util.HashMap;
import java.util.Map;


public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("ana", 30);
        ages.put("bo", 25);


        // get returns null when the key is missing
        Integer ana = ages.get("ana");
        System.out.println(ana != null ? "ana is " + ana : "no ana");


        int zed = ages.getOrDefault("zed", 0);
        System.out.println("zed is " + zed);


        // count words: merge adds 1, or inserts 1 the first time
        Map<String, Integer> counts = new HashMap<>();
        for (var word : "a b a c a".split(" ")) {
            counts.merge(word, 1, Integer::sum);
        }
        System.out.println("a appears " + counts.get("a") + " times");
    }
}
$ javac Main.java && java Main
ana is 30
zed is 0
a appears 3 times
var ages = new Dictionary<string, uint>
{
    ["ana"] = 30,
    ["bo"] = 25,
};


if (ages.TryGetValue("ana", out var age))
{
    Console.WriteLine($"ana is {age}");
}
else
{
    Console.WriteLine("no ana");
}


// 0 when the key is missing
var zed = ages.GetValueOrDefault("zed");
Console.WriteLine($"zed is {zed}");


// count words
var counts = new Dictionary<string, uint>();
foreach (var word in "a b a c a".Split(' '))
{
    counts[word] = counts.GetValueOrDefault(word) + 1;
}
Console.WriteLine($"a appears {counts["a"]} times");
$ dotnet run
ana is 30
zed is 0
a appears 3 times
#include <stdio.h>
#include <string.h>


// C has no map: a small array of key/value pairs, searched in order
struct Entry {
    const char *key;
    unsigned value;
};


struct Map {
    struct Entry items[16];
    int len;
};


// returns a pointer to the value, or NULL when the key is missing
unsigned *get(struct Map *m, const char *key) {
    for (int i = 0; i < m->len; i++) {
        if (strcmp(m->items[i].key, key) == 0) return &m->items[i].value;
    }
    return NULL;
}


void insert(struct Map *m, const char *key, unsigned value) {
    unsigned *v = get(m, key);
    if (v) {
        *v = value;
    } else {
        m->items[m->len++] = (struct Entry){key, value};
    }
}


int main(void) {
    struct Map ages = {0};
    insert(&ages, "ana", 30);
    insert(&ages, "bo", 25);


    unsigned *age = get(&ages, "ana");
    if (age) {
        printf("ana is %u\n", *age);
    } else {
        printf("no ana\n");
    }


    // a default on purpose: 0 when the key is missing
    unsigned *z = get(&ages, "zed");
    printf("zed is %u\n", z ? *z : 0);


    // count words: get it, or insert it first
    struct Map counts = {0};
    const char *words[] = {"a", "b", "a", "c", "a"};
    for (int i = 0; i < 5; i++) {
        if (!get(&counts, words[i])) insert(&counts, words[i], 0);
        *get(&counts, words[i]) += 1;
    }
    printf("a appears %u times\n", *get(&counts, "a"));
    return 0;
}
$ gcc -Wall -Wextra main.c -o main && ./main
ana is 30
zed is 0
a appears 3 times
#include <iostream>
#include <ranges>
#include <string>
#include <string_view>
#include <unordered_map>


int main() {
    std::unordered_map<std::string, unsigned> ages;
    ages["ana"] = 30;
    ages["bo"] = 25;


    // find gives an iterator: end() means "not there"
    if (auto it = ages.find("ana"); it != ages.end()) {
        std::cout << "ana is " << it->second << "\n";
    } else {
        std::cout << "no ana\n";
    }


    // a default on purpose: 0 when the key is missing (without inserting it)
    auto it = ages.find("zed");
    unsigned zed = it != ages.end() ? it->second : 0;
    std::cout << "zed is " << zed << "\n";


    // count words: operator[] inserts 0 first when the key is new
    std::unordered_map<std::string_view, unsigned> counts;
    for (auto word : std::string_view("a b a c a") | std::views::split(' ')) {
        counts[std::string_view(word.begin(), word.end())] += 1;
    }
    std::cout << "a appears " << counts.at("a") << " times\n";
}
$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main
ana is 30
zed is 0
a appears 3 times

What's different

  • get hands back &u32, a reference to the number inside the map. .copied() turns it into a plain u32, which is cheap for a small number.
  • counts["a"] reads a value, but panics if the key is missing. Prefer get when you are not sure.
  • insert moves the key and the value into the map. A String you inserted is the map's now, and you can't use it afterwards.
  • Use BTreeMap when you want the keys kept in sorted order.
Gotcha

Treating a lookup as if the key is always there

Looks fine: in Go, Python, Java, C#, C and C++ it runs fine. Rust won't compile it.

Fine in Go. Rust can't prove it's safe.Kotlin refuses this too. Same idea, different words.Fine in Python. Rust can't prove it's safe.TypeScript refuses this too. Same idea, different words.Fine in Java. Rust can't prove it's safe.Fine in C#. Rust can't prove it's safe.Fine in C. Rust can't prove it's safe.Fine in C++. Rust can't prove it's safe.
Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut ages: HashMap<&str, u32> = HashMap::new();
    ages.insert("ana", 30);
    let age: u32 = ages.get("ana");
    println!("{age}");
}
package main


import "fmt"


func main() {
  ages := map[string]int{"ana": 30}
  age := ages["ana"]
  fmt.Println(age)
}
$ go run main.go✓ runs
30
Kotlin✗ refuses too

Kotlin refuses this too: ages["ana"] is an Int?, so val age: Int = ages["ana"] doesn't compile until you add a null check, ?: or !!.

fun main() {
    val ages = mutableMapOf<String, Int>()
    ages["ana"] = 30
    val age: Int = ages["ana"]
    println(age)
}
Main.kt:4:18: error: initializer type mismatch: expected 'Int', actual 'Int?'.
    val age: Int = ages["ana"]
                 ^
ages: dict[str, int] = {}
ages["ana"] = 30
age = ages["ana"]
print(age)
$ python3 main.py✓ runs
30
TypeScript✗ refuses too

TypeScript refuses this too, under strict (which the runner uses): Map.get returns number | undefined, which does not fit in a number until you handle the missing case.

const ages = new Map<string, number>();
ages.set("ana", 30);
const age: number = ages.get("ana");
console.log(age);
main.ts(3,7): error TS2322: Type 'number | undefined' is not assignable to type 'number'.
  Type 'undefined' is not assignable to type 'number'.
import java.util.HashMap;
import java.util.Map;


public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("ana", 30);
        int age = ages.get("ana");
        System.out.println(age);
    }
}
$ javac Main.java && java Main✓ runs
30
var ages = new Dictionary<string, uint>();
ages["ana"] = 30;
uint age = ages["ana"];
Console.WriteLine(age);
$ dotnet run✓ runs
30
#include <stdio.h>
#include <string.h>


struct Entry {
    const char *key;
    unsigned value;
};


// returns a pointer to the value, or NULL when the key is missing
unsigned *get(struct Entry *items, int len, const char *key) {
    for (int i = 0; i < len; i++) {
        if (strcmp(items[i].key, key) == 0) return &items[i].value;
    }
    return NULL;
}


int main(void) {
    struct Entry ages[] = {{"ana", 30}};
    unsigned age = *get(ages, 1, "ana");
    printf("%u\n", age);
    return 0;
}
$ gcc -Wall -Wextra main.c -o main && ./main✓ runs
30
#include <iostream>
#include <string>
#include <unordered_map>


int main() {
    std::unordered_map<std::string, unsigned> ages{{"ana", 30}};
    unsigned age = ages["ana"];
    std::cout << age << "\n";
}
$ g++ -std=c++20 -Wall -Wextra main.cpp -o main && ./main✓ runs
30
What does the compiler say? Guess first, then open.
$ cargo buildWhat is E0308?
error[E0308]: mismatched types
 --> src/main.rs:6:20
  |
6 |     let age: u32 = ages.get("ana");
  |              ---   ^^^^^^^^^^^^^^^ expected `u32`, found `Option<&u32>`
  |              |
  |              expected due to this
  |
  = note: expected type `u32`
             found enum `Option<&u32>`
What happens in Go

Go runs this and prints 30. A missing key would quietly give 0, unless you write the comma-ok form, age, ok := ages["ana"], and check ok.

What happens in Kotlin

Kotlin refuses this too: ages["ana"] is an Int?, so val age: Int = ages["ana"] doesn't compile until you add a null check, ?: or !!.

What happens in Python

Python prints 30 because the key is there. With a missing key, ages["zed"] raises KeyError, and ages.get("zed") gives None, an optional value that nothing forces you to check at run time.

What happens in TypeScript

TypeScript refuses this too, under strict (which the runner uses): Map.get returns number | undefined, which does not fit in a number until you handle the missing case.

What happens in Java

This prints 30 because get returns an Integer that Java unboxes for you. With a missing key, get returns null and that same line throws a NullPointerException.

What happens in C#

The indexer returns the value directly and prints 30. If the key were missing it would throw a KeyNotFoundException, so use TryGetValue when you are not sure.

What happens in C

C lets you use *get(...) without checking for NULL. It works because "ana" is there; with a missing key it would dereference NULL, which is undefined behaviour.

What happens in C++

ages["ana"] gives the value directly and prints 30. For a missing key it would quietly insert a 0 into the map. Rust's ages["ana"] is closer to at: it only reads, and panics on a missing key.

What Rust sees

get returns an Option<&u32>, because the map might not hold the key. The compiler does not track which keys you inserted, so it asks you to say what happens when the key is missing. (Rust's ages["ana"] would compile too, and panic on a missing key; get is the one that makes you decide.)

Why Rust says no

Some languages answer a missing key with something that can look like a value: a 0, a null, a crash, or undefined behaviour. A typo in a key then turns into a wrong number or a crash far from the typo. Rust makes you say what a missing key means: handle None, use .unwrap_or(0) for a default on purpose, or write ages["ana"] or unwrap and accept a panic.

The fix

Compiles and runs.

Rust, fixedsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut ages: HashMap<&str, u32> = HashMap::new();
    ages.insert("ana", 30);
    let age: u32 = ages.get("ana").copied().unwrap_or(0);
    println!("{age}");
}
$ cargo run
30

The toolkit

A map stores values under keys, so you can find a value by its key instead of by position. Rust’s everyday map is HashMap<K, V>: K is the type of the keys and V the type of the values. It lives in std::collections, so you import it with use std::collections::HashMap;. A hash map turns each key into a number (its hash) and uses that number to decide where to store the pair, so a lookup does not have to scan every pair. Outputs on this page come from Linux on 64-bit ARM with Rust 1.99.1.

Creating, reading, changing

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut stock: HashMap<String, u32> = HashMap::new();
    println!("insert apple 3: {:?}", stock.insert("apple".to_string(), 3));
    println!("insert pear 5: {:?}", stock.insert("pear".to_string(), 5));
    println!("insert apple 4: {:?}", stock.insert("apple".to_string(), 4));
    println!("len: {}", stock.len());


    println!("get apple: {:?}", stock.get("apple"));
    println!("get plum: {:?}", stock.get("plum"));
    println!("contains_key pear: {}", stock.contains_key("pear"));


    if let Some(n) = stock.get_mut("pear") {
        *n += 10;
    }
    println!("pear after get_mut: {:?}", stock.get("pear"));


    println!("remove pear: {:?}", stock.remove("pear"));
    println!("remove pear again: {:?}", stock.remove("pear"));
    println!("len: {}", stock.len());


    let prices = HashMap::from([("tea", 3), ("milk", 2)]);
    println!("prices[\"tea\"]: {}", prices["tea"]);
}
$ cargo run
insert apple 3: None
insert pear 5: None
insert apple 4: Some(3)
len: 2
get apple: Some(4)
get plum: None
contains_key pear: true
pear after get_mut: Some(15)
remove pear: Some(15)
remove pear again: None
len: 1
prices["tea"]: 3
You want Write You get back Example on {"a": 1}
Add or replace m.insert(k, v) Option<V>: the old value, if there was one insert("b", 2) is None, insert("a", 5) is Some(1)
Read m.get(&k) Option<&V> get("a") is Some(&1), get("z") is None
Change in place m.get_mut(&k) Option<&mut V> get_mut("z") is None
Is it there? m.contains_key(&k) bool true for "a", false for "z"
Take out m.remove(&k) Option<V>: the removed value Some(1), then None
Read, or panic m[&k] the value m["a"] is 1
Size m.len(), m.is_empty() usize, bool

HashMap::from([(k, v), …]) builds a map from an array of pairs, and collect() can build one from any iterator of pairs (Iterators).

The methods take the key by reference because they only need to look at it. A map with String keys can be searched with a &str: stock.get("apple") needs no String to be built first. get gives you a reference into the map. .copied() turns it into a plain number (for a String value, use .cloned() or keep the reference). The Option lesson covers the rest of what you can do with the result.

m[&k] is the short form of “get, and stop the program if it is missing”:

Rustsrc/main.rs! panics at runtimeRun ↗
use std::collections::HashMap;


fn main() {
    let prices = HashMap::from([("tea", 3), ("milk", 2)]);
    println!("tea: {}", prices["tea"]);
    println!("coffee: {}", prices["coffee"]);
}
$ cargo run
tea: 3

thread 'main' (1) panicked at src/main.rs:6:34:
no entry found for key
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Use it where a missing key would be a bug, the way you would use unwrap. For anything else use get.

There is no m[k] = v. The [] read goes through a trait called Index; writing would need IndexMut, and HashMap does not have it, as the error says. Writing is insert or entry.

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut stock: HashMap<&str, u32> = HashMap::new();
    stock["apple"] = 3;
    println!("{}", stock.len());
}
$ cargo buildWhat is E0594?
error[E0594]: cannot assign to data in an index of `HashMap<&str, u32>`
 --> src/main.rs:5:5
  |
5 |     stock["apple"] = 3;
  |     ^^^^^^^^^^^^^^^^^^ cannot assign
  |
  = help: trait `IndexMut` is required to modify indexed content, but it is not implemented for `HashMap<&str, u32>`
help: use `.insert()` to insert a value into a `HashMap<&str, u32>`
  |
5 -     stock["apple"] = 3;
5 +     stock.insert("apple", 3);
  |
help: use the entry API to modify a `HashMap<&str, u32>` for more flexibility
  |
5 -     stock["apple"] = 3;
5 +     let val = stock.entry("apple").insert_entry(3);
  |
help: use `.get_mut()` to modify an existing key in a `HashMap<&str, u32>`
  |
5 -     stock["apple"] = 3;
5 +     if let Some(val) = stock.get_mut("apple") { *val = 3; };

The map owns its keys and values

insert takes the key and the value by value, so both move into the map, as in the ownership lesson:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let name = String::from("ana");
    let mut ages: HashMap<String, u32> = HashMap::new();
    ages.insert(name, 30);
    println!("inserted {name}");
}
$ cargo buildWhat is E0382?
error[E0382]: borrow of moved value: `name`
 --> src/main.rs:7:25
  |
4 |     let name = String::from("ana");
  |         ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
5 |     let mut ages: HashMap<String, u32> = HashMap::new();
6 |     ages.insert(name, 30);
  |                 ---- value moved here
7 |     println!("inserted {name}");
  |                         ^^^^ value borrowed here after move
  |
help: consider cloning the value if the performance cost is acceptable
  |
6 |     ages.insert(name.clone(), 30);
  |                     ++++++++

Insert name.clone() if you still need name. Values move in the same way, and remove moves them back out to you.

The key type decides who owns the text. HashMap<String, V> owns its keys. HashMap<&str, V> stores references into text owned elsewhere:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let text = String::from("red green red");


    // &str keys point into `text`: nothing is copied, but `text` must outlive the map.
    let mut borrowed: HashMap<&str, u32> = HashMap::new();
    for word in text.split(' ') {
        *borrowed.entry(word).or_insert(0) += 1;
    }


    // String keys are copies: the map owns them.
    let mut owned: HashMap<String, u32> = HashMap::new();
    for word in text.split(' ') {
        *owned.entry(word.to_string()).or_insert(0) += 1;
    }


    println!("borrowed red: {:?}", borrowed.get("red"));
    println!("owned red: {:?}", owned.get("red"));
}
$ cargo run
borrowed red: Some(2)
owned red: Some(2)

Borrowed keys avoid copying the text, but the text must outlive the map. Here it does not:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut counts: HashMap<&str, u32> = HashMap::new();
    {
        let text = String::from("red green red");
        for word in text.split(' ') {
            *counts.entry(word).or_insert(0) += 1;
        }
    }
    println!("{}", counts.len());
}
$ cargo buildWhat is E0597?
error[E0597]: `text` does not live long enough
  --> src/main.rs:7:21
   |
 6 |         let text = String::from("red green red");
   |             ---- binding `text` declared here
 7 |         for word in text.split(' ') {
   |                     ^^^^ borrowed value does not live long enough
...
10 |     }
   |     - `text` dropped here while still borrowed
11 |     println!("{}", counts.len());
   |                    ------ borrow later used here

A good default: String keys for a map that is stored in a struct or returned from a function, &str keys for a short-lived tally over text you already hold. Borrowing explains the rule behind E0597.

Looping

for (key, value) in &map visits every pair, giving a reference to each. &mut map makes the values changeable. The keys stay read-only, because changing a key would change its hash and the map could no longer find it (the docs call that a logic error). keys(), values() and values_mut() give just one side. They return iterators, a way of handing out items one at a time (Iterators). collect() gathers an iterator’s items into whatever collection you ask for; here it is a Vec, which iterate.rs then sorts.

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut stock = HashMap::from([("apple", 3), ("pear", 5), ("fig", 1)]);


    let mut total = 0;
    for (_name, count) in &stock {
        total += count;
    }
    println!("total: {total}");


    for count in stock.values_mut() {
        *count *= 2;
    }
    for (_name, count) in &mut stock {
        *count += 1;
    }


    // The order of a HashMap is arbitrary, so sort the keys to print in a fixed order.
    let mut names: Vec<_> = stock.keys().collect();
    names.sort();
    for name in names {
        println!("{name}: {}", stock[name]);
    }
}
$ cargo run
total: 9
apple: 7
fig: 3
pear: 11

You cannot add or remove pairs while a loop is walking the map, because the loop holds a reference into it:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut stock = HashMap::from([("apple", 3), ("pear", 5)]);
    for name in stock.keys() {
        stock.insert("fig", name.len());
    }
}
$ cargo buildWhat is E0502?
error[E0502]: cannot borrow `stock` as mutable because it is also borrowed as immutable
 --> src/main.rs:6:9
  |
5 |       for name in stock.keys() {
  |       -           ------------
  |       |           |
  |       |           immutable borrow occurs here
  |  _____|           immutable borrow later used here
  | |
6 | |         stock.insert("fig", name.len());
  | |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
7 | |     }
  | |_____- this for loop borrows `stock` immutably, preventing mutation within its body
  |
  = help: consider using an index-based loop instead, or collecting modifications into a separate collection

To remove pairs while walking, use retain (below). To add them, collect what you want to add first and insert after the loop.

The order is not yours to rely on

The docs say a HashMap visits its pairs in “arbitrary order”. This program builds four maps with exactly the same pairs, one after another in one run:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    // Four maps with exactly the same pairs, built one after another in one run.
    for n in 1..=4 {
        let map = HashMap::from([
            ("one", 1),
            ("two", 2),
            ("three", 3),
            ("four", 4),
            ("five", 5),
            ("six", 6),
        ]);
        let keys: Vec<_> = map.keys().collect();
        let again: Vec<_> = map.keys().collect();
        println!(
            "map {n}: {keys:?}, same map looped again gives the same order: {}",
            keys == again
        );
    }
}
$ cargo run
map 1: ["five", "one", "three", "four", "six", "two"], same map looped again gives the same order: true
map 2: ["five", "three", "two", "one", "four", "six"], same map looped again gives the same order: true
map 3: ["three", "two", "four", "six", "one", "five"], same map looped again gives the same order: true
map 4: ["five", "six", "one", "two", "three", "four"], same map looped again gives the same order: true

This program prints something slightly different each run. This is one real run.

Each map loops in one order, here the same one every time you ask, but a second map with the same pairs can differ, and so can the next run. The docs do not promise either. They say the default hashing is chosen to resist HashDoS attacks (someone who picks your keys so that they all collide and slow the map down) and that it is randomly seeded; the seed is why. If the order matters, sort the keys, as iterate.rs did, or use a BTreeMap (below).

The entry API: look up once, then decide

A very common job for a map is counting: “if the key is there, add one, otherwise start at one”. With get and insert that is two lookups and an if. map.entry(key) looks the key up once and gives back an Entry: that key’s slot, either occupied or vacant. A method on the Entry says what to do. The first three hand back a &mut V, a mutable reference to the value in the slot, which you change with * (*count += 1 changes the number, not the reference). and_modify hands the entry back, so you can chain another method after it:

Method Key missing Key present
or_insert(v) stores v leaves the value alone
or_insert_with(f) calls f, stores the result does not call f
or_default() stores the type’s default (0, an empty Vec) leaves the value alone
and_modify(f) does nothing calls f on the value

The || { … } and |n| … are closures: small functions written inline, without a name. Here they only mean “run this code, but only when needed”. The Closures lesson covers them.

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut stock: HashMap<&str, u32> = HashMap::new();


    // or_insert: add 10 if the key is missing. Either way you get a &mut to the value.
    *stock.entry("apple").or_insert(10) += 1;
    *stock.entry("apple").or_insert(99) += 1;
    println!("apple: {:?}", stock.get("apple"));


    // or_insert_with: build the value only if the key is missing.
    stock.entry("pear").or_insert_with(|| {
        println!("building the pear value");
        7
    });
    stock.entry("pear").or_insert_with(|| {
        println!("building the pear value again");
        7
    });


    // or_default: the type's default value (0 for a number).
    *stock.entry("fig").or_default() += 1;


    // and_modify: change the value if the key is there, otherwise insert.
    stock.entry("fig").and_modify(|n| *n *= 10).or_insert(0);
    stock.entry("kiwi").and_modify(|n| *n *= 10).or_insert(0);


    let mut pairs: Vec<_> = stock.iter().collect();
    pairs.sort();
    println!("{pairs:?}");
}
$ cargo run
apple: Some(12)
building the pear value
[("apple", 12), ("fig", 10), ("kiwi", 0), ("pear", 7)]

The second or_insert_with printed nothing, because "pear" was already there. or_insert(v) is different: v is worked out before the call even when the key exists (the Option lesson shows the same thing for unwrap_or), so use or_insert_with when building the value is costly.

entry takes the key by value. With String keys you build the String before the lookup, even when the key turns out to be there. If that matters in a hot loop, try get_mut first and entry only when it returns None.

Counting votes is or_insert(0) and add one. The loop variable name is a &str pointing at text in the program, so the keys are not Strings:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let votes = ["ana", "bo", "ana", "cy", "ana", "bo"];


    let mut tally: HashMap<&str, u32> = HashMap::new();
    for name in votes {
        *tally.entry(name).or_insert(0) += 1;
    }


    // `iter()` yields the pairs one at a time. `collect()` gathers them into a Vec,
    // and a Vec of pairs can be sorted.
    let mut results: Vec<_> = tally.iter().collect();
    results.sort();
    for (name, count) in results {
        println!("{name}: {count}");
    }
}
$ cargo run
ana: 3
bo: 2
cy: 1

As in iterate.rs, collect() gathers the pairs into a Vec so they can be sorted.

Grouping is or_default() on a map whose values are Vecs, then push. The Vectors lesson covers Vec.

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let words = ["fig", "apple", "kiwi", "pear", "plum", "lime", "nut"];


    let mut by_length: HashMap<usize, Vec<&str>> = HashMap::new();
    for word in words {
        by_length.entry(word.len()).or_default().push(word);
    }


    let mut lengths: Vec<_> = by_length.keys().collect();
    lengths.sort();
    for length in lengths {
        println!("{length}: {:?}", by_length[length]);
    }
}
$ cargo run
3: ["fig", "nut"]
4: ["kiwi", "pear", "plum", "lime"]
5: ["apple"]

Write the map’s type, as grouping.rs does. or_default needs it to know what “default” means, and without it the compiler cannot tell:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut by_length = HashMap::new();
    by_length.entry(3).or_default().push("fig");
    println!("{}", by_length.len());
}
$ cargo buildWhat is E0282?
error[E0282]: type annotations needed for `HashMap<{integer}, _>`
 --> src/main.rs:4:9
  |
4 |     let mut by_length = HashMap::new();
  |         ^^^^^^^^^^^^^
5 |     by_length.entry(3).or_default().push("fig");
  |     ------------------------------- type must be known at this point
  |
help: consider giving `by_length` an explicit type, where the type for type parameter `V` is specified
  |
4 |     let mut by_length: HashMap<{integer}, V> = HashMap::new();
  |                      +++++++++++++++++++++++

Why not get, then insert?

Because a reference into the map blocks every change to the map:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut stock: HashMap<&str, u32> = HashMap::from([("apple", 3)]);
    let apples = stock.get("apple");
    stock.insert("pear", 5);
    println!("apples: {apples:?}");
}
$ cargo buildWhat is E0502?
error[E0502]: cannot borrow `stock` as mutable because it is also borrowed as immutable
 --> src/main.rs:6:5
  |
5 |     let apples = stock.get("apple");
  |                  ----- immutable borrow occurs here
6 |     stock.insert("pear", 5);
  |     ^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
7 |     println!("apples: {apples:?}");
  |                        ------ immutable borrow later used here

That is E0502, the rule from mutable borrows: apples is a reference into the map’s storage, and insert may have to grow that storage and move every pair to a new place. Copy the number out first (.copied()) and the borrow ends. The program below prints each time the capacity changes while pairs are inserted, and shows with_capacity, which reserves room up front:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut scores: HashMap<u32, u32> = HashMap::new();
    println!("new: len {}, capacity {}", scores.len(), scores.capacity());


    let mut last = scores.capacity();
    for i in 0..40 {
        scores.insert(i, i * i);
        if scores.capacity() != last {
            println!(
                "len {}: capacity {} -> {}",
                scores.len(),
                last,
                scores.capacity()
            );
            last = scores.capacity();
        }
    }


    let roomy: HashMap<u32, u32> = HashMap::with_capacity(100);
    println!(
        "with_capacity(100): len {}, capacity >= 100: {}",
        roomy.len(),
        roomy.capacity() >= 100
    );
}
$ cargo run
new: len 0, capacity 0
len 1: capacity 0 -> 3
len 4: capacity 3 -> 7
len 8: capacity 7 -> 14
len 15: capacity 14 -> 28
len 29: capacity 28 -> 56
with_capacity(100): len 0, capacity >= 100: true

The docs say a map can hold “at least” its capacity, so the exact numbers above are not something to rely on. entry avoids the problem because the lookup and the change happen in one step.

Keys need Hash and Eq

To be a key, a type must be hashable (Hash) and comparable for equality (Eq), and two equal keys must give the same hash. These are traits: named sets of abilities a type can have. The Traits lesson explains them. Strings, integers, char and bool have them already. For your own struct or enum, add #[derive(Hash, PartialEq, Eq)], which the Structs lesson introduced (PartialEq gives ==, and Eq adds the promise that it is a full equality).

Floats do not have them:

Rustsrc/main.rs✗ won't compile
use std::collections::HashMap;


fn main() {
    let mut readings: HashMap<f64, &str> = HashMap::new();
    readings.insert(20.5, "warm");
    println!("{}", readings.len());
}
$ cargo buildWhat is E0599?
error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied
 --> src/main.rs:5:14
  |
5 |     readings.insert(20.5, "warm");
  |              ^^^^^^
  |
  = note: the following trait bounds were not satisfied:
          `f64: Eq`
          `f64: Hash`

Notice the error is on insert, not on HashMap::new(): you can name the type, but you cannot call insert on it. Eq signals that every value is equal to itself, and NaN breaks that:

Rustsrc/main.rsRun ↗
fn main() {
    let nan = f64::NAN;
    println!("NAN == NAN: {}", nan == nan);
    println!("1.5 == 1.5: {}", 1.5_f64 == 1.5_f64);
}
$ cargo run
NAN == NAN: false
1.5 == 1.5: true

NaN (“not a number”) is a float that is not equal to anything, itself included, so a map that used == could never find it again. If you need decimals as keys, store an integer (cents instead of dollars) or a string.

Tuples, Vecs and Options are keys when their parts are, and keys are compared by value:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


#[derive(Debug, Hash, PartialEq, Eq)]
struct Point {
    x: i32,
    y: i32,
}


fn main() {
    // A struct key: derive Hash, PartialEq and Eq. Keys are compared by value.
    let mut names: HashMap<Point, &str> = HashMap::new();
    names.insert(Point { x: 0, y: 0 }, "origin");
    println!("Point 0,0: {:?}", names.get(&Point { x: 0, y: 0 }));
    println!("Point 1,0: {:?}", names.get(&Point { x: 1, y: 0 }));


    // A tuple is a key if all its parts are.
    let mut grid: HashMap<(i32, i32), char> = HashMap::new();
    grid.insert((1, 2), '#');
    println!("(1, 2): {:?}", grid.get(&(1, 2)));


    // So is a Vec, if its items are.
    let mut visits: HashMap<Vec<&str>, u32> = HashMap::new();
    visits.insert(vec!["usr", "bin"], 3);
    println!("[usr, bin]: {:?}", visits.get(&vec!["usr", "bin"]));


    // Option works as a key, so "no key" can be one of the keys.
    let mut by_owner: HashMap<Option<&str>, u32> = HashMap::new();
    by_owner.insert(None, 1);
    by_owner.insert(Some("ana"), 2);
    println!("None: {:?}", by_owner.get(&None));
}
$ cargo run
Point 0,0: Some("origin")
Point 1,0: None
(1, 2): Some('#')
[usr, bin]: Some(3)
None: Some(1)

A Vec can be a key because the map owns it and only lends it out as &K, so ordinary code cannot change it while it is inside.

A map uses the key type’s own Hash and Eq; there is no separate equality or comparator argument. For another idea of “equal” (say, ignoring case), wrap the key in your own struct and implement Hash and Eq for that. The map’s third type parameter is the hasher, the algorithm that mixes the key’s fields into a number (see “Going deeper”).

BTreeMap: a map that stays sorted

BTreeMap<K, V> has the same methods, but keeps its keys in order. Its keys need Ord, the ability to be put in order, in place of Hash. Like HashMap, it uses the key type’s own ordering; to reverse it, wrap the key in std::cmp::Reverse or your own struct.

Rustsrc/main.rsRun ↗
use std::collections::BTreeMap;


fn main() {
    let mut scores = BTreeMap::new();
    scores.insert("cy", 70);
    scores.insert("ana", 91);
    scores.insert("dee", 60);
    scores.insert("bo", 85);


    println!("all: {scores:?}");
    println!("first: {:?}", scores.first_key_value());
    println!("last: {:?}", scores.last_key_value());
    for (name, score) in scores.range("b".."d") {
        println!("from b up to (not including) d: {name} {score}");
    }
    // Like Java's floorKey and ceilingKey:
    println!(
        "last key at or below \"c\": {:?}",
        scores.range(..="c").next_back()
    );
    println!(
        "first key at or after \"c\": {:?}",
        scores.range("c"..).next()
    );
}
$ cargo run
all: {"ana": 91, "bo": 85, "cy": 70, "dee": 60}
first: Some(("ana", 91))
last: Some(("dee", 60))
from b up to (not including) d: bo 85
from b up to (not including) d: cy 70
last key at or below "c": Some(("bo", 85))
first key at or after "c": Some(("cy", 70))
HashMap BTreeMap
Key needs Hash and Eq Ord
Loop order arbitrary sorted by key
First, last, ranges no yes
Cost of a lookup (std docs) O(1), expected O(log n)
The docs suggest it for “a map, with no extra functionality”, a cache a map sorted by key, ranges, the smallest or largest key

“Expected” is the docs’ word: hashing is probabilistic, so a HashMap can in theory be much slower than O(1), though the docs call that very unlikely. The docs give no timings, and this page does not either. If speed matters, measure on your own data.

Which to pick? If you need sorted output once, at the end, collect and sort (as iterate.rs does). Use a BTreeMap when you read in order again and again, when you need the smallest, largest or a range, or when you want the same output on every run (tests, logs). A BTreeMap loops in key order every time.

A set keeps keys without values, for “have I seen this?” and for removing duplicates. HashSet<T> is, in the docs’ words, “implemented as a HashMap where the value is ()”, and BTreeSet<T> is the sorted one. insert returns whether the value was new:

Rustsrc/main.rsRun ↗
use std::collections::{BTreeSet, HashSet};


fn main() {
    let mut seen: HashSet<&str> = HashSet::new();
    println!("insert ana: {}", seen.insert("ana"));
    println!("insert ana again: {}", seen.insert("ana"));
    println!("contains bo: {}", seen.contains("bo"));


    let mine = BTreeSet::from([1, 2, 3, 4]);
    let yours = BTreeSet::from([3, 4, 5]);
    let both: Vec<_> = mine.intersection(&yours).collect();
    let either: Vec<_> = mine.union(&yours).collect();
    let only_mine: Vec<_> = mine.difference(&yours).collect();
    println!("both: {both:?}");
    println!("either: {either:?}");
    println!("only mine: {only_mine:?}");
}
$ cargo run
insert ana: true
insert ana again: false
contains bo: false
both: [3, 4]
either: [1, 2, 3, 4, 5]
only mine: [1, 2]

Housekeeping

Rustsrc/main.rsRun ↗
use std::collections::HashMap;


fn main() {
    let mut stock = HashMap::from([("apple", 3), ("pear", 0)]);


    // extend inserts every pair; a key that is already there gets the new value.
    stock.extend([("apple", 9), ("fig", 2), ("kiwi", 0)]);
    println!(
        "after extend: len {}, apple {:?}",
        stock.len(),
        stock.get("apple")
    );


    // retain keeps the pairs for which the function returns true.
    stock.retain(|_name, count| *count > 0);
    println!("after retain: len {}", stock.len());


    // drain hands out every pair and leaves the map empty.
    let mut taken: Vec<_> = stock.drain().collect();
    taken.sort();
    println!("drained: {taken:?}");
    println!("after drain: len {}", stock.len());
}
$ cargo run
after extend: len 4, apple Some(9)
after retain: len 2
drained: [("apple", 9), ("fig", 2)]
after drain: len 0

extend inserts many pairs at once. retain keeps the pairs for which the closure says true. drain hands out every pair and leaves the map empty (and still holding its memory).

Your maps in Rust

Pick your language in “Coming from” at the top of the page to see how the calls you already know map to Rust. Programs in other languages ran in the same Linux/ARM64 runner; where an order is a detail of one implementation, the text says so.

Going deeper

What insert does to a key

ages.insert(name, 30) moves the String into the map. The String value itself (24 bytes here) goes into the map’s storage, and the text on the heap is not copied. This program checks it:

Rustsrc/main.rsRun ↗
use std::collections::HashMap;
use std::collections::hash_map::RandomState;
use std::mem::size_of;


fn main() {
    let name = String::from("ana");
    let name_bytes = name.as_ptr();
    println!(
        "name before: len {}, capacity {}",
        name.len(),
        name.capacity()
    );


    let mut ages: HashMap<String, u32> = HashMap::new();
    ages.insert(name, 30);


    let (key, value) = ages.iter().next().unwrap();
    println!(
        "key in the map: {key}, len {}, capacity {}",
        key.len(),
        key.capacity()
    );
    println!(
        "key bytes at the same address as name's bytes: {}",
        key.as_ptr() == name_bytes
    );
    println!("value in the map: {value}");


    println!("size_of String: {}", size_of::<String>());
    println!("size_of (String, u32): {}", size_of::<(String, u32)>());
    println!(
        "size_of RandomState (the hasher): {}",
        size_of::<RandomState>()
    );
    println!(
        "size_of HashMap<String, u32>: {}",
        size_of::<HashMap<String, u32>>()
    );
}
$ cargo run
name before: len 3, capacity 3
key in the map: ana, len 3, capacity 3
key bytes at the same address as name's bytes: true
value in the map: 30
size_of String: 24
size_of (String, u32): 32
size_of RandomState (the hasher): 16
size_of HashMap<String, u32>: 48
let name = String::from("ana"); ages.insert(name, 30);
STACKHEAPname: String (moved)ptrlen 3cap 3its text now belongs to the mapages: HashMap<String, u32>hasher seedtable ptr, …the map's storage (shown with one pair; a real table has more, mostly empty, slots)key: ptr, len 3, cap 3value: 303 bytes of UTF-8ana
A simplified picture. What the program above proves is that the key's text is at the same heap address as the original name's text (it prints true), and that the hasher is 16 of the map's 48 bytes. How the standard library arranges the rest is private and can change.

One stored pair is 32 bytes on this machine, but sizes are not promises.

Where the randomness comes from

HashMap has a third type parameter, the hasher: the code that turns a key into a number. Rust splits what C++ keeps in one std::hash: the key’s Hash says which fields to feed in, and the map’s hasher says how to mix them. The default hasher is RandomState. Its docs say a particular RandomState “will create the same instances of Hasher”, but two different ones “are unlikely to produce the same result for the same values”. This program hashes with two of them:

Rustsrc/main.rsRun ↗
use std::collections::hash_map::RandomState;
// BuildHasher is the trait that provides hash_one: "hash this key with my seed".
use std::hash::BuildHasher;


fn main() {
    let first = RandomState::new();
    let second = RandomState::new();


    println!(
        "same state, same key: {}",
        first.hash_one("ana") == first.hash_one("ana")
    );
    println!(
        "same state, other key: {}",
        first.hash_one("ana") == first.hash_one("bo")
    );
    println!(
        "other state, same key: {}",
        first.hash_one("ana") == second.hash_one("ana")
    );
}
$ cargo run
same state, same key: true
same state, other key: false
other state, same key: false

Different seeds give different hashes, so the pairs land in different places and loop in a different order. The docs say the default algorithm is currently SipHash 1-3 “though this is subject to change”, and that other hashers beat it for small keys such as integers but “will typically not protect against attacks such as HashDoS”. You can swap the hasher in when you have measured a need, with HashMap::with_hasher and the BuildHasher trait. Most programs never do.

Practice

Try it

Each exercise is a function with checks in main. Open it in the Playground, replace the todo!(), and run it until it prints all checks passed. A plain for loop is fine for all of them.

Word frequency

Count how many times each word appears in a text, ignoring case. "The" and "the" are one word, an empty text gives an empty map, and non-English letters must be lowercased too. Use entry.

Starterexercises/word-frequency.rs
use std::collections::HashMap;


/// Count how many times each word appears. Words are separated by whitespace,
/// and "The" and "the" are the same word.
fn word_counts(text: &str) -> HashMap<String, u32> {
    todo!("loop over text.split_whitespace(), lowercase each word, and count with entry")
}


fn main() {
    assert!(word_counts("").is_empty());


    let counts = word_counts("the Cat saw THE dog");
    assert_eq!(counts.len(), 4);
    assert_eq!(counts["the"], 2);
    assert_eq!(counts["cat"], 1);
    assert_eq!(counts.get("fish"), None);


    let counts = word_counts("École école ÉCOLE");
    assert_eq!(counts.len(), 1);
    assert_eq!(counts["école"], 3);


    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/word-frequency.solution.rsRun ↗
use std::collections::HashMap;


/// Count how many times each word appears. Words are separated by whitespace,
/// and "The" and "the" are the same word.
fn word_counts(text: &str) -> HashMap<String, u32> {
    let mut counts = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word.to_lowercase()).or_insert(0) += 1;
    }
    counts
}


fn main() {
    assert!(word_counts("").is_empty());


    let counts = word_counts("the Cat saw THE dog");
    assert_eq!(counts.len(), 4);
    assert_eq!(counts["the"], 2);
    assert_eq!(counts["cat"], 1);
    assert_eq!(counts.get("fish"), None);


    let counts = word_counts("École école ÉCOLE");
    assert_eq!(counts.len(), 1);
    assert_eq!(counts["école"], 3);


    println!("all checks passed");
}
$ cargo run
all checks passed

Group by first letter

Group a list of names by their first character, keeping the order inside each group. An empty name has no first character, so it must be skipped, and a name like "élan" must group under 'é', not under a byte.

Starterexercises/group-by-initial.rs
use std::collections::HashMap;


/// Group names by their first character. Names keep their order inside a group,
/// and an empty name belongs to no group.
fn group_by_initial(names: &[&str]) -> HashMap<char, Vec<String>> {
    todo!("name.chars().next() is an Option<char>; group with entry(first).or_default()")
}


fn main() {
    assert!(group_by_initial(&[]).is_empty());


    let groups = group_by_initial(&["ana", "al", "bo", "", "élan", "ed"]);
    assert_eq!(groups.len(), 4);
    assert_eq!(groups[&'a'], vec!["ana", "al"]);
    assert_eq!(groups[&'b'], vec!["bo"]);
    assert_eq!(groups[&'é'], vec!["élan"]);
    assert_eq!(groups[&'e'], vec!["ed"]);
    assert_eq!(groups.get(&'x'), None);


    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/group-by-initial.solution.rsRun ↗
use std::collections::HashMap;


/// Group names by their first character. Names keep their order inside a group,
/// and an empty name belongs to no group.
fn group_by_initial(names: &[&str]) -> HashMap<char, Vec<String>> {
    let mut groups: HashMap<char, Vec<String>> = HashMap::new();
    for name in names {
        let Some(first) = name.chars().next() else {
            continue;
        };
        groups.entry(first).or_default().push(name.to_string());
    }
    groups
}


fn main() {
    assert!(group_by_initial(&[]).is_empty());


    let groups = group_by_initial(&["ana", "al", "bo", "", "élan", "ed"]);
    assert_eq!(groups.len(), 4);
    assert_eq!(groups[&'a'], vec!["ana", "al"]);
    assert_eq!(groups[&'b'], vec!["bo"]);
    assert_eq!(groups[&'é'], vec!["élan"]);
    assert_eq!(groups[&'e'], vec!["ed"]);
    assert_eq!(groups.get(&'x'), None);


    println!("all checks passed");
}
$ cargo run
all checks passed

Invert a map

Turn a map of name to score into a BTreeMap of score to names, so the scores come out in increasing order. Two names can share a score, and a plain insert would silently drop one of them, so each score maps to a sorted list.

Starterexercises/invert.rs
use std::collections::{BTreeMap, HashMap};


/// Turn name -> score into score -> names, with the scores in increasing order.
/// Two names can share a score, so each score maps to a list. Every list is sorted.
fn invert(scores: &HashMap<String, u32>) -> BTreeMap<u32, Vec<String>> {
    todo!("use entry(score).or_default() to collect names, and sort each list afterwards")
}


fn main() {
    assert!(invert(&HashMap::new()).is_empty());


    let scores = HashMap::from([
        ("cy".to_string(), 7),
        ("ana".to_string(), 7),
        ("bo".to_string(), 2),
        ("dee".to_string(), 90),
    ]);
    let inverted = invert(&scores);
    assert_eq!(inverted.len(), 3);
    assert_eq!(inverted[&7], vec!["ana", "cy"]);
    assert_eq!(inverted[&2], vec!["bo"]);
    assert_eq!(inverted.get(&3), None);


    // A BTreeMap loops in key order, so this is the same on every run.
    let order: Vec<u32> = inverted.keys().copied().collect();
    assert_eq!(order, vec![2, 7, 90]);
    assert_eq!(inverted.last_key_value().map(|(score, _)| *score), Some(90));


    println!("all checks passed");
}

Open in the Rust Playground ↗Run it first: it stops at todo!() with not yet implemented and a hint, and the compiler warns that the parameter is unused. Both are expected. Replace the todo!() with your code and run it again until it prints all checks passed.

Show a solution
One solutionexercises/invert.solution.rsRun ↗
use std::collections::{BTreeMap, HashMap};


/// Turn name -> score into score -> names, with the scores in increasing order.
/// Two names can share a score, so each score maps to a list. Every list is sorted.
fn invert(scores: &HashMap<String, u32>) -> BTreeMap<u32, Vec<String>> {
    let mut inverted: BTreeMap<u32, Vec<String>> = BTreeMap::new();
    for (name, score) in scores {
        inverted.entry(*score).or_default().push(name.clone());
    }
    for names in inverted.values_mut() {
        names.sort();
    }
    inverted
}


fn main() {
    assert!(invert(&HashMap::new()).is_empty());


    let scores = HashMap::from([
        ("cy".to_string(), 7),
        ("ana".to_string(), 7),
        ("bo".to_string(), 2),
        ("dee".to_string(), 90),
    ]);
    let inverted = invert(&scores);
    assert_eq!(inverted.len(), 3);
    assert_eq!(inverted[&7], vec!["ana", "cy"]);
    assert_eq!(inverted[&2], vec!["bo"]);
    assert_eq!(inverted.get(&3), None);


    // A BTreeMap loops in key order, so this is the same on every run.
    let order: Vec<u32> = inverted.keys().copied().collect();
    assert_eq!(order, vec![2, 7, 90]);
    assert_eq!(inverted.last_key_value().map(|(score, _)| *score), Some(90));


    println!("all checks passed");
}
$ cargo run
all checks passed

Read more

Learn Rust is an independent project, not affiliated with the Rust Project or the Rust Foundation. Code and text are under the MIT licence.Source on GitHub.