The Hash-Array Mapped Trie

A hash table stores entries in buckets and resizes by rehashing everything. That is a whole-table operation, which makes it hostile to persistence: there is no small set of nodes to copy, so keeping the old version means keeping a second table.

Bagwell's answer in 2001 was to remove the resize by making the table a tree. The key is hashed once and the resulting bits are spent a few at a time as a path through a trie. There is no load factor, no resize threshold, and no rehash — the structure grows by adding nodes where they are needed.

Five bits per level means 32 slots per node, and a node holding three children should not pay for 32 pointers. Each node therefore stores a 32-bit bitmap plus a dense array holding only the children that exist.

struct Node {
    uint32_t bitmap;      // bit k set iff slot k is occupied
    void    *children[];  // only the occupied ones, in slot order
}

Bit k is set exactly when slot k is occupied, and the array holds those children in slot order with no gaps. A node with three children costs one word plus three pointers instead of thirty-two.

The bitmap has to translate a slot number into an array position. The child's index is the number of occupied slots below it, which is a population count over the masked bitmap.

bool has(Node *n, int k) {
    return n->bitmap & (1u << k);
}

int index(Node *n, int k) {
    return popcount(n->bitmap & ((1u << k) - 1));
}

Both are a handful of instructions, and popcount is a single one on current hardware. This is what makes wide branching affordable: selection stays constant-time without storing the empty slots.

Lookup hashes the key once, then walks down consuming five bits per level.

value_t get(Node *n, key_t key, uint32_t hash, int shift) {
    int k = (hash >> shift) & 31;
    if (!has(n, k)) return NOT_FOUND;

    void *child = n->children[index(n, k)];
    if (is_entry(child))
        return keys_equal(child->key, key) ? child->value : NOT_FOUND;

    return get(child, key, hash, shift + 5);
}

The full key is compared at the bottom, because arriving at an entry means the hash bits agreed, not that the keys did. A 32-bit hash at five bits per level bottoms out after seven levels, so the depth does not depend on how many entries the map holds.

Insertion descends the same way, then rebuilds the path back to the root. Each node on the path is copied with one pointer changed; everything hanging off the path is reattached.

Node *assoc(Node *n, key_t key, value_t val, uint32_t hash, int shift) {
    int k = (hash >> shift) & 31;
    int i = index(n, k);

    if (!has(n, k))                       // empty slot: widen this node
        return copy_with_inserted(n, k, i, entry(key, val));

    void *child = n->children[i];
    if (is_entry(child))
        return copy_with_replaced(n, i, resolve(child, key, val, hash, shift + 5));

    return copy_with_replaced(n, i, assoc(child, key, val, hash, shift + 5));
}

Every return is a fresh node, so the old map is untouched and stays valid. With at most seven levels, an insertion allocates at most seven nodes whatever the map's size — the bounded update cost a flat table cannot offer.

The interesting case is resolve: the slot already holds an entry, and a different key wants it. The two keys' hashes agree on the bits consumed so far, so the fix is to push both down until they disagree.

void *resolve(Entry *old, key_t key, value_t val, uint32_t hash, int shift) {
    if (hash == old->hash) return collision_node(old, entry(key, val));

    int a = (old->hash >> shift) & 31;
    int b = (hash      >> shift) & 31;
    if (a == b)                              // still agreeing: go deeper
        return node_with(a, resolve(old, key, val, hash, shift + 5));

    return node_with_two(a, old, b, entry(key, val));
}

The trie therefore deepens only where hash values actually share a prefix, and stays shallow everywhere else. Depth is driven by collisions in the consumed bits, not by the number of entries.

When two distinct keys hash to the same value, no amount of descending separates them — the bits run out. The structure then stores a collision node holding every entry with that full hash, searched by linear scan with full key equality.

With a 32-bit hash the birthday bound makes this ordinary rather than exotic: collisions become likely at tens of thousands of entries. It is a required case, not a defensive branch, and implementations on 32-bit hash platforms such as the JVM must handle it for the map to be correct. Unlike a Bloom filter, a collision here costs time and never correctness, because the full key is always compared.

Removal clears a bit, drops a pointer, and rebuilds the path — the mirror of insertion. The subtlety is what to do when that leaves a node nearly empty.

Node *dissoc(Node *n, key_t key, uint32_t hash, int shift) {
    int k = (hash >> shift) & 31;
    if (!has(n, k)) return n;                    // absent: unchanged

    int   i     = index(n, k);
    void *child = n->children[i];
    void *next  = is_entry(child)
                ? (keys_equal(child->key, key) ? NULL : child)
                : dissoc(child, key, hash, shift + 5);

    if (next == NULL)   return copy_with_removed(n, k, i);
    if (is_lone_entry(next)) return copy_with_replaced(n, i, next);  // collapse
    return copy_with_replaced(n, i, next);
}

