F4 · Persistent maps · module 5
Hash array mapped tries
F4.04 sent a key through a hash to a slot in one flat table. A HAMT — a hash
array mapped trie — spreads that idea over a tree. It consumes the key’s hash a few bits at a time,
branching up to 32 ways at each level, so a node is a small bitmap plus one packed array, and
the depth is about log₃₂ n — roughly four levels for millions of
keys.
It is the structure the BEAM uses for a large immutable map, and the first of the chapter’s three persistent-map modules: the page registry behind the portal is a map, and that map is a trie like this one.
A set bit maps to a packed slot by popcount
bitmap 0b00100100 · 2 slots set
Each set bit owns one packed slot; its index is the popcount below it.
Inside a HAMT node
A node describes its 32 slots with one bitmap: a bit is set for each occupied slot. The occupants live in a single packed array sized to the number of set bits, so an empty slot costs nothing. A slot can hold an inline entry or a child node — both kinds share that one array. Select an angle.
The angle · select one (8 of 32 slots shown)
role: one bitmap, one packed array
in short: the array holds only the present slots
A bitmap plus a packed array turns a 32-wide node into a compact one, and a few hash bits per level keep the tree shallow. The three dives take the node, the descent, and the way an edit shares structure in turn.
Three deep dives
In order: how one node packs its slots, how the hash chooses a path down the tree, and how an insert reuses almost all of the old map — each tied to the portal’s page registry.
bitmap marks the occupied slots; a single packed array holds them, and a slot’s position is found by popcount.log₃₂ n.Advanced: a tree of 32-way nodes
Why 32, and not two? A binary trie on a 27-bit hash would be 27 levels deep; a 32-way trie reads five bits at a time, so 27 bits is about six levels and a realistic hash about four. Each level is a constant-time slot lookup, so a wide, shallow tree behaves like the flat table from F4.04 while staying a tree — which is what makes it cheap to share and to grow. A small map skips the tree entirely and stays a flat sorted array until it outgrows 32 keys; only then does it become a trie.
The BEAM’s built-in map is exactly this kind of structure, so reaching for Map
already gives you a HAMT — you build one by hand only when you want a variant the runtime does not offer,
which is where F4.06 (CHAMP) and the stack’s BrandedChamp trie come in. For the
portal, the page registry is a map from a route to a %Page{}, keyed by a branded
Snowflake id; storing it as a trie is what lets a new snapshot reuse the old one.
# a HAMT node: one bitmap + one packed array, sized to the set bits defmodule Hamt.Node do defstruct bitmap: 0, slots: {} # slots holds leaves and children, packed end # F4.04: one flat table, a slot per hash-mod-size, resized as it fills # F4.05: a tree of these nodes, branch-32 per level, depth ~ log32 n
F4.04 · one flat slot table
A hash sends each key to a slot in a single array that is resized as it fills.
F4.05 · a tree of 32-way nodes
The hash picks a path through small bitmapped nodes; depth stays near log₃₂ n.
Start with bitmapped nodes, then hash-prefix indexing, then structural sharing. Predecessor: F4.04 — Maps, sets & hashing. Next module: F4.06 — CHAMP maps, the compressed successor that splits the one array into two and gives the tree a canonical shape.
References
Primary sources for this lesson, and where it connects in the course.
Sources
- Bagwell, P. (2001). Ideal Hash Trees. — the original HAMT paper.
- Hash array mapped trie — Wikipedia — the structure in brief.
Related in this course
- F4.04 · Maps, sets & hashing — the flat table this trie generalises.
- F4.06 · CHAMP maps — the compressed successor.
- Structural sharing — how an insert reuses the old map.