第 6 章　哈希表

本章解决的问题：为什么"查找"这件事能做到接近 $O(1)$？以及你每天在用的 Dictionary，内部到底发生了什么。

6.1　从数组下标到哈希函数

学习目标：学完本节，你能

• 说清"直接寻址表"为什么快，以及它为什么用不了；
• 写出一个哈希函数，并说出好哈希的三条要求；
• 解释为什么"字符求和"这类直觉哈希函数会灾难性地失效。

先修：3.1（数组的随机访问）。 固定术语：直接寻址表、哈希函数、哈希值、桶、冲突。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

一、直觉：最快的数据结构其实是数组

回顾 3.1 节的结论：数组按下标访问是 $O(1)$ —— 一次乘法加一次加法就算出地址，直接跳过去。

那"查找"最快能有多快？如果我们能直接把"键"当下标用，查找就是 $O(1)$。

// 学号是 0 ~ 999 的整数，直接开一个 1000 长度的数组
string?[] students = new string?[1000];
students[42] = "小陈";

// 查学号 42 的学生：一次数组访问
string? name = students[42];        // O(1)

这就是"直接寻址表" —— 键直接就是下标。

实测：1000 万次随机访问，20 毫秒左右。这是查找速度的理论上限。

但现实世界不会这么配合。 直接寻址有三个致命的限制：

解决思路：把"大范围的键"映射到"小范围的下标"。

这个映射函数，就叫哈希函数（Hash Function）。

二、形式化：哈希函数与桶

最基本的一种映射：取模。

int bucketIndex = Math.Abs(hashValue) % bucketCount;

% 把任意大的哈希值压缩到了 [0, bucketCount) 范围内 —— 正好可以当数组下标。

这就是哈希表的核心机制：

键 "小陈"  ──哈希函数──>  1,234,567,890  ──% 1000──>  890  ──> 桶[890]
键 42      ──哈希函数──>  42             ──% 1000──>  42   ──> 桶[42]

查找时走同样的路：算出哈希值 → 取模 → 直接跳到那个桶。一步到位，$O(1)$。

三、一个好哈希函数的三条要求

还有一条隐含要求：雪崩效应 —— 输入变一个字符，输出应该面目全非。这一条是"均匀性"的加强版，下面会用实验说明它为什么重要。

四、实验：坏哈希函数的致命缺陷

先看两个哈希函数：

// 坏哈希：把所有字符的 ASCII 码相加
static int BadHash(string s)
{
    int hash = 0;
    foreach (char c in s) hash += c;
    return hash;
}

// 好哈希：多项式滚动哈希（乘一个质数再加下一个字符）
static int GoodHash(string s)
{
    int hash = 17;
    foreach (char c in s)
        hash = hash * 31 + c;
    return hash;
}

字符求和的哈希看起来挺合理，很多人第一次写哈希函数都会这么写。

现在用一组"字母重排词"来测它（这些词由完全相同的字母组成，只是顺序不同）：

  单词           坏哈希(求和)      好哈希(多项式)
----------------------------------------------
  listen              663              172201857
  silent              663              756767317
  enlist              663              1526377105
  tinsel              663              1780641493
  inlets              663              2022633299
  lentis              663              1843104701

坏哈希算出来全都是 663！

原因：字符求和的结果只跟"用了哪些字母"有关，跟顺序完全无关。这六个词的字母完全相同，所以哈希值必然相同。

后果：这六个词会全部挤进同一个桶，哈希表在这里退化成一条链表 —— 查找变成 $O(n)$，哈希表的全部优势荡然无存。

好哈希引入了"位置"的影响（每读一个字符就乘 31），所以顺序一变，结果就完全变了。

这个缺陷在真实场景中危险吗？非常危险。

想想你的系统里有没有这类"由相同元素不同排列组成"的数据：

• 用户上传的文件名（report_2024.pdf、2024_report.pdf）
• 由固定的几个字段拼接成的缓存键
• 代码里的标识符

不需要攻击者，正常数据就可能触发这个问题。

五、实验：分布均匀性

