1029 Intermediate

1029-hashmap-entry — HashMap Entry API

Functional Programming

Tutorial

The Problem

The naive approach to insert-or-update a hash map performs two lookups: one to check if the key exists, one to insert or update. This is O(2 log n) for tree maps and O(2) amortized for hash maps — and worse, it requires the key to be hashed twice. For hot code paths like frequency counting or cache updates, this overhead matters.

Rust's Entry API solves this with a single lookup that returns a handle to either the existing entry or a vacancy. Operations on the handle modify the map in-place without a second lookup. This pattern originated in C++'s std::unordered_map::emplace and was refined in Rust.

🎯 Learning Outcomes

• Use entry().or_insert(default) for insert-if-absent with a constant default

• Use entry().or_insert_with(|| expr) to compute the default lazily

• Use entry().and_modify(|v| *v += 1).or_insert(1) for increment-or-insert

• Understand why the Entry API avoids double lookups

• Apply the Entry API to frequency counting and cache initialization

Code Example

#![allow(clippy::all)]
// 1029: HashMap Entry API
// Rust's Entry API avoids double lookups for insert-or-update patterns

use std::collections::HashMap;

/// or_insert: insert a default value if key is absent
fn or_insert_demo() {
    let mut m = HashMap::new();
    m.insert("a", 1);

    // Insert "b" with default 42 if not present
    m.entry("b").or_insert(42);
    // "a" already exists — or_insert does nothing
    m.entry("a").or_insert(99);

    assert_eq!(m["a"], 1);
    assert_eq!(m["b"], 42);
}

/// or_insert_with: compute default lazily
fn or_insert_with_demo() {
    let mut m = HashMap::new();

    let keys = vec!["x", "y"];
    for key in keys {
        m.entry(key).or_insert_with(|| {
            // Expensive computation only runs if key absent
            match key {
                "x" => 100,
                "y" => 200,
                _ => 0,
            }
        });
    }

    assert_eq!(m["x"], 100);
    assert_eq!(m["y"], 200);
}

/// and_modify + or_insert: modify existing OR insert default
fn and_modify_demo() {
    let mut m: HashMap<&str, i32> = HashMap::new();

    // First insert: key absent → or_insert(1)
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 1);

    // Second: key exists → and_modify runs
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 2);

    // Third: still modifying
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 3);
}

/// or_insert returns a mutable reference for in-place mutation
fn entry_ref_demo() {
    let mut m: HashMap<char, Vec<usize>> = HashMap::new();
    let word = "hello";

    for (i, ch) in word.chars().enumerate() {
        m.entry(ch).or_default().push(i);
    }

    assert_eq!(m[&'l'], vec![2, 3]);
    assert_eq!(m[&'h'], vec![0]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_or_insert() {
        or_insert_demo();
    }

    #[test]
    fn test_or_insert_with() {
        or_insert_with_demo();
    }

    #[test]
    fn test_and_modify() {
        and_modify_demo();
    }

    #[test]
    fn test_entry_ref() {
        entry_ref_demo();
    }

    #[test]
    fn test_or_default() {
        let mut m: HashMap<&str, Vec<i32>> = HashMap::new();
        m.entry("nums").or_default().push(42);
        assert_eq!(m["nums"], vec![42]);
    }
}

(* 1029: HashMap Entry API *)
(* OCaml doesn't have a direct entry API — we simulate with find_opt + add *)

module StringMap = Map.Make(String)

(* Approach 1: Insert if absent (or_insert equivalent) *)
let or_insert () =
  let m = StringMap.empty |> StringMap.add "a" 1 in
  (* Insert "b" only if not present *)
  let m = match StringMap.find_opt "b" m with
    | Some _ -> m
    | None -> StringMap.add "b" 42 m
  in
  (* "a" already exists, so don't overwrite *)
  let m = match StringMap.find_opt "a" m with
    | Some _ -> m
    | None -> StringMap.add "a" 99 m
  in
  assert (StringMap.find "a" m = 1);
  assert (StringMap.find "b" m = 42)

(* Approach 2: Insert with default function (or_insert_with equivalent) *)
let or_insert_with () =
  let defaults = [("x", fun () -> 100); ("y", fun () -> 200)] in
  let m = StringMap.empty in
  let m = List.fold_left (fun acc (k, f) ->
    match StringMap.find_opt k acc with
    | Some _ -> acc
    | None -> StringMap.add k (f ()) acc
  ) m defaults in
  assert (StringMap.find "x" m = 100);
  assert (StringMap.find "y" m = 200)

(* Approach 3: Modify existing or insert (and_modify + or_insert) *)
let and_modify_or_insert () =
  let update_or_insert m key default modify =
    match StringMap.find_opt key m with
    | Some v -> StringMap.add key (modify v) m
    | None -> StringMap.add key default m
  in
  let m = StringMap.empty in
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 1);
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 2);
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 3)

