负载因子与扩容

复习

• 哈希函数与哈希表：由键直接算出位置
• 拉链法：冲突元素串成链表
• 开放寻址：在表内继续寻找空位
• 摊还分析：偶尔昂贵的操作会被摊平

TL;DR

• 负载因子 = 已存元素数 除以 桶的数量
• 负载因子越高，冲突越多，性能越差
• 超过阈值就扩容，并重新散列已有元素
• 重新散列让扩容的摊还代价保持较低

正文

　　不管是拉链法还是开放寻址，冲突多不多，直接决定哈希表快不快。而冲突的多少，又和一个简单的比值有关——负载因子（load factor）。

一个衡量“挤不挤”的比值

　　负载因子定义为：

负载因子 = 已存元素数 / 桶的数量

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

• 负载因子小：桶多、元素少，冲突少，查找快
• 负载因子大：元素拥挤，冲突频繁，查找变慢

　　不同类型的冲突处理，能容忍的负载因子也不同。拉链法因为可以挂链，通常能撑到接近 1；开放寻址对拥挤更敏感，往往在 0.7 左右就该扩容了。

太挤就扩容

　　当负载因子超过某个阈值时，哈希表就要扩容：

1. 申请一个更大的桶数组（通常是原来的两倍）
2. 把所有已有元素重新计算位置，搬进新表
3. 释放旧表

　　为什么不能直接“照搬”？因为位置是用“键对表长取模”算出来的，表长变了，位置也就变了。所以每个元素都得重新用哈希函数算一遍该放哪，这个过程叫重新散列（rehashing）。

为什么这样也能摊还到 O(1)

　　rehash 一次要搬动全部元素，是 O(n)，看着又贵又吓人。

　　但和动态数组扩容的道理一样：扩容之后，要再插入差不多同样多的新元素，才会再次装满。把这次昂贵的搬家，摊到中间那许多次廉价插入上，平均每次仍是 O(1)。

　　所以哈希表的 O(1)，背后同样有摊还分析在支撑。一处昂贵、多处廉价，平均下来依旧划算。

　　到这里，哈希这块的“零件”就齐了。最后再用它拼出两个最常用的抽象：集合和映射。

思考题 1

　　为什么负载因子太高，会让哈希表变慢？

思考题 2

　　扩容时为什么要“重新散列”，而不能把元素直接搬到同样的位置？

小结

知识点

• 负载因子衡量哈希表的拥挤程度
• 负载因子越高，冲突越多、性能越差
• 超过阈值应扩容并重新散列
• 重新散列虽昂贵，但摊还代价较低

参考资料

1. Wikipedia(zh)：哈希表：负载因子与扩容机制
2. Wikipedia(zh)：摊还分析：解释扩容的平均代价

思考题答案（仅供参考）

思考题 1

　　因为负载因子高意味着桶里元素拥挤、冲突频繁。拉链法的链会变长，开放寻址要探测更久，查找、插入都从接近 O(1) 退化，最坏甚至到 O(n)。所以需要控制负载因子。

思考题 2

　　因为元素的位置是由哈希函数结合表长算出的。表长改变后，同一个键算出的位置通常也变了。若直接把元素搬到原下标，就会破坏哈希表“由键算位置”的规则，后续查找就会失败。所以必须按新表长重新计算每个元素的位置。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