The HAMT: How Immutable Maps Stay Fast

The idea: a trie indexed by the hash, not the key

A trie routes a lookup by consuming a key one piece at a time — one character, one digit, one bit — descending a level per piece until it reaches the value. A HAMT plays the same game, but the "pieces" it consumes are fixed-width chunks of the key's hash rather than the key itself. The canonical chunk is 5 bits, so each node fans out up to 2⁵ = 32 ways, and the index into a node is simply the next 5 bits of the hash:

• Compute h = hash(key) (a 32- or 64-bit integer).
• At depth d, take idx = (h >>> (5·d)) & 0x1F — the next 5 bits.
• Follow the child at slot idx; if it is another internal node, recurse; if it is a leaf, you've found the key/value pair.

Because the hash is (ideally) uniform, this trie is self-balancing without any rotations: keys scatter evenly across slots regardless of insertion order, so the tree can't degenerate into a chain the way an unbalanced BST does. Consuming 5 bits per level means d levels distinguish 32^d keys, so to separate n keys you need only about log₃₂ n levels. For a billion entries (2³⁰) that's log₃₂(2³⁰) = 6 levels; the depth is hard-capped by the hash width — 7 levels for a 32-bit hash, 13 for a 64-bit hash — so lookup is O(log₃₂ n), which for any real map is a small constant.

Bitmap + popcount: dense speed at sparse cost

The obvious way to build a 32-way node is a 32-slot pointer array. But most nodes hold only two or three children, so an array-mapped trie that always allocates 32 slots wastes up to ~32× the memory — 256 bytes of pointers per node (on a 64-bit machine) to store a single child. Bagwell's insight was to make the array compact and reconstruct the mapping with a bitmap.

Each internal node stores a 32-bit bitmap plus a densely packed array holding only the occupied children. Bit i of the bitmap is 1 exactly when slot i is present. To find where child idx lives in the compact array:

• bit = 1 << idx
• If (bitmap & bit) == 0, the slot is empty — the key is absent, answered in one instruction.
• Otherwise the compact index is popcount(bitmap & (bit − 1)) — the number of occupied slots below idx.

popcount (population count, a.k.a. CTPOP) counts set bits. Modern CPUs do it in a single instruction — Intel's POPCNT shipped with SSE4.2 on Nehalem (2008), with single-cycle throughput; the JVM lowers Integer.bitCount to it, and LLVM lowers __builtin_popcount. So a HAMT node gives you the O(1) random access of a dense array with the footprint of a sparse one: a node with k children costs one bitmap word plus a k-slot array, and the popcount turns the sparse bitmap into a dense offset for free. This is the single trick that makes 32-way branching affordable enough to keep the tree shallow.

Path copying and structural sharing: why 'immutable' stays cheap

A HAMT is a persistent (immutable) data structure: an update never mutates a node that anyone can still see. Instead, inserting or changing a key uses path copying. Walk from the root to the leaf that must change, and copy only the nodes on that path — each copy is a fresh node with one array slot and one bitmap bit adjusted. Every subtree hanging off the side of the path is shared by reference with the old map. The new root you return points at the copied spine and the old, untouched branches; the old root still points at the original spine. Both maps are fully valid, and they physically share almost all of their nodes.

The cost is exactly the depth: O(log₃₂ n) node copies per update — at most 7 (32-bit hash) or 13 (64-bit) small allocations, not a full clone of the map. That is the whole reason immutability is affordable here. "Copy the map, then change one key" sounds like O(n); path copying makes it effectively O(1).

The correctness invariant is one sentence: a node is immutable once it is reachable from a published root. From it, everything else follows. Old versions are valid forever, which gives you free undo/history and time-travel debugging. And because no reachable node is ever mutated, concurrent readers need no locks — there are no data races because there are no writes to shared state. A thread holding an old root simply keeps seeing a consistent snapshot while others build new ones. This is why HAMTs underpin the immutable collections of languages built for concurrency.

Collisions, attacks, and the failure modes

Two distinct keys can hash to the same value. Once a HAMT exhausts the hash bits (all 32 or 64 consumed) and two live keys still share the full hash, it cannot separate them by descending further, so it parks them in a collision node — a small bucket of key/value pairs scanned linearly and compared with the real equals. With a good hash and 32/64-bit widths, this is astronomically rare: by the birthday bound you expect a full-hash collision only after roughly 2¹⁶ ≈ 65,000 keys for a 32-bit hash, or ~2³² ≈ 4 billion for 64-bit. Collision nodes keep correctness intact regardless.

The real danger is adversarial. In a hash-flooding (algorithmic-complexity) attack, an attacker who knows the hash function crafts thousands of keys that collide in their low bits, forcing deep chains and fat collision nodes and dragging operations toward O(n) — a denial-of-service vector famously demonstrated against web frameworks' hash maps in 2011. Defenses:

