1029: HashMap Entry API

Difficulty: Intermediate Category: Data Structures Concept: The Entry API pattern for efficient insert-or-update without double lookups Key Insight: Rust's Entry API (`entry().or_insert()`, `and_modify()`) performs a single hash lookup for insert-or-update, while OCaml requires explicit `find_opt` + `add` (two traversals in the mutable case).

// 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_insert_with(Vec::new).push(i);
    }

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

fn main() {
    or_insert_demo();
    or_insert_with_demo();
    and_modify_demo();
    entry_ref_demo();
    println!("✓ All tests passed");
}

#[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"

📊 Detailed 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`