为什么哈希表通过加倍来resize？
在线检查java和google搜索哈希表代码示例，似乎通过加倍来完成表的大小调整。
但是大多数教科书都说桌子的最佳尺寸是素数。
所以我的问题是：
加倍的方法是因为：
- 它易于实现，或
- 找到素数太低效了（但我认为找到下一个素数超过
n+=2并使用模数测试素数是O（loglogN）这很便宜） - 或者这是我的误解，只有某些散列表变体只需要主表大小？
更新：
某些属性需要使用素数在教科书中呈现的方式（例如，二次探测需要一个素数表来certificate，例如，如果一个表不是完整的项目X将被插入）。
发布为重复的链接一般要求增加任何数字，例如25％或下一个素数，并且接受的答案表明我们加倍以使resize操作“罕见”，因此我们可以保证摊销时间。
这并没有回答这样一个问题：使用一个表格大小是素数并且使用素数来resize甚至大于两倍。 因此，我们的想法是保持主要大小的属性考虑resize开销
问：但大多数教科书都说桌子的最佳尺寸是素数。
关于大小素数：
什么是大小的素数，它取决于你选择的碰撞分辨率算法。 一些算法需要素数表大小（双重散列，二次散列），其他算法不需要，并且它们可以从2的幂表大小中受益，因为它允许非常便宜的模运算。 但是，当最接近的“可用表大小”相差2倍时，哈希表的内存使用可能不可靠。 因此，即使使用线性散列或单独链接，您也可以选择2大小的非幂。 在这种情况下，反过来，值得选择特定的素数，因为：
如果你选择素数表大小（因为算法需要这个，或者因为你对2的幂大小暗示的内存使用不可靠性不满意），表格槽计算（按表大小模数）可以与散列相结合。 请参阅此答案了解更多信息
当哈希函数分布不好（来自Neil Coffey的答案）时，表2的幂大小是不可取的，这是不切实际的，因为即使你有糟糕的哈希函数，雪崩它仍然使用2的幂大小将是切换到素数表大小的速度更快，因为单个积分除法在现代CPU上仍然较慢，因为良好的雪崩函数需要多个多重复用和移位操作，例如来自MurmurHash3。
问：老实说，如果你真的推荐素数，我会迷失一点。 似乎它取决于哈希表变体和哈希函数的质量？
-
哈希函数的质量无关紧要，你总是可以通过MurMur3平衡来“改进”哈希函数，这比从2表格大小切换到素数表大小便宜，见上文。
-
我建议选择素数大小，使用QHash或二次散列算法（ 不相同 ）， 只有当您需要对哈希表负载因子和可预测的高实际负载进行 精确控制 时 。 对于2的幂表大小，最小resize因子是2，并且通常我们不能保证散列表将具有高于0.5的实际负载因子。 看到这个答案。
否则，我建议使用带有线性探测function的2-power大小哈希表。
问：加倍的方法是因为：
它易于实现，或
基本上，在许多情况下，是的。 看到关于负载系数的这个大答案 ：
负载因子不是哈希表数据结构的重要部分 – 它是为动态系统定义行为规则的方法（增长/收缩哈希表是一个动态系统）。
此外，在我看来，在95％的现代哈希表案例中，这种方式过于简化，动态系统表现不理想。
什么是倍增 ？ 这只是最简单的resize策略。 该策略可能是任意复杂的，在您的用例中表现最佳。 它可以考虑当前的哈希表大小，增长强度（自上次resize以来完成了多少操作）等等。没有人禁止你实现这样的自定义大小调整逻辑。
问：找到素数太低效了（但我认为找到下一个素数超过n + = 2并使用模数测试素数是O（loglogN）这很便宜）
有一个很好的做法是预先计算一些主要哈希表大小的子集，在运行时使用二进制搜索在它们之间进行选择。 请参阅列表双哈希容量和解释 ， QHash容量 。 或者，即使使用直接查找 ，也非常快。
问：或者这是我的误解，只有某些散列表变体只需要主表大小？
是的，只有某些类型需要，见上文。
Java HashMap（ java.util.HashMap ）链接链表中的桶冲突（或[从JDK8]树开始，具体取决于bin的大小和溢出）。
因此，关于二次探测function的理论不适用。 似乎消息“使用散列表的素数大小”已经脱离了多年来适用的情况……
使用2的幂具有将表格条目的哈希值减少的优点（如其他答案所述）可以通过比特掩码来实现。 整数除法相对昂贵，在高性能情况下，这可能有所帮助。
我将观察到“重新分配碰撞链时，重新划分对于能够为2的幂的表来说是一个很大的力量”。
请注意，当使用两次重新散列的权限时，根据哈希码的“下一个”位，在两个桶之间“拆分”每个桶。 也就是说，如果哈希表有256个桶，那么使用哈希值重新散列的最低8位根据第9位拆分每个冲突链，并且保留在同一个桶B（第9位为0）或转到桶B + 256（第9位为1）。 这种分裂可以保留/利用铲斗处理方法。 例如， java.util.HashMap保持以插入的相反顺序排序的小桶，然后将它们分成遵循该顺序的两个子结构。 它将大桶保存在按哈希码排序的二叉树中，并类似地拆分树以保留该顺序。
注意：这些技巧直到JDK8才实现。
（我很确定） Java.util.HashMap只有大小（永不下降）。 但是将哈希表减半使其加倍也有类似的效率。
这种策略的一个“缺点”是没有明确要求Object实现者确保散列码的低阶位分布良好。 完全有效的哈希码可以在整体上很好地分布，但在其低阶位中分布不佳。 因此，服从hashCode()的一般契约的对象在HashMap实际使用时可能仍然存在！ Java.util.HashMap通过在提供的hashCode()实现上应用额外的散列“spread”来缓解这种情况。 那”传播’真的是快速的原油（16位高位和低位）。
对象implmenters应该知道（如果还没有）他们的哈希码（或缺少哈希码）中的偏差会对使用哈希的数据结构的性能产生重大影响。
为了记录，我将此分析基于此源的副本：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java