skip to content

HashMap and HashSet

HashMap uses SipHash by default to resist collision attacks, and the Entry API updates without a second lookup. Interviewers ask about Entry, hashing cost and borrowed lookups.

on this pageshow

questions

5

In a Rust session cache `HashMap<String, u32>`, what do `insert`, `get` and `map[key]` return when a key is new, present or missing?

level: juniorimportance: must knowfreq 72%

answer

  1. Option reports what happened
  2. insert hands back what it displaced
  3. get borrows into the map
  4. Index cannot return None

basics

~20 s

insert returns None for a new key and Some(old value) when it overwrites one; get returns Option<&V>, None when the key is missing; map[key] returns the value directly and panics with "no entry found for key" when it is absent.

solid answer

~40 s

`HashMap::insert(k, v)` returns `Option<V>`: `None` if the key was new, `Some(old)` if it replaced a value (the stored key itself is kept). `get(&k)` returns `Option<&V>`, a borrow into the map, and `get_mut` gives `Option<&mut V>`; on a `HashMap<String, u32>` you can pass `"s-1"` straight to `get` because `String: Borrow<str>`. Indexing with `map["s-1"]` goes through the `Index` impl, which cannot return `None`, so a missing key panics with `no entry found for key`; use it only where presence is guaranteed. Sets differ: `HashSet::insert` returns `bool`, `false` when an equal value was already there, and in that case the set keeps the original and drops the argument.

code

rust · 16 lines
rust
use std::collections::{HashMap, HashSet};

fn main() {
    let mut sessions: HashMap<String, u32> = HashMap::new();
    println!("{:?}", sessions.insert("s-1".to_string(), 10)); // None
    println!("{:?}", sessions.insert("s-1".to_string(), 20)); // Some(10)
    println!("{:?}", sessions.get("s-1"));                     // Some(20)
    println!("{:?}", sessions.get("s-9"));                     // None

    let mut seen: HashSet<String> = HashSet::new();
    println!("{}", seen.insert("alice".to_string()));         // true
    println!("{}", seen.insert("alice".to_string()));         // false

    let user_id = sessions["s-9"];                             // panics here
    println!("{user_id}");
}

go deeper

for a junior

Recall the three return shapes: insert gives Option<V> with the old value, get gives Option<&V>, indexing gives the value or panics. Say which one you would use for a key that comes from a request.

for a middle

Explain why indexing must panic: Index::index returns a reference and has no way to signal absence. Mention that get borrows the map, so an insert while the reference is live is E0502.

for a senior

Show the production habit: never index with untrusted keys, read insert's Option when an overwrite would be a bug, and copy values out of get before mutating the map.

for a principal

Treat map[key] on input-derived keys as a review finding, since it turns a missing entry into a crash. Steer the team toward get-based handling with explicit fallbacks at service boundaries.

