哈希

有两件事，哈希函数都能做，而且性质完全不同：

第一件：把任意数据映射到一个小的固定范围（如 0 到 999），用来快速查找——你在 Python 字典里每次用 d[key]，背后就是这个。

第二件：把任意数据映射到一个 256 位的"指纹"，改动数据的任何一个字节，指纹就会面目全非——Bitcoin 区块链和 Git 的版本控制系统依赖这个。

两者都叫"哈希"，但目标和性质截然不同。理解这两种哈希，是理解现代软件系统的钥匙。

哈希的本质：确定性映射#

哈希函数是一个函数 $h$：

$$h: \text{任意长度的输入} \to \text{固定大小的输出}$$

确定性指同样的输入永远产生同样的输出；单向性（只有密码哈希要求）指给定 $h(x)$ 无法有效还原 $x$。这两个性质看起来简单，工程实现和数学设计却大有学问。

第一种：哈希表的哈希函数#

哈希表（见data-structures）使用哈希函数把键映射到数组下标：

index = hash(key) % table_size
```

对于这种用途，好的哈希函数需要：

1. 均匀分布：不同键尽量映射到不同下标，避免集中碰撞
2. 速度快：每次字典操作都要调用，必须极快（通常比较、乘法等几条指令）
3. 雪崩效应：输入的微小变化让输出大幅变化（减少系统性碰撞）

碰撞（Collision）：两个不同的键哈希到同一个下标。碰撞不可避免（鸽巢原理：无限输入映射到有限输出），但要尽量减少并妥善处理。

碰撞处理两大策略：

链地址法（Separate Chaining）：每个桶存一个链表，碰撞的元素加入链表。

开放地址法（Open Addressing）：碰撞时找下一个空桶（线性探测、二次探测、双重哈希）。CPython 的 dict 用的是开放地址法，但探测序列不是简单的线性递增，而是 j = (5*j + 1 + perturb) % size，其中 perturb 初值取自完整哈希值、每轮右移 5 位——前几次探测由高位比特搅动，走的是伪随机跳跃；perturb 耗尽后才退化成确定的循环遍历。这个设计同时要两样东西：早期探测像双重哈希那样打散聚簇，后期又保证一定能扫完全表。

负载因子（Load Factor）：哈希表已存元素数 / 桶总数。负载因子过高时碰撞增多，性能退化，触发就扩容（Resizing）：分配更大的数组，重新哈希所有元素。这个阈值在真实实现里是硬编码的常数：Java HashMap 的 DEFAULT_LOAD_FACTOR 是 0.75，CPython 的 USABLE_FRACTION 是 $2/3$。下文有一节专门算这个数字凭什么是 0.75 而不是 0.9。

桶太长时换数据结构：Java 8 起，HashMap 的单个桶链表长到 TREEIFY_THRESHOLD = 8 且表容量已达 MIN_TREEIFY_CAPACITY = 64 时，把链表转成红黑树；缩回 UNTREEIFY_THRESHOLD = 6 时再转回链表。两个阈值故意不相等（8 转树、6 转回），是为了避免桶长在临界值附近抖动时来回转换。JDK 源码里给出的理由是泊松分布计算：哈希函数表现正常、负载因子 0.75 时，一个桶里出现 8 个及以上元素的概率约 $6\times10^{-8}$。换句话说，转红黑树这条路径设计出来不是为了正常情况，是为了哈希函数失效的情况——它是一道防线，而不是优化。

均摊分析下，哈希表查找、插入、删除都是 $O(1)$——这是它被广泛使用的原因。但"均摊 $O(1)$"这四个字里藏着两个前提：哈希函数把键打得足够散，以及负载因子被控制住。下面两节分别拆开这两个前提，看它们失效时会发生什么。

走一遍：8 槽表上的线性探测#

用一张 8 槽的表、$h(k) = k \bmod 8$、线性探测（碰撞就往右找下一个空位，到末尾回绕），依次插入 12、20、5、28、13。

五个键，13 次探测，平均 2.6 次，而负载因子只有 $5/8 = 0.625$——离"满"还远得很。这张表最该注意的是第 3 步：键 5 只和一个键（20）真正撞了哈希值，却被挤到了 6 号槽。 这就是线性探测的主聚簇（primary clustering）——槽 4 开始的那一串连续占用格子会互相吞并，任何落进这个区间的新键都要走完整段。到第 5 步，槽 4、5、6、7、0 已经连成一条长度 5 的簇；此后凡是哈希到 4–7 或 0 的键，都得付这段路的代价。簇越长，越容易被命中；被命中就更长。 这是一个正反馈。

现在删除键 20（在槽 5）。如果直接把槽 5 清空：

清空后：  13 · · · 12 [空] 5 28
查询 28： h=4 → 槽4 是 12，不等，继续
          → 槽5 是空 → 停止，报告"不存在"
```

