1.5 哈希算法

前面几篇的数据都是排好序、有结构的数组。这一篇讲一个不同思路的结构——哈希（hashing）。它放弃"有序"这个性质，换来一个惊人的回报：插入和查找平均只要 $O(1)$。这是所有数据结构里最快的查找档次，也是为什么字典、缓存、数据库索引、密码学都离不开它。

1.核心想法：直接算出该放哪

回到问题：我想存一堆键值对（比如"姓名→电话"），支持快速插入和查找。

有序数组配二分查找，查找是 $O(\log n)$。要更快，得换思路：能不能不算、不比，直接用一个函数把键"算"成它该存放的位置？ 这样查找时，我拿键过一遍这个函数，直接定位到位置，一次到位。

这就是哈希。那个函数叫哈希函数 $h$，它把键 $k$ 映射到一个数组下标 $h(k)\in\{0,1,\dots,m-1\}$（$m$ 是数组大小，这个数组叫哈希表）。存的时候算 $h(k)$ 放进去；找的时候算 $h(k)$ 去那个位置拿。理想情况下，插入、查找、删除都是 $O(1)$。

举个例子，哈希函数 $h(k)=k\bmod m$，$m=10$。键 $25$ 存到下标 $5$，键 $38$ 存到下标 $8$。查 $25$？算 $25\bmod 10=5$，直接去下标 5 拿，一步到位。

2.不可避免的麻烦：碰撞

理想很美，但有个根本矛盾：键的取值范围通常远大于表的大小 $m$。 比如键是任意字符串，可能有无穷多种，但表只有 $m$ 个格子。所以必然有两个不同的键 $k_1\neq k_2$ 算出同一个下标 $h(k_1)=h(k_2)$，这叫碰撞（collision）。

碰撞不是 bug，是数学上必然的（鸽巢原理：$m$ 个巢装不下多于 $m$ 个键）。所以哈希表的设计，核心就是怎么处理碰撞。两大流派：

链地址法（chaining）：每个槽位挂一个链表。算出下标 $i$ 后，把元素插到 $A[i]$ 这个链表里；查找时算 $i$，然后在这个链表里线性找。碰撞的元素全堆在同一个链表里。

开放地址法（open addressing）：不挂链表，碰撞了就按某个探测序列找下一个空槽。比如线性探测：算出 $i$，如果 $i$ 被占了就看 $i+1$，再被占就看 $i+2$，直到找到空位。

不管哪种，关键都是让碰撞尽量少、尽量均匀。如果所有键都挤到同一个槽，链表退化成全长链，查找就退化成 $O(n)$——这是哈希表最坏的情况。而碰撞多不多，取决于两件事：哈希函数好不好、装得多满不满。

3.负载因子与好的哈希函数

负载因子 $\alpha=n/m$（已存元素数 / 表大小），衡量表装得多满。链地址法里，$\alpha$ 也就是每个链表的平均长度——所以平均查找代价正比于 $\alpha$。要让查找保持 $O(1)$，得让 $\alpha$ 控制在小常数（实践中常取 $\alpha\le 0.75$）。超过阈值就扩容（rehash）：开一个更大的表（通常两倍），把所有元素重新哈希搬过去。

好的哈希函数要做到：对任意输入，输出下标尽量均匀散布在 $\{0,\dots,m-1\}$ 上，不能让某些下标特别拥挤。常用的有除留余数法 $h(k)=k\bmod m$（$m$ 要选素数，避免周期性聚集）、乘法法、以及密码学哈希（MD5/SHA 那一族，第六卷 6.5 通用哈希会细讲）。

一个反例能让你印象深刻：如果 $m=100$，键都是 10 的倍数（$10,20,30,\dots$），那 $k\bmod 100$ 全落在 $\{0,10,20,\dots,90\}$ 这几个槽，其余 90 个槽全空——极度不均匀，性能崩。选素数 $m$ 就能缓解这种聚集。

4.复杂度：平均 $O(1)$，最坏 $O(n)$

哈希表的复杂度是这本书里第一个强烈依赖输入的例子，值得讲清楚：

• 平均情况 $O(1)$：假设哈希函数足够好、负载因子 $\alpha$ 有界，每个键等概率落到各个槽，链表平均长度 $O(1)$，于是插入/查找平均 $O(1)$。
• 最坏情况 $O(n)$：所有键都碰撞到同一个槽（哈希函数极差，或有人故意构造碰撞攻击），整张表退化成一个长链表，查找 $O(n)$。

所以"哈希表是 $O(1)$"这句话有个隐藏前提——哈希函数均匀 + 负载因子有界。实践中用扩容控制 $\alpha$、用好的哈希函数保证均匀，平均 $O(1)$ 就能稳稳成立。但要心里有数：它的最坏情况是 $O(n)$，6.5 节的通用哈希就是为了对抗"有人恶意构造碰撞"这种攻击。

5.哈希函数的另一个面孔：指纹

到目前为止我们讲的哈希是用来寻址的（算出存哪）。但哈希函数还有个完全不同的用途：给任意数据生成一个固定长度的指纹（fingerprint）。

比如密码学里存密码：绝不能明文存，而是存 $h(\text{密码})$。登录时把输入密码过一遍 $h$，和存的比对——哪怕数据库泄露，攻击者拿到的也只是指纹，反推不出原密码（前提是 $h$ 不可逆，像 SHA-256 这种）。第六卷的布隆过滤器（6.6）也是这个思路：把一堆元素各自算个哈希指纹，用指纹快速判断"某元素大概在不在这个集合里"。

寻址哈希和指纹哈希要求不一样：寻址要快、均匀；指纹要抗碰撞、不可逆（密码学哈希）。别混了。

6.练习

Q1. 负载因子 $\alpha$ 是什么？为什么哈希表要控制 $\alpha$ 不超过某个阈值（比如 0.75）？超过会怎样？

$\alpha=n/m$，是已存元素数除以表大小。链地址法下 $\alpha$ 等于每条链表的平均长度，所以平均查找代价正比于 $\alpha$。$\alpha$ 太大意味着表太挤、链表太长，查找退化。超过阈值要扩容 rehash：开更大的表、重哈希所有元素，把 $\alpha$ 压回去，恢复 $O(1)$ 性能。

Q2. 为什么说哈希表"平均 $O(1)$ 但最坏 $O(n)$"？什么情况下会退化到最坏？

平均情况下哈希函数把键均匀分散，每条链表 $O(1)$ 长，查找 $O(1)$。最坏情况是所有键碰撞到同一个槽（哈希函数极差，或被恶意构造碰撞攻击），整张表退化成一条长链，查找变 $O(n)$。6.5 节通用哈希就是为对抗恶意构造而设计的。

Q3.（思考题） 哈希表放弃了"有序"，换来 $O(1)$ 查找。如果你既需要 $O(1)$ 查找、又需要按顺序遍历元素，该怎么办？

单一数据结构难两全。哈希表快但无序，有序结构（平衡树）有序但查找 $O(\log n)$。工程上的解法是组合：用哈希表做 $O(1)$ 查找，另维护一个有序结构（或链表）做顺序遍历，两者同步更新。Java 的 LinkedHashMap 就是这么做的。这是"按需组合数据结构各取所长"的典型思维。

7.小结

哈希用"直接算出位置"的思路，把查找压到平均 $O(1)$，代价是放弃有序、且必须处理碰撞。记住三件事：负载因子控制（靠扩容）、好哈希函数保证均匀、平均 $O(1)$ 但最坏 $O(n)$。下一篇我们离开"查找一个元素"，进入"遍历整个图"的世界——广度优先搜索和深度优先搜索。