load factor · 摊还 · 尾延迟

负载因子与成倍扩容

前三页的分析都假定表长 $m$ 固定。真实的表装到一定程度必须换一张更大的，因为两类实现的代价都是负载因子 $\alpha = n/m$ 的函数：链地址法的未命中比较次数就是 $\alpha$ ，开放寻址在 $\alpha \to 1$ 时探测次数发散。

换表意味着把已有的 $n$ 个 key 全部重新算下标、搬进新数组——旧下标在新表里没有意义，因为 $h \bmod m$ 随 $m$ 变。这一步叫 rehash，它是哈希表唯一一处代价与 $n$ 成正比的操作。本页的问题是：什么时候换、换多大、代价怎么算。

1 · 阈值那一侧的取舍

扩容阈值定在哪，是一道空间换时间的题。

$\alpha$ 取小则槽多、探测短，但空槽占的内存被白付。开放寻址下空槽占一整个 entry；链地址法下空槽只是一个指针，所以它的阈值可以定得高一些——Redis 的 dict 用 $\alpha \ge 1$ ，Java 的 HashMap 用 0.75，Go 的 map 用 6.5（它每个桶装 8 个 key，口径不同），Python 的 dict 用 2/3，Rust 的 hashbrown 用 7/8。

数量级差别在开放寻址那一侧最明显： $\alpha$ 从 0.75 提到 0.875，省下 14% 的内存，而 linear probing 的未命中期望探测次数从 8.5 涨到 32.5。这就是为什么用开放寻址的实现普遍把阈值压在 0.875 以下，而链地址法可以放宽到 1 以上。

2 · 为什么必须成倍

假设每次扩容只加固定量 $c$ 个槽。那么装到 $n$ 个 key 要扩容 $n/c$ 次，第 $i$ 次搬 $ic$ 个 key，总搬迁量是 $\sum_{i} ic = \Theta(n^2/c)$ ——摊还到每次插入是 $\Theta(n)$ ，哈希表的常数时间承诺当场作废。

按倍数 $f$ 扩容则不然。设最后一次扩容发生在容量 $m_K$ ，它搬走了约 $n/f$ 个 key；再往前一次搬 $n/f^2$ ，依此类推。总搬迁量是一个公比 $1/f$ 的几何级数：

$\displaystyle \text{总搬迁量} \approx \frac{n}{f} \left(1 + \frac{1}{f} + \frac{1}{f^2} + \cdots \right) = \frac{n}{f} \cdot \frac{f}{f-1} = \frac{n}{f-1}$

加上 $n$ 次插入本身的写入，摊还每次插入约 $1 + 1/(f-1)$ 次数组写入： $f = 2$ 时 2 次， $f = 1.5$ 时 3 次， $f = 1.25$ 时 5 次， $f = 1.05$ 时 21 次。

图 2-1 · 六个扩容倍数在时间（摊还写入）与空间（末容量与 n 之比）两侧的取舍，下方另附扩容阈值那一侧的对照。可改插入次数与阈值。

实测值系统性地高于那个闭式解： $f = 2$ 、 $n = 100000$ 时是 2.97 而非 2.00， $f = 1.05$ 时 21.76 而非 21.00。两个原因叠在一起。其一，初始容量只有 4，头几次扩容经 Math.ceil 之后实际倍数被抬高（4 到 8 是 2 倍，但 $f = 1.05$ 时 4 到 5 是 1.25 倍）。其二，也是更主要的，这个比值取决于 $n$ 落在扩容周期的哪个位置： $n = 100000$ 时末容量是 262144，比值 2.62，说明刚扩完容不久，分母 $n$ 还没长上来， $\frac{\text{总写入}}{n}$ 于是偏大。把 $n$ 换成 1000 再看， $f = 2$ 的实测是 2.53——同一个式子，换个采样点就差 17%。闭式解描述的是整个周期的平均，不是任意一点的值。

3 · 摊还常数与尾延迟

摊还分析给出的是总量的界，它对单次操作的延迟一句话也没说。

图 3-1 · 每次插入的数组写入次数，纵轴取对数，红柱是触发扩容的那一次。下方给出代价的分位数与容量阶梯。可改扩容倍数、阈值、插入次数与初始容量。

$f = 2$ 、 $\alpha$ 阈值 0.75、插入 10 万次的实测分布：

分位	单次数组写入
p50	1
p99	1
p99.99	193
最贵一次	98305

摊还是 2.97 次，最贵的一次是 98305 次——相差三万三千倍。这一次发生在第 98305 次插入，容量从 131072 翻到 262144，把已有的 98304 个 key 全部重算下标搬过去。

p50 与 p99 都是 1，因为 10 万次插入里只有 16 次触发扩容，尖峰在百分位上几乎不可见；要到 p99.99 才第一次冒头（193 次写入，对应容量还小的那几次扩容）。平均值和 p99 都看不见这个问题，只有 max 看得见。 一个 QPS 报表漂亮的服务照样可能有几个请求慢了几十毫秒，而慢的原因就在这张表上。

对策分两类。第一类是绕开：如果规模事先知道，直接预分配够大的容量，扩容一次都不发生（图 3-1 里把初始容量调到 1024、插入 1000 次即可看到）。Go 的 make(map[K]V, hint)、Java 的 new HashMap<>(expected)、Rust 的 with_capacity 都是这个用途。第二类是把这一坨代价切碎——不减少总搬迁量，只把它摊到时间轴上，这就是渐进式 rehash 的做法。

4 · 缩容是另一道题

扩容的镜像操作不对称：删除到一定程度要不要缩容？

朴素做法「 $\alpha$ 低于某阈值就减半」有一个坑：如果阈值定得和扩容阈值太近，一串「插入、删除、插入、删除」就会在边界上反复触发扩容与缩容，每次都搬全表。这叫 thrashing。避免它的办法是留一段滞后区间——扩容看 0.75，缩容看 0.1，中间那一大段什么都不做。

Redis 的 dict 缩容阈值是 $\alpha < 0.1$ ，且缩容和扩容一样走渐进式搬迁。Java 的 HashMap 干脆不缩容：remove 从不减小 table 的长度，一个曾经装过一百万条的 map 清空后仍占着一百万个槽的数组，只有整个对象被回收时才还给堆。这不是疏漏而是选择——省掉了缩容判据、thrashing 防护与相关的并发问题，代价是使用方得知道「大 map 用完要丢掉整个对象，不要 clear() 后复用」。

5 · 参考文献

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., §17.4 动态表). MIT Press.
Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3 (2nd ed., §6.4). Addison-Wesley.
Redis. src/dict.c 中的 dictExpandIfNeeded 与 dictResize（HASHTABLE_MIN_FILL 一节）。