Hash array mapped tries

Phil Bagwell’s hash array mapped trie (2001) treats a key’s hash as a path: the first 5 bits pick one of 32 children at the root, the next 5 bits one of 32 at the next level, and so on until the key is the only one on its branch. Each node stores a 32-bit bitmap of which children exist plus a packed array of just those children, found by counting the set bits below the target (a single CPU popcount). Empty slots cost one bit each, and there is no root table to size or resize. Bagwell’s paper presents it as a fast, space-efficient hash table; making it persistent came later.

Rich Hickey turned it into the persistent hash map at the heart of Clojure (released 2007): a 32-way HAMT where an update copies the nodes on one path, so lookups take about log₃₂ n hops. Hickey called it the breakthrough that made Clojure practical, and Hickey’s paper credits Clojure’s example for persistent HAMTs in Scala 2.8 (2010), Haskell’s unordered-containers (2011) and Erlang’s large maps (2015). Scala 2.13 uses a refined variant, the compressed hash-array mapped prefix-tree (CHAMP), which improves locality and keeps one canonical shape per set of keys.

Use a HAMT for unordered maps and sets with lots of updates and shared versions. Implementations specialise small maps: Scala stores maps of up to four entries as single objects, and Immutable.js keeps maps of up to eight entries as a flat array before switching to trie nodes. If you need sorted keys, use a balanced search tree instead.