为什么哈希表通过加倍来调整大小？

Question

在线检查java和google搜索哈希表代码示例,似乎通过加倍来完成表的大小调整.
但是大多数教科书都说桌子的最佳尺寸是素数.
所以我的问题是:
加倍的方法是因为:

1. 它易于实现,或
2. 找到素数太低效了(但我认为找到下一个素n+=2数并使用模数测试素数是O(loglogN)这很便宜)
3. 或者这是我的误解,只有某些散列表变体只需要主表大小？

更新:
教科书中使用素数的方式是某些属性工作所必需的(例如,二次探测需要一个素数表来证明,例如,如果一个表不是完整的项目X将被插入).
发布为重复的链接一般要求增加任何数字,例如25%或下一个素数,并且答案接受说明我们加倍以保持调整大小操作"罕见",因此我们可以保证摊销时间.
这并没有回答这样一个问题:使用一个表格大小是素数并使用素数来调整大小甚至大于两倍.因此,我们的想法是保持主要大小的属性考虑调整大小开销

Answer 1

问:但大多数教科书都说桌子的最佳尺寸是素数.

关于大小素数:

什么是大小的素数,它取决于你选择的碰撞解决算法.一些算法需要素数表大小(双重散列,二次散列),其他算法则不需要,并且它们可以从2的幂的表大小中受益,因为它允许非常便宜的模运算.但是,当最接近的"可用表大小"相差2倍时,哈希表的内存使用可能不可靠.因此,即使使用线性散列或单独链接,您也可以选择2大小的非幂.在这种情况下,反过来,值得选择特定的素数大小,因为:

如果你选择素数表大小(因为算法需要这个,或者因为你不满意2的幂大小所暗示的内存使用不可靠性),表槽计算(按表大小为模)可以与散列相结合.请参阅此答案了解更多信息

当散列函数分布不好(来自Neil Coffey的答案)时,表2的幂大小是不可取的,这是不切实际的,因为即使你有糟糕的散列函数,雪崩它仍然使用2的幂大小将是切换到素数表大小的速度更快,因为单个积分除法在现代CPU上仍然较慢,即多次复杂和移位操作,需要良好的雪崩函数,例如来自MurmurHash3.

问:老实说,如果你真的推荐素数,我会迷失一点.似乎它取决于哈希表变体和哈希函数的质量？

1. 散列函数的质量无关紧要,你总是可以通过MurMur3平衡来"改进"散列函数,这比从2的表格大小切换到素数表大小便宜,见上文.

2. 我建议选择素数大小,使用QHash或二次散列算法(不相同),只有当您需要对哈希表负载因子和可预测的高实际负载进行精确控制时.对于2的幂表大小,最小调整大小因子是2,并且通常我们不能保证哈希表将具有任何高于0.5的实际负载因子.看到这个答案.
   
   否则,我建议使用带有线性探测功能的2-power大小的哈希表.

问:加倍的方法是因为:
它易于实现,或者

基本上,在许多情况下,是的.看到关于负载系数的这个大答案:

负载因子不是哈希表数据结构的重要部分 - 它是为动态系统定义行为规则的方法(增长/收缩哈希表是一个动态系统).

此外,在我看来,95%的现代哈希表情况都是这种方式过度简化,动态系统表现不理想.

什么是倍增？这只是最简单的调整大小策略.该策略可能是任意复杂的,在您的用例中表现最佳.它可以考虑当前的哈希表大小,增长强度(自上次调整大小以来完成了多少操作)等等.没有人禁止你实现这样的自定义大小调整逻辑.

问:找到素数太低效了(但我认为找到下一个素数超过n + = 2并使用模数测试素数是O(loglogN)这很便宜)

有一个很好的做法是预先计算一些主要哈希表大小的子集,在运行时使用二进制搜索在它们之间进行选择.请参阅列表双哈希容量和解释,QHash容量.或者,即使使用直接查找,也非常快.

问:或者这是我的误解,只有某些散列表变体只需要主表大小？

是的,只有某些类型需要,见上文.