Skip to content

Persistent Hash Array Mapped Trie Visualization

Insert Key-Value Pair (Creates New Version)

Lookup Key

Version Control

Operation Log

HAMT Structure (Version 0)

Trie is empty. Insert some key-value pairs.

About

This does not represent the HAMTs algorithm. It is a toy display to show the idea of how the tree/trie would be built, sharing partial paths, and versioning.

Persistent HAMTs use path copying to maintain multiple versions efficiently:

  1. When a key is inserted or updated, only nodes along the affected path are copied
  2. Green nodes are newly created in the current version
  3. Yellow nodes are shared from previous versions (structural sharing)
  4. Each version maintains references to its unique nodes and shared nodes
  5. This enables efficient memory usage while allowing access to any previous version

Key Demonstration:

  • Insert multiple key-value pairs to create new versions
  • Switch between versions to see how each version preserves its state
  • Notice how updating an existing key creates a new path while maintaining the original
  • Observe which nodes are shared between versions (highlighted in yellow)