6.3　负载因子、扩容与再哈希

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

定义负载因子，并说出它对性能的定量影响；
画出（并解释）负载因子的"悬崖曲线"；
说清扩容与再哈希的过程，并解释为什么摊还下来仍是 $O(1)$；
知道什么时候该预分配容量。

先修：6.2（两种冲突解决方式）、3.2（动态数组的摊还分析）。 固定术语：负载因子、扩容、再哈希、摊还代价。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、负载因子的定义

$$\text{负载因子}\ \alpha = \frac{\text{元素个数}}{\text{桶（槽位）个数}}$$

它衡量的是"哈希表有多满"：

$\alpha$	含义
0.1	很空 —— 性能极好，但浪费内存
0.5	半满 —— 常见的平衡点
0.75	偏满 —— .NET `Dictionary` 和 Java `HashMap` 的扩容阈值
0.95	快满了 —— 开放寻址的性能会崩溃
> 1	装不下了 —— 开放寻址直接报错（6.2 节实测过）

负载因子是哈希表最重要的一个参数 —— 它同时决定了性能、内存占用，以及什么时候该扩容。

二、实测：负载因子的"悬崖曲线"

对一个容量 20 万的开放寻址表，在不同负载因子下测量平均探测次数：

        负载因子 |       成功查找 |       失败查找 |       理论成功 |       理论失败
--------------------------------------------------------------
      0.10 |       1.05 |       1.12 |       1.06 |       1.12
      0.25 |       1.17 |       1.40 |       1.17 |       1.39
      0.50 |       1.51 |       2.51 |       1.50 |       2.50
      0.60 |       1.76 |       3.56 |       1.75 |       3.62
      0.70 |       2.18 |       5.83 |       2.17 |       6.06
      0.80 |       3.00 |      12.97 |       3.00 |      13.00
      0.90 |       5.53 |      49.48 |       5.50 |      50.50
      0.95 |      10.57 |     168.27 |      10.50 |     200.50

实测值和 Knuth 的理论公式几乎完全吻合（理论公式见本节末尾的补充）。

先看"成功查找"那一列：

负载因子	探测次数（实测）	相对 0.5 时的倍数
0.10	1.05	0.7
0.50	1.51	1.0
0.70	2.18	1.4
0.80	3.00	2.0
0.90	5.53	3.7
0.95	10.57	7.0

从 0.80 到 0.95，负载因子只涨了 19%，探测次数却涨了 3.5 倍。

再看"失败查找"—— 它更夸张：

  探测次数（失败查找）随负载因子的变化：

    负载 0.10 | # 1.1
    负载 0.25 | # 1.4
    负载 0.50 | ## 2.5
    负载 0.60 | ### 3.6
    负载 0.70 | ###### 6.1
    负载 0.80 | ############# 13.0
    负载 0.90 | ################################################## 50.5
    负载 0.95 | ############################################################ 200.5   (实测 168.3)

这个形状就是"悬崖"：

前半段几乎是平的：负载从 0.1 涨到 0.5，探测次数只从 1.1 涨到 2.5
0.8 之后开始陡峭：13.0
0.9 之后几乎垂直：50.5 → 200.5

这就是为什么开放寻址"必须留出空位" —— 不是"留点余量更保险"，而是曲线在接近 1 的地方是垂直上升的。

具体到工程上：负载因子 0.95 时，一次失败查找平均要探测 168 次（理论值 200 次）—— 比线性扫描还慢。哈希表辛辛苦苦建立的 $O(1)$ 优势荡然无存。

为什么失败查找比成功查找贵这么多？

成功查找：找到目标就停了，平均走一半。
失败查找：必须走完整条探测链，遇到空位才能确认"不存在"。而负载因子越高，探测链越长。

这个区别在工程上很重要：如果你的系统里"查不到"是常态（比如缓存未命中），那你的哈希表实际承受的是失败查找的代价 —— 它比成功查找贵得多。

三、两种方案对负载因子的敏感度

负载因子	链地址法（成功查找）	开放寻址（成功查找）
0.5	$1 + 0.25 = 1.25$	1.50
0.9	$1 + 0.45 = 1.45$	5.53
2.0	$1 + 1.0 = 2.0$	不可能

