Hash array mapped trie

A hash array mapped trie (HAMT) is a trie over the bits of the keys' hash values. Each level of the tree consumes a few bits of the hash, usually five, to choose one of 32 children, and each node stores only the children that exist, in a compact array, together with a 32-bit bitmap recording which of the 32 slots they occupy. A child's position in the array is the number of set bits in the bitmap before its slot, one population-count instruction. Lookups follow about $lo g_{32} n$ levels, which is at most seven for any hash map that fits in memory. Updated by copying only the path from the root to the changed leaf, a HAMT is a persistent hash map. Bagwell introduced it in 2001^[1], and it is the standard implementation of immutable maps and sets in Clojure^[3], Scala^[4] and Haskell's unordered-containers^[9].

§ 01

Structure

A key is hashed to a fixed-width integer, and the hash is split into chunks of $b$ bits, usually $b = 5$ . The chunk at level $d$ selects one of $2^{b}$ slots in the node at that level:

slot_{d} (h) = ⌊ h / 2^{b d} ⌋ mod 2^{b}

A node with a full array of 32 children would waste most of its space in a sparse tree, since most nodes near the leaves have only a few children. A HAMT node instead stores a bitmap $B$ with bit $s$ set when slot $s$ is occupied, and an array holding only the occupied children, in slot order. The child for slot $s$ is at position

index (B, s) = popcount (B \land (2^{s} - 1))

the number of occupied slots before it. Population count is a single instruction on current processors^[7]. A key is stored in a leaf as soon as its prefix of chunks is unique, so the tree is only as deep as needed to separate the keys. Keys whose entire hashes are equal share a collision node at the bottom, searched linearly.

§ 02

Operations

Lookup hashes the key and walks down, at each node testing the bitmap bit for the current chunk and, if it is set, moving to the child at the computed index; at a leaf it compares the key. Insertion follows the same path. If the slot is empty, it copies the node into an array one longer with the new leaf inserted. If the slot holds a leaf with a different key, it replaces the leaf with a new node one level down that contains both, continuing down while their chunks coincide. Every node on the path is copied, and everything else is shared with the previous version, so the old map remains valid^[6]^[8].

A persistent HAMT in OCaml with 5-bit chunks, bitmap-indexed nodes and collision lists.

(* A persistent hash array mapped trie. The hash of a key is read 5 bits
   at a time; each 5-bit chunk chooses one of 32 slots. A node stores only
   its occupied slots, in a dense array, with a 32-bit bitmap saying which
   slots they are. *)
type ('k, 'v) t =
  | Empty
  | Leaf of int * 'k * 'v                (* hash, key, value *)
  | Collision of int * ('k * 'v) list     (* keys whose whole hash is equal *)
  | Node of int * ('k, 'v) t array       (* bitmap, occupied children *)
 
let bits = 5
let chunk h shift = (h lsr shift) land 31
 
let popcount x =
  let x = x - ((x lsr 1) land 0x55555555) in
  let x = (x land 0x33333333) + ((x lsr 2) land 0x33333333) in
  let x = (x + (x lsr 4)) land 0x0f0f0f0f in
  ((x * 0x01010101) lsr 24) land 0xff
 
(* The position of a slot in the dense array: the number of occupied slots
   before it. *)
let index bitmap bit = popcount (bitmap land (bit - 1))
 