let () =
  or_insert ();
  or_insert_with ();
  and_modify_or_insert ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Single lookup: Rust's Entry API guarantees one hash computation; OCaml's Map and Hashtbl require two separate operations.

Lazy default: or_insert_with runs the closure only on miss; OCaml's Option.value ~default:(compute ()) is eager.

and_modify chain: Rust's and_modify(f).or_insert(v) is a fluent chain unavailable in OCaml's stdlib.

Mutable reference: or_insert returns &mut V, allowing direct mutation of the value without re-hashing; OCaml always rebuilds the map.

OCaml Approach

OCaml's immutable Map requires two operations:

let increment key m =
  let count = try Map.find key m with Not_found -> 0 in
  Map.add key (count + 1) m

Hashtbl (mutable) is closer to Rust's HashMap but has no equivalent Entry API — you always do two operations. The Base.Hashtbl module adds find_or_add as a partial equivalent.

Full Source

#![allow(clippy::all)]
// 1029: HashMap Entry API
// Rust's Entry API avoids double lookups for insert-or-update patterns

use std::collections::HashMap;

/// or_insert: insert a default value if key is absent
fn or_insert_demo() {
    let mut m = HashMap::new();
    m.insert("a", 1);

    // Insert "b" with default 42 if not present
    m.entry("b").or_insert(42);
    // "a" already exists — or_insert does nothing
    m.entry("a").or_insert(99);

    assert_eq!(m["a"], 1);
    assert_eq!(m["b"], 42);
}

/// or_insert_with: compute default lazily
fn or_insert_with_demo() {
    let mut m = HashMap::new();

    let keys = vec!["x", "y"];
    for key in keys {
        m.entry(key).or_insert_with(|| {
            // Expensive computation only runs if key absent
            match key {
                "x" => 100,
                "y" => 200,
                _ => 0,
            }
        });
    }

    assert_eq!(m["x"], 100);
    assert_eq!(m["y"], 200);
}

/// and_modify + or_insert: modify existing OR insert default
fn and_modify_demo() {
    let mut m: HashMap<&str, i32> = HashMap::new();

    // First insert: key absent → or_insert(1)
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 1);

    // Second: key exists → and_modify runs
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 2);

    // Third: still modifying
    m.entry("count").and_modify(|c| *c += 1).or_insert(1);
    assert_eq!(m["count"], 3);
}