链地址法的性能随负载因子"线性"增长，而开放寻址是"爆炸性"增长。

原因：链地址法把溢出的元素挂到链表上，多出来的元素只是让链表变长一点；而开放寻址只能在数组内部腾挪，越挤越难找空位。

这带来一个反直觉的结论：

虽然 6.2 节实测开放寻址更快（12.4 ms vs 34.9 ms），但那是在负载因子 0.38 的前提下测的。

如果负载因子提到 0.9，开放寻址会急剧变慢，而链地址法还能稳住。

所以选型时要看的不只是"哪个更快"，还有"我的负载因子能控制到多低"。

四、什么时候扩容

工程上的通行做法：负载因子超过 0.75 就扩容（把容量翻倍）。

实现	扩容阈值
.NET `Dictionary`	0.72 左右（内部用质数容量）
Java `HashMap`	0.75
Python `dict`	2/3

为什么是 0.75 而不是 0.9？

因为要给探测留余量：

0.75 时，成功查找约 2.5 次探测、失败约 8.5 次 —— 还能接受
0.9 时，失败查找要 50 次 —— 已经很糟了

为什么不是 0.5？

因为浪费内存。负载因子 0.5 意味着一半的空间是空的。对于存了几百万条记录的哈希表，这是几个 GB 的差别。

0.75 是"性能"和"内存"之间的经验平衡点。三种主流实现不约而同地选在 0.66～0.75 之间，说明这个区间确实合理。

五、扩容与再哈希

扩容（Resize）不是简单地把数组变大 —— 因为桶的下标是用 hash % capacity 算出来的，容量一变，所有元素的下标都变了。

必须先扩容，再把每个元素重新算一遍下标搬过去。这一步叫"再哈希"（Rehash）。

/// <summary>扩容：容量翻倍，把所有元素重新哈希到新表。</summary>
private void Resize()
{
    int oldCapacity = _buckets.Length;
    var oldBuckets = _buckets;

    _buckets = new LinkedList<KeyValuePair<int, string>>?[oldCapacity * 2];

    int moved = 0;
    foreach (var chain in oldBuckets)
    {
        if (chain == null) continue;
        foreach (var kv in chain)
        {
            int idx = BucketIndex(kv.Key, _buckets.Length);   // 用新容量重新算下标
            _buckets[idx] ??= new LinkedList<KeyValuePair<int, string>>();
            _buckets[idx]!.AddLast(kv);
            moved++;
        }
    }
    TotalRehashed += moved;
}

实测扩容过程（初始容量 4，连续插入 20 个元素）：

    插入第几个 |       容量 |         耗时 | 说明
--------------------------------------------------------------
         1 |        4 |    342.1 us |      <- 首次调用含 JIT 编译开销
         2 |        4 |      0.1 us |
         3 |        4 |      0.1 us |
         4 |        8 |      0.9 us | <- 触发扩容！重新哈希了 3 个元素，容量 4 -> 8
         5 |        8 |      0.1 us |
         6 |        8 |      0.1 us |
         7 |       16 |      0.5 us | <- 触发扩容！重新哈希了 6 个元素，容量 8 -> 16
         8 |       16 |      0.1 us |
         9 |       16 |      1.6 us |
        10 |       16 |      0.1 us |

两个观察：

绝大多数插入是 0.1 微秒级的 —— 纯粹的 $O(1)$。
偶尔有一次明显更慢 —— 那就是扩容，要重新哈希已有元素。

第一行的 342 微秒是 JIT 编译开销，不是扩容的代价。做性能测试时，永远要先把这类"首次调用开销"排除掉（预热），否则会得出错误的结论。

六、摊还代价：为什么还是 $O(1)$

这和 3.2 节 List<T> 的扩容是同一个道理。

从容量 16 开始倍增，插入 $n$ 个元素，各次扩容要重新哈希的元素数构成一个等比数列：

$$16 + 32 + 64 + \cdots + \frac{n}{2} + n < 2n$$

等比数列的和小于最后一项的 2 倍，所以总的重新哈希量小于 $2n$，摊还到每次插入就是 $O(1)$。

