hash function · avalanche · 折算

从 key 到下标：散列函数

数组按下标取值是常数时间，前提是下标得是一个小整数。哈希表补上「任意 key 变成小整数」这一步，于是按 key 取值也降到常数时间。这一步不可能是双射：key 的取值空间通常是无限的，槽位只有 $m$ 个，两个不同的 key 必然会算出同一个下标。哈希表后续的一切设计，都是在应对这件必然发生的事。

而在处理冲突之前，先要把冲突压到最少。这就是本页的题目：怎样的折算算「散得开」。

1 · 两步折算

从 key 到下标是两个独立的环节，各有各的责任。

定义 1.1（hash function） 一个把任意 key 映到固定位宽整数的函数 $h$ ，要求相等的 key 必得相同的值（确定性），而不相等的 key 尽量得到在整个值域上均匀分布、且互不相关的值。

折算规则则把 $h(k)$ 压进 $0$ 到 $m-1$ 。常用两种：除法散列 $h \bmod m$ ，与乘法散列 $\lfloor m \cdot \mathrm{frac}(h \cdot A) \rfloor$ ，后者在 $m$ 为 2 的幂时等价于「乘一个奇数常数后取高位」。

图 1-1 · 一个 key 走完两步折算的全过程。上方 32 位视图里绿框标出被折算规则实际读到的位，下方两条分布带是同一批内置 key 在两种折算下的落点。可改 key、换散列函数与表长，留意表长取 2 的幂时除法散列只读最低几位。

两个环节的失效方式不同，这一点值得先说清。散列函数的失效是「差异没被搅开」——两个只差一个字符的 key，算出的 $h$ 只差低几位。折算规则的失效是「只读了一部分位」—— $m$ 取 $2^b$ 时， $h \bmod m$ 恰好等于 $h$ 的最低 $b$ 位，高 $32-b$ 位一句话也传不到下标上。

单独看，两者都能勉强工作：散列函数够好时，取低位也够散；折算规则读全部 32 位（ $m$ 取质数）时，弱散列也能凑合。两者叠在一起才致命，而这恰恰是最常见的组合——现代实现几乎都取 $m = 2^b$ ，因为位与运算比整数除法快一个数量级。既然折算规则这一侧已经定死只读低位，全部担子就压在散列函数上。

2 · 位混淆的强度

「把差异搅开」有一个可度量的形式：翻转输入的任意一个位，输出应该有大约一半的位跟着改变。

定义 2.1（avalanche criterion） 对散列函数 $h$ ，若输入任一单个位翻转都使输出的每一位以接近 $1/2$ 的概率改变，则称 $h$ 满足雪崩条件。32 位输出下，单 bit 翻转的期望改变位数为 16。

图 2-1 · 三档混淆强度下的单 bit 雪崩。上三行是输入与输出的位视图，红框标出改变的位；下方柱状图是 32 个输入位各自翻转后输出改变的位数。可切换混淆步骤，对比只做一次乘法与完整 finalizer 的差别。

不做任何混淆时，平均改变位数恒为 1.00——翻一个位就只改那一个位，信息一点也没流动。只做一次乘法能把差异往高位搬，因为乘法的进位只朝高位传播，所以低位翻转带动的改变多、高位翻转几乎无人响应，柱状图右侧明显偏矮。murmur3 的 finalizer 在乘法前后各补一次「右移再异或」，把高位的差异也拉回低位，两个方向都通了。2000 个随机 seed、共 64000 次单 bit 翻转的实测均值是 16.01，最小 4、最大 27。

这解释了工程上一个反复出现的写法：许多语言的标准库拿到用户提供的 hashCode 后不直接用，而是再过一遍混淆。Java 的 HashMap 用 h ^ (h >>> 16)，只有一行，作用就是把高 16 位的差异折进低 16 位，因为它的表长是 2 的幂、只读低位。

3 · 已经是整数的 key

散列函数的输入常常本来就是整数：对象地址、自增 id、时间戳。这些整数的低位往往不随机，而是带着规律。

图 3-1 · 低位有规律的整数在两种折算下的落点。上方是头几个 key 的最低 12 位，绿框是除法散列读到的那几位。可换 key 来源与表长，也可勾选先过一遍 fmix32 看混淆如何救回除法散列。

16 字节对齐的地址最低 4 位恒为 0。表长取 16 时，除法散列把所有这类地址全部送进 0 号槽——64 个 key 一条链。乘法散列读的是乘积的高位，同一批 key 仍散在 10 个不同的槽里（引擎的 fibIndex 对 16 个 16 对齐的值给出 10 个不同下标，这条断言在 ht.test.ts 里锁着）。自增 id 的情形温和一些但同样有害：落点是等差的，空槽与挤槽相间，这种规律分布在开放寻址的 linear probing 下会直接长成一条长聚簇。

