March Docs

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:
  1. Check bit s in bitmap.   If clear → key absent.
  2. dense index = popcount(bitmap & ((1 << s) - 1))
  3. 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, called with two arguments as eq_fn(a, b) The same hash_fn and eq_fn must be passed to every call on one trie. Only the low 35 bits of the hash pick a path (7 levels of 5 bits). Keep hashes non-negative and below 2^35 (the 30-bit mask above does this): two keys whose hashes agree on the low 35 bits but differ above them land in one collision bucket tagged with the first hash, and get then misses the second key.

Types

typeHEntryHEntry(k, v) =#

Functions

fnemptyempty()#

Returns an empty HAMT node (HEmpty).

Examples

march> Hamt.size(Hamt.empty())
0
fnfoldfold(node : HEntry(k, v), acc : b, f : b -> k -> v -> b) : b#

Left fold over all (key, value) pairs. Argument order: collection first, init second, callback last (uncurried-collection convention). Note: the callback f is still curried as f(acc)(key)(val) because HAMT internals expect that shape. Entries are visited in trie order (by hash bits), not insertion order.

Examples

march> let h3 = Hamt.insert(Hamt.insert(Hamt.empty(), 1, 10, fn k -> k, fn (a, b) -> a == b), 2, 20, fn k -> k, fn (a, b) -> a == b)
march> Hamt.fold(h3, 0, fn acc -> fn k -> fn v -> acc + k + v)
33
fngetget(node, key, hash_fn, eq_fn)#

Look up a key. Returns Some(value) if found, None otherwise. hash_fn : k -> Int eq_fn : two-argument equality, called as eq_fn(a, b)

Examples

march> let h = Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 2, "b", fn k -> k, fn (a, b) -> a == b)
march> Hamt.get(h, 2, fn k -> k, fn (a, b) -> a == b)
Some("b")
march> let h = Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 2, "b", fn k -> k, fn (a, b) -> a == b)
march> Hamt.get(h, 3, fn k -> k, fn (a, b) -> a == b)
None
fninsertinsert(node, key, val, hash_fn, eq_fn)#

Insert or update key→val. Returns the new trie; an existing key has its value replaced. Keys whose hashes are equal but which are not eq_fn-equal are kept side by side in a collision bucket. hash_fn : k -> Int eq_fn : two-argument equality, called as eq_fn(a, b)

Examples

march> let h1 = Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 1, "z", fn k -> k, fn (a, b) -> a == b)
march> Hamt.get(h1, 1, fn k -> k, fn (a, b) -> a == b)
Some("z")
march> let hc = Hamt.insert(Hamt.insert(Hamt.empty(), "x", 1, fn _ -> 0, fn (a, b) -> a == b), "y", 2, fn _ -> 0, fn (a, b) -> a == b)
march> Hamt.get(hc, "y", fn _ -> 0, fn (a, b) -> a == b)
Some(2)
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 : two-argument equality, called as eq_fn(a, b)

Examples

march> let h2 = Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 2, "b", fn k -> k, fn (a, b) -> a == b)
march> Hamt.get(Hamt.remove(h2, 1, fn k -> k, fn (a, b) -> a == b), 1, fn k -> k, fn (a, b) -> a == b)
None
march> let h2 = Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 2, "b", fn k -> k, fn (a, b) -> a == b)
march> Hamt.size(Hamt.remove(h2, 9, fn k -> k, fn (a, b) -> a == b))
2
fnsizesize(node)#

Count entries in O(n) (the count is not cached).

Examples

march> Hamt.size(Hamt.insert(Hamt.insert(Hamt.empty(), 1, "a", fn k -> k, fn (a, b) -> a == b), 2, "b", fn k -> k, fn (a, b) -> a == b))
2