359 Intermediate

359: Multimap Pattern

Functional Programming

Tutorial

The Problem

Standard maps store one value per key. A multimap stores multiple values per key — every tag in an index has multiple documents, every author writes multiple books, every event has multiple handlers. While no MultiMap exists in Rust's standard library, the pattern is straightforwardly implemented as HashMap<K, Vec<V>> with the entry API. This is the basis for inverted indexes in full-text search, adjacency lists in graph algorithms, and event subscription registries. Understanding the pattern helps recognize when it applies vs using (K, V) pair collections.

🎯 Learning Outcomes

• Implement MultiMap<K, V> wrapping HashMap<K, Vec<V>>

• Use entry(key).or_default().push(value) to append values

• Retrieve all values for a key with get(&key) -> Option<&Vec<V>>

• Remove one value from a key's list without removing the entire key

• Count values per key with count(&key)

• Recognize the multimap as an inverted index and adjacency list

Code Example

#![allow(clippy::all)]
//! # Multimap Pattern
//! Map with multiple values per key.

use std::collections::HashMap;

pub struct MultiMap<K, V> {
    inner: HashMap<K, Vec<V>>,
}

impl<K: Eq + std::hash::Hash, V> MultiMap<K, V> {
    pub fn new() -> Self {
        Self {
            inner: HashMap::new(),
        }
    }

    pub fn insert(&mut self, key: K, value: V) {
        self.inner.entry(key).or_default().push(value);
    }

    pub fn get(&self, key: &K) -> Option<&Vec<V>> {
        self.inner.get(key)
    }

    pub fn get_all(&self, key: &K) -> Vec<&V> {
        self.inner
            .get(key)
            .map(|v| v.iter().collect())
            .unwrap_or_default()
    }

    pub fn remove_one(&mut self, key: &K) -> Option<V> {
        self.inner.get_mut(key).and_then(|v| v.pop())
    }

    pub fn count(&self, key: &K) -> usize {
        self.inner.get(key).map(|v| v.len()).unwrap_or(0)
    }
}

impl<K: Eq + std::hash::Hash, V> Default for MultiMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn multiple_values() {
        let mut mm = MultiMap::new();
        mm.insert("tags", "rust");
        mm.insert("tags", "async");
        assert_eq!(mm.count(&"tags"), 2);
    }
    #[test]
    fn get_all_values() {
        let mut mm = MultiMap::new();
        mm.insert(1, "a");
        mm.insert(1, "b");
        let vals: Vec<_> = mm.get_all(&1).into_iter().cloned().collect();
        assert_eq!(vals, vec!["a", "b"]);
    }
    #[test]
    fn remove_one() {
        let mut mm = MultiMap::new();
        mm.insert("k", 1);
        mm.insert("k", 2);
        assert_eq!(mm.remove_one(&"k"), Some(2));
        assert_eq!(mm.count(&"k"), 1);
    }
}

(* 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

Key Differences

Aspect	Rust `HashMap<K, Vec<V>>`	OCaml `Hashtbl` (multimap)
Multiple values	Explicit `Vec<V>` per key	Implicit stacked bindings
Get all values	`get(k)` → `&Vec<V>`	`find_all k` → `list`
Ordered values	Yes (insertion order in `Vec`)	Yes (reverse insertion order)
Remove one	`Vec::pop()` on the inner vec	`Hashtbl.remove` removes one
Remove all	`HashMap::remove(k)`	`Hashtbl.remove` repeatedly

OCaml Approach

OCaml's Hashtbl natively supports multiple bindings per key:

let mm = Hashtbl.create 16

(* Hashtbl.add allows multiple values per key *)
let insert tbl k v = Hashtbl.add tbl k v

(* Retrieve all values for a key *)
let get_all tbl k = Hashtbl.find_all tbl k

(* Count values for a key *)
let count tbl k = List.length (Hashtbl.find_all tbl k)

Hashtbl.find_all returns all values associated with a key as a list. This differs from Rust's explicit HashMap<K, Vec<V>> — OCaml's multimap is implicit in Hashtbl's design (multiple add calls for the same key stack bindings).

Full Source

#![allow(clippy::all)]
//! # Multimap Pattern
//! Map with multiple values per key.

use std::collections::HashMap;

pub struct MultiMap<K, V> {
    inner: HashMap<K, Vec<V>>,
}

impl<K: Eq + std::hash::Hash, V> MultiMap<K, V> {
    pub fn new() -> Self {
        Self {
            inner: HashMap::new(),
        }
    }

    pub fn insert(&mut self, key: K, value: V) {
        self.inner.entry(key).or_default().push(value);
    }

    pub fn get(&self, key: &K) -> Option<&Vec<V>> {
        self.inner.get(key)
    }

    pub fn get_all(&self, key: &K) -> Vec<&V> {
        self.inner
            .get(key)
            .map(|v| v.iter().collect())
            .unwrap_or_default()
    }

    pub fn remove_one(&mut self, key: &K) -> Option<V> {
        self.inner.get_mut(key).and_then(|v| v.pop())
    }

    pub fn count(&self, key: &K) -> usize {
        self.inner.get(key).map(|v| v.len()).unwrap_or(0)
    }
}

impl<K: Eq + std::hash::Hash, V> Default for MultiMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn multiple_values() {
        let mut mm = MultiMap::new();
        mm.insert("tags", "rust");
        mm.insert("tags", "async");
        assert_eq!(mm.count(&"tags"), 2);
    }
    #[test]
    fn get_all_values() {
        let mut mm = MultiMap::new();
        mm.insert(1, "a");
        mm.insert(1, "b");
        let vals: Vec<_> = mm.get_all(&1).into_iter().cloned().collect();
        assert_eq!(vals, vec!["a", "b"]);
    }
    #[test]
    fn remove_one() {
        let mut mm = MultiMap::new();
        mm.insert("k", 1);
        mm.insert("k", 2);
        assert_eq!(mm.remove_one(&"k"), Some(2));
        assert_eq!(mm.count(&"k"), 1);
    }
}

(* 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

✓ Tests Rust test suite

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

    #[test]
    fn multiple_values() {
        let mut mm = MultiMap::new();
        mm.insert("tags", "rust");
        mm.insert("tags", "async");
        assert_eq!(mm.count(&"tags"), 2);
    }
    #[test]
    fn get_all_values() {
        let mut mm = MultiMap::new();
        mm.insert(1, "a");
        mm.insert(1, "b");
        let vals: Vec<_> = mm.get_all(&1).into_iter().cloned().collect();
        assert_eq!(vals, vec!["a", "b"]);
    }
    #[test]
    fn remove_one() {
        let mut mm = MultiMap::new();
        mm.insert("k", 1);
        mm.insert("k", 2);
        assert_eq!(mm.remove_one(&"k"), Some(2));
        assert_eq!(mm.count(&"k"), 1);
    }
}

Deep Comparison

OCaml vs Rust: Multimap Pattern

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Inverted index: Build a multimap from Vec<(word, doc_id)> pairs; query "all documents containing 'rust'" and "all documents containing both 'rust' and 'async'" (intersection of two value lists).

Adjacency list graph: Represent a directed graph as MultiMap<usize, usize> where insert(from, to) adds an edge; implement reachable_from(start) using BFS.

Dedup multimap: Add a insert_unique method that only adds the value if it's not already present for that key (requires V: PartialEq); implement using .contains() check before .push().

Open Source Repos

functional-rust

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

Rust