HAMT: Hash Array Mapped Trie

From Hash Codes to Trie Paths

A HAMT begins with an ordinary hash function that turns a key into a fixed-width integer, commonly thirty-two bits. Rather than using that hash as a single array index the way a plain hash table does, a HAMT treats the hash as a sequence of small chunks and uses each chunk to navigate one level deeper into a tree. With a chunk size of five bits, a thirty-two bit hash yields up to seven levels of chunks (the last one partial), and each chunk can take one of thirty-two values since five bits encode numbers from zero through thirty-one. At the root, the first five bits of the hash select which of thirty-two possible child branches to follow. At the next level down, the following five bits of the same hash select the next branch, and so on until the key is either found in a leaf or the trie runs out of levels and falls back to a linked list or collision node for keys that hash identically. This is why the branching factor of thirty-two is so important: with only five levels needed to distinguish among roughly one billion possible hash values, the tree stays extremely shallow even for very large collections. Contrast this with a plain binary tree, which needs roughly thirty levels to hold the same number of entries. Because the depth grows as the logarithm of the number of elements, but with base thirty-two instead of base two, the number of levels actually traversed for any realistic map, even one with billions of entries, is typically no more than six or seven hops. Each hop does a small constant amount of work: extract the next five-bit chunk, and use it to index into an array. This is what gives HAMTs their reputation for near-constant time get, insert, and remove operations, even though technically the complexity is logarithmic rather than truly constant. The trie structure alone, however, does not explain the memory efficiency or the immutability story; for that, the bitmap and popcount mechanism described next is essential.

The Bitmap: Marking Which Children Exist

If every node in the trie allocated a full thirty-two-slot array to hold its children, most of those slots would sit empty for any node that is not densely populated, which is the overwhelmingly common case in real-world maps. A node near the bottom of the trie might have only one or two actual children out of the thirty-two possible positions, so reserving thirty-two pointers, most of them null, would waste enormous amounts of memory across millions of nodes. The HAMT design solves this with a thirty-two bit bitmap stored alongside each internal node. Each of the thirty-two bit positions in this bitmap corresponds to one of the thirty-two possible child slots at that level of the trie, determined by the five-bit chunk value used to reach that slot. If a child exists at position k, the bit at position k in the bitmap is set to one; if no child exists there, the bit stays zero. So instead of a sparse thirty-two element array, the node stores a single thirty-two bit integer as the bitmap plus a compact array sized exactly to the number of actual children, no more and no fewer. This is a direct application of a general technique called a bitset or bit-indexed structure, and it means memory usage scales with the number of elements actually stored, not with the theoretical branching factor. A node with three children uses a bitmap plus a three-element array; a node with thirty children uses the same size bitmap plus a thirty-element array. The bitmap itself costs a small constant amount of space, typically a single machine word, regardless of how many children are present. When a lookup or update needs to check whether a child exists at a given five-bit index, it simply tests whether that one bit is set in the bitmap, an extremely fast bitwise operation. The harder question, addressed next, is how the algorithm finds where in the compact array that child actually lives, since the compact array does not have thirty-two slots to index into directly.

Popcount: Mapping Bitmap Positions to Array Indices