That third case is the one naive implementations omit, and the next card is what it costs to skip it.

A node left holding a single entry and no child nodes is an indirection that a freshly built map of the same contents would not have. Left in place, the tree's shape depends on its history rather than its contents.

Two properties break. Structural equality — comparing two maps by walking their trees — reports a difference between maps holding identical entries, so equality has to fall back on an entry-by-entry comparison. And iteration walks nodes containing nothing, so traversal cost reflects what was deleted rather than what remains. Collapsing on the way up costs nothing asymptotically, since the path is being rebuilt anyway.

Steindorfer and Vinju's CHAMP keeps the algorithm and changes the node. Two bitmaps replace one, separating slots holding entries from slots holding children, and the two kinds live at opposite ends of a single array.

struct ChampNode {
    uint32_t data_map;   // slots holding entries
    uint32_t node_map;   // slots holding child nodes
    void    *slots[];    // entries packed from the front,
                         // child pointers from the back
}

The bitmap now says which kind a slot holds, removing a type check per access, and every entry of a node sits in one contiguous run. With strict canonicalisation that makes structural equality a valid shortcut again, and improves memory and whole-map traversal rather than single-key lookup, which was already fast.

Building a map by inserting n entries allocates a path per insertion, so constructing a large map allocates far more nodes than it keeps. Every intermediate version is garbage the moment the next insertion happens.

Clojure's transients recover that. A transient carries an ownership token, and nodes created while it is owned record that token; an insertion reaching a node stamped with the same token mutates it in place, because no other version can observe it. Nodes without the token are copied as usual, and the copy takes the token. Converting back clears it, after which every node is immutable again. The safety condition is that the transient must not be shared, and use after conversion is detected rather than silently wrong.

The bits consumed per level set the tree's shape. Four bits give 16-way nodes and depth eight for a 32-bit hash; five give 32-way and depth seven; six give 64-way and depth six. Wider nodes mean fewer dependent loads per lookup and fewer nodes copied per update.

The pressure back is the cost of a node. A 64-way node needs a 64-bit bitmap and a 64-bit popcount, and copying a node costs one write per child it holds, so wide nodes make each path-copy step more expensive even though there are fewer steps. Thirty-two wins because the bitmap is one machine word and its popcount is one instruction. Spending more bits per level also exhausts the hash sooner, reaching collision nodes at shallower depth.

Against a flat open-addressed table, a HAMT costs more per entry and more per access: each level is a separately allocated node with a header, a bitmap, and an array, and a lookup is a chain of dependent loads rather than one probe. For a single mutable map doing exact lookups, the flat table wins on both axes.

What the tree buys back is that an update is bounded work rather than an occasional whole-table rehash, that any number of versions coexist sharing storage, and that a version can cross threads with no synchronisation because nothing is mutated. A million-entry map and a snapshot taken a moment earlier differ by the nodes on the changed paths.

The structure gives lookup bounded by hash width, updates that copy at most one path, persistence with structural sharing across arbitrarily many versions, no resize step and so no latency spike, and lock-free concurrent reads. Transients recover most of the bulk-construction cost.

It costs a dependent load per level, per-node overhead above a flat table's, and allocation on every update. It also carries a correctness burden that is easy to omit — collision nodes and canonical deletion — whose absence produces a structure that is subtly wrong rather than plainly broken. And it offers no ordering at all: iteration follows hash bits, so range queries need a persistent search tree instead, at O(log n) rather than near-constant.

Clojure implements PersistentHashMap and PersistentHashSet as 32-way HAMTs, and they are what the language's map and set literals produce. Their persistence is what lets Clojure's reference types update by installing a new immutable value rather than mutating shared state. Scala's 2.13 collections rewrote immutable.HashMap and immutable.HashSet onto CHAMP.

Erlang's maps switch representation by size: small maps are a flat sorted structure, and above 32 keys the runtime converts them to a HAMT, so the trie backs any large map in Erlang or Elixir. In Haskell, unordered-containers implements Data.HashMap as a HAMT, and it is the map underneath aeson's JSON objects — so parsing a JSON document builds these tries. Immutable.js uses the same construction for its Map and Set.

A hash-array mapped trie hashes the key and spends the hash a few bits at a time as a path. Each node holds a bitmap and a dense array of its occupied slots, so child selection is a bit test plus a popcount and a node costs one word per actual child. A 32-bit hash at five bits per level bottoms out in seven levels.

Because the path is short and bounded, an update copies at most that many nodes and shares the rest — persistence without a whole-table rehash. Correctness requires collision nodes where hashes are equal and canonical collapsing on delete. What it gives up is one dependent load per level against a flat table, and ordering entirely against a search tree.