Rust HashMap
last modified October 25, 2026
In this article we show how to work with HashMap collections in
Rust.
A HashMap stores key-value pairs. Each key is unique, and the key
is used to find its value quickly: inserting, looking up, and removing an
entry take constant time on average. A HashMap<K, V> is
the Rust version of what other languages call a dictionary, an associative
array, or a hash table.
The keys must implement the Eq and Hash traits.
Integers, bool, char, strings, tuples of such
types, and our own types with a derived implementation can be keys. The
values can be of any type. A HashMap does not keep its entries
in any particular order; when the order matters, we use a
BTreeMap or sort the entries.
The HashMap type is not in the prelude. We import it from the
std::collections module. The examples were tested with Rust 1.97
and the 2024 edition. They are run as Cargo projects with
cargo run -q.
Creating a HashMap
The HashMap::new function creates an empty map. The
insert method adds a key-value pair.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::new();
scores.insert("Blue", 10);
scores.insert("Yellow", 50);
println!("Number of entries: {}", scores.len());
println!("Is empty: {}", scores.is_empty());
let mut stock: HashMap<String, u32> = HashMap::new();
stock.insert(String::from("apples"), 12);
println!("Stock entries: {}", stock.len());
println!("Empty map is empty: {}", HashMap::<i32, i32>::new().is_empty());
}
We create two maps and fill them with data.
let mut scores = HashMap::new();
scores.insert("Blue", 10);
scores.insert("Yellow", 50);
The map must be declared mut, because insert changes
it. We do not write the type of the map; the compiler infers
HashMap<&str, i32> from the first insert.
let mut stock: HashMap<String, u32> = HashMap::new();
When we cannot infer the type from the code, or when we want to be explicit,
we annotate it. The len method returns the number of entries and
is_empty tells whether there are any.
$ cargo run -q Number of entries: 2 Is empty: false Stock entries: 1 Empty map is empty: true
Accessing values
The get method returns an Option<&V>:
Some with a reference to the value if the key exists and
None if it does not.
use std::collections::HashMap;
fn main() {
let mut scores: HashMap<String, i32> = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
let team = String::from("Blue");
match scores.get(&team) {
Some(score) => println!("{team}: {score}"),
None => println!("{team}: no such team"),
}
println!("{:?}", scores.get("Yellow"));
println!("{:?}", scores.get("Red"));
println!("{:?}", scores.get_key_value("Blue"));
println!("{}", scores.contains_key("Red"));
if let Some(score) = scores.get("Yellow") {
println!("Yellow has {score} points");
}
let red = scores.get("Red").copied().unwrap_or(0);
println!("Red has {red} points");
println!("Index operator: {}", scores["Yellow"]);
}
We look up values in several ways.
match scores.get(&team) {
Some(score) => println!("{team}: {score}"),
None => println!("{team}: no such team"),
}
Because a missing key is a normal situation, get forces us to
handle it. We pass a reference to the key.
println!("{:?}", scores.get("Yellow"));
The map has String keys, but we look up with a &str
literal; there is no need to create a new String for each lookup.
This works because String implements
Borrow<str>, and str hashes the same way as
String. The same applies to contains_key,
get_mut, and remove.
println!("{:?}", scores.get_key_value("Blue"));
println!("{}", scores.contains_key("Red"));
The get_key_value method returns both the stored key and the
value. The contains_key method only tests for presence.
let red = scores.get("Red").copied().unwrap_or(0);
To work with a default value, we turn Option<&i32> into
Option<i32> with copied and then call
unwrap_or. See the Option type
tutorial for the other Option methods.
println!("Index operator: {}", scores["Yellow"]);
The index operator returns the value directly, but it panics if the key is missing, as the next example shows.
$ cargo run -q
Blue: 10
Some(50)
None
Some(("Blue", 10))
false
Yellow has 50 points
Red has 0 points
Index operator: 50
The index operator and missing keys
Indexing a HashMap with a missing key causes a panic.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::new();
scores.insert("Blue", 10);
println!("Blue: {}", scores["Blue"]);
println!("Red: {}", scores["Red"]);
}
The first lookup works; the second one fails.
println!("Red: {}", scores["Red"]);
The panic message does not say which key was missing. Therefore, the index
operator is suited only for keys that must be present. In other cases we use
get. The thread ID in the message differs between runs. See the
unwrap tutorial for more about panics.
$ cargo run -q Blue: 10 thread 'main' (80703) panicked at src/main.rs:8:31: no entry found for key note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Updating values
Inserting a key that already exists replaces its value. The
insert method returns the old value as an Option.
use std::collections::HashMap;
fn main() {
let mut ages = HashMap::new();
let old = ages.insert("Alice", 30);
println!("First insert returned {old:?}");
let old = ages.insert("Alice", 31);
println!("Second insert returned {old:?}");
println!("Alice is now {:?}", ages.get("Alice"));
if let Some(age) = ages.get_mut("Alice") {
*age += 1;
}
println!("Alice is now {:?}", ages.get("Alice"));
println!("Number of entries: {}", ages.len());
}
We insert the same key twice and then modify the value in place.
let old = ages.insert("Alice", 31);
The first insert returns None, because the key was
new. The second returns Some(30), the replaced value. The key
itself is not replaced; the original key stays in the map.
if let Some(age) = ages.get_mut("Alice") {
*age += 1;
}
The get_mut method returns a mutable reference to the value, so
we can change it without inserting again. We dereference the reference with
*. The map still has one entry.
$ cargo run -q First insert returned None Second insert returned Some(30) Alice is now Some(31) Alice is now Some(32) Number of entries: 1
Removing entries
The remove method removes an entry and returns its value;
remove_entry returns the key and the value.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([("Red", 20), ("Green", 40), ("Blue", 60)]);
let removed = scores.remove("Green");
println!("Removed: {removed:?}");
let again = scores.remove("Green");
println!("Removed again: {again:?}");
let entry = scores.remove_entry("Red");
println!("Removed entry: {entry:?}");
println!("Left: {}", scores.len());
}
We remove entries from a map initialized from an array.
let removed = scores.remove("Green");
let again = scores.remove("Green");
The first call returns Some(40). The key is gone now, so the
second call returns None; removing a missing key is not an error.
let entry = scores.remove_entry("Red");
We get back the pair ("Red", 20). This is useful when the key owns
data we want to reuse, such as a String.
$ cargo run -q
Removed: Some(40)
Removed again: None
Removed entry: Some(("Red", 20))
Left: 1
Iteration and the order of entries
A for loop over a reference to the map yields the pairs
(&K, &V).
use std::collections::HashMap;
fn main() {
let fruits = HashMap::from([
(1, "apple"),
(2, "banana"),
(3, "cherry"),
(4, "date"),
(5, "elderberry"),
]);
for (key, value) in &fruits {
println!("{key}: {value}");
}
}
We iterate over a map of five entries. The program is run three times.
for (key, value) in &fruits {
println!("{key}: {value}");
}
The order of entries is unspecified. It depends on the hash function, and the default hasher (SipHash 1-3) is seeded randomly for every map, so even the same program prints a different order on each run. Programs must never depend on this order. The random seed makes the hash function resistant to denial-of-service attacks that would try to create many colliding keys.
Looping over &mut map gives (&K, &mut V), and
a loop over map itself consumes the map and yields owned pairs.
$ cargo run -q 5: elderberry 2: banana 1: apple 3: cherry 4: date $ cargo run -q 5: elderberry 1: apple 3: cherry 2: banana 4: date $ cargo run -q 3: cherry 2: banana 5: elderberry 1: apple 4: date
Sorting a HashMap
A HashMap cannot be sorted, because it keeps no order. To get a
sorted view, we collect the entries into a vector and sort the vector.
use std::collections::HashMap;
fn main() {
let scores = HashMap::from([("Blue", 10), ("Yellow", 50), ("Red", 100), ("Green", 50)]);
let mut by_key: Vec<_> = scores.iter().collect();
by_key.sort();
println!("{by_key:?}");
let mut by_value: Vec<_> = scores.iter().collect();
by_value.sort_by(|a, b| b.1.cmp(a.1).then(a.0.cmp(b.0)));
println!("{by_value:?}");
for (team, score) in by_value {
println!("{team:<8}{score:>4}");
}
}
We print the scores sorted by team name and by score.
let mut by_key: Vec<_> = scores.iter().collect(); by_key.sort();
The vector contains tuples of references. Tuples are compared element by element, so sorting puts the pairs in the order of the keys.
by_value.sort_by(|a, b| b.1.cmp(a.1).then(a.0.cmp(b.0)));
To sort by value in descending order, we compare the second elements in
reverse order. The then method compares the keys when the
values are equal: "Green" and "Yellow" both have 50 points, and a hash map
gives no guarantee about which one comes first. The tie-breaker makes the
output deterministic.
for (team, score) in by_value {
println!("{team:<8}{score:>4}");
}
The format specifiers align the team names to the left in a field of eight characters and the scores to the right in a field of four characters.
$ cargo run -q
[("Blue", 10), ("Green", 50), ("Red", 100), ("Yellow", 50)]
[("Red", 100), ("Green", 50), ("Yellow", 50), ("Blue", 10)]
Red 100
Green 50
Yellow 50
Blue 10
Keys and values
The keys and values methods return iterators over
the keys and the values. The values_mut method returns mutable
references to the values.
use std::collections::HashMap;
fn main() {
let mut stock = HashMap::from([("apples", 12), ("pears", 5), ("plums", 31)]);
let mut names: Vec<_> = stock.keys().collect();
names.sort();
println!("Keys: {names:?}");
let total: i32 = stock.values().sum();
println!("Total: {total}");
println!("Largest: {:?}", stock.values().max());
for quantity in stock.values_mut() {
*quantity *= 2;
}
for (name, quantity) in stock.iter_mut() {
if name.starts_with('p') {
*quantity += 1;
}
}
let mut quantities: Vec<_> = stock.values().copied().collect();
quantities.sort();
println!("Quantities: {quantities:?}");
let mut owned: Vec<&str> = stock.into_keys().collect();
owned.sort();
println!("Owned keys: {owned:?}");
}
We work with a map of stock quantities.
let mut names: Vec<_> = stock.keys().collect(); names.sort();
The keys come in an arbitrary order, so we sort them before printing.
let total: i32 = stock.values().sum();
println!("Largest: {:?}", stock.values().max());
Since values is an iterator, we can use all iterator adapters on
it: sum, max, filter, and others.
for quantity in stock.values_mut() {
*quantity *= 2;
}
The values_mut method lets us change all values in place.
for (name, quantity) in stock.iter_mut() {
if name.starts_with('p') {
*quantity += 1;
}
}
The iter_mut method also gives access to the keys, so we can
decide by the key which values to change. The keys themselves are immutable,
because changing a key would break the map.
let mut owned: Vec<&str> = stock.into_keys().collect();
The into_keys and into_values methods consume the
map and return the keys or the values by value. The map cannot be used after
that.
$ cargo run -q Keys: ["apples", "pears", "plums"] Total: 48 Largest: Some(31) Quantities: [11, 24, 63] Owned keys: ["apples", "pears", "plums"]
Creating a HashMap from arrays and iterators
Besides new and insert, a map can be created from
an array of pairs with HashMap::from, or from any iterator of
pairs with collect.
use std::collections::HashMap;
fn main() {
let capitals = HashMap::from([
("Slovakia", "Bratislava"),
("Hungary", "Budapest"),
("Czechia", "Prague"),
]);
println!("{}", capitals["Hungary"]);
let teams = ["Blue", "Yellow"];
let points = [10, 50];
let scores: HashMap<_, _> = teams.into_iter().zip(points).collect();
println!("{}", scores["Yellow"]);
let squares: HashMap<u32, u32> = (1..=5).map(|n| (n, n * n)).collect();
let mut pairs: Vec<_> = squares.into_iter().collect();
pairs.sort();
println!("{pairs:?}");
let duplicates: HashMap<_, _> = [("a", 1), ("b", 2), ("a", 3)].into_iter().collect();
println!("a = {}, entries = {}", duplicates["a"], duplicates.len());
}
We create four maps in different ways.
let capitals = HashMap::from([
("Slovakia", "Bratislava"),
("Hungary", "Budapest"),
("Czechia", "Prague"),
]);
The From<[(K, V); N]> implementation builds a map from an
array of tuples. This is the shortest way to create a map with known
contents.
let scores: HashMap<_, _> = teams.into_iter().zip(points).collect();
The zip method combines two sequences into pairs, and
collect builds the map. The type annotation tells
collect what to produce; the underscores are inferred.
let squares: HashMap<u32, u32> = (1..=5).map(|n| (n, n * n)).collect();
Any iterator that yields pairs works, for example a range with
map. We sort the entries to print them in a fixed order.
let duplicates: HashMap<_, _> = [("a", 1), ("b", 2), ("a", 3)].into_iter().collect();
When the same key appears more than once, the last value wins and the map has two entries. See also the collect tutorial.
$ cargo run -q Budapest 50 [(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)] a = 3, entries = 2
The entry API
A common task is to insert a value only if the key is missing, or to update
the value if the key exists. Doing this with get and
insert looks up the key twice. The entry method
looks it up once and returns an Entry that describes the slot.
use std::collections::HashMap;
fn default_price() -> u32 {
println!("computing the default price");
99
}
fn main() {
let mut stock: HashMap<&str, u32> = HashMap::new();
stock.insert("apples", 12);
stock.entry("apples").or_insert(100);
stock.entry("pears").or_insert(5);
*stock.entry("plums").or_insert(0) += 10;
stock.entry("apples").and_modify(|q| *q += 1).or_insert(1);
stock.entry("cherries").and_modify(|q| *q += 1).or_insert(1);
*stock.entry("kiwis").or_default() += 7;
let mut items: Vec<_> = stock.iter().collect();
items.sort();
println!("{items:?}");
let mut prices = HashMap::from([("apples", 3)]);
prices.entry("apples").or_insert_with(default_price);
prices.entry("pears").or_insert_with(default_price);
println!("pears cost {}", prices["pears"]);
}
We update a stock map in several ways.
stock.entry("apples").or_insert(100);
stock.entry("pears").or_insert(5);
The or_insert method inserts the value only when the key is
absent. "apples" exists, so it keeps 12; "pears" is added.
*stock.entry("plums").or_insert(0) += 10;
The or_insert method returns a mutable reference to the value,
whether it was already there or has just been inserted. Dereferencing it lets
us modify the value right away. This is the standard counting idiom.
stock.entry("apples").and_modify(|q| *q += 1).or_insert(1);
stock.entry("cherries").and_modify(|q| *q += 1).or_insert(1);
The and_modify method runs a closure when the entry exists;
or_insert supplies the value when it does not. "apples" becomes
13 and "cherries" starts with 1.
*stock.entry("kiwis").or_default() += 7;
The or_default method inserts the default value of the type, which
is zero for u32, an empty string for String, and an
empty vector for Vec.
prices.entry("apples").or_insert_with(default_price);
prices.entry("pears").or_insert_with(default_price);
The or_insert_with method takes a function that is called only
when the key is missing. The function ran once, for "pears". With
or_insert(default_price()) the default would be computed every
time, even when the key exists. Use or_insert_with when the
default is expensive to create.
$ cargo run -q
[("apples", 13), ("cherries", 1), ("kiwis", 7), ("pears", 5), ("plums", 10)]
computing the default price
pears cost 99
Counting words
The entry API makes counting short. We count how many times each word occurs in a text.
use std::collections::HashMap;
fn main() {
let text = "the quick brown fox jumps over the lazy dog \
the fox barks and the dog runs after the fox";
let mut counts: HashMap<&str, usize> = HashMap::new();
for word in text.split_whitespace() {
*counts.entry(word).or_insert(0) += 1;
}
let mut top: Vec<_> = counts.into_iter().collect();
top.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
for (word, n) in top.iter().take(3) {
println!("{word}: {n}");
}
}
We print the three most frequent words.
let mut counts: HashMap<&str, usize> = HashMap::new();
for word in text.split_whitespace() {
*counts.entry(word).or_insert(0) += 1;
}
The keys are string slices that borrow from text, so no strings
are allocated. For each word, entry finds or creates the counter,
and we increment it.
let mut top: Vec<_> = counts.into_iter().collect(); top.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(b.0)));
We turn the map into a vector of pairs and sort it by count, highest first.
Words with the same count are ordered alphabetically. The
take(3) adapter limits the output to the first three pairs.
$ cargo run -q the: 5 fox: 3 dog: 2
Grouping values
When the value is a collection, or_default creates an empty one on
the first use of the key. We group words by their first letter.
use std::collections::HashMap;
fn main() {
let words = ["apple", "avocado", "banana", "blueberry", "cherry", "apricot"];
let mut groups: HashMap<char, Vec<&str>> = HashMap::new();
for word in words {
let Some(first) = word.chars().next() else {
continue;
};
groups.entry(first).or_default().push(word);
}
let mut letters: Vec<_> = groups.keys().copied().collect();
letters.sort();
for letter in letters {
println!("{letter}: {:?}", groups[&letter]);
}
}
Each key maps to a vector of words.
let Some(first) = word.chars().next() else {
continue;
};
groups.entry(first).or_default().push(word);
The let else statement skips empty words. Then
entry(first).or_default() returns the vector for this letter,
creating it if needed, and push appends the word.
for letter in letters {
println!("{letter}: {:?}", groups[&letter]);
}
We sort the keys to get a stable output. The words inside each vector keep the order in which they were inserted.
$ cargo run -q a: ["apple", "avocado", "apricot"] b: ["banana", "blueberry"] c: ["cherry"]
Matching on Entry
The Entry type is an enum with the variants
Occupied and Vacant. Matching on it gives us full
control over both cases.
use std::collections::HashMap;
use std::collections::hash_map::Entry;
fn main() {
let mut users = HashMap::from([(1, "Alice")]);
for (id, name) in [(1, "Anna"), (2, "Bob")] {
match users.entry(id) {
Entry::Occupied(entry) => {
println!("id {} is taken by {}", entry.key(), entry.get());
}
Entry::Vacant(entry) => {
entry.insert(name);
println!("id {id} added for {name}");
}
}
}
println!("{}", users.len());
}
We try to register users; ids that are already taken are rejected.
match users.entry(id) {
Entry::Occupied(entry) => {
println!("id {} is taken by {}", entry.key(), entry.get());
}
Entry::Vacant(entry) => {
entry.insert(name);
println!("id {id} added for {name}");
}
}
An occupied entry offers get, get_mut,
insert, and remove. A vacant entry offers
insert. The enum lives in the std::collections::hash_map
module. The map is looked up only once in each case.
$ cargo run -q id 1 is taken by Alice id 2 added for Bob 2
Filtering with retain and extract_if
The retain method keeps only the entries for which a closure
returns true. The extract_if method does the
opposite: it removes the matching entries and returns them.
use std::collections::HashMap;
fn main() {
let mut scores = HashMap::from([("Blue", 10), ("Yellow", 50), ("Red", 100), ("Green", 30)]);
scores.retain(|_, score| *score >= 30);
let mut left: Vec<_> = scores.iter().collect();
left.sort();
println!("Retained: {left:?}");
let mut removed: Vec<_> = scores.extract_if(|_, score| *score > 40).collect();
removed.sort();
println!("Extracted: {removed:?}");
let mut rest: Vec<_> = scores.into_iter().collect();
rest.sort();
println!("Rest: {rest:?}");
}
We filter a map of scores in two steps.
scores.retain(|_, score| *score >= 30);
The closure receives a reference to the key and a mutable reference to the value. The entry for "Blue" with 10 points is removed.
let mut removed: Vec<_> = scores.extract_if(|_, score| *score > 40).collect();
The extract_if method returns an iterator, and the entries are
removed from the map while it is consumed. If we do not consume the iterator,
nothing is removed. Here we collect the extracted pairs, so "Red" and "Yellow"
leave the map and only "Green" remains.
$ cargo run -q
Retained: [("Green", 30), ("Red", 100), ("Yellow", 50)]
Extracted: [("Red", 100), ("Yellow", 50)]
Rest: [("Green", 30)]
Merging maps
The extend method adds all pairs from another map or any iterator
of pairs.
use std::collections::HashMap;
fn sorted<'a>(map: &'a HashMap<&str, i32>) -> Vec<(&'a &'a str, &'a i32)> {
let mut items: Vec<_> = map.iter().collect();
items.sort();
items
}
fn main() {
let mut first = HashMap::from([("Blue", 10), ("Yellow", 50)]);
let second = HashMap::from([("Yellow", 70), ("Red", 100)]);
first.extend(second);
println!("{:?}", sorted(&first));
let mut totals = HashMap::from([("apples", 5), ("pears", 2)]);
let delivery = HashMap::from([("apples", 10), ("plums", 4)]);
for (name, quantity) in delivery {
*totals.entry(name).or_insert(0) += quantity;
}
println!("{:?}", sorted(&totals));
}
We merge maps with two different strategies.
first.extend(second);
Both maps contain "Yellow". After extend the value from the
second map, 70, replaces the value from the first one. The second map is
consumed.
for (name, quantity) in delivery {
*totals.entry(name).or_insert(0) += quantity;
}
When we want to combine the values of equal keys instead of replacing them, we loop over the pairs and use the entry API. Apples are added up to 15.
The helper function sorted returns the entries sorted by key, so
that the output is stable.
$ cargo run -q
[("Blue", 10), ("Red", 100), ("Yellow", 70)]
[("apples", 15), ("pears", 2), ("plums", 4)]
Cloning and comparing maps
The clone method creates an independent copy of the map,
including all keys and values. The == operator compares maps by
content.
use std::collections::HashMap;
fn main() {
let original = HashMap::from([(1, "one"), (2, "two")]);
let mut copy = original.clone();
println!("equal after clone: {}", original == copy);
copy.insert(3, "three");
println!("equal after insert: {}", original == copy);
println!("{} and {} entries", original.len(), copy.len());
let reordered: HashMap<_, _> = [(2, "two"), (1, "one")].into_iter().collect();
println!("insertion order does not matter: {}", original == reordered);
}
We clone a map, change the copy, and compare the maps.
let mut copy = original.clone(); copy.insert(3, "three");
After the insertion the copy has three entries while the original still has two. The maps do not share data.
let reordered: HashMap<_, _> = [(2, "two"), (1, "one")].into_iter().collect();
Two maps are equal when they have the same keys with equal values. The order
of insertion, which a hash map does not keep anyway, plays no role. Equality
requires the value type to implement PartialEq.
$ cargo run -q equal after clone: true equal after insert: false 2 and 3 entries insertion order does not matter: true
Ownership of keys and values
The insert method takes the key and the value by value. A
String that we pass in is moved into the map. Types that
implement Copy, such as integers and &str, are
copied.
use std::collections::HashMap;
fn main() {
let name = String::from("Alice");
let city = "Paris";
let age = 30;
let mut ages: HashMap<String, i32> = HashMap::new();
ages.insert(name.clone(), age);
let mut cities: HashMap<&str, String> = HashMap::new();
cities.insert(city, name.clone());
println!("{name} is {age} and lives in {city}");
println!("{:?} {:?}", ages.get("Alice"), cities.get("Paris"));
}
We keep using the variables after we insert them.
ages.insert(name.clone(), age); cities.insert(city, name.clone());
We insert a clone of the String, so name is still
valid. The integer age and the string slice city
are copied. A map with &str keys does not allocate the keys, but
the slices must outlive the map. See the ownership
tutorial.
$ cargo run -q
Alice is 30 and lives in Paris
Some(30) Some("Alice")
Using a moved key
When we insert a String without cloning it, the map becomes its
owner, and the variable cannot be used anymore.
use std::collections::HashMap;
fn main() {
let name = String::from("Alice");
let mut ages = HashMap::new();
ages.insert(name, 30);
println!("{name}");
}
The program does not compile.
ages.insert(name, 30);
println!("{name}");
The compiler reports the error E0382: name was moved into the
map by insert and is borrowed after the move. We fix it by
cloning the string or by inserting a &str key.
$ cargo run -q
error[E0382]: borrow of moved value: `name`
--> src/main.rs:9:16
|
4 | let name = String::from("Alice");
| ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
...
7 | ages.insert(name, 30);
| ---- value moved here
8 |
9 | println!("{name}");
| ^^^^ value borrowed here after move
|
help: consider cloning the value if the performance cost is acceptable
|
7 | ages.insert(name.clone(), 30);
| ++++++++
For more information about this error, try `rustc --explain E0382`.
Custom key types
Our own types can be keys if they implement Eq and
Hash. In nearly all cases we derive them, together with
PartialEq.
use std::collections::HashMap;
#[derive(Debug, PartialEq, Eq, Hash)]
struct Point {
x: i32,
y: i32,
}
#[derive(Debug, PartialEq, Eq, Hash)]
enum Terrain {
Forest,
Lake,
}
fn main() {
let mut map = HashMap::new();
map.insert(Point { x: 1, y: 2 }, "tree");
map.insert(Point { x: 5, y: 0 }, "rock");
println!("{:?}", map.get(&Point { x: 1, y: 2 }));
println!("{:?}", map.get(&Point { x: 2, y: 1 }));
let mut grid: HashMap<(i32, i32), char> = HashMap::new();
grid.insert((0, 0), '#');
grid.insert((0, 1), '.');
println!("{:?}", grid.get(&(0, 1)));
let mut areas = HashMap::new();
areas.insert(Terrain::Forest, 120.5);
areas.insert(Terrain::Lake, 14.25);
println!("{:?}", areas[&Terrain::Lake]);
}
We use a struct, a tuple, and an enum as keys.
#[derive(Debug, PartialEq, Eq, Hash)]
struct Point {
x: i32,
y: i32,
}
The derived implementations use all fields. Two points are equal when both
coordinates are equal, and equal points always have the same hash. This is the
rule that every Hash implementation must obey: if
a == b, then hash(a) == hash(b). A hand-written
implementation of one trait without the other can break the rule, which leads
to entries that cannot be found; therefore we derive both.
let mut grid: HashMap<(i32, i32), char> = HashMap::new();
Tuples of hashable types are hashable, which makes them handy keys for
coordinates. The enum Terrain is a key as well. Note that we
pass a temporary Point to get; the lookup compares
by value, not by identity.
$ cargo run -q
Some("tree")
None
Some('.')
14.25
Floating-point keys
The types f32 and f64 cannot be keys.
use std::collections::HashMap;
fn main() {
let mut map = HashMap::new();
map.insert(1.5_f64, "one and a half");
println!("{}", map.len());
}
We try to insert a float key.
map.insert(1.5_f64, "one and a half");
The floating-point numbers do not implement Eq and
Hash, because NaN is not equal to itself. The
compiler reports the unsatisfied trait bounds of insert (we show
only the first of two errors). We can use the integer bit pattern returned by
to_bits as the key, scale the number to an integer (for example
cents), or use a crate that wraps floats in an orderable type.
$ cargo run -q
error[E0277]: the trait bound `f64: Eq` is not satisfied
--> src/main.rs:5:9
|
5 | map.insert(1.5_f64, "one and a half");
| ^^^^^^ the trait `Eq` is not implemented for `f64`
|
= help: the following other types implement trait `Eq`:
i128
i16
i32
i64
i8
isize
u128
u16
and 4 others
note: required by a bound in `HashMap::<K, V, S, A>::insert`
--> /home/user/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/collections/hash/map.rs:892:8
|
892 | K: Eq + Hash,
| ^^ required by this bound in `HashMap::<K, V, S, A>::insert`
...
1333 | pub fn insert(&mut self, k: K, v: V) -> Option<V> {
| ------ required by a bound in this associated function
Structs and nested maps as values
Values can be any type, including structs, vectors, and other maps.
use std::collections::HashMap;
#[derive(Debug)]
struct Employee {
name: String,
salary: u32,
}
fn main() {
let staff = [
("Alice", "IT", 4200),
("Bob", "Sales", 3100),
("Carol", "IT", 4800),
("Dave", "Sales", 2900),
("Erin", "HR", 3300),
];
let mut by_dept: HashMap<&str, Vec<Employee>> = HashMap::new();
for (name, dept, salary) in staff {
by_dept.entry(dept).or_default().push(Employee {
name: name.to_string(),
salary,
});
}
let mut depts: Vec<_> = by_dept.keys().copied().collect();
depts.sort();
for dept in depts {
let employees = &by_dept[dept];
let total: u32 = employees.iter().map(|e| e.salary).sum();
let names: Vec<_> = employees.iter().map(|e| e.name.as_str()).collect();
println!("{dept}: {names:?}, total {total}");
}
let mut matrix: HashMap<&str, HashMap<&str, u32>> = HashMap::new();
matrix.entry("IT").or_default().insert("Alice", 4200);
matrix.entry("IT").or_default().insert("Carol", 4800);
println!("{:?}", matrix["IT"]["Carol"]);
println!("{:?}", matrix.get("HR").and_then(|m| m.get("Erin")));
println!("{:?}", by_dept["HR"][0]);
}
We group employees by department and build a map of maps.
let mut by_dept: HashMap<&str, Vec<Employee>> = HashMap::new();
for (name, dept, salary) in staff {
by_dept.entry(dept).or_default().push(Employee {
name: name.to_string(),
salary,
});
}
Each department maps to a vector of Employee structs. We compute
the total salary of a department by iterating over its vector.
let mut matrix: HashMap<&str, HashMap<&str, u32>> = HashMap::new();
matrix.entry("IT").or_default().insert("Alice", 4200);
For a nested map, or_default creates the inner map when it is
missing. Reading goes through chained lookups:
matrix["IT"]["Carol"] panics if a key is missing, while
matrix.get("HR").and_then(|m| m.get("Erin")) returns an
Option.
println!("{:?}", by_dept["HR"][0]);
The struct derives Debug, so we can print it with
{:?}.
$ cargo run -q
HR: ["Erin"], total 3300
IT: ["Alice", "Carol"], total 9000
Sales: ["Bob", "Dave"], total 6000
4800
None
Employee { name: "Erin", salary: 3300 }
Capacity
A map allocates memory for a number of entries (its capacity) and grows when
it is full. The with_capacity function reserves space up front,
reserve asks for more, and shrink_to_fit releases
unused memory.
use std::collections::HashMap;
fn main() {
let mut scores: HashMap<u32, u32> = HashMap::new();
println!("new: {}", scores.capacity());
scores.insert(1, 10);
println!("after one insert: {}", scores.capacity());
let mut big: HashMap<u32, u32> = HashMap::with_capacity(10);
println!("with_capacity(10): {}", big.capacity());
for i in 0..100 {
big.insert(i, i * i);
}
println!("after 100 inserts: {}", big.capacity());
big.retain(|k, _| *k < 5);
println!("after retain: {} entries, capacity {}", big.len(), big.capacity());
big.shrink_to_fit();
println!("after shrink_to_fit: {}", big.capacity());
big.reserve(50);
println!("after reserve(50): {}", big.capacity() >= big.len() + 50);
}
We watch how the capacity changes.
let mut big: HashMap<u32, u32> = HashMap::with_capacity(10);
We asked for room for ten entries and got fourteen. The capacity is the number
of entries the map can hold without allocating again; it is at least the
requested value, and the exact numbers are an implementation detail that can
change between Rust versions. An empty map created by new
allocates nothing, so its capacity is zero.
big.retain(|k, _| *k < 5); big.shrink_to_fit();
Removing entries does not give the memory back. After retain the
map has five entries but still the capacity of 57. The
shrink_to_fit method reduces it. Calling with_capacity
is worth it only when we know the number of entries in advance and want to
avoid repeated reallocation while the map grows.
$ cargo run -q new: 0 after one insert: 3 with_capacity(10): 14 after 100 inserts: 112 after retain: 5 entries, capacity 91 after shrink_to_fit: 7 after reserve(50): true
Caching results with a HashMap
A hash map is a natural cache. The recursive Fibonacci function is slow, because it computes the same values again and again. If we store each result under its argument, every value is computed only once.
use std::collections::HashMap;
fn fib(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
if n < 2 {
return n;
}
if let Some(&value) = cache.get(&n) {
return value;
}
let value = fib(n - 1, cache) + fib(n - 2, cache);
cache.insert(n, value);
value
}
fn main() {
let mut cache = HashMap::new();
println!("fib(10) = {}", fib(10, &mut cache));
println!("entries after fib(10): {}", cache.len());
println!("fib(80) = {}", fib(80, &mut cache));
println!("entries after fib(80): {}", cache.len());
}
The function takes a mutable reference to the cache.
if let Some(&value) = cache.get(&n) {
return value;
}
If the result is cached, we return it immediately. The pattern
Some(&value) copies the u64 out of the reference.
let value = fib(n - 1, cache) + fib(n - 2, cache); cache.insert(n, value);
Otherwise, we compute the value recursively and store it. Computing
fib(10) stores the nine values for n from 2 to 10. When we then
ask for fib(80), the cached values are reused and only the values
from 11 to 80 are added. Without the cache, fib(80) would need
more than 1016 calls.
$ cargo run -q fib(10) = 55 entries after fib(10): 9 fib(80) = 23416728348467685 entries after fib(80): 79
HashMap or BTreeMap
The BTreeMap keeps its keys sorted. Its operations take
logarithmic time, but iteration is in key order, and it supports range queries
and access to the smallest and largest key.
use std::collections::BTreeMap;
fn main() {
let mut scores = BTreeMap::new();
scores.insert("Yellow", 50);
scores.insert("Blue", 10);
scores.insert("Red", 100);
scores.insert("Green", 30);
println!("{scores:?}");
println!("first: {:?}", scores.first_key_value());
println!("last: {:?}", scores.last_key_value());
for (team, score) in scores.range("C".."Z") {
println!("{team}: {score}");
}
}
We store the same scores in a BTreeMap.
println!("{scores:?}");
The entries are printed in the order of the keys, on each run.
println!("first: {:?}", scores.first_key_value());
for (team, score) in scores.range("C".."Z") {
println!("{team}: {score}");
}
The first_key_value and last_key_value methods return
the extreme entries, and range iterates over the keys from "C"
up to, but not including, "Z". Use a HashMap when we only need
fast lookups by key; use a BTreeMap when the order matters. The
key of a BTreeMap must implement Ord instead of
Hash.
$ cargo run -q
{"Blue": 10, "Green": 30, "Red": 100, "Yellow": 50}
first: Some(("Blue", 10))
last: Some(("Yellow", 50))
Green: 30
Red: 100
Yellow: 50
Source
The Rust Programming Language: Storing Keys with Associated Values in Hash Maps
In this article we have worked with HashMap collections in Rust.
Author
List all Rust tutorials.