Hash Maps and Hash Sets

The Entry API

Calling map.entry(key) on a HashMap<K, V> hashes key once, probes the bucket table once, and returns an Entry<'a, K, V> enum that borrows &'a mut HashMap<K, V> and points directly to either the occupied bucket or the vacant insertion slot.

Types in std::collections::hash_map

pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}

map.entry(key)  (Hashes `key` ONCE and probes table ONCE)
  │
  ├── Key found in bucket `i`     ──> Entry::Occupied(OccupiedEntry)
  │                                     ├── .get() / .get_mut() / .into_mut()
  │                                     ├── .insert(new_v) -> old_v
  │                                     └── .remove() / .remove_entry()
  │
  └── Key absent (slot `i` ready) ──> Entry::Vacant(VacantEntry)
                                        ├── .key()
                                        └── .insert(v) -> &'a mut V

Combinator Methods on Entry<'a, K, V>

Method Signature Behavior
e.key() fn key(&self) -> &K Returns a reference to the entry's key (either in the map or inside VacantEntry)
e.and_modify(f) fn and_modify<F: FnOnce(&mut V)>(self, f: F) -> Self Runs f(&mut v) before any potential insertion if the entry is already Occupied
e.or_insert(v) fn or_insert(self, default: V) -> &'a mut V Inserts default if Vacant, returning &'a mut V
e.or_insert_with(f) fn or_insert_with<F: FnOnce() -> V>(self, f: F) -> &'a mut V Calls f() lazily if Vacant, returning &'a mut V
e.or_insert_with_key(f) fn or_insert_with_key<F: FnOnce(&K) -> V>(self, f: F) -> &'a mut V Calls f(e.key()) lazily if Vacant, returning &'a mut V
e.or_default() fn or_default(self) -> &'a mut V (V: Default) Inserts V::default() if Vacant, returning &'a mut V
e.insert_entry(v) fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V> Unconditionally sets the entry's value to v and returns an OccupiedEntry

Using and_modify vs. Matching on Entry

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

fn main() {
    let mut scores = HashMap::from([("alice", 10_u32)]);

    // 1. Combinator style: increment by 5 if occupied, or initialize to 1 if vacant:
    for player in ["alice", "bob"] {
        scores
            .entry(player)
            .and_modify(|s| *s += 5)
            .or_insert(1);
    }
    println!("After combinators: alice={}, bob={}", scores["alice"], scores["bob"]);

    // 2. Pattern matching directly on `Entry::Occupied` and `Entry::Vacant`:
    match scores.entry("alice") {
        Entry::Occupied(occ) => {
            println!("Removing occupied entry '{}' = {}", occ.key(), occ.remove());
        }
        Entry::Vacant(vac) => {
            vac.insert(100);
        }
    }
    println!("Remaining keys: {:?}", scores.keys().collect::<Vec<_>>());
}

After combinators: alice=15, bob=1
Removing occupied entry 'alice' = 15
Remaining keys: ["bob"]