Dive C4.05.2

The HAMT

Hash the key, read it five bits at a time, and a node fits in a bitmap and one packed array.

A HAMT — a hash array mapped trie — is the prefix trie of the last dive with two changes. First, the key is hashed, and the descent reads the hash in fixed 5-bit slices: each slice is a number 0–31 that picks one of a node's 32 slots, and 5 bits per level means the depth is about log₃₂ n — four levels for millions of keys. Second, a node does not store 32 cells. It stores a 32-bit bitmap (a bit set per occupied slot) and one packed array sized to the set bits; a slot's array position is the popcount of the bits below it. This dive builds those pieces in F#, with System.Numerics.BitOperations.PopCount, all verified in dotnet fsi. One thing it states up front and never walks back: F#'s built-in Map is not a HAMT.

Insert into a node Module hub

C4.05.2 · the honest part

F#'s Map is a balanced tree — read this first

This dive teaches the HAMT as a technique — a structure you would build by hand or take from a library. It does not describe F#'s Map. F#'s Map is the standard library's immutable persistent map, and it is a balanced binary search tree (an AVL tree), not a HAMT. The two are kin — both O(log n) lookup, both persistent — but they place keys differently: a HAMT by hash with 32-way fan-out, a balanced tree in sorted order with binary branching. So when this dive shows a bitmap and a popcount, that is the HAMT design, and where it shows F# code calling Map, that is the balanced tree. The course never conflates them.

Held throughout: F#'s Map is not a HAMT, and the echo_fs port does not ship a HAMT — it uses the stdlib Map. The HAMT below is the design Elixir's Map and Clojure use; on the BEAM, reaching for Map does give you a HAMT, which is the difference C4.05 keeps in view.

C4.05.2 · part 1

A slot's place is the popcount below it

The node's compactness rests on one fact: given the bitmap, a slot's index in the packed array is the number of set bits strictly below that slot — its popcount. .NET exposes popcount directly as System.Numerics.BitOperations.PopCount, so the index is a couple of bitwise operations and one count. Masking the bits below a slot is (1u <<< slot) - 1u.

open System.Numerics

// the slot's array index = popcount of the set bits strictly below it
let indexOfSlot (bitmap: uint32) (slot: int) : int =
    let below = bitmap &&& ((1u <<< slot) - 1u)
    BitOperations.PopCount below

let bitmap = 0b00100100u            // slots 2 and 5 set
BitOperations.PopCount bitmap        // val it : int = 2
indexOfSlot bitmap 2               // val it : int = 0
indexOfSlot bitmap 5               // val it : int = 1

Inserting a slot splices a cell into the packed array at that index, and a 5-bit slice of the hash chooses the slot at each level:

// insert one cell at the popcount index — the packed array grows by one
let insertAt (i: int) (x: 'v) (arr: 'v array) : 'v array =
    Array.concat [ arr.[.. i-1]; [| x |]; arr.[i ..] ]

let packed = [| "a"; "c" |]               // slots 2,5 -> array[0],array[1]
insertAt (indexOfSlot bitmap 4) "b" packed   // val it : string[] = [|"a"; "b"; "c"|]

// a level's slot = a 5-bit slice of the hash (0..31)
let sliceAt (hash: uint32) (level: int) : int =
    int ((hash >>> (5 * level)) &&& 0x1Fu)

bitmap: a uint32; bit k set means slot k is occupied.
popcount: BitOperations.PopCount — counts set bits; of the bits below a slot, it is that slot's array index.
packed array: one cell per set bit, in slot order; an empty slot costs nothing.
5-bit slice: (hash >>> 5*level) &&& 0x1F — the slot to take at that level, 0–31.

C4.05.2 · part 2

The node, as an F# record

A node is a bitmap and a packed array. The array holds either inline entries or child nodes — both kinds share the one array, indexed the same way. Modelled as a record, the lookup hashes the key, then descends slice by slice: at each level, check the slot's bit; if set, take its packed cell; if it is a child, recurse with the next slice. Depth is bounded by ~log₃₂ n.