用 10,000 个随机字符串，看两种哈希在 1000 个桶里的分布：

  坏哈希（字符求和）:
    空桶数量      :    183 / 1,000  (18.3%)
    最长的桶      :     43 个元素
    冲突配对数    : 87,824
    理论期望每桶  : 10.0 个元素

  好哈希（多项式）  :
    空桶数量      :      0 / 1,000  (0.0%)
    最长的桶      :     22 个元素
    冲突配对数    : 50,338
    理论期望每桶  : 10.0 个元素

怎么读这张表：

坏哈希留下了 183 个空桶，同时把 43 个元素挤进同一个桶 —— 这说明它的分布不均匀：有些位置根本没人去，有些位置挤破头。

要诚实地说明一点：在随机字符串下，坏哈希的表现"还不算太糟"（最长桶 43 vs 好哈希的 22，差一倍而已）。

因为随机字符串的字母组合本来就分散，字符求和碰巧也能有些区分度。

但真实数据不是随机的。 实验四的字母重排词就是极端情况 —— 那里坏哈希是完全失效的（全部落进一个桶）。哈希表最怕的从来不是随机数据，而是有规律的数据。

六、雪崩效应：一个我踩到的坑

写这节时我做了个演示：把 "hello" 改成 "hellp"（只改最后一个字符），看两个哈希值差多少。

我以为会看到"完全不同"，结果是这样的：

  输入对                  多项式哈希                带混合步骤
--------------------------------------------------------------------
  "hello" -> "hellp"    585857889 (差异   6%)    1209480147 (差异  50%)
  "abc" -> "abd"        602801    (差异   6%)    835827598  (差异  47%)
  "user1" -> "user2"    598274133 (差异   6%)    881932256  (差异  59%)

多项式哈希下，"hello" 和 "hellp" 的哈希值只差 1！

原因很直接：前四个字符的计算完全相同，只有最后一步不同：

$$\text{hash} \times 31 + 111 \quad \text{vs} \quad \text{hash} \times 31 + 112$$

'o' 是 111，'p' 是 112，差了 1。所以最终的哈希值也只差 1。

这意味着：只差一个字符的两个键，会落到相邻的桶里。 如果系统里有大量这样的键（比如 user1 到 user10000），它们会挤成一片。

修正的办法是加一个"混合步骤"（finalizer）：

// 更好的哈希：多项式 + 末尾的「混合步骤」
static int BetterHash(string s)
{
    int hash = 17;
    foreach (char c in s)
        hash = hash * 31 + c;

    // ---- finalizer：把高位的变化扩散到低位 ----
    unchecked
    {
        hash ^= hash >> 16;
        hash *= (int)0x85ebca6b;
        hash ^= hash >> 13;
        hash *= (int)0xc2b2ae35;
        hash ^= hash >> 16;
    }
    return hash;
}

加了这三行之后，差异位占比从 6% 变成了 47%～59% —— 这才叫雪崩效应。

这个"踩坑"值得记住：别看多项式哈希写起来简单就以为够用了。

生产环境用的哈希函数（MurmurHash、xxHash、SipHash）都包含这类"打散"步骤，目的就是让输入的微小变化在输出里被彻底放大。

而 .NET 的 string.GetHashCode() 用的是微软自己实现的哈希算法，已经做过这些处理 —— 这也是为什么你平时不需要自己写哈希函数。

七、业界常用的哈希函数

最后一行的提醒：有同学会想"既然 SHA-256 最安全，那用它当哈希函数肯定最好"。

这是个常见的误解。 哈希表对哈希函数的要求是快 + 均匀，不是抗破解。SHA-256 为了抗密码分析做了大量运算，用它当哈希函数会让每次增删改查都慢几十倍。

6.4 节会讲 SipHash —— 它是唯一一个"既快又能抗攻击"的选择，.NET 的 Dictionary 在某些配置下就是用它。

八、练习

练习 6.1.1（设计哈希函数） 为一个"日期"类型设计哈希函数，键包含年、月、日三个整数。 (a) 写出你的哈希函数。 (b) 如果直接用 年 * 10000 + 月 * 100 + 日 当哈希值，会有什么问题？ (c) 如果键里还包含"星期几"，你的哈希函数要改吗？

