The pain of double lookups

When I first started writing services in Rust, I reached for HashMap::get_mut followed by an insert when the key was missing. It works, but it forces two hash calculations and two traversals of the same bucket chain. In a hot path that processes millions of requests per second, that extra work shows up in profiles.

Enter the entry API

The standard library ships a tiny, zero‑cost abstraction called Entry. It represents a *vacant* or *occupied* slot for a given key and lets you manipulate the value in place. The method signature is:

pub fn entry(&mut self, key: K) -> Entry<'_, K, V>

From there you match on Entry::Occupied or Entry::Vacant and call the appropriate helper. The whole operation stays a single hash and a single bucket walk.

Real‑world scenario: counting request frequencies

Imagine a telemetry service that tracks how many times each endpoint is hit. The map key is the endpoint path, the value is a u64 counter. The naïve version looks like this:

fn record_naive(map: &mut HashMap, path: &str) {
    if let Some(count) = map.get_mut(path) {
        *count += 1;
    } else {
        map.insert(path.to_string(), 1);
    }
}

Two lookups, an allocation for the owned string on the miss, and a branch. With entry we can collapse it:

use std::collections::hash_map::Entry;

fn record_entry(map: &mut HashMap, path: &str) {
    match map.entry(path.to_string()) {
        Entry::Occupied(mut occ) => *occ.get_mut() += 1,
        Entry::Vacant(vac) => { vac.insert(1); },
    }
}

Notice the path.to_string() is still required because the map owns its keys. If the caller already has an owned String, you can avoid the clone entirely:

fn record_owned(map: &mut HashMap, path: String) {
    match map.entry(path) {
        Entry::Occupied(mut occ) => *occ.get_mut() += 1,
        Entry::Vacant(vac) => { vac.insert(1); },
    }
}

Why it matters

  • Single hash – the key is hashed once, no matter the branch.
  • In‑place mutation – OccupiedEntry::get_mut returns a mutable reference directly inside the bucket, so no extra pointer chase.
  • Allocation control – the VacantEntry::insert takes ownership of the value you provide, letting you move an already‑allocated String into the map without a second allocation.
  • Ergonomics – the pattern reads like intent: "ensure this key exists, then do something".

In a benchmark on my laptop (Rust 1.78, release build) the entry version was ~18 % faster than the naïve get_mut/insert combo when the map held 10 000 keys and the workload was 90 % hits.

Common gotchas

  1. Borrow checker – you cannot hold a reference into the map while also calling entry on the same map. The mutable borrow from OccupiedEntry::get_mut lasts until the match arm ends.
  2. Key type must implement Eq + Hash – nothing new, but remember that custom keys need a solid hash implementation to keep the single‑lookup guarantee.
  3. Orphan entries – if you create an Entry and then drop it without inserting, the map stays unchanged. That's intentional, but it can surprise newcomers who expect a side effect.

Extending the pattern

The same API works for BTreeMap, IndexMap (from the indexmap crate), and even the experimental hashbrown::HashMap. If you need a default value that is expensive to compute, VacantEntry::or_insert_with lets you supply a closure that runs only on a miss:

fn get_or_compute(map: &mut HashMap, key: String) -> &mut Expensive {
    map.entry(key).or_insert_with(|| Expensive::new())
}

This is the idiomatic replacement for the classic "check‑then‑act" pattern you see in other languages.

Wrap‑up

Next time you reach for a get_mut followed by an insert, pause and ask whether entry fits. It’s a small change, but in latency‑sensitive code it removes a whole hash round‑trip and makes the intent crystal clear. I’ve adopted it as the default way to mutate maps in every crate I maintain, and the profiler thanks me for it.