Hamt

HAMT — Hash Array Mapped Trie engine.

A 32-way persistent trie indexed by 5-bit chunks of a 32-bit hash. Provides O(log₃₂ n) ≈ O(1) amortized lookup, insert, and delete with excellent structural sharing under Perceus reference counting.

Node representation (bitmap compression): Each internal node stores a 32-bit bitmap recording which of the 32 slots are occupied, plus a dense list containing only the occupied children. Empty slots cost nothing.

To locate child for slot s:

Check bit s in bitmap. If clear → key absent.
dense index = popcount(bitmap & ((1 << s) - 1))
Child = list[dense_index]

Collision nodes hold all (key, value) pairs that share the same 32-bit hash. Collisions are rare with a good hash function (~50% chance at 77k entries for 32-bit hashes). They are scanned linearly using the equality function.

This module provides the raw engine. Map and Set build typed wrappers on top; PersistentVector uses its own index-trie (see array.march).

Hash / equality convention used by callers: hash_fn : k -> Int (must be deterministic; wrap with int_and(h, 1073741823) for safety) eq_fn : k -> k -> Bool

Types

typeHEntryHEntry(k, v) =#

Functions

fnemptyempty()#

Returns an empty HAMT node.

fngetget(node, key, hash_fn, eq_fn)#

Look up a key. Returns Some(value) if found, None otherwise. hash_fn : k -> Int eq_fn : k -> k -> Bool

fninsertinsert(node, key, val, hash_fn, eq_fn)#

Insert or update key→val. hash_fn : k -> Int eq_fn : k -> k -> Bool

fnremoveremove(node, key, hash_fn, eq_fn)#

Remove a key. Returns the trie unchanged if the key is absent. hash_fn : k -> Int eq_fn : k -> k -> Bool

fnfoldfold(acc, node, f)#

Left fold over all (key, value) pairs. f is curried: f(acc)(key)(val) = new_acc

fnsizesize(node)#

Count entries in O(n).