HAMT(哈希数组映射字典树)

定义

HAMT(Hash Array Mapped Trie,哈希数组映射字典树)由 Phil Bagwell 于 2001 年提出,把键的哈希值按每 5 位(或 6 位)切段,逐段作为下标在 32 叉(或 64 叉)树中下行,叶子存放键值对。

原理

关键优化是位图压缩:每个内部节点用一个 32 位位图标记哪些分支存在,子节点指针紧凑地存放在数组中,通过 popcount 指令由位图算出目标分支在数组中的偏移,既保持 32 叉的浅树高(百万级元素仅约 4 层),又不为缺失分支浪费空间。哈希冲突时用链表或扩展哈希段解决。

应用

HAMT 与路径复制结合即得到高效的持久化哈希映射:Clojure 的 PersistentHashMap 是最著名的实现(Rich Hickey 基于 Bagwell 论文改造),Scala 的 immutable.HashMap、Haskell 的 unordered-containers、Erlang 大容量 map 的底层、Frege 与 Immutable.js 等均采用 HAMT;Clojure 的持久化向量也用类似的宽分支树。

优缺点

优点是近乎 O(1) 的查找(树高与 log32 n 成正比)、结构共享的廉价不可变更新;缺点是缓存局部性与纯数组哈希表有差距,迭代顺序不直观。