hash array mapped trie · bitmap · popcount

HAMT：bitmap 加 popcount 的 32 叉 trie

哈希表的持久化版本不能照抄哈希表：一个连续数组的表，改一个槽就得复制整个表。要让「改一个 key」的代价降到对数级，得先把表换成树。

Bagwell 在 2001 年给出的答案是 hash array mapped trie [1]：拿 hash 值当路径，把 key 挂到 trie 上。它现在是 Clojure 的 PersistentHashMap、Scala 的 immutable.HashMap、Immutable.js 的 Map 的共同底层，也是本系列里最值得讲透的一个结构。

1 · 拿 hash 当路径

trie 的每一层要一个「往哪个孩子走」的整数。HAMT 从 hash 值里现取：第 $d$ 层看 hash 的第 $5d$ 到 $5d+4$ 位，得到一个 $0$ 到 $31$ 的 fragment。

定义 1.1（HAMT） 一棵分支因子 32 的 trie。key 的路径由 $h(key)$ 决定：深度 $d$ 处的分支取 $(h \gg 5d) \bmod 32$ 。32 位 hash 最多切出 7 段（前 6 段各 5 位，第 7 段 2 位），故 trie 层数不超过 7；同 hash 的 key 在第 7 层之下用一个线性表兜底。

树深有上界这一点值得单独说。二叉搜索树的深度随 $n$ 增长， $n = 10^5$ 时是 17 层；HAMT 的深度封顶在 7，而且实测远达不到。10 万个 key 的实测分布是：4782 个 key 在第 4 层、86033 个在第 5 层、8849 个在第 6 层、322 个在第 7 层、14 个在第 8 层（第 8 层是叶子，其上有 7 层 bitmap 节点）。绝大多数查找走 5 步就到。

trie 只铺到「不再分叉」为止：一个 key 若在某层的这个槽里独占，就直接把它挂在那一层，不再往下建空节点。这条规则让 10 个 key 的 HAMT 只有 2 个内部节点。

2 · bitmap 与紧凑数组

朴素实现给每个节点开一个 32 长的数组，多数槽是空的。10 万 key 的实测里每个内部节点平均只有 4.10 个孩子，铺满 32 槽要 1032096 个指针，实际只需要 132252 个，浪费 87.2%。

Bagwell 的压缩办法是两个字段：一个 32 位整数记「哪些槽非空」，一个只装实际孩子的数组。第 $f$ 个槽有没有孩子看 bitmap 的第 $f$ 位；它在紧凑数组里排第几，看 bitmap 低 $f$ 位里有几个 1。

\text{slot} = \operatorname{popcount}(\text{bitmap} \mathbin{\&} (2^f - 1))

图 2-1 · 一个 bitmap 节点的槽位查询，从 fragment 到紧凑数组下标的三步换算。可拖动 fragment 观察下标随低位 1 的个数变化，也可单击任意一位翻转 bitmap。

popcount 在现代 CPU 上是一条指令（x86 的 POPCNT、ARM 的 CNT 加横向加法），所以这个换算的代价与「直接取下标」相差无几。JS 没有这条指令，引擎里用的是经典的 SWAR 写法：先两位一组求和，再四位、八位，最后一次乘法把四个字节的部分和横向加起来取高 8 位。测试对全部 $2^{16}$ 个 16 位值与 2000 个随机 32 位值逐一核对过。

分支因子取 32 而非更大，一半的理由就在这个字段上：一个 32 位整数刚好索引 32 个槽。 $b = 64$ 要 64 位掩码，而 JS 的位运算只有 32 位。

3 · assoc 的路径复制

有了节点表示，写操作就是上一页那套 path copying。assoc(key, value) 沿 fragment 逐层下降，回溯时逐层新建：命中已有槽就复制孩子数组、替换一个元素；撞上空槽就复制数组、在 slot 位置插进新 entry 并把 bitmap 的对应位置 1。

图 3-1 · 逐个插入或删除 key，蓝色是本次操作新建的节点，灰色是与上一版本共用的。可插入已存在的 key 观察新建量不随 key 总数增长。

新建量随规模的实测：10 个 key 时平均每次 assoc 新建 2.20 个节点，100 个时 3.05，1000 个时 3.65，1 万个时 4.26，10 万个时 5.04，最多 7 个。它增长得比 $\log_{32} n$ 还慢，因为浅层的节点在 key 稀疏时根本不存在。10 万 key 的树共 132253 个节点，一次 assoc 的共享率是 99.9962%；同一次修改若换成复制整个 Map，要写 10 万个 entry，是路径复制的 19826 倍。