Fibonacci hashing 的常数 $A = 2654435769$ 是 $2^{32}/\varphi$ 的整数近似， $\varphi$ 为黄金比。选它的理由来自 Knuth 的分析： $\mathrm{frac}(i \cdot \varphi^{-1})$ 这个序列在 $[0, 1)$ 上的分布最均匀，任意前缀的落点都尽量互相远离。实践中它的价值更朴素——一次整数乘法加一次右移，比取模便宜，且不要求输入的低位是随机的。

4 · key 集的形状决定能否测出散列质量

前三节的叙述都在讲「坏散列会出问题」。真拿一批 key 去测，结论要打个折扣。

图 4-1 · 三种散列在同一 key 集上并排装表。每条柱状图是各槽的链长，下方表格给出空槽数、最长链与命中的平均比较次数。可切换 key 集，注意同一个 sumBytes 在三组 key 上的表现相差一个量级。

原先的猜想是：sumBytes 这种连字符次序都不看的散列，随便找一批真实 key 就能立刻打穿它。实测不成立。100 个英文常用词装进 64 槽，三种散列的空槽都是 14 个，最长链 4 到 5，命中的平均比较次数分别是 1.70（sumBytes）、1.79（djb2）、1.74（FNV-1a）——最差的那个反而最低。这批 key 的长度从 1 到 5 不等、字母分布本身够杂，字符码求和的结果取模 64 之后仍然够散。

换成「固定前缀 AB 加两位大写字母」的 676 个码，sumBytes 立刻崩掉：'A' 到 'Z' 是 65 到 90，两个字母之和只有 261 到 311 这 51 个取值，676 个 key 于是只能落在 51 个槽上，1024 槽里 973 个是空的，最长链 26，命中平均比较 9.17 次；FNV-1a 在同一批 key 上最长链 2、平均 1.06 次，差 8.6 倍。400 条只有尾部编号不同的路径也是同一回事，sumBytes 的平均比较是 13.45 次。

所以「散列函数够不够好」这句话没法只对函数说，它取决于 key 集的形状。这也是 SMHasher 这类测试套件要用几十种人工构造的输入分布（稀疏位、连续整数、同前缀、单字符变动）分别测的原因：真实业务的 key 恰恰常常是「固定前缀加短后缀」，正是这类最容易被弱散列打穿的形状。

5 · 把碰撞当武器

均匀分布这个假设有一个前提：key 不是敌人挑的。

2003 年 Crosby 与 Wallach 指出，只要散列函数是公开且无密钥的，攻击者可以离线算出成千上万个落在同一槽的 key，一次请求把它们全塞进服务端的哈希表。表退化成一条长链， $n$ 次插入的代价从 $O(n)$ 变成 $O(n^2)$ 。这类攻击叫 hash flooding，它不需要大流量：2011 年的 28C3 演讲展示了用几十 KB 的 POST 表单参数打满一台 Web 服务器的 CPU。

对策是让攻击者算不出碰撞：散列函数带一个进程启动时随机生成的密钥。SipHash 是为此设计的，短输入下够快，同时具备伪随机函数的安全性质。Python 自 3.3 起默认开启（PYTHONHASHSEED）、Rust 的 HashMap 默认用它、Redis 的 siphash.c 也是同一套。代价是每次求 hash 慢一些，换来的是最坏情形不再可被构造。

值得留意的是两个目标的分界：SipHash 解决的是「对手能否构造碰撞」，与 §2 讲的雪崩不是一回事。一个满足雪崩条件的散列函数完全可能毫无抗攻击性——FNV-1a 的雪崩不差，但它无密钥、可离线求逆，构造碰撞是几分钟的事。反过来，带密钥不等于分布好，两项要分别验。

6 · 参考文献

Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., §6.4). Addison-Wesley.
Crosby, S. A., & Wallach, D. S. (2003). Denial of service via algorithmic complexity attacks. Proceedings of the 12th USENIX Security Symposium, 29–44.
Aumasson, J.-P., & Bernstein, D. J. (2012). SipHash: a fast short-input PRF. Progress in Cryptology — INDOCRYPT 2012, 489–508.
Fowler, G., Noll, L. C., & Vo, K.-P. (1991). FNV hash. 规范与测试向量见 isthe.com/chongo/tech/comp/fnv.
Appleby, A. (2011). MurmurHash3 与 SMHasher 测试套件. github.com/aappleby/smhasher.