• Avalanche the hash. Many implementations spread high bits into low ones (Java's HashMap XORs h ^ (h >>> 16)) so that keys with weak hashCode()s still fill the trie evenly.
• Keyed hashing. Use a per-process randomized, keyed hash such as SipHash for untrusted keys, so an attacker cannot predict which keys collide.

The subtler failure mode is a merely bad hash: clustering deepens the trie, inflates collision nodes, and erodes the log₃₂ n guarantee toward the balanced-tree O(log₂ n) or worse. The structure's speed is only ever as good as the uniformity of its hash.

Why the complexity holds — the numbers with reasoning

Lookup. Each level does a constant amount of work: extract 5 bits, test one bitmap bit, one popcount, one array index, then chase a pointer. The number of levels is bounded by the hash width divided by 5 — ≤7 for 32-bit, ≤13 for 64-bit hashes — and expected depth is log₃₂ n because uniform hashing fills 32^d buckets at depth d. So worst-case lookup is O(log₃₂ n), a genuine hard cap, not an average that a bad workload can blow up (short of a hash attack).

Update. An assoc/dissoc descends the same path, then rebuilds it bottom-up, allocating one new node per level. That's O(log₃₂ n) copies; each copy's array grows or shrinks by one slot (an O(32) memcpy worst case, tiny in practice). No rebalancing, no rotations, no amortized resize — unlike a mutable hash table, a HAMT never stops the world to rehash into a bigger bucket array.

• Memory: a node with k children costs one bitmap word + k pointers, so the whole structure is roughly proportional to n, with the fan-out keeping depth (and therefore per-op allocation) low.
• Constant factors: the win over a persistent red-black tree is that 32-way branching makes the tree ~5× shallower (log₃₂ vs log₂), so a persistent update copies ~5× fewer nodes — the difference between copying ~7 nodes and ~30 for a million-entry map.
• The trade you accept: keys come out in hash order, i.e. effectively unordered. If you need sorted iteration or range queries, a balanced BST is the right tool; a HAMT is a hash map, not an ordered map.

Real systems, transients, and CHAMP

HAMTs are the default immutable map across a swath of production runtimes. Clojure (Rich Hickey, ~2007) built PersistentHashMap on a HAMT and the analogous 32-way bit-partitioned vector trie for PersistentVector; the same machinery powers the immutable database Datomic. Scala's immutable.HashMap, Facebook's Immutable.js Map (5-bit, 32-way), and Haskell's unordered-containers HashMap are all HAMTs. Erlang/OTP is a neat hybrid: a map with ≤32 entries is a flat sorted array, and above that threshold it switches to a HAMT internally.

Two refinements matter in practice:

• Transients. Building a big map one path-copy at a time allocates a lot. Clojure's transients add a temporary, single-threaded mutable mode: each node carries an ownership tag, and nodes owned by the current builder are mutated in place while shared nodes are still copied on first touch — a targeted copy-on-write that makes bulk construction fast, then "freezes" back into a persistent map in O(1).
• CHAMP. Steindorfer & Vinju's Compressed Hash-Array Mapped Prefix-tree (OOPSLA 2015) splits the node into two bitmaps — one for inline data entries, one for sub-node pointers — and keeps entries in a canonical order. That improves cache locality and iteration/equality speed and shrinks the footprint; the paper reports memory savings of roughly 1.3–6.7× over the incumbent Clojure/Scala HAMTs. Scala 2.13 adopted CHAMP for its immutable HashMap.

Benchmarks use footprint measurement over the object graph and JMH throughput for lookup, insert, and iteration — the metrics that separate CHAMP's tightened layout from the classic design.

How it differs from look-alikes

vs. a mutable hash table. A java.util.HashMap is one mutable object: O(1) lookup and update, but a write is destructive, sharing it across threads needs locks, and it periodically rehashes into a larger bucket array (an O(n) hiccup). A HAMT trades a hair of lookup speed (a few pointer chases) for cheap immutability, snapshotting, and lock-free reads.

vs. a persistent balanced BST. Clojure's sorted-map and Haskell's Data.Map are persistent red-black / weight-balanced trees: same path-copying idea, but 2-way branching means log₂ n depth — ~5× deeper than a HAMT, so ~5× more nodes copied per edit — in exchange for sorted key order and range queries a HAMT can't offer.

vs. a full array-mapped trie. Drop the bitmap and store 32 slots per node and you get the same O(1) branching but up to ~32× the memory. The bitmap+popcount compression is precisely what makes 32-way fan-out practical.

vs. a radix tree / Patricia trie. Those branch on chunks of the key itself and preserve key order and prefix queries; a HAMT branches on chunks of the hash, giving uniform shallow balance at the cost of any meaningful ordering.

vs. an LSM-tree. Both favor immutability and sharing, but an LSM-tree is a disk-oriented write-batching structure with compaction; a HAMT is an in-memory persistent map optimized for point lookups and cheap versioned snapshots.

How a HAMT compares with other map implementations (n = number of entries)

Implementation	Lookup	Persistent update	Key order	Memory / notes
Mutable hash table (java.util.HashMap)	O(1) avg	destructive — not persistent	none (bucket order)	Bucket array, resize at load factor; one shared copy
Persistent balanced BST (Clojure sorted-map, Haskell Data.Map)	O(log₂ n)	O(log₂ n) path copy	sorted by key	2-way nodes; ~log₂ n nodes copied per edit
HAMT (Clojure, Scala, Immutable.js)	O(log₃₂ n) ≈ O(1)	O(log₃₂ n) path copy	hash order (unordered)	Bitmap + compact array; ≤7 (32-bit) / ≤13 (64-bit) levels
Array-mapped trie without bitmap	O(log₃₂ n)	O(log₃₂ n) path copy	hash order	Same depth as a HAMT — bitmap changes memory, not time; full 32-pointer array per node → up to ~32× waste
CHAMP (Scala 2.13 immutable HashMap)	O(log₃₂ n)	O(log₃₂ n) path copy	hash order	Two bitmaps; reported ~1.3–6.7× leaner, faster iteration