4 · hash 碰撞

32 位 hash 不是单射，两个 key 的 hash 完全相同时 trie 分不开它们。此时在第 7 层之下挂一个 collision node：一个线性表，查找靠逐个比 key。

图 4-1 · 三档 hash 质量下的 trie 形状，橙色是 collision 节点。可切换到常数 hash 观察全部 key 落进同一个线性表，此时查找退化但结果仍然正确。

写这一段时踩到一个反直觉的地方。assoc 里有一条分支处理「下降途中遇到 collision 节点，但待插入 key 的 hash 与它不同」。按 trie 的构造这不可能发生：能走到某个 collision 节点，说明前 7 层的 fragment 全部对上，也就是 32 位 hash 完全相同。这条分支看起来是死代码。

实际上它是活的，触发路径要绕一圈：dissoc 删掉节点后若某个 bitmap 节点只剩一个非 bitmap 孩子，会把这个孩子提上一层（不然树里会留下一串单孩子的空转层）。被提上来的可以是 collision 节点，它此后就坐在一个浅得多的位置上，而那个位置只对应 hash 的前几位。此时任何一个前几位相同、后几位不同的 key 插进来，就正好走到这条分支。测试里用一组手工指定 hash 的 key 复现了这条路径：ka 与 kb 同 hash 被压到第 7 层，kd 只在最高两位不同、给 collision 的父节点添了个兄弟；删掉 kd 之后 collision 被逐层提到深度 2，再插入 hash 低 5 位与 ka 相同的 kf 即触发。

碰撞到底有多罕见，实测给了个偏离直觉的数字。100 万个 user:0 到 user:999999 形式的 key，32 位 hash 只撞了 8 对，而生日问题的期望是 116 对。原因有两层：fmix32（murmur3 的 finalizer）由异或右移与奇数乘法组成，两者在 32 位上都可逆，所以它是一个双射，一个碰撞也不会新增或消除；碰撞数完全由前面的 FNV-1a 决定，而 FNV-1a 在这一族「固定前缀加递增十进制数」的短 key 上几乎是单射。换成互不相关的十进制串重测，碰撞数是 115，与期望严丝合缝。

警示 · 上一段的意思不是「FNV-1a 比随机函数更好」。散列质量对 key 集的形状高度敏感，同一个函数在另一族 key 上可能远差于期望。这类结论只能针对具体 key 集下，不能上升成对函数的评价（同一现象的反面见从 key 到下标：散列函数 §4）。

5 · 与开地址哈希表的取舍

同样存 10 万个 key，一张开地址哈希表在负载因子 0.7 下是一段 14 万槽的连续内存，查找一次访存、cache 友好；HAMT 是 13 万个小对象，查找要 5 次指针追逐，每一跳都可能是 cache miss。单看读性能，HAMT 输得毫无悬念，Bagwell 自己在论文里给的数字也是 1.3 到 2 倍慢。

换来的是三件哈希表给不了的事。其一是持久性本身：改一个 key 得到新 Map，旧 Map 原样可用，代价 5 个节点而非 10 万个 entry。其二是「两个 Map 有没有变」可以用一次指针比较回答，这是前端 memo 的地基（见结构共享的代价）。其三是天然的线程安全，不可变对象不需要锁。

判据因此不是「哪个快」，而是「有没有人要看旧版本」。只有一个可变状态、读多写少的场景选哈希表；状态要留档、要跨线程共享、或者要做引用相等剪枝的场景选 HAMT。

6 · 参考文献

Bagwell, P. (2001). Ideal hash trees. Technical Report LAMP-REPORT-2001-001, École Polytechnique Fédérale de Lausanne.
Bagwell, P. (2000). Fast and space efficient trie searches. Technical Report, EPFL.
Steindorfer, M. J., & Vinju, J. J. (2015). Optimizing hash-array mapped tries for fast and lean immutable JVM collections. OOPSLA 2015, 783–800.
Appleby, A. (2011). MurmurHash3 的 finalizer 与 SMHasher 测试套件. github.com/aappleby/smhasher
Clojure 的 PersistentHashMap 与 Immutable.js 的 Map 实现。