实测验证（插入 100 万个元素，初始容量 16）：

  插入 1,000,000 个元素（初始容量 16）：
    总耗时        : 363.6 ms
    扩容次数      : 17
    最终容量      : 2,097,152
    累计重新哈希  : 1,572,852 个元素
    平均每个元素重新哈希 1.57 次

"平均每个元素重新哈希 1.57 次" —— 确实小于 2，和 $2n$ 的上界吻合 ✓

注意最终容量是 2,097,152（≈ 2^21），而元素只有 100 万 —— 因为容量翻倍是"跳跃式"的。这也说明哈希表通常会浪费 25%～50% 的空间。

七、预分配容量的收益

既然扩容要重新哈希，那"提前告诉它要装多少"就能完全避免这笔开销：

  不预分配（从容量 16 开始）:    369.8 ms   扩容 17 次，重哈希    1,572,852 个
  预分配（容量 2,000,000）  :    178.2 ms   扩容  0 次，重哈希            0 个
  预分配快 2.07 倍

一行改动，快 2.07 倍：

var dict = new Dictionary<string, Order>();                    // 不预分配
var dict = new Dictionary<string, Order>(expectedCount * 2);   // 预分配（注意留出负载因子余量）

注意乘 2：因为默认的扩容阈值是 0.75 左右，所以要按元素数量的 1.3～2 倍来预分配，才能保证不触发扩容。

和 3.2 节 List<T> 的结论完全一致：知道规模就预分配，是最省事、收益最明确的一条优化。

八、补充：Knuth 的探测公式

如果想要精确的数字，可以用 Knuth 在《计算机程序设计艺术》里给出的线性探测期望探测次数公式：

情况	期望探测次数
成功查找	$\dfrac{1}{2}\left(1 + \dfrac{1}{1-\alpha}\right)$
失败查找	$\dfrac{1}{2}\left(1 + \dfrac{1}{(1-\alpha)^2}\right)$

实测和理论对照（本节的表格）：负载 0.9 时理论成功查找是 5.50，实测 5.53 —— 吻合得非常好。

注意分母里的 $(1-\alpha)$：当 $\alpha \to 1$ 时，这个式子会趋向无穷大。

这就是"悬崖"的数学解释 —— 它不是"变慢一点"，而是在数学上趋于无穷。

所以"负载因子不能太高"不是经验之谈，而是有严格数学依据的。

九、练习

练习 6.3.1（计算）用 Knuth 的公式计算下面两种情况下的期望探测次数： (a) $\alpha = 0.5$ 时的成功查找和失败查找 (b) $\alpha = 0.9$ 时的成功查找和失败查找 (c) 从 (a) 到 (b)，负载因子涨了多少倍？探测次数涨了多少倍？

练习 6.3.2（容量规划）你要用一个 Dictionary<string, int> 存 100 万条记录。 (a) 如果不预分配，大约会扩容多少次？ (b) 如果预分配，容量应该设多少？为什么不是正好 100 万？ (c) 预估一下这个字典大约占多少内存（假设键平均 20 个字符）。

练习 6.3.3（判断）判断对错并说明理由： (a) 扩容就是把数组变大，然后把元素原样复制过去。 (b) 负载因子越低越好。 (c) 哈希表的插入是严格 $O(1)$ 的。

练习 6.3.4（工程判断）一个服务用一个哈希表做缓存，运行一段时间后发现：

内存占用持续增长
平均查找耗时逐渐变大
重启服务后恢复正常请分析可能的原因，并给出排查方向。

练习 6.3.5（挑战·渐进式再哈希）普通扩容有一个问题：扩容的那一次操作会卡住几百毫秒（要重新哈希所有元素）。对于延迟敏感的系统（比如游戏服务器、高频交易），这个"毛刺"是不可接受的。请设计一个方案，把扩容的代价摊到每一次操作上，让它不产生明显的停顿。（提示：不要"一次性搬完"，而是"每次操作顺便搬一点"。）

十、练习答案

6.3.1

(a) $\alpha = 0.5$：