28 明明在槽 7，却查不到了。 因为开放地址法里"遇到空槽就停"是查找的终止条件——它依赖一个不变量：从 $h(k)$ 开始的探测链上不能有洞。删除一旦打洞，后面的键就被切断了。

正确做法是写墓碑标记（tombstone）：槽 5 标记为 DELETED，查找遇到它继续往下走，插入可以覆盖它。

带墓碑：  13 · · · 12 [墓碑] 5 28
查询 28： 槽4(12≠28) → 槽5(墓碑, 继续) → 槽6(5≠28) → 槽7(28) ✓
```

墓碑的代价是它只占位、不装东西。查找时它和占用槽一样要走过去，但它不能让插入停下来算作"找到位置"以外的任何用处。于是一个反复插入删除的表会慢慢被墓碑填满：元素数没涨，探测长度却在涨，直到一次重建（rehash）把墓碑清掉。一个长期运行的开放地址哈希表，性能退化的原因往往不是元素变多，而是删除留下的坑变多。

负载因子与探测次数：0.75 这个数字是算出来的#

Knuth 在《计算机程序设计艺术》第三卷里给出了线性探测在均匀哈希假设下的平均探测次数闭式解——查找失败（也就是插入）是

$$\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$$

查找成功是 $\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$。双重哈希（近似"均匀探测"）对应的两个值分别是 $\frac{1}{1-\alpha}$ 和 $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$。代入数字：

这张表有两条读法，一条纵向、一条横向。

纵向看第二列：从 0.75 到 0.90，表里只多装了 20% 的元素，插入代价从 8.5 涨到 50.5，是 6 倍。$(1-\alpha)^2$ 这个平方项让代价在接近满表时爆炸式增长。这就是 0.75 这个阈值的来历——它不是随手取的整数，而是"再往上一点点就要付几倍代价"的那个拐点。

横向看 0.90 那一行：线性探测 50.5 次，双重哈希 10 次，差 5 倍。这 5 倍全部来自主聚簇——两种方案的哈希函数质量一样，区别只在探测序列会不会把碰撞堆到一起。

不过现代实现常常反过来选线性探测，理由不在这张表里：表里数的是探测次数，CPU 上真正贵的是缓存缺失。 线性探测的连续 8 个槽通常落在同一条 64 字节缓存行里，走 8 步只有 1 次内存访问；双重哈希每一步都跳到随机位置，8 步可能是 8 次缓存缺失。所以在 $\alpha \le 0.75$ 的区间里，线性探测的 8.5 次探测往往比双重哈希的 4 次更快。渐近分析和硬件现实各说一半，这是哈希表工程里最经典的一处分歧。

顺带一句：链地址法的对应公式温和得多——查找失败平均比较 $\alpha$ 次，成功 $1 + \alpha/2$ 次，$\alpha = 0.9$ 时是 0.9 和 1.45。它对高负载因子的耐受性好得多，代价是每个节点一个指针的内存开销和指针追逐的缓存缺失。

Robin Hood 与布谷鸟：重新设计探测序列#

线性探测的问题是探测长度的方差大：大多数键一步到位，少数键走几十步。有两条思路各自攻击这一点。

Robin Hood 哈希（Celis、Larson 与 Munro，1985；Celis 1986 年的博士论文给出完整分析）改的是碰撞时谁让位。标准线性探测里先到先得：占住槽的键不动，新来的往后走。Robin Hood 反过来——插入时比较双方"已经走了多远"，让走得少的那个让位给走得多的那个（抢富济贫，故名）。这不改变平均探测长度，但显著压掉了方差和长尾。副作用很实用：探测链上的键按"距离原始位置的偏移"单调排列，于是查找可以在偏移量超过当前键时提前判定"不存在"，不必走到空槽。

布谷鸟哈希（Pagh 与 Rodler，2004）更激进：每个键有两个候选位置，插入时如果两个都被占，就把其中一个踢出去，让它去自己的另一个位置，连锁踢下去（像布谷鸟把别人的蛋推出巢）。代价是插入可能触发长链甚至死循环（此时必须重建），换来的是查找最坏情况只要 2 次探测——不是平均 2 次，是最坏 2 次。这个最坏保证让它在硬件路由表、GPU 哈希表这类需要固定延迟的场合有不可替代的价值。

对比着看，这三种方案卖的是同一样东西的不同切法：线性探测卖缓存友好，Robin Hood 卖低方差，布谷鸟卖最坏界。没有哪个"更快"，它们只是把不确定性放在了不同的地方。

第二种：密码学哈希函数#

密码学哈希函数要求更强的性质：

1. 抗原像攻击（Preimage Resistance）：给定 $h$，找任意 $x$ 使 $h(x) = h$ 在计算上不可行
2. 抗第二原像攻击（Second Preimage Resistance）：给定 $x$，找 $y \neq x$ 使 $h(x) = h(y)$ 不可行
3. 抗碰撞性（Collision Resistance）：找任意一对 $x \neq y$ 使 $h(x) = h(y)$ 不可行

主要密码学哈希函数：

密码学哈希的应用：

• 密码存储：不存明文密码，只存 $h(\text{password} || \text{salt})$（加盐防止彩虹表攻击）
• 数据完整性：Git 用 SHA-1（后迁移到 SHA-256）标识每次提交的内容指纹——改变任何字节，哈希值就变
• 区块链：Bitcoin 区块头包含前一个区块的哈希值，链式结构使篡改历史需要重算后续所有区块
• 数字签名：先对消息取哈希，再对哈希值签名（消息可能很长，哈希值固定大小）

哈希碰撞攻击：不只是学术问题#

2005 年，山东大学王小云教授团队（王小云、殷益群、于红波）展示了对 MD5 的实际碰撞攻击——在普通计算机上可以在数小时内找到两个不同输入，产生相同的 MD5 哈希值。

2017 年，Google 研究人员展示了 SHA-1 的首个实际碰撞（称为 SHAttered 攻击）：构造了两个内容不同、SHA-1 哈希值完全相同的 PDF 文件。这次攻击花费了约 6500 年 CPU 时间和 110 年 GPU 时间（并行完成）。

这说明：密码学哈希的安全性不是永久的。随着算力提升和攻击技术进步，曾经"安全"的哈希函数会逐渐变得不安全。定期评估和迁移是密码学工程的基本纪律。

现场：哈希碰撞变成拒绝服务攻击#

上一节讲的是密码学碰撞——找碰撞难，需要 GPU 集群跑几个月。哈希表的碰撞是另一回事：那些函数为速度设计，找碰撞是几分钟的事。这条攻击面被发现了两次。

第一次是 2003 年。 Scott Crosby 与 Dan Wallach 在 USENIX Security 上发表《通过算法复杂度攻击实现拒绝服务》，指出"平均情况远优于最坏情况"的数据结构本身就是攻击面。他们打了 Perl 的哈希表、Squid 代理和 Bro 入侵检测系统：用低于拨号调制解调器的带宽，六分钟精心构造的数据包让一台专用 Bro 服务器丢弃了高达 71% 的流量、CPU 完全跑满。

第二次是 2011 年 12 月，而这次终于改变了行业。 Alexander Klink 与 Julian Wälde 在柏林的第 28 届混沌通信大会（28C3）上做了《对 Web 应用平台的高效拒绝服务攻击》报告，把同一套原理对准了 Web 框架：HTTP POST 请求里的表单参数会被服务端塞进一个哈希表，参数名就是键——攻击者完全控制键。他们构造出上千个哈希值相同的参数名，报告的实测数字是 70–100 kbit/s 的上行带宽就能让一个 Intel i7 核心满载。

算一下就明白为什么这么便宜。$n$ 个键全撞到同一个桶，链地址法下插入第 $i$ 个键要和桶里已有的 $i-1$ 个键逐个比较，总比较次数

$$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$$

$n = 10^4$ 个参数就是约 $5\times10^7$ 次字符串比较——一个请求，几十毫秒到几秒的纯 CPU。而攻击者只需发几百 KB。这是效率比最悬殊的一类 DoS：$O(1)$ 假设一旦失效，代价直接跳到 $O(n^2)$。

受影响的名单是当时的整个 Web 生态：PHP、Python、Java、Ruby 和 v8 JavaScript 引擎都被证实可攻击。Ruby 的编号是 CVE-2011-4815，PHP 的是 CVE-2011-4885。

修补分成两代，很能说明工程思路的演进：

第一代是打补丁式的限流。 PHP 5.3.9 加了配置项 max_input_vars，默认值 1000——直接限制单个请求能处理的参数个数。这不解决哈希函数的问题，只是把 $n$ 卡住，让 $n^2$ 大不到哪里去。今天很多 PHP 部署仍会因为表单字段过多而撞上这个默认值，那正是 2011 年这场攻击留下的疤。

第二代是换掉哈希函数。 Jean-Philippe Aumasson 与 Daniel J. Bernstein 在 2012 年发布 SipHash，正是为回应哈希洪泛攻击而设计：128 位密钥、64 位输出，纯加-旋转-异或（ARX）运算，短输入上极快。

它的安全论证方式和 SHA-256 完全不同，这一点常被误解：SipHash 并不声称抗碰撞。 它是一个带密钥的伪随机函数（PRF），保证的是"不知道密钥的人无法构造碰撞"。哈希表需要的恰好只是这一条——攻击者猜不到你进程启动时随机生成的那个密钥，就没法预先算出撞在一起的键。

于是随机化种子成了语言运行时的标配。Python 通过 PEP 456 在 3.4 版把默认字符串哈希换成 SipHash-2-4；Rust 标准库的 HashMap 默认哈希器 RandomState 用的是 SipHash-1-3，官方文档还专门写明：其他哈希算法在小键和长键上都会更快，"但那些算法通常不能抵御 HashDoS 这类攻击"。

该记住的是这条判断链：性能假设可以是攻击面。 "平均 $O(1)$" 在攻击者能选择输入的场景里不是保证而是漏洞，而修复它的正确层次不是限制输入大小（那只是止血），而是让输入与内部行为的映射变成攻击者不可预测的——把确定性换成密钥控制的随机性。这个思路后来在缓存、路由、限流等一堆"平均情况很好"的系统里被反复复用。

布隆过滤器：概率性的哈希应用#

同一套多重哈希还能拿来做另一件事：用远小于存储元素本身的空间，回答"这个元素在集合里吗"，代价是允许小概率的假阳性。这就是布隆过滤器（Bloom Filter，Bloom 1970）——它用 $k$ 个哈希函数把每个元素映射到一个位数组的 $k$ 个位置并置 1；查询时若有任一位为 0 就绝对不在，全为 1 则可能在。

这里只点出它与本文的关系：布隆过滤器把哈希表"存键、能精确回答"的能力卖掉了，换来的是空间从每元素几十字节降到每元素十个比特左右。假阳性率的公式推导、最优哈希个数、以及它在 LevelDB / RocksDB 里的实际参数，见 bloom-filter。

跨域连接#

• 概率论：负载因子与探测次数的关系有闭式解，线性探测的插入代价里含着"一减负载因子"的平方在分母上。这就是把阈值定在四分之三的理由：再往上一点点，代价按平方项爆炸。同一套球投箱分析还定下另一个常数——正常哈希下单桶元素数服从泊松分布，桶长到八的概率小到可忽略，所以转红黑树是防线而不是优化。
• 计算机安全原理：平均常数时间是一个关于输入分布的假设，而攻击者可以挑输入。所有键撞进同一个桶时，插入代价跳到平方级，几十千比特每秒的上行带宽就能打满一个核。正确的修法不是限制参数个数（那只是止血），而是让"输入到桶"的映射依赖进程启动时生成的密钥——把确定性换成攻击者不可预测的随机性。
• Unicode 与数字书写：字符串相等在多语言场景下不是平凡概念。同一个字形可以有预组合与分解两种码点序列，视觉相同而字节不同，哈希值自然不同。所以哈希之前必须规范化，而选哪种规范化形式会改变"哪些串算同一个键"。安全场景还要提防视觉混淆字符——它们规范化后依然不同，靠哈希区分不了。
• 基因检测与隐私：把身份证号、手机号或邮箱哈希一遍并不构成去标识化。输入空间有限且结构已知时，穷举反查是分分钟的事；基因型这类高维数据即使不带标识符，也可能被少数几个位点重新识别。有意义的做法是带密钥的哈希或加盐，且密钥不能与数据一起发布——与上一条的防御原理相同。
• 药物化学：化学信息学把分子的子结构枚举后哈希成固定长度的位向量，用重合比例估计相似度，从而在千万级化合物库里快速筛选。结构与概率型过滤器同构，代价也同构：不同子结构撞进同一位会造成假相似，向量越短假相似越多。所以筛出的候选必须再做精确的子结构匹配，粗筛与精查两级不可省。

参考文献#

• Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd ed., 6.4 节（散列）. Addison-Wesley, 1998. （线性探测与双重哈希的平均探测次数闭式解）
• Wang, X. et al. How to Break MD5 and Other Hash Functions. Eurocrypt 2005. （王小云团队的碰撞攻击论文）
• Stevens, M. et al. The First Collision for Full SHA-1. CRYPTO 2017. （SHAttered 攻击论文）
• Bloom, B. Space/Time Trade-offs in Hash Coding with Allowable Errors. CACM 13(7), 1970. （布隆过滤器原始论文）
• Crosby, S. A. & Wallach, D. S. Denial of Service via Algorithmic Complexity Attacks. 12th USENIX Security Symposium, 29–44 (2003).
• Klink, A. & Wälde, J. Efficient Denial of Service Attacks on Web Application Platforms. 28th Chaos Communication Congress (28C3), 2011.
• Aumasson, J.-P. & Bernstein, D. J. SipHash: A Fast Short-Input PRF. INDOCRYPT 2012.
• Celis, P., Larson, P.-Å. & Munro, J. I. Robin Hood Hashing. IEEE FOCS 1985；Celis, P. 博士论文, University of Waterloo, 1986.
• Pagh, R. & Rodler, F. F. Cuckoo Hashing. Journal of Algorithms 51(2), 122–144 (2004).
• Python 增强提案 PEP 456, Secure and Interchangeable Hash Algorithm（Python 3.4 起默认 SipHash-2-4）。
• CPython 源码 Objects/dictobject.c（USABLE_FRACTION、PERTURB_SHIFT 与探测递推）；OpenJDK java/util/HashMap.java（DEFAULT_LOAD_FACTOR、TREEIFY_THRESHOLD 及其泊松分布注释）。

延伸阅读#

• Rust 标准库文档：std::collections::HashMap（默认哈希器与 HashDoS 权衡的说明）— https://doc.rust-lang.org/std/collections/struct.HashMap.html
• Mitzenmacher, M. & Upfal, E. Probability and Computing. 2nd ed. Cambridge University Press, 2017. （第 5 章球与箱子模型，哈希分析的概率工具）
• Ferguson, N., Schneier, B. & Kohno, T. Cryptography Engineering. Wiley, 2010. （密码学哈希的工程使用与迁移纪律）