separate chaining · 负载因子 · 树化

链地址法：把冲突挪到槽外

冲突不可避免，问题是把撞在一起的 key 放哪。separate chaining 的答案最直白：放在槽外面，本页此后称链地址法。槽里只存一个指针，指向一条链，同槽的 key 全挂在这条链上。

这个选择带来两个别处没有的性质。其一，负载因子可以超过 1——装了多少 key 与槽有多少个是两件事。其二，删除就是摘一个链节点，不留任何痕迹。这两条在开放寻址那边都不成立。

1 · 一次查找加一次链头插入

图 1-1 · 8 个槽的链地址表逐个装入 12 个 key。橙色 = 本次沿链比较过的节点，绿色 = 命中的节点。可手动查找与删除，也可把散列函数换成 sumBytes 看链如何堆到一处。

值得留意插入的实际代价。哈希表的语义是 key 唯一，所以插入前必须确认这个 key 还不在表里——也就是先做一次完整的失败查找，走完整条链，然后才把新节点接到链头。「插入是 $O(1)$ 」这句话只描述了最后那一步；整个 insert 的代价与一次未命中查找同阶，也就是与链长同阶。图 1-1 的 verdict 里那个「比较了链上 $n$ 个节点」就是这一段。

链头插入而非链尾，是因为链尾要先走到底。Redis 的 dict.c 也是链头插入，注释里给的理由是「刚插入的元素更可能被再次访问」——这条局部性假设在缓存场景成立，在别处未必。

2 · 链长的分布

把 $n$ 个 key 随机丢进 $m$ 个槽，各槽的链长服从二项分布， $m$ 大时可用参数为 $\alpha = n/m$ 的泊松分布近似：某个槽恰好装 $j$ 个 key 的概率约为 $e^{-\alpha} \alpha^j / j!$ 。

图 2-1 · 512 个槽在不同负载因子下的链长直方图，每档左柱是实测槽数、右柱是泊松近似。下方表格并列实测值与理论式。可拖动 α 从 0.25 到 8。

三条闭式解都能在实测里对上：

空槽比例 $\to e^{-\alpha}$ ｜未命中查找的平均比较次数 $= \alpha$ ｜命中查找的平均比较次数 $= 1 + \alpha/2$

$m = 1024$ 的实测： $\alpha = 0.25$ 时空槽 77.7%（理论 77.9%）， $\alpha = 1$ 时 35.9%（理论 36.8%）， $\alpha = 4$ 时 1.5%（理论 1.8%）；命中平均比较在 $\alpha = 1$ 时是 1.48，理论值 1.50。中间那个数字值得停一下：即便 key 数与槽数相等，仍有超过三分之一的槽是空的。这不是散列函数不好，而是随机投掷的固有不均——把 $n$ 个球随机丢进 $n$ 个桶，空桶比例趋于 $1/e \approx 0.368$ 。哈希表的空间从来不可能被填满。

最长链是另一回事，它不由 $\alpha$ 单独决定，还随 $n$ 缓慢增长。经典结论是 $\alpha = 1$ 时最长链为 $\Theta(\log n / \log \log n)$ 。实测的绝对值比这个式子大： $n = m$ 从 64 涨到 65536，最长链依次是 3、5、6、6、6、7，而 $\ln n / \ln \ln n$ 从 2.92 涨到 4.61。渐近式抓住了增长速度（六万五千个 key 的最长链也只有 7），但它的常数因子在实际规模下并不能忽略，把它当估算公式用会低估四成左右。

3 · 两种查找的代价差一倍

命中与未命中的代价不对称，这一点常被忽略。未命中必须比较完整条链才能断言「不在」，期望恰好是 $\alpha$ ；命中平均在链的中间停下，期望是 $1 + \alpha/2$ 。 $\alpha = 4$ 时前者是 4 次、后者 3 次，看着差不多； $\alpha = 8$ 时是 8 次对 5 次。

这个不对称决定了什么样的负载适合链地址法。以查询为主、且大部分查询能命中的场景（缓存读、字典查词）对高负载相对宽容；而以「判断存不存在」为主的场景（去重、黑名单）每次都走满一条链， $\alpha$ 必须压得更低，或者干脆换成 Bloom filter 那种为不存在优化的结构。

链地址法真正的代价不在比较次数上，而在访存模式上。链上每一跳都是一次指针追逐，节点由分配器给出、在内存里彼此无关，于是每一跳都可能是一次 cache miss。一次 cache miss 的代价约为几十到上百个时钟周期，而一次 key 比较通常只有几个周期。所以「平均比较 1.5 次」这个数字里，真正花钱的是那 1.5 次里的指针跳转次数，不是比较本身。开放寻址与 Swiss table 的全部动机都指向这一项开销。

4 · 扩容治不了的那种链

链变长有两种成因，补救方式完全不同。

第一种是负载因子高了——key 多、槽少。扩容能解决：槽数翻倍，链长期望减半。

第二种是这些 key 的 hash 值本来就相同。此时它们在任何容量的表里都同槽，扩容一次不落地全都跟着搬过去，链长丝毫不减。

图 4-1 · 26 个 hash 值完全相同的 key 挤在一条链上。下方对照单链、有序链与红黑树三种 bucket 结构的比较次数。可拖动 key 数越过 Java 的树化阈值 8，注意此时负载因子仍然很低。

Java 8 给 HashMap 加的树化正是针对第二种。规则有两条而不是一条：链长达到 TREEIFY_THRESHOLD（8）且表容量不小于 MIN_TREEIFY_CAPACITY（64）时，把这条链换成红黑树；容量不足 64 时先扩容，因为那多半是第一种成因。降级阈值取 6 而非 8，是为了避免链长在阈值上反复横跳导致来回转换。

阈值取 8 的理由写在 HashMap 的源码注释里：散列均匀时链长服从泊松分布， $\alpha = 0.75$ 下某条链达到 8 的概率约为 $6 \times 10^{-8}$ ，也就是说正常情况下树化根本不会触发，它只在散列质量崩坏或遭到构造攻击时才起作用。这也解释了为什么阈值不设在 2 或 3——树节点的内存开销约为链节点的两倍，为一件几乎不发生的事付常驻成本不划算。

值得对照的是，Redis 的 dict 至今没有树化。它的应对是另一条路：字符串散列用带密钥的 SipHash（见散列函数 §5），从源头上让攻击者构造不出碰撞，于是长链根本不会出现。两种设计的分歧点是「假定散列函数可信吗」——Java 必须容忍用户自己写的 hashCode，Redis 的 hash 是自己算的。

5 · 参考文献

Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3 (2nd ed., §6.4). Addison-Wesley.
Gonnet, G. H. (1981). Expected length of the longest probe sequence in hash code searching. Journal of the ACM, 28(2), 289–304.
Raab, M., & Steger, A. (1998). Balls into bins: a simple and tight analysis. Randomization and Approximation Techniques in Computer Science, 159–170.
OpenJDK. java.util.HashMap 源码注释（TREEIFY_THRESHOLD 一节）。