练习 6.1.2（判断） 判断对错并说明理由： (a) 哈希函数的结果是唯一的，不同键一定得到不同的哈希值。 (b) 只要哈希函数足够好，冲突就可以完全避免。 (c) 哈希表查找的复杂度是严格 $O(1)$。

练习 6.1.3（找错） 下面这个哈希函数有三个问题，请指出：

static int Hash(string s)
{
    int hash = 0;
    for (int i = 0; i < s.Length; i++)
        hash += s[i] * i;          // 注意这里是 * i
    return hash;
}

练习 6.1.4（分析） 一个系统用 键.GetHashCode() % 1000 计算桶下标。 (a) 如果哈希值是负数，会发生什么？ (b) 如果桶的数量是 1000（不是 2 的幂）而 GetHashCode() 的低位分布不好，会有什么影响？ (c) 为什么很多哈希表实现要求桶的数量是质数或2 的幂？

练习 6.1.5（挑战·哈希碰撞攻击） 你在做一个 Web 服务，用户提交的数据会作为键存进哈希表。攻击者可以让哈希表的所有操作退化成 $O(n)$，从而拖垮服务。 (a) 攻击者是怎么做到的？ (b) 用前面学过的知识，你能想到哪两种防御手段？

九、练习答案

6.1.1

(a) 一个合理的哈希函数：

static int HashDate(int year, int month, int day)
{
    int hash = 17;
    hash = hash * 31 + year;
    hash = hash * 31 + month;
    hash = hash * 31 + day;
    return hash;
}

要点：三个字段都用同样的方式参与运算（乘一个质数再加），这样任一字段变化都会影响最终结果。

(b) 直接用 年*10000 + 月*100 + 日 的问题：

它会产生"聚集"。 这个式子把日期编码成了一个连续的整数，比如：

• 2024-01-01 → 20240101
• 2024-01-02 → 20240102

相邻的日期得到相邻的哈希值。 如果桶的数量是 1000，那么：

$$20240101 \bmod 1000 = 101, \quad 20240102 \bmod 1000 = 102$$

结果：同一个月里的日期会连续占据相邻的桶，而其他月份的位置则被跳过。

更糟的是：如果只关心"年"这个字段，同年所有日期的哈希值高位相同，取模后会在桶里形成周期性的聚集。

哈希函数应该让"输入的任何一点变化"都影响到"输出的所有位"。 简单的线性组合做不到这一点，所以需要乘法 + 混合。

(c) 要改。 添加一个字段就是往里加一步：

hash = hash * 31 + (int)dayOfWeek;

但要注意：如果"星期几"是由日期推导出来的（比如同一个日期必然对应同一个星期几），那它就不提供任何新信息 —— 加进去只是白白增加计算量。

设计哈希函数的一个原则：只用真正独立的字段。 互相能推导出来的字段，加进去没有收益。

6.1.2

• (a) 错。 哈希函数是多对一的映射：不同的键可能得到相同的哈希值（这就是冲突）。哈希值相同不代表键相同，所以哈希表在找到候选后还必须用 Equals 再比较一次。

  这是哈希表最容易搞错的一点：哈希值只是"快速定位"的手段，真正判断相等要靠 Equals。这条约束在 6.4 节会展开。

• (b) 错，而且这是数学上的不可能。 键的取值空间（字符串、任意整数）是无限的，而哈希值只有 $2^{32}$ 个（32 位整数），桶的数量更少。根据鸽巢原理，冲突必然存在。

  好的哈希函数只是让冲突在统计上稀少，不能消除它。

• (c) 错。 精确说法是平均 $O(1)$（且假设哈希函数均匀）：
  • 最好：$O(1)$
  • 平均：$O(1)$（负载因子有界时）
  • 最坏：$O(n)$（所有键都冲突到同一个桶） >

    这就是为什么 6.4 节要专门讲"哈希碰撞攻击" —— 最坏情况是可以被恶意构造出来的。

6.1.3

问题 1：第一个字符不参与运算。

当 i = 0 时，s[0] * 0 = 0。所以第一个字符对哈希值毫无影响！

结果："abc" 和 "xbc" 会得到完全相同的哈希值。