Knowing that a bit is set at position k in the bitmap tells you a child exists, but the compact array is dense, meaning its elements are packed together with no gaps, so the child is not necessarily sitting at index k in that array. Instead, its position in the compact array equals the number of bits that are set in the bitmap at positions below k. This count of set bits is known as the population count, or popcount, of the bitmap masked to only the bits before position k. Concretely, to find a child at bit position k, the algorithm creates a mask covering bits zero through k minus one, applies a bitwise AND between that mask and the node's bitmap, and counts how many one-bits remain; that count is exactly the index into the compact array where the child lives, because every set bit before position k corresponds to a child that was packed into the array before this one. Modern processors provide a dedicated popcount instruction, often called POPCNT, that computes this count in a single fast operation, which is why this technique is efficient enough for a data structure meant to be used pervasively throughout a program's data. Without hardware support, popcount can still be computed quickly with a handful of bitwise tricks that process multiple bits in parallel rather than looping over each of the thirty-two bits individually. This bitmap-plus-popcount combination is sometimes called a compressed or bit-indexed array, and it appears in other space-efficient data structures beyond HAMTs, such as succinct rank and select structures used in some search indexes. The overall effect for a HAMT is that every internal node pays only for the children it actually has: one bitmap word of fixed overhead plus one array slot per real child, with the popcount calculation providing the bridge between the sparse conceptual thirty-two-way branching and the dense physical storage layout, all computed on demand rather than stored explicitly.

Structural Sharing and Persistent Updates

The second pillar of the HAMT design, alongside the bitmap and popcount trick, is how it supports immutability without paying for a full copy on every change. In a persistent data structure, an update operation such as inserting or removing a key never modifies the original structure in place; instead it produces a brand new version of the structure while leaving the old version fully intact and usable, which is essential for safe concurrent access and for features like undo history or snapshotting. A naive way to achieve this would be to copy the entire trie on every update, but that would destroy the performance benefits of the shallow tree. HAMTs avoid this by using structural sharing: an update walks down from the root along the same five-bit-chunk path used for a lookup, and at each level it allocates a new node that is a shallow copy of the old node with one child pointer added, removed, or replaced, plus an updated bitmap if a child was added or removed. Crucially, all of the other child pointers in that new node still point to the exact same subtrees as the old node, meaning those subtrees are not copied at all. Since the trie is shallow, typically only five to seven nodes deep, an update allocates only that many new nodes, roughly the logarithm base thirty-two of the collection size, while every branch not on the path from root to the changed key remains shared between the old and new versions of the map. This is why the earlier claim of logarithmic time operations applies equally to inserts and deletes, not just lookups: the work done is proportional to the depth of the trie, not to the total number of elements. The old version of the map remains a perfectly valid, unmodified data structure that other parts of a program can keep using safely even after the update happened, which is exactly the guarantee that functional languages rely on for safe concurrency without locks.

Why This Matters in Practice

The combination of a shallow wide trie, compact bitmap-indexed nodes, and structural sharing is what makes HAMTs practical as the default map and set implementation in production functional languages rather than just a theoretical curiosity. Clojure's persistent hash map, introduced by Rich Hickey and directly inspired by earlier academic work on HAMTs by Phil Bagwell, is used pervasively throughout idiomatic Clojure code because programs can pass around what looks like a plain immutable map value while the runtime shares memory aggressively behind the scenes, avoiding the cost that naive copy-on-write collections would impose. Scala's immutable HashMap and HashSet in its standard library use the same approach, and similar bitmap-indexed trie techniques appear in Erlang and Elixir's map implementation. The practical benefits show up in several ways. First, memory overhead per update is small and predictable, proportional to trie depth rather than collection size, so even maps with millions of entries can be updated cheaply thousands of times per second. Second, because old versions remain valid and unchanged, multiple threads can read a shared map concurrently without any locking, since no thread ever mutates data another thread might be reading; a new version simply becomes available as a separate value. Third, the shallow depth from the wide branching factor keeps read performance close to that of a mutable hash table, so functional programs do not pay a steep performance tax for immutability the way they would with, for example, a naive immutable linked list or an unbalanced tree. There are trade-offs: HAMTs typically have somewhat higher constant-factor overhead than a raw mutable hash table due to the extra indirection of tree nodes and the popcount computation on every access, and hash collisions still need a fallback mechanism such as collision nodes holding multiple entries. Still, for languages and systems that need genuinely immutable collections at scale, the HAMT remains the standard, well-understood answer.

Frequently asked questions

Try it live

Everything above runs in your browser — open HAMT: Hash Array Mapped Trie and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.