Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 132 ยท Collections and Iterators

The HashMap Entry API in Depth

Master the Rust HashMap entry API: or_insert, or_insert_with, or_default, and_modify, matching on Entry, plus counting, grouping and nested map patterns.

Almost every real program that uses a HashMap ends up asking the same question: "Is this key already in the map? If so, update the value. If not, create one." The naive answer is to call contains_key, then get_mut or insert. That works, but it hashes the key two or three times, and in some shapes it does not even compile because of the borrow checker.

Rust gives you a single tool for this job: the entry API. One call to entry(key) looks the key up once and hands you a handle to the slot, whether it is occupied or empty. From that handle you decide what to do. This lesson goes through every method on the handle, the patterns they enable (counting, grouping, nested maps, caches) and the one situation where you should not reach for entry. It builds on HashMap and HashSet, where the basics were introduced.

What entry returns

map.entry(key) returns an Entry<K, V>, which is an enum with two variants:

  • Entry::Occupied(OccupiedEntry): the key exists, and you hold a handle to its value.
  • Entry::Vacant(VacantEntry): the key is missing, and you hold a handle that can insert a value for it.

Most of the time you never name these variants. You chain one of the convenience methods instead, and each of them returns a &mut V pointing to the value inside the map, which you can read or change right away.

flowchart TD
    A["map.entry(key)"] --> B{"key present?"}
    B -->|yes| C["Occupied<br/>and_modify closure runs<br/>or_insert is skipped"]
    B -->|no| D["Vacant<br/>and_modify is skipped<br/>or_insert stores the default"]
    C --> E["returns &mut V into the map"]
    D --> E

The map is searched once; the entry decides which branch runs.

Notice that entry takes the key by value. The map needs to own the key if it has to insert it. We will come back to what that costs for String keys.

or_insert, or_insert_with and or_default

The simplest methods supply a value for the vacant case:

  • or_insert(value) inserts the value you pass if the key is missing.
  • or_insert_with(|| value) runs a closure only when the key is missing, so an expensive default is never built needlessly.
  • or_insert_with_key(|key| value) is the same, but the closure receives a reference to the key.
  • or_default() inserts V::default() (0 for numbers, an empty Vec, an empty String, and so on).

All four return &mut V. The classic idiom for a counter is *map.entry(key).or_insert(0) += 1: the * dereferences the returned &mut u32 so you can add to the number stored inside the map.

and_modify(|v| ...) is the partner method. It runs a closure on the existing value if the key is present, and does nothing otherwise. You usually chain it before an or_insert, which reads like "if it is there, change it, otherwise insert this":

Rust or_insert, and_modify and or_default

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 value returned by these methods is a mutable reference that borrows the map. You can use it immediately, but you cannot keep it around while touching the map again; that is the usual rule of borrowing.

Counting and frequency tables

Counting is the single most common use of the entry API. Because or_default works for any numeric type, the idiom becomes *counts.entry(key).or_default() += 1, and it works equally well for words, characters, status codes or enum variants. If you want the result sorted by count, collect the entries into a Vec and sort it, because a HashMap has no order:

Rust A word-frequency table

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 has the same entry API with the same method names, so everything in this lesson applies to it too, and the output comes out sorted.

Grouping values by a key

Counting stores a number per key. Grouping stores a collection per key: a HashMap<K, Vec<V>>. The entry API makes this a one-liner, because or_default() creates the empty Vec the first time and returns a &mut Vec you can push onto:

Rust
groups.entry(key).or_default().push(item);

No contains_key check, no separate insert for the empty list. The same trick works with HashSet for unique members, String for concatenation or BTreeSet for sorted members. Nesting works too: a map of maps is outer.entry(a).or_default().entry(b).or_default().

Rust Group, index and nest

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.

Matching on the Entry enum