## The session cache A **`HashMap<K, V>`** in `std::collections` stores values under keys of type `K`, which must implement `Hash` and `Eq`. Take a session cache that maps a session token (`String`) to a user id (`u32`): `let mut sessions: HashMap<String, u32> = HashMap::new();`. Three operations do almost all the work, and each one reports a missing or present key in a different way. Knowing which one returns an `Option`, which one panics and which one hands back the old value is what an interviewer checks first. ## `insert`: it returns what it displaced `HashMap::insert(k, v)` has the signature `fn insert(&mut self, k: K, v: V) -> Option<V>`. - If the key was **not** present, the pair is stored and `insert` returns **`None`**. - If the key **was** present, the value is replaced and the **old value** comes back as `Some(old)`. - The stored **key is not replaced**. std's documentation says so explicitly: this matters for key types whose values can compare equal with `==` without being identical. Nothing fails, nothing panics, and there is no "duplicate key" error: overwriting is the normal behaviour, and the `Option` is how you find out it happened. Ignoring the return value is common and fine. Matching on it is how you detect "this session already existed". ## `get` and `get_mut`: borrows, not copies `get` returns **`Option<&V>`**: `Some(&value)` when the key exists, `None` when it does not. The value stays inside the map; you receive a shared reference into it. `get_mut` returns `Option<&mut V>` for changing a value in place. Two consequences follow: 1. To keep a plain value, copy or clone it out: `sessions.get("s-1").copied()` gives `Option<u32>`. 2. While that reference is alive, the map is borrowed. Calling `insert` before the last use of the reference is rejected with **E0502** ("cannot borrow `sessions` as mutable because it is also borrowed as immutable"). On a `HashMap<String, u32>` you can look up with a string literal, `sessions.get("s-1")`, without building a `String`, because `String` implements `Borrow<str>`; how that `Borrow` bound works is covered with the conversion traits. ## Indexing: `map[key]` has no `None` to give `HashMap` implements `Index`, so `sessions["s-1"]` (or `map[&key]` for non-string keys) returns the value directly. `Index::index` must return a reference, so it cannot express absence. std's implementation is `self.get(key).expect("no entry found for key")`. A missing key therefore **panics** with the message `no entry found for key`. Use indexing only when the key's presence is an invariant you have already established; anywhere a key might be missing, use `get`. | Operation | Return type | New / present key | Missing key | |---|---|---|---| | `insert(k, v)` | `Option<V>` | `None` / `Some(old)` | not applicable | | `get(&k)` | `Option<&V>` | `Some(&v)` | `None` | | `get_mut(&k)` | `Option<&mut V>` | `Some(&mut v)` | `None` | | `contains_key(&k)` | `bool` | `true` | `false` | | `map[&k]` | the value, through `&V` | the value | **panic** | ## `HashSet::insert` returns `bool` `HashSet<T>` is implemented as a `HashMap<T, ()>`, but its `insert` has a different shape: it returns **`bool`**. - `true` means the value was newly added. - `false` means an equal value was already present. The set is **not modified**: the original value stays and the argument is dropped. To overwrite the stored element with the new equal one, call `HashSet::replace`, which returns `Option<T>` with the element it displaced. A deduplication loop such as `if seen.insert(token.clone()) { first_time(...) }` relies on the `bool`. ## Habits that keep you out of trouble - Read the `Option` from `insert` when an overwrite would be a bug, for example a session token that must be unique. - Prefer `get` plus `copied`, `cloned` or `unwrap_or` over indexing whenever the key comes from input. - Do not call `contains_key` and then `get` or `insert`: that is two or three lookups where one would do. The Entry API covers the insert-or-update case in one. - Remember that a panic on a missing key happens at run time, not compile time: `map["x"]` compiles whether or not `"x"` will ever be present. - Use the same `Option` reading for removal: `remove(&k)` returns `Option<V>` with the value it took out, and `remove_entry(&k)` returns the key as well, as `Option<(K, V)>`. Logging out a session is `sessions.remove(token)`, and a `None` there means the token was already gone.

  • How do you read a value with a fallback, without panicking and without inserting anything?
    Chain on the `Option` from `get`: `sessions.get(token).copied().unwrap_or(0)` for a `Copy` value, `.cloned()` for a `Clone` one, or `if let Some(uid) = sessions.get(token) { ... }` to branch. None of these touch the map. If the fallback should also be stored, that is the Entry API's job: `entry(key).or_insert(default)` inserts it and returns a mutable reference.
  • Why does holding the result of `sessions.get("s-1")` and then calling `sessions.insert(...)` fail to compile?
    `get` returns `Option<&u32>`, a shared borrow of the whole map, and `insert` needs `&mut self`. If the reference is used after the `insert`, rustc rejects it with E0502 (cannot borrow `sessions` as mutable because it is also borrowed as immutable). Copy the value out first with `.copied()`, or finish using the reference before inserting, so the borrow ends earlier.
  • When does it matter that `HashMap::insert` keeps the old key and only replaces the value?
    Only when two keys can be equal under `Eq` while still differing in some way, for instance a key type whose equality ignores a field. `insert` leaves the originally stored key in place, so the map keeps the old variant. To store the new key as well, remove the entry and insert again; for sets, `HashSet::replace` swaps in the new element and returns the old one.

  • insert panics or returns an error when the key already exists
  • get moves the value out of the map instead of borrowing it
  • map[key] returns a default value or None for a missing key
  • HashSet::insert overwrites the stored element with the new equal one
  • You must allocate a String to look up a HashMap<String, V>
open as a page

In a Rust word counter, what does `*counts.entry(word.to_string()).or_insert(0) += 1` do, and why prefer it to `contains_key` then `insert`?

level: middleimportance: must knowfreq 70%

basics

~20 s

entry hashes the key once and returns an Entry, Occupied or Vacant; or_insert(0) stores 0 only when vacant and returns &mut usize to the value either way, so the increment costs one lookup instead of two.

open as a page

In Rust, why do two `HashMap<String, u32>` maps built from the same keys, in the same order, iterate in different orders?

level: middleimportance: should knowfreq 45%

basics

~20 s

Each HashMap gets its own RandomState: SipHash 1-3 keys taken from OS randomness once per thread and incremented for every new RandomState, so the same keys land in different buckets and iteration order usually differs between maps and runs.

open as a page

A Rust game loop profile shows SipHash dominating lookups in a `HashMap<u64, Entity>` keyed by engine-assigned IDs; how do you swap the hasher, and what changes?

level: seniorimportance: should knowfreq 38%

basics

~10 s

Set HashMap's third type parameter to a faster BuildHasher, such as rustc-hash's FxBuildHasher, and build maps with default() or with_hasher; HashMap::new stops applying, and functions taking HashMap<K, V> must become generic over S: BuildHasher.

open as a page

As a Rust lead, what rule do you set for when code may replace HashMap's default SipHash hasher with a faster one?

level: principalimportance: should knowfreq 30%

basics

~20 s

Keep RandomState wherever an outsider can choose or influence keys, such as words from uploaded documents; allow a fast hasher only for internal keys, after a profile shows hashing matters, behind named types that clippy's disallowed_types enforces.

open as a page