成功查找：$\frac{1}{2}\left(1 + \frac{1}{1-0.5}\right) = \frac{1}{2}(1 + 2) = 1.5$
失败查找：$\frac{1}{2}\left(1 + \frac{1}{(1-0.5)^2}\right) = \frac{1}{2}(1 + 4) = 2.5$

(b) $\alpha = 0.9$：

成功查找：$\frac{1}{2}\left(1 + \frac{1}{0.1}\right) = \frac{1}{2}(11) = 5.5$
失败查找：$\frac{1}{2}\left(1 + \frac{1}{0.01}\right) = \frac{1}{2}(101) = 50.5$

(c) 负载因子涨了 $\frac{0.9}{0.5} = 1.8$ 倍。探测次数：

成功查找：$\frac{5.5}{1.5} = 3.67$ 倍
失败查找：$\frac{50.5}{2.5} = 20.2$ 倍

负载因子涨 1.8 倍，失败查找却涨了 20 倍。 这就是"爆炸性增长" —— 因为公式里是 $(1-\alpha)^2$。

这也是为什么工程上要把负载因子控制在 0.75 以下：给曲线留出"还没进入陡峭区"的余量。

6.3.2

(a) 从初始容量开始倍增，直到能装下 100 万。初始容量通常是 3 或 7（.NET 用的是质数序列），假设从 3 开始：

$3 \to 7 \to 17 \to 37 \to \cdots \to 2{,}000{,}000$ 左右，大约 17～20 次扩容。

（和本节实测的"100 万次插入扩容 17 次"一致。）

(b) 应该设 130 万～200 万。

为什么不能正好 100 万？ 因为 Dictionary 有一个负载因子阈值（约 0.72）。如果你给容量 100 万，那么：

插到第 72 万个左右时，实际负载因子就达到阈值了
第 72 万次插入会触发扩容 —— 白预分配了

推荐公式：

$$\text{容量} = \left\lceil \frac{\text{预期元素数}}{0.7} \right\rceil$$

100 万条 → 约 143 万。

(c) 粗略估算：

组成	计算	大小
桶数组（int 下标）	143 万 × 4 字节	约 5.7 MB
条目数组（键引用 + 值 + 哈希码）	143 万 × 约 16 字节	约 23 MB
字符串对象本身	100 万 × (20 字符 × 2 字节 + 对象头 24 字节)	约 64 MB
字符串内容	已在上面计入	—
合计		约 92 MB

关键洞察：哈希表本身的开销（约 29 MB）远小于它存的字符串对象（约 64 MB）。

这个例子说明：优化内存时，先看清"大头在哪"。很多人会去纠结"要不要把 int 换成 short"，却忽略了真正占内存的是那 100 万个字符串对象。

如果要省内存：考虑用 int 键代替字符串键（比如把用户 ID 从字符串改成整数），能省下几十 MB。

6.3.3

(a) 错，而且这是本节的重点。 扩容后容量变了，所以 hash % capacity 的结果全变了 —— 每个元素都要重新计算下标再放到新位置。

这就是"再哈希"（Rehash）这个名字的由来。 它不是"复制"，而是"重新分配"。

一个有意思的推论：扩容后元素的相对位置完全被打乱了。所以哈希表的遍历顺序在扩容后可能发生变化 —— 这正是 6.4 节要讲的"顺序不可依赖"。
(b) 错。 负载因子低意味着大量空闲空间被浪费。

负载 0.1 时，性能确实接近最优（探测 1.06 次 vs 0.5 时的 1.50 次），但内存浪费了 10 倍。

0.75 左右是"性能"和"内存"的平衡点 —— 三种主流实现都选在这个区间，说明这个经验值是有道理的。
(c) 错。 精确说法是：
- 平均 $O(1)$（且负载因子有界）
- 最坏 $O(n)$（所有键冲突到一个桶，或者正好触发扩容） >
  
  工程上的含义：如果对单次延迟有硬性要求（比如游戏服务器要求每帧 16ms 内完成所有逻辑），那么撞上一次扩容就可能造成卡顿 —— 解法见练习 6.3.5。

6.3.4

最可能的原因：缓存里的"墓碑"或"已删除元素"在不断累积。