Sometimes the convenience methods are not enough: you want different logic for the two cases, you want to remove an entry, or you need to return an error when a key is missing. In that case, match on the Entry enum directly. It lives in std::collections::hash_map::Entry (and btree_map::Entry).

  • OccupiedEntry offers get(), get_mut(), into_mut() (a &mut V that lives as long as the map borrow), insert(new) (returns the old value) and remove() (returns the value and deletes the slot).
  • VacantEntry offers insert(value) (returns &mut V), key() and into_key().

Both entry kinds also have a key() method, and Entry itself has key() as well, so you can look at the key before deciding.

Rust Taking items from a stock map

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 match gives you complete control and still performs only one lookup. It also solves a classic borrow-checker puzzle. Code like "if the key exists, return a reference to the value, otherwise insert one and return that" often fails to compile with get_mut followed by insert, because the first borrow is considered alive in both branches. A single entry call avoids the problem entirely, because there is only one borrow.

The cost of owned keys

entry(key) consumes the key, so with String keys you must create a String before the call, even when the key turns out to exist and the new String is thrown away. For a hot loop over millions of words that is a lot of wasted allocations. When the key is only borrowed (a &str from some text), a lookup with get_mut first avoids the allocation in the common "already there" case:

Rust Counting allocations: entry vs get_mut first

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.

If your keys are Copy (integers, &'static str, small enums) or you only count a few thousand items, prefer entry for its clarity. Reach for get_mut-first when profiling shows allocation of keys is a bottleneck. (A newer pattern, raw_entry, never became stable, so there is no borrowed-key entry in the standard library today.)

Two more things to know

  • Memoization. A map used as a cache fits entry(n).or_insert_with(|| compute(n)), but only if compute does not itself touch the map. The closure runs while the map is mutably borrowed, so a recursive function that updates the same map from inside the closure will not compile. Compute the value first with a normal lookup, then insert it.
  • insert_entry. Both Entry and VacantEntry have insert_entry(value), which inserts and gives you back an OccupiedEntry handle, useful when you want to keep working with the slot afterwards. The API is the same on HashMap and BTreeMap, so patterns transfer between them.

Whenever you see if !map.contains_key(&k) { map.insert(k, v); } or if let Some(x) = map.get_mut(&k) { ... } else { map.insert(...) } in your own code, stop and ask whether entry says the same thing in one line. Clippy even has a lint (map_entry) that points out the first form.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does *counts.entry(word).or_insert(0) += 1 do the first time word is seen?

    or_insert returns &mut V in both the vacant and occupied cases. For a new key the value is 0, and the += 1 then updates it inside the map.
  2. 2. Which call creates an empty Vec for a new key and returns it so you can push onto it?

    or_default inserts V::default() (an empty Vec) for a missing key and returns &mut Vec<_>. insert returns the old value, not a reference to the new one, and get_or_create does not exist.
  3. 3. When would you match on Entry::Occupied and Entry::Vacant instead of chaining or_insert?

    Matching gives full control (get, get_mut, insert, remove) with a single lookup. The chained methods are shorter but only cover insert-or-update.
  4. 4. Why can entry(w.to_string()) waste work in a loop over many repeated words?

    entry consumes its key argument, so you must build an owned String before calling it. When most words repeat, trying get_mut with a borrowed &str first avoids those allocations.

Summary

  • map.entry(key) searches the map once and returns an Entry: Occupied or Vacant.
  • or_insert, or_insert_with, or_insert_with_key and or_default supply a value for a missing key and return &mut V.
  • and_modify(|v| ...) changes an existing value; chain it before or_insert for "update or create".
  • Counting is *map.entry(k).or_default() += 1; grouping is map.entry(k).or_default().push(x); nesting chains several entry calls.
  • Match on Entry when the cases differ: OccupiedEntry has get, get_mut, insert, remove; VacantEntry has insert.
  • entry takes the key by value, which can cost allocations for String keys; a get_mut check first avoids that.
  • BTreeMap offers the same API, with sorted iteration.

Next: Panics