// a HAMT node: one bitmap + one packed array sized to the set bits
type HamtNode<'v> =
    { Bitmap: uint32
      Slots: 'v array }   // packed: one entry per set bit, in slot order

// is slot k occupied?  -> test bit k
let isSet (bm: uint32) (slot: int) = (bm &&& (1u <<< slot)) <> 0u
isSet 0b00100100u 2   // val it : bool = true
isSet 0b00100100u 3   // val it : bool = false

Why 32 and not 2? A binary trie on a 32-bit hash is 32 levels deep; reading 5 bits at a time makes 32 bits about seven levels, and a realistic key around four. Each level is a constant-time bit test plus a popcount, so a wide, shallow tree behaves like a flat table while staying a tree — which is what keeps it cheap to share and to grow.

Insert a key into one node

Insert a key on the node below. The bitmap flips the new slot's bit on; the packed array grows by exactly one cell, spliced in at the popcount index; and the readout shows the arithmetic — popcount(bits below slot) giving the array position. Every value is computed by the same indexOfSlot the code uses, over a fixed eight-slot bitmap. The static diagram and table below stand without scripting.

index(slot) = popcount(bits below slot) · 8 of 32 slots

bitmap 0b00100100 · 2 slots set. A slot's array index is the popcount of the bits below it: slot 2 → array[0], slot 5 → array[1].

Without JavaScript: the initial node, slots 2 and 5 set
bitmap	0b00100100 (popcount 2)
slot 2	popcount(below) = 0 → array[0]
slot 5	popcount(below) = 1 → array[1]
insert slot 4	popcount(below) = 1 → splice at array[1]

A bitmap plus a packed array makes a 32-wide node compact, and popcount turns a slot into an array index in a couple of instructions. Five hash bits per level keep the tree four-deep for millions of keys.

The trade F#'s standard library took

F#'s standard library could have shipped a HAMT for Map; it shipped a balanced tree instead. Both are good immutable maps. The balanced tree keeps keys in sorted order, which makes ordered iteration and range queries free and the comparison the only requirement on a key. The HAMT keys by hash, which gives near-constant depth and needs only equality and a hash. Neither is wrong; they answer different defaults. The point of this module is to know which structure you are reasoning about.

The HAMT · this dive

Hash the key; nodes branch 32 ways via a bitmap + packed array; depth ~log₃₂ n; iteration in hash order.

F#'s Map · what shipped

A balanced search tree; keys in sorted order; depth O(log n) binary; ordered iteration and range queries for free.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

A job registry calls for a high-fan-out persistent map: many keys, cheap lookups, non-destructive writes. That is exactly what a HAMT is for — and what the F# EchoMQ's registry is. The honest framing holds here too: the F# port's registry, EchoMQ.Store.Rows, is a plain F# Map (a balanced tree) today; the production Elixir bus backs the equivalent registry with the echo_data HAMT/CHAMP family; the port keeps the same surface so a HAMT/CHAMP swaps in later with no caller change.

EchoMQ in F#

The registry is the persistent map a HAMT would back

The queue state holds its rows in a Map keyed by branded id. Quoted verbatim from echo_fs/EchoMQ/Store.fs:

/// One queue's state.
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      // id -> due-at (ms), id -> lease deadline (ms), ... }

An admission writes a row without disturbing the old state — the persistent-map property. Quoted verbatim from the enqueue transition in the same file:

// echo_fs/EchoMQ/Store.fs — enqueue admission (verbatim)
{ st with
    Rows = st.Rows.Add(id, row)
    Pending = st.Pending.Add id },
Admission.Enqueued

The F# EchoMQ keeps its job registry in EchoMQ.Store.Rows today — an immutable F# Map (a balanced tree, not a HAMT), in the in-memory core (echo_fs/EchoMQ/Store.fs — built and tested). The HAMT/CHAMP backing the Elixir bus uses, and the Valkey transport EchoMQ.Connector, land next; the enqueue/claim surface holds across the swap.

The HAMT is one way to build the persistent map a registry calls for; the balanced tree is another. The bus's registry is that map. The next dive reads the property both structures share: an update keeps the old version standing.

Where this leads

The node is a bitmap and a packed array; the descent reads 5-bit hash slices; popcount turns a slot into an array index. The next dive reads how an insert keeps the old map intact and shares structure — the property a HAMT and a balanced tree both provide, and the reason either is a persistent map.

↑ C4.05 · Hash Array Mapped Tries ← C4.05.1 · Prefix tries C4.05.3 · Structural sharing →

References

Sources

Microsoft — .NET documentation — System.Numerics.BitOperations.PopCount and the bitwise operators.
Microsoft — F# documentation — records, arrays, and the bitwise operators (&&&, <<<).
FSharp.Core API reference — the Map module (the immutable balanced-tree map) and Array.
The F# Software Foundation — F#'s home on the .NET runtime.

Related in this course

Elixir — Hash array mapped tries (E4.05) — the same structure on the BEAM, whose Map is a HAMT.
C4.05 — Hash Array Mapped Tries — the module hub.
C4.05.1 — Prefix tries — the trie shape this dive indexes by hash.
C1.07 — Collections — Map, arrays, and the cost model in F#.