🗄️ Hash Map

Persistent functional hash map with separate chaining

Overview

An immutable hash map using separate chaining with resizable bucket arrays. All operations return new maps — old versions remain valid (structural sharing via Array.copy). Automatically resizes when load factor exceeds 0.75.

Concepts Demonstrated

Persistent data structures — immutable maps with structural sharing
Hash tables — bucket arrays, hash functions, collision resolution
Load factor management — automatic resizing at 75% capacity
Functor-style API — FunMap module with comprehensive operations
Higher-order functions — fold, map, filter, merge, for_all, exists

Key Functions

Function	Description
`create`	Create empty map with optional capacity
`insert`	Add/update a key-value pair
`find`	Look up by key (returns `option`)
`remove`	Remove a key
`mem`	Check membership
`fold` / `iter`	Traverse all bindings
`map` / `mapi`	Transform values (with or without keys)
`filter`	Keep bindings matching a predicate
`merge`	Combine two maps with a merge function
`equal`	Structural equality comparison
`of_list` / `to_list`	Convert to/from association lists

Usage

open FunMap

let m = empty
  |> insert "alice" 30
  |> insert "bob" 25
  |> insert "charlie" 35

let _ = find "alice" m         (* → Some 30 *)
let _ = mem "dave" m           (* → false *)
let _ = size m                 (* → 3 *)

(* Immutable: original 'm' unchanged after operations *)
let m2 = remove "bob" m       (* m still has 3 entries *)

Resizing Strategy

The map starts with 16 buckets and doubles capacity when the load factor (size/capacity) exceeds 0.75. Resizing rehashes all entries into the new bucket array. This amortizes to O(1) per insertion.

let should_resize m =
  m.size > (m.capacity * 3 / 4)