359: Multimap Pattern

Difficulty: 2 Level: Intermediate Map each key to multiple values using `HashMap<K, Vec<V>>` — the idiomatic Rust multimap.

The Problem This Solves

Sometimes one key legitimately maps to many values. A tag index maps each tag to many posts. An inverted search index maps each word to many document IDs. An event system maps each event type to many listeners. You could reach for a dedicated `MultiMap` type, but Rust doesn't have one in the standard library — and you don't need one. The pattern `HashMap<K, Vec<V>>` covers most cases directly. It's simple, obvious, and composes cleanly with iterators. When you need sorted keys or sorted values, swap in `BTreeMap<K, BTreeSet<V>>`. When you need uniqueness within a key's values, use `HashSet<V>` instead of `Vec<V>`. The main friction point is the "insert if key not present, then push" dance — which `entry().or_insert_with(Vec::new).push(v)` handles elegantly in one line.

The Intuition

There's no magic here. A multimap is just a map where each value is a collection. The `Entry` API is the key insight: instead of checking "does this key exist?", you grab a handle to the entry (occupied or vacant) and act on it atomically. This avoids a double-lookup and keeps the borrow checker happy. For sorted multimaps, `BTreeMap<K, BTreeSet<V>>` gives you keys in sorted order and deduplicated, sorted values per key — at the cost of `O(log n)` operations instead of `O(1)`.

How It Works in Rust

use std::collections::HashMap;

let mut index: HashMap<&str, Vec<u32>> = HashMap::new();

// The idiomatic insert pattern
let entries = [("rust", 1), ("rust", 2), ("ocaml", 3), ("rust", 4)];
for (tag, id) in entries {
 index.entry(tag).or_insert_with(Vec::new).push(id);
}

// Lookup
if let Some(ids) = index.get("rust") {
 println!("rust posts: {:?}", ids); // [1, 2, 4]
}

// Iterate all pairs
for (tag, ids) in &index {
 println!("{tag}: {} entries", ids.len());
}

For a sorted, deduplicated variant:

use std::collections::{BTreeMap, BTreeSet};
let mut sorted: BTreeMap<&str, BTreeSet<u32>> = BTreeMap::new();
sorted.entry("rust").or_default().insert(1);

What This Unlocks

Inverted indexes — word → document IDs, the foundation of every search engine.
Event dispatching — event type → list of handlers, without a framework.
Grouping — equivalent to SQL `GROUP BY`, using `entry().or_default().push()`.

Key Differences

Concept	OCaml	Rust
Multimap	No stdlib type; use `Hashtbl` with list values	`HashMap<K, Vec<V>>` with `entry().or_default()`
Insert-or-append	Manual check + add	`.entry(k).or_insert_with(Vec::new).push(v)`
Sorted multimap	`Map` with `Set` values	`BTreeMap<K, BTreeSet<V>>`
Unique values per key	`Hashtbl` with list dedup	`HashMap<K, HashSet<V>>`

use std::collections::HashMap;

struct MultiMap<K: Eq + std::hash::Hash, V> {
    inner: HashMap<K, Vec<V>>,
}

impl<K: Eq + std::hash::Hash, V> MultiMap<K, V> {
    fn new() -> Self { Self { inner: HashMap::new() } }
    fn insert(&mut self, k: K, v: V) { self.inner.entry(k).or_default().push(v); }
    fn get(&self, k: &K) -> &[V] { self.inner.get(k).map_or(&[], Vec::as_slice) }
    fn remove_all(&mut self, k: &K) -> Vec<V> { self.inner.remove(k).unwrap_or_default() }
    fn len(&self) -> usize { self.inner.values().map(|v| v.len()).sum() }
    fn keys_count(&self) -> usize { self.inner.len() }
}

fn invert_index(docs: &[(&str, Vec<&str>)]) -> MultiMap<String, String> {
    let mut idx: MultiMap<String,String> = MultiMap::new();
    for (doc, words) in docs {
        for &w in words { idx.insert(w.to_string(), doc.to_string()); }
    }
    idx
}

fn main() {
    let mut mm: MultiMap<&str,&str> = MultiMap::new();
    for (k,v) in [("fruit","apple"),("veg","carrot"),("fruit","banana"),("veg","broccoli"),("fruit","cherry")] {
        mm.insert(k,v);
    }
    let mut fruits = mm.get(&"fruit").to_vec(); fruits.sort();
    println!("Fruits: {fruits:?}");
    let mut vegs = mm.get(&"veg").to_vec(); vegs.sort();
    println!("Vegs: {vegs:?}");
    println!("Total entries: {}", mm.len());

    let docs = [("doc1", vec!["rust","ownership"]), ("doc2", vec!["rust","lifetimes"]), ("doc3", vec!["ocaml","ownership"])];
    let idx = invert_index(&docs);
    let mut rust_docs = idx.get(&"rust".to_string()).to_vec(); rust_docs.sort();
    println!("Docs with 'rust': {rust_docs:?}");
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn multi_insert() {
        let mut m: MultiMap<&str,i32> = MultiMap::new();
        m.insert("a",1); m.insert("a",2); m.insert("b",3);
        assert_eq!(m.get(&"a").len(), 2);
        assert_eq!(m.get(&"b"), &[3]);
    }
    #[test] fn missing_key_empty() {
        let m: MultiMap<&str,i32> = MultiMap::new();
        assert!(m.get(&"x").is_empty());
    }
}

(* OCaml: multimap via Hashtbl with list values *)

let mm_add tbl k v =
  let lst = try Hashtbl.find tbl k with Not_found -> [] in
  Hashtbl.replace tbl k (v::lst)

let () =
  let mm = Hashtbl.create 8 in
  List.iter (fun (k,v) -> mm_add mm k v)
    [("fruit","apple");("veg","carrot");("fruit","banana");("veg","broccoli");("fruit","cherry")];
  Hashtbl.iter (fun k vs ->
    Printf.printf "%s: [%s]\n" k (String.concat ", " vs)
  ) mm