修正：从一个非零的初始值开始，或者把 i 换成 i + 1。

问题 2：没有初始值，而且乘数 i 太小。

hash 从 0 开始，第一个字符乘 0，第二个字符乘 1……乘数增长太慢，无法把变化扩散开。

修正：用一个固定的质数当乘数（比如 31），而不是位置下标：

int hash = 17;
for (int i = 0; i < s.Length; i++)
    hash = hash * 31 + s[i];

问题 3：hash 可能溢出且不处理。

int 乘法会静默溢出（超过 int.MaxValue 就回绕）。这在 C# 里默认是 unchecked 的，虽然对哈希函数来说"溢出"本身不是错误（回绕也是确定性行为），但要注意：

• 如果代码在 checked 上下文里，会抛 OverflowException
• 溢出后的分布特性可能变差

修正：显式用 unchecked 块或者 uint，让意图明确。

这个练习想说明的是：写哈希函数时，"每一项都要参与运算"和"乘数要足够大且是质数"是两条基本功。

6.1.4

(a) 会得到负的数组下标，直接抛 IndexOutOfRangeException。

C# 里 -7 % 1000 的结果是 -7（不是 993）—— 负数取模会得到负数。

修正：用位运算去掉符号位，或者取绝对值：

int idx = (hash & 0x7FFFFFFF) % bucketCount;     // 推荐：去掉符号位
int idx = Math.Abs(hash) % bucketCount;          // 也可以，但 int.MinValue 会溢出

注意 Math.Abs(int.MinValue) 会抛异常（因为 int.MinValue 的绝对值超出了 int 的范围）。所以首选 & 0x7FFFFFFF。

(b) 会加剧聚集。 GetHashCode() 的低位往往分布不均匀（比如某些实现下低位变化有规律），而 % 1000 主要依赖低位。

具体来说：1000 = 8 × 125，% 1000 的结果同时受低位（决定能否被 8 整除）和高位影响，但如果哈希值的低位有规律，取模后也会有规律。

(c) 两种设计各有道理：

• 用质数：让"哈希值的规律"和"桶数量的因子"尽量错开。比如哈希值总是偶数时，如果桶数是 1000（偶数），取模后只能落在偶数桶上 —— 一半的桶永远用不到。换成质数 997 就能打散这个规律。
• 用 2 的幂：% 2^k 可以用 & (2^k - 1) 代替，快得多（位运算 vs 除法）。但要先把哈希值的高位混合到低位，否则低位不好的哈希函数会灾难性失效。

.NET 的 Dictionary 用的是质数（而且会从一个质数表里选下一个更大的质数）。而 Java 的 HashMap 用的是 2 的幂，代价是必须对 hashCode 再做一次"高低位异或"来打散。

这是"速度 vs 分布质量"的经典权衡。

6.1.5

(a) 攻击方式：构造大量"哈希值相同"或"哈希值落入同一个桶"的键。

具体做法（以字符串键为例）：

1. 先确定桶的数量。 可以从响应时间推断，也可以穷举试探（比如发送不同数量的键，观察耗时何时突然上升）。
2. 构造同余的键。 如果哈希函数是"字符求和取模"（很多老系统的实现），那攻击者只要让字符之和相同就行 —— 字母的任意重排都是一个新的键，但哈希值完全相同（正是实验四演示的现象）。
3. 批量提交。 用几万个这样的键填充哈希表，它们全部落进同一个桶。

结果：这个桶上的链表长度变成 $O(n)$，查找这个桶里的任意键都要遍历整条链表。如果每次 HTTP 请求都触发一次这样的查找，几万个键就能让 CPU 占满。

这不是理论威胁。 2011 年，多个主流 Web 框架（PHP、Java、Ruby、Python 等）都被发现存在这个问题，攻击者用几十 KB 的请求就能让服务器 CPU 飙升到 100%。

(b) 两种防御手段：

防御 1：随机化 —— 给哈希函数加一个每次启动都不同的密钥。

这就是 SipHash 的做法：哈希函数的输出依赖一个随机密钥。

