Hash Array Mapped Trie (HAMT)
Hash → 5-bit chunks → bitmap + popcount → dense child array → immutable insert (path copying)
get: O(log₃₂ n)
insert: O(log₃₂ n)
delete: O(log₃₂ n)
space: O(n)
1 · Hash of key, sliced into 5-bit chunks
2 · Bitmap + popcount at the current node
Slots 0..31 — purple = present. Target slot outlined; green underline = slots counted by popcount (below target).
3 · Trie (insert copies only the path; rest is shared)
Info
Press Insert with a key, then Step ▶ to walk the algorithm one stage at a time.
Big-O
| Operation | Time | Extra space / update | Note |
|---|
| get(key) | O(log₃₂ n) | O(1) | ~6 hops for 10⁹ keys |
| insert(key,val) | O(log₃₂ n) | O(log₃₂ n) | copies path, shares rest |
| delete(key) | O(log₃₂ n) | O(log₃₂ n) | collapses single-child nodes |
| popcount index | O(1) | O(1) | one hardware instruction |
| whole-map memory | — | O(n) | bitmap+popcount, no 32-wide waste |