let rec find_h h k shift = function
  | Empty -> None
  | Leaf (h', k', v) -> if h = h' && k = k' then Some v else None
  | Collision (h', kvs) -> if h = h' then List.assoc_opt k kvs else None
  | Node (bitmap, children) ->
      let bit = 1 lsl chunk h shift in
      if bitmap land bit = 0 then None else find_h h k (shift + bits) children.(index bitmap bit)
 
let find k t = find_h (Hashtbl.hash k) k 0 t
 
(* Two entries that fall in the same slot go into a new node one level
   down; once all 30 bits of the hash are used up, into a collision list. *)
let rec merge shift ((h1, k1, v1) as e1) ((h2, k2, v2) as e2) =
  if shift >= 30 then Collision (h1, [ (k1, v1); (k2, v2) ])
  else
    let c1 = chunk h1 shift and c2 = chunk h2 shift in
    if c1 = c2 then Node (1 lsl c1, [| merge (shift + bits) e1 e2 |])
    else
      let l1 = Leaf (h1, k1, v1) and l2 = Leaf (h2, k2, v2) in
      Node ((1 lsl c1) lor (1 lsl c2), if c1 < c2 then [| l1; l2 |] else [| l2; l1 |])
 
let rec add_h h k v shift t =
  match t with
  | Empty -> Leaf (h, k, v)
  | Leaf (h', k', _) when h = h' && k = k' -> Leaf (h, k, v)
  | Leaf (h', k', v') -> merge shift (h', k', v') (h, k, v)
  | Collision (h', kvs) -> Collision (h', (k, v) :: List.remove_assoc k kvs)
  | Node (bitmap, children) ->
      let bit = 1 lsl chunk h shift in
      let i = index bitmap bit in
      if bitmap land bit <> 0 then begin
        (* Path copying: a new array with one child replaced. *)
        let a = Array.copy children in
        a.(i) <- add_h h k v (shift + bits) children.(i);
        Node (bitmap, a)
      end else begin
        let n = Array.length children in
        let a = Array.make (n + 1) (Leaf (h, k, v)) in
        Array.blit children 0 a 0 i;
        Array.blit children i a (i + 1) (n - i);
        Node (bitmap lor bit, a)
      end
 
let add k v t = add_h (Hashtbl.hash k) k v 0 t
 
let rec stats depth (nodes, slots, leaves, sum_depth, max_depth) = function
  | Empty -> (nodes, slots, leaves, sum_depth, max_depth)
  | Leaf _ -> (nodes, slots, leaves + 1, sum_depth + depth, max max_depth depth)
  | Collision (_, kvs) -> (nodes, slots, leaves + List.length kvs, sum_depth + depth * List.length kvs, max max_depth depth)
  | Node (_, a) -> Array.fold_left (fun acc c -> stats (depth + 1) acc c) (nodes + 1, slots + Array.length a, leaves, sum_depth, max_depth) a

Running it.

1000000 keys inserted, all found: true, absent key: None
307474 internal nodes, 4.3 children per node on average
depth of a key: average 4.64, maximum 6   (log32 n = 3.99)
after an update: new -1, old 42
bitmap with slots 3, 9, 20 occupied: index of slot 9 = 1, of slot 20 = 2

With a million keys, lookups visit on average 4.64 nodes and at most 6. The average is above $lo g_{32} n \approx 4$ because a key needs one more level whenever another key shares its chunks so far, and at the fourth level there are about as many slots as keys. Internal nodes near the root are full and those near the leaves hold two or three children, 4.3 on average; with full 32-entry arrays the same tree would use more than seven times as much space for child pointers.

Cost

For a hash of $w$ bits the depth is at most $w / b$ , so lookup, insertion and deletion take $O (w / b)$ steps, constant for a fixed hash width, and $O (lo g_{32} n)$ on average when the hash is uniform. Each update allocates the copied path, at most $w / b$ small arrays. Compared with a balanced binary tree the depth is about five times smaller, and nodes are arrays, so a lookup touches fewer cache lines; compared with a hash table, a HAMT never needs to be resized all at once, and it is persistent.

§ 03

Persistence and concurrency

Because updates never modify existing nodes, a HAMT can be shared between threads without locks, and a snapshot of a map is just a pointer to its root. Clojure made persistent HAMTs its default map and set in 2007, and used them together with atomic references to the root to build its concurrency model^[3]. Prokopec, Bronson, Bagwell and Odersky's Ctrie is a mutable, lock-free concurrent HAMT that updates nodes with compare-and-swap and supports constant-time snapshots^[5].

Implementations add a transient mode for bulk construction, in which nodes created by the current operation may be modified in place until the result is published, avoiding repeated path copying when building a map from many keys.

§ 04

Variants

Steindorfer and Vinju's CHAMP (compressed hash-array mapped prefix tree) keeps two bitmaps per node, one for leaves stored inline and one for child nodes, and stores the two kinds at opposite ends of the array. This makes nodes smaller, iteration faster and structural equality cheaper, and guarantees a canonical shape after deletions, since a node reduced to a single leaf is always merged into its parent^[4]. Scala's immutable HashMap has used CHAMP since version 2.13.

Bagwell's earlier work applied the bitmap-and-popcount idea to tries over the characters of string keys, as a space-efficient alternative to ternary search trees^[2].

§ 05

History

Bagwell described array mapped tries for string keys in 2000^[2] and hash array mapped tries in "Ideal hash trees" in 2001^[1]. Hickey adopted them as the persistent maps of Clojure, released in 2007^[3], from where they spread to Scala, to Haskell's unordered-containers^[9] and to immutable-collection libraries for JavaScript and other languages. Prokopec and his coauthors published the concurrent Ctrie in 2012^[5], and Steindorfer and Vinju CHAMP in 2015^[4].