为什么链地址法推荐将负载因子设为1.0？

这个问题问得特别到位！其实链地址法和开放寻址法的负载因子推荐值差异，核心在于两者处理冲突的底层逻辑完全不同，咱们掰开揉碎了说：

先回顾下开放寻址法的0.5-0.7负载因子 #

开放寻址法是在哈希表的数组内部“挤位置”——当发生哈希冲突时，它会通过线性探测、二次探测等方式，在数组里找下一个空闲的空位来存元素。这就导致：

• 当负载因子超过0.7时，数组里的空闲位置已经很少了，找空位的探测次数会急剧增加，平均查找时间会从理想的O(1)快速向O(n)恶化。
• 负载因子控制在0.5-0.7，是为了保证有足够的空闲位置，让探测次数维持在很低的水平，从而保证性能。

链地址法推荐1.0负载因子的核心原因 #

链地址法的结构是数组+链表（或红黑树），每个数组槽位挂着一个独立的链表，冲突的元素都存在对应槽位的链表上。这时候负载因子1.0的意思是平均每个槽位挂1个元素——注意是“平均”，不是每个槽位都刚好1个，就像你说的哈希表大小100时，完全可能出现部分槽位挂多个元素、部分槽位为空的情况，但整体平均下来是1。

为什么这个值是合理的？有这几点：

• 性能代价极低：链地址法的查找成本是“计算哈希找到槽位”+“遍历槽位上的链表”。当负载因子为1.0时，大部分槽位要么是空的，要么只有1个元素，遍历成本几乎可以忽略；就算少数槽位有多个元素，只要哈希函数足够均匀，这些链表的长度也不会太长，整体平均查找时间依然能维持在O(1)级别。
• 内存利用率更高：相比开放寻址法要预留大量空闲位置，链地址法在负载因子1.0时，数组的空间被充分利用，同时链表的额外开销也很小（毕竟大部分链表长度都很短）。
• 扩容成本更低：开放寻址法扩容需要把所有元素重新哈希插入到新数组，而链地址法扩容只需要新建一个更大的数组，把原数组的链表头节点迁移过去（或按需重新哈希元素），操作成本低很多，所以不用太早扩容，等负载因子到1.0左右再扩容是很平衡的选择。

举个直观的例子：哈希表大小100，插入100个元素（负载因子1.0）。如果哈希函数均匀，可能80个槽位各存1个元素，10个槽位空着，剩下10个槽位各存2个元素。这时候查找任意元素，要么直接命中槽位里的元素，要么最多遍历2个元素的链表，速度依然很快。但如果换成开放寻址法，负载因子1.0意味着数组几乎被填满，查找不存在的元素时可能要遍历整个数组，性能会暴跌。

当然，如果负载因子继续上升到2.0甚至更高，平均每个槽位挂2个以上元素，链表遍历的成本才会开始明显上升，这时候就需要考虑扩容了。但1.0确实是一个兼顾性能和内存利用率的最优平衡点。

内容的提问来源于stack exchange，提问作者JozzWhers