Home▸Algorithms & AI▸HAMT: Hash Array Mapped Trie

🌳 HAMT: Hash Array Mapped Trie

Explore how Hash Array Mapped Tries let languages like Clojure and Scala implement immutable maps and sets that update in near-constant time without copying the whole structure.

Algorithms & AI3DModerate60 FPS

The simulator visually builds a HAMT step by step as keys are inserted, showing each key's hash code being sliced into five-bit chunks, the resulting bitmap at each node lighting up the bit corresponding to the chunk value, and the compact child array growing only by the exact number of real children, with the popcount calculation highlighted live to show exactly how a bitmap position translates into an array index.

🔬 What It Demonstrates

🎮 How to Use

Add keys one at a time to watch the trie grow and observe which existing nodes are reused versus which new nodes get created along the insertion path; toggle a highlight mode to trace one key's hash chunk by chunk from the root down to its leaf; and trigger an update on an existing key to see structural sharing in action, with untouched branches dimmed to show they were not copied while the new path lights up in a different color.

💡 Did You Know?

Did you know that Clojure's persistent hash map, one of the most widely used real-world HAMT implementations, can be updated thousands of times per second even when it holds millions of entries, because each update allocates only a handful of new nodes along one short path instead of copying the whole map, thanks to the same bitmap and popcount trick you are exploring here.

⚙ Under the hood

Explore how Hash Array Mapped Tries let languages like Clojure and Scala implement immutable maps and sets that update in near-constant time without copying the whole structure.

data-structuresimmutabilityfunctional-programmingtriebitmappersistent-structures

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install