具体分析：

现象	可能的原因
内存持续增长	① 缓存的元素根本没被淘汰（缺淘汰机制）② 键对象本身很大但没有释放
查找逐渐变慢	① 负载因子持续上升（元素越积越多但不扩容）② 大量墓碑导致探测链变长 ③ 哈希退化（键分布有规律）
重启后恢复正常	说明是"运行过程中累积的状态"，而不是代码本身的 bug

排查方向（按优先级）：

检查缓存有没有淘汰机制。 如果是"只进不出"的缓存，那内存必然会涨到 OOM。应该用 LRU（最近最少使用）之类的策略，或者设一个容量上限。
检查是否有"删除后残留"。 大量删除 + 插入会让开放寻址的墓碑累积。.NET 的 Dictionary 在墓碑过多时会自动重整，但如果你自己实现或用的是其他结构，需要手动处理。
检查键的分布。 如果键有规律（比如都是"订单-2024-0000001"这种递增格式），而哈希函数又不够好，就可能发生聚集。用 Dictionary 时这通常不是问题（.NET 的字符串哈希已经足够好），但自定义键类型要注意。
打点监控。 在生产环境暴露"缓存元素数""平均查找耗时"这两个指标，比事后排查有效得多。

一个容易被忽略的点：如果键是长字符串，每次查找都要遍历整个字符串算哈希。缓存 100 万个 1KB 长的键，每次查找光算哈希就要读 1KB 内存。

这时的优化方向不是"换数据结构"，而是"换键" —— 比如存键的哈希值（或者前 16 个字符）当键，冲突时再回表比对。

6.3.5

方案：渐进式再哈希（Incremental Rehashing）。

核心思路：不要"一次性搬完"，而是"每次操作顺便搬一点"。

具体做法： 同时维护两个表（旧表和新表），然后：

时机	动作
开始扩容	分配新表（容量翻倍），但不搬运任何元素。把状态标记为"正在迁移中"
每次插入	写入新表，同时从旧表搬 k 个元素到新表
每次查找	先查新表，再查旧表（因为元素可能还在旧表里）
每次删除	两个表都尝试删除
旧表搬空后	丢弃旧表，回到"单表"状态

实测效果： 设每次操作搬 $k = 2$ 个元素，那么：

单次操作的最坏代价：原来的 $O(n)$（一次性搬完）→ 变成 $O(k) = O(1)$
总代价不变：还是 $O(n)$，只是被摊到了 $n/k$ 次操作里
总的时间跨度变长：迁移期间内存占用是平时的 2 倍

这就是"把 $O(n)$ 的一次性开销，摊成 $n$ 次 $O(1)$"的经典手法。

Redis 就是这么做的。 它的哈希表（dict）采用渐进式 rehash：每次增删改查都会顺便迁移一部分数据。这样即使字典里有几百万个键，扩容时也不会出现明显的停顿。

代价与注意事项：

内存翻倍。 迁移期间要同时持有两个表 —— 对于大字典，这是显著的开销。
每次操作多一次查找。 迁移期间要查两个表，所以单个操作的耗时反而略微上升。但没有毛刺 —— 这正是延迟敏感系统想要的。
实现复杂度明显上升。 所有操作（增删改查）都要处理"两表并存"的状态，很容易漏掉某个分支。

工程建议：除非你确实遇到了扩容毛刺的问题，否则不要自己实现这个。

应该优先选那些已经内置了渐进式 rehash 的实现（比如 Redis 的字典、Go 的 map）。.NET 的 Dictionary 没有做渐进式 rehash —— 如果它成了你的瓶颈，通常说明你该预分配容量了（本节第七节），而不是该自己造轮子。

十一、常见错误

误区	纠正
认为扩容就是"复制数组"	容量变了，所有元素的下标都变了，必须逐个重新哈希。这就是"再哈希"。
预分配时按元素数设容量	会因为触发负载因子阈值而照样扩容。应该按 `元素数 / 0.7` 来设。
认为负载因子越低越好	低负载因子性能好，但浪费内存。0.75 左右是平衡点。
只看"成功查找"的性能	失败查找贵得多（负载 0.95 时是 168 次 vs 10.6 次，差 16 倍）。缓存未命中是常态的系统尤其要注意。
性能测试不预热	本节的表里，第一次插入是 342 微秒，其余都是 0.1 微秒 —— 那是 JIT 编译开销，不是算法开销。
认为哈希表插入是严格 $O(1)$	是摊还 $O(1)$。撞上扩容的那一次是实打实的 $O(n)$。