/// or_insert returns a mutable reference for in-place mutation
fn entry_ref_demo() {
    let mut m: HashMap<char, Vec<usize>> = HashMap::new();
    let word = "hello";

    for (i, ch) in word.chars().enumerate() {
        m.entry(ch).or_default().push(i);
    }

    assert_eq!(m[&'l'], vec![2, 3]);
    assert_eq!(m[&'h'], vec![0]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_or_insert() {
        or_insert_demo();
    }

    #[test]
    fn test_or_insert_with() {
        or_insert_with_demo();
    }

    #[test]
    fn test_and_modify() {
        and_modify_demo();
    }

    #[test]
    fn test_entry_ref() {
        entry_ref_demo();
    }

    #[test]
    fn test_or_default() {
        let mut m: HashMap<&str, Vec<i32>> = HashMap::new();
        m.entry("nums").or_default().push(42);
        assert_eq!(m["nums"], vec![42]);
    }
}

(* 1029: HashMap Entry API *)
(* OCaml doesn't have a direct entry API — we simulate with find_opt + add *)

module StringMap = Map.Make(String)

(* Approach 1: Insert if absent (or_insert equivalent) *)
let or_insert () =
  let m = StringMap.empty |> StringMap.add "a" 1 in
  (* Insert "b" only if not present *)
  let m = match StringMap.find_opt "b" m with
    | Some _ -> m
    | None -> StringMap.add "b" 42 m
  in
  (* "a" already exists, so don't overwrite *)
  let m = match StringMap.find_opt "a" m with
    | Some _ -> m
    | None -> StringMap.add "a" 99 m
  in
  assert (StringMap.find "a" m = 1);
  assert (StringMap.find "b" m = 42)

(* Approach 2: Insert with default function (or_insert_with equivalent) *)
let or_insert_with () =
  let defaults = [("x", fun () -> 100); ("y", fun () -> 200)] in
  let m = StringMap.empty in
  let m = List.fold_left (fun acc (k, f) ->
    match StringMap.find_opt k acc with
    | Some _ -> acc
    | None -> StringMap.add k (f ()) acc
  ) m defaults in
  assert (StringMap.find "x" m = 100);
  assert (StringMap.find "y" m = 200)

(* Approach 3: Modify existing or insert (and_modify + or_insert) *)
let and_modify_or_insert () =
  let update_or_insert m key default modify =
    match StringMap.find_opt key m with
    | Some v -> StringMap.add key (modify v) m
    | None -> StringMap.add key default m
  in
  let m = StringMap.empty in
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 1);
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 2);
  let m = update_or_insert m "count" 1 (fun x -> x + 1) in
  assert (StringMap.find "count" m = 3)

let () =
  or_insert ();
  or_insert_with ();
  and_modify_or_insert ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_or_insert() {
        or_insert_demo();
    }

    #[test]
    fn test_or_insert_with() {
        or_insert_with_demo();
    }

    #[test]
    fn test_and_modify() {
        and_modify_demo();
    }

    #[test]
    fn test_entry_ref() {
        entry_ref_demo();
    }

    #[test]
    fn test_or_default() {
        let mut m: HashMap<&str, Vec<i32>> = HashMap::new();
        m.entry("nums").or_default().push(42);
        assert_eq!(m["nums"], vec![42]);
    }
}

Deep Comparison

HashMap Entry API — Comparison

Core Insight

The "check-then-insert" pattern is so common that Rust dedicates a first-class API to it. The Entry API does one lookup and returns a handle that lets you insert, modify, or inspect — no second lookup needed. OCaml's immutable maps make this less critical (no aliasing bugs), but still require two operations.

OCaml Approach

• find_opt + add: check if key exists, then add if not

• No entry API — pattern matching on Option is idiomatic

• Helper function update_or_insert encapsulates the pattern

• Immutability means no aliasing hazards, so double-lookup is safe

Rust Approach

• entry() returns Entry<K, V> enum: Occupied or Vacant

• or_insert(val): insert default if vacant

• or_insert_with(|| expr): lazy default computation

• or_default(): use Default::default()

• and_modify(|v| ...): modify if occupied, chain with or_insert

• Returns &mut V — can mutate in place

Comparison Table

Pattern	OCaml	Rust
Insert if absent	`find_opt` + `add`	`entry(k).or_insert(v)`
Lazy default	`find_opt` + `add (f ())`	`entry(k).or_insert_with(f)`
Modify or insert	custom helper	`entry(k).and_modify(f).or_insert(v)`
Lookups needed	2 (find + add)	1 (entry)
Return value	new map	`&mut V`
Thread safety	N/A (immutable)	Requires `&mut HashMap`

Exercises

Use the Entry API to implement a group_by<K, V, F>(items: &[V], key_fn: F) -> HashMap<K, Vec<V>> function that avoids double lookups.

Write a cache<K, V, F>(cache: &mut HashMap<K, V>, key: K, compute: F) -> &V function using entry().or_insert_with(compute).

Implement word_pairs(text: &str) -> HashMap<(String, String), usize> that counts consecutive word pairs using the Entry API.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust