Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 132 ยท Collections and Iterators

HashMap and HashSet

Learn Rust's HashMap and HashSet - insert, get and the entry API, ownership of keys and values, random iteration order, BTreeMap for sorted keys, set operations and custom Hash and Eq.

A HashMap<K, V> stores key-value pairs and finds a value by its key in (on average) constant time, no matter whether the map holds ten entries or ten million. It is Rust's version of Python's dict, JavaScript's Map, Java's HashMap and C++'s unordered_map. Reach for it when the question is "what is the value that belongs to this key?": word counts, user records by id, caches, lookup tables.

A HashSet<T> is the same machine with keys only. It answers the question "have I seen this value before?" and removes duplicates. This lesson covers both, plus the ordered siblings BTreeMap and BTreeSet, the ownership rules that surprise newcomers, the powerful entry API, and how to use your own types as keys. After Vec and strings this is the third collection you will use daily; the next lesson completes the tour.

Creating a map and basic operations

Maps live in std::collections, so you import them. Insert with insert, read with get, remove with remove:

Rust The basic HashMap operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

A few things to take from this:

  • get returns Option<&V>: either a reference to the value or None. Rust has no null; the missing case must be handled. See Option.
  • stock["pears"] is the shortcut that panics if the key is absent. Use it only when absence would be a bug.
  • The key type for get can be a &str even though the map stores String keys. This works because String: Borrow<str>, and the lookup only needs something that hashes the same way.
  • insert on an existing key replaces the value and hands the old one back.

You can create a map directly from an array of pairs, or from an iterator of pairs with collect:

Rust Building maps from pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Iteration order is random

One property catches everybody once: the iteration order of a HashMap is unspecified. It may differ from run to run, because Rust seeds its hash function with a random value for each map to resist hash-flooding attacks. Never rely on it, never print a map directly in a test and compare the text, and never assume entries come out in insertion order.

When you need a stable order, sort the keys (or the entries) first:

Rust Sorting before printing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Aggregate results such as the total or the maximum do not depend on the order. Printing does, so sort first. If you always need sorted keys, use a BTreeMap (below).

Ownership: what happens to keys and values

insert takes its arguments by value. Types that implement Copy (integers, bool, char) are copied into the map. Owned types such as String are moved, and the map becomes their owner.