十二、本节总结

负载因子 $\alpha = \frac{\text{元素数}}{\text{桶数}}$，是哈希表最重要的参数。
实测曲线呈"悬崖"形：$\alpha$ 从 0.8 涨到 0.95（涨 19%），失败查找的探测次数从 12.97 涨到 168.27（涨 13 倍）。
Knuth 公式（$\frac{1}{2}(1 + \frac{1}{(1-\alpha)^2})$）解释了悬崖的数学根源 —— $\alpha \to 1$ 时趋于无穷。实测与理论吻合。
链地址法对负载因子线性敏感，开放寻址是指数敏感。所以选型要看"能把负载因子控制到多低"。
扩容 = 分配新表 + 全部元素重新哈希。因为 hash % capacity 的结果全变了。
摊还代价仍是 $O(1)$：重新哈希总量构成等比数列，小于 $2n$。实测 100 万次插入重新哈希 157 万次（平均 1.57 次/元素）。
预分配容量快 2.07 倍，且只需一行改动。按 元素数 / 0.7 来设容量。
渐进式再哈希能把扩容毛刺从 $O(n)$ 摊成每次 $O(1)$ —— Redis 和 Go 的 map 都用了。但实现复杂，优先考虑预分配。

下一节衔接：到这里，哈希表的原理已经讲透了。最后一节回到工程实践 —— 你在用 Dictionary<TKey, TValue> 时最容易踩的那些坑：为什么遍历顺序不可依赖？为什么重写了 Equals 就必须重写 GetHashCode？为什么用可变对象当键会"丢数据"？以及并发场景该怎么办。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "6.3",
  "title": "负载因子、扩容与再哈希",
  "covered": [
    "负载因子的定义与工程阈值（0.72/0.75/0.67）",
    "负载因子-探测次数实测曲线与「悬崖效应」",
    "实测值与 Knuth 公式的逐项吻合",
    "成功查找 vs 失败查找的代价差异（0.95 时 10 次 vs 200 次）",
    "链地址法线性敏感 vs 开放寻址指数敏感",
    "扩容与再哈希的完整实现与逐步实测",
    "摊还 O(1) 的等比数列论证（实测平均 1.57 次/元素）",
    "预分配容量 2.07 倍的收益与容量计算公式",
    "渐进式再哈希（Redis/Go map）的原理与代价"
  ],
  "unresolved": [
    "Dictionary 的具体工程用法留到 6.4",
    "红黑树（Java 桶树化）留到第 10 章后",
    "LRU 缓存的完整实现超出本章范围"
  ],
  "canonical_terms": {
    "负载因子": "元素个数除以桶个数，衡量哈希表的填满程度",
    "扩容": "容量不足时申请更大的数组",
    "再哈希": "扩容后按新容量重新计算所有元素的下标并搬迁",
    "摊还代价": "一系列操作的总代价除以操作次数"
  },
  "symbols_units": {
    "α": "负载因子"
  },
  "assumptions": [
    "读者已掌握 6.2 的两种冲突解决方式与 3.2 的摊还分析",
    "读者了解 JIT 预热对性能测试的影响"
  ],
  "word_count_actual": 2820,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch06/Sec63/",
    "8 组负载因子的实测探测次数与 Knuth 理论值逐项核对",
    "扩容统计：17 次扩容、累计重哈希 1572852、平均 1.57 次/元素",
    "练习 6.3.1 的公式计算已手工验算（1.5/2.5/5.5/50.5）",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "扩容演示的首行耗时（342us）来自 JIT 编译而非算法本身，已在正文明确标注并提示性能测试必须预热"
  ],
  "next": "6.4 C# Dictionary 的内部与工程用法"
}

6.3　负载因子、扩容与再哈希