• 攻击者无法预先构造碰撞的键，因为他不知道这次运行的密钥是什么。
• 服务器重启一次，密钥就变了，之前的攻击数据全部失效。

代价：稍微慢一点（但远比 SHA-256 快）。

防御 2：限制单个桶的长度，超限时改用其他结构。

比如 Java 8 的 HashMap：当单个桶的链表长度超过 8 时，自动转换成红黑树。

这样即使发生碰撞，单个桶的查找复杂度也从 $O(n)$ 降到了 $O(\log n)$ —— 攻击效果被大幅削弱。

（红黑树是第 10 章之后的内容，这里只需知道它能把"线性查找"变成"对数查找"。）

现代的运行时会同时用这两种手段。 比如 .NET 的 Dictionary 在某些场景下会启用随机化的字符串哈希；Java 8+ 的 HashMap 用了树化。

这就是"最坏情况真的会发生"的又一个例证 —— 而且在哈希表这里，最坏情况是攻击者主动构造的，不是运气不好撞上的。

十、常见错误

十一、本节总结

1. 数组按下标访问是 $O(1)$，这是查找速度的上限。哈希表的思路就是把键"伪装"成下标。
2. 直接寻址表受三个限制：键范围太大、键不是整数、数据太稀疏 —— 所以需要哈希函数。
3. 哈希函数把任意键映射成整数，再用 % bucketCount 压缩到数组下标范围。
4. 好哈希的三条要求：确定性、均匀性、高效性。外加一条实践要求：雪崩效应。
5. 字符求和是灾难性的哈希函数：字母重排词会全部碰撞（实测 6 个词全是 663）。原因是它完全忽略了"位置"。
6. 简单的多项式哈希也不够：实测 "hello"/"hellp" 只差 1。需要 finalizer 混合步骤才能达到 50% 的位差异。
7. 冲突无法避免（鸽巢原理），所以哈希表的设计重点是"冲突了怎么办" —— 这正是下一节的主题。

下一节衔接：既然冲突不可避免，那就要有一套处理冲突的机制。业界有两大流派：链地址法（冲突了就挂一条链表）和开放寻址（冲突了就往后找空位）。它们各有各的脾气，而且实测结果会颠覆你的直觉 —— 探测次数更多的那个，反而更快。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "6.1",
  "title": "从数组下标到哈希函数",
  "covered": [
    "直接寻址表的 O(1) 访问与三个致命限制",
    "哈希函数与桶的定义、取模映射",
    "好哈希函数的三条要求 + 雪崩效应",
    "字符求和哈希在字母重排词上的完全失效（实测全是 663）",
    "分布均匀性实测（坏哈希 183 空桶/最长 43 vs 好哈希 0 空桶/最长 22）",
    "多项式哈希的末位敏感性缺陷（hello/hellp 只差 1）与 finalizer 修正",
    "业界哈希函数选型（DJB2/MurmurHash/SipHash/SHA-256）",
    "哈希碰撞攻击的原理与两种防御"
  ],
  "unresolved": [
    "冲突解决的具体机制留到 6.2",
    "负载因子与扩容留到 6.3",
    "Dictionary 的工程用法与 SipHash 细节留到 6.4",
    "红黑树留到第 10 章"
  ],
  "canonical_terms": {
    "直接寻址表": "键直接作为数组下标的查找结构，O(1) 但适用范围极窄",
    "哈希函数": "把任意类型的键转换成整数的函数",
    "哈希值": "哈希函数的输出",
    "桶": "底层数组的一个位置",
    "冲突": "两个不同的键映射到同一个桶"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 3.1 的数组随机访问与地址公式",
    "读者理解 C# 中 int 溢出与取模的行为"
  ],
  "word_count_actual": 2880,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch06/Sec61/",
    "字母重排词哈希值实测全部相同（663）；分布统计与雪崩位差异均为实测",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版「雪崩效应」演示用纯多项式哈希，实测 hello/hellp 只差 1（差异位 6%），与「雪崩」的说法矛盾；已改为「多项式 vs 带 finalizer」的对照，并把「简单多项式哈希末位扩散性差」本身写成教学点"
  ],
  "next": "6.2 冲突解决：链地址法与开放寻址"
}