Rust Using a String after inserting it (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The compiler rejects the last line with error[E0382]: borrow of moved value: `name` and explains that name moved into ages.insert(...), which takes ownership of the key. This is the same rule as everywhere in Rust (see ownership). The fixes are the usual ones: insert name.clone() if you still need your copy, or use references as keys:

Rust References in a map and clones

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Owning keys and values (String) is simplest, and the best default. Borrowing (&str) avoids allocations, but ties the map to the lifetime of the text; it is great for short-lived maps built from a big input string, for instance when counting words in a text you already hold.

The entry API

A very common job: "if the key exists, update its value; otherwise insert a starting value." The naive way looks the key up twice and is clumsy. The entry API does it in one lookup:

map.entry(key) returns an Entry, which is either occupied or vacant. Methods on it complete the job:

  • or_insert(default) inserts default if vacant and returns &mut V either way.
  • or_insert_with(f) calls f to build the default only when needed.
  • or_default() inserts V::default() (0, empty String, empty Vec...).
  • and_modify(f) runs f on an existing value; chain .or_insert(...) for the vacant case.
Rust Counting words with the entry API

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

or_insert(0) returns a mutable reference to the counter, and the * dereferences it so += 1 updates the value in the map. Forgetting the * is a classic compile error. The same idea groups items:

Rust Grouping with or_default and and_modify

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

groups.entry(letter).or_default().push(word) is the idiomatic way to build a "multi-map": the missing Vec is created empty, and then push is called on it.

Calling if !map.contains_key(&k) { map.insert(k, v); } hashes the key twice and is easy to get subtly wrong. Prefer entry, which does a single lookup and reads better too.

HashSet: unique values

A HashSet<T> stores each value at most once. insert returns true when the value was new, which makes a one-liner for duplicate detection.

Rust HashSet basics and set algebra

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The set operations return lazy iterators, so we collect and sort them to print in a fixed order. Removing duplicates from a vector is a one-liner when order does not matter: let unique: HashSet<_> = v.into_iter().collect();. To keep the first-seen order, use retain with a set of seen items:

Rust Removing duplicates but keeping order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

BTreeMap and BTreeSet: sorted collections

BTreeMap<K, V> and BTreeSet<T> keep their entries sorted by key. They have the same main methods as the hash versions, require K: Ord instead of Hash + Eq, and give you deterministic, ordered iteration.

Rust A BTreeMap stays sorted

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

How do you choose?

HashMap / HashSet BTreeMap / BTreeSet
Lookup, insert, remove O(1) on average O(log n)
Iteration order Unspecified, changes per run Sorted by key
Key requirement Hash + Eq Ord
Range queries, min/max key No Yes
Memory and cache behavior One big table Nodes holding several keys each

Use HashMap by default. Switch to BTreeMap when you need sorted iteration, range queries, or the first/last key, or want reproducible output (a handy property for tests and for printing). For small maps (tens of entries) the difference in speed is rarely measurable; choose by the features you need.

Using your own types as keys

A hash map key needs two traits: Eq (equality that is a true equivalence relation) and Hash. For most types, derive all three: #[derive(PartialEq, Eq, Hash)].

Rust A struct as a key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Floating-point numbers are the usual exception. f64 is not Eq (because NaN differs from itself) and not Hash, so it cannot be a key directly:

Rust f64 as a key (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The error is error[E0599]: the method `insert` exists for struct `HashMap<f64, &str>`, but its trait bounds were not satisfied, with notes saying that f64: Eq and f64: Hash are not satisfied. The usual workarounds are to key by the integer bits (value.to_bits()), by a scaled integer such as millidegrees, or by a wrapper type that implements Eq and Hash for the cases you care about.

Writing Hash and Eq by hand

You sometimes want equality that differs from the derived one: for example, a case-insensitive key. Then you implement PartialEq, Eq and Hash yourself. The one rule that you must obey:

If a == b, then hash(a) == hash(b).

If two keys are equal but hash differently, lookups will fail unpredictably (though it is never memory-unsafe).

Rust A case-insensitive key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The second insert finds an equal key and replaces the value, so there is still one entry. If hash ignored the lowercase step, the two spellings would likely land in different buckets and the map would hold both.

The hasher, and why the default is slowish

By default HashMap uses SipHash 1-3 with a random seed. It is strong against attackers who craft keys to make a table slow, but slower for tiny keys like integers than simple hashes. Programs that need raw speed on trusted data swap the hasher: the rustc-hash (FxHash) or ahash crates are popular choices (read-only advice; we cannot install crates here). You can also write a tiny hasher yourself and plug it in through BuildHasherDefault:

Rust Plugging in your own hasher

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The map still works the same way; only the hash function changed. With a fixed hasher the iteration order becomes repeatable for a given sequence of inserts, but that is an accident, not a promise: do not rely on it.

Common mistakes

  • Relying on iteration order. Sort, or use BTreeMap.
  • Holding a reference from get while inserting. get borrows the map; insert needs a mutable borrow. Copy or clone the value out first, or finish using the reference.
  • Double lookup instead of entry.
  • Forgetting the * after or_insert. counts.entry(w).or_insert(0) += 1 does not compile; you need *counts.entry(w).or_insert(0) += 1.
  • Expecting Hash for floats. Convert to an integer key.
  • Using a HashMap for tiny, fixed lookups. A match or a small sorted Vec is often faster and simpler.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does map.insert(key, value) return when the key already exists?

    insert replaces the value and returns the previous one wrapped in Some. It returns None only when the key was new.
  2. 2. In which order does for (k, v) in &map visit the entries of a HashMap?

    The order is unspecified and randomized per map. Sort the keys or use a BTreeMap when order matters.
  3. 3. What is the purpose of *counts.entry(word).or_insert(0) += 1?

    or_insert returns &mut V in both cases. Dereferencing it with * lets you add to the counter stored in the map.
  4. 4. Which pair of traits must a HashMap key type implement?

    HashMap needs Hash to find the bucket and Eq to confirm a match. BTreeMap needs Ord instead.
  5. 5. Why can't f64 be used as a HashMap key?

    NaN is not equal to itself, so f64 is not Eq, and it has no Hash implementation. Use to_bits(), a scaled integer, or a wrapper.

Summary

  • HashMap<K, V> finds values by key in O(1) on average; HashSet<T> stores unique values.
  • insert returns the old value; get returns Option<&V>; map[key] panics when the key is missing.
  • Iteration order is unspecified. Sort for stable output, or use BTreeMap/BTreeSet for sorted keys and range queries.
  • insert moves owned keys and values into the map; clone, or store references that outlive the map.
  • The entry API (or_insert, or_default, or_insert_with, and_modify) does insert-or-update with one lookup.
  • HashSet offers union, intersection, difference, symmetric_difference and is_subset.
  • Key types need Hash + Eq (derive them); custom implementations must keep equal values hashing equally. Floats need a workaround.
  • The default hasher is secure but not the fastest; a custom BuildHasher can be plugged in when you trust your keys.

Next: VecDeque, BinaryHeap and Other Collections