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

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

关于大小素数：

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

  如果你选择素数表大小（因为算法需要这个，或者因为你对2的幂大小暗示的内存使用不可靠性不满意），表格槽计算（按表大小模数）可以与散列相结合。看到 这个答案 更多。

当哈希函数分布不好（来自Neil Coffey的答案）时，表2的幂大小是不可取的，这是不切实际的，因为即使你有糟糕的哈希函数，雪崩它仍然使用2的幂大小将是切换到主表大小的速度更快，因为在现代CPU上单个积分除法仍然较慢，因为良好的雪崩函数所需的多个多重复用和移位操作，例如。 G。来自MurmurHash3。

问： 另外说实话，如果你真的推荐素数，我会迷失一点。似乎它取决于哈希表变体和哈希函数的质量？

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

2. 我建议选择素数大小，使用QHash或二次散列算法（不一样） 只要 什么时候需要 精确控制哈希表加载因子 和 可预测的高实际负载。对于2的幂表大小，最小调整大小因子是2，并且通常我们不能保证散列表将具有高于0.5的实际负载因子。 看到这个答案。
   
   否则，我建议使用带有线性探测功能的2-power大小哈希表。

问： 加倍的方法是因为：
  它易于实现，或

基本上，在许多情况下，是的。 看到 关于载荷因子的这个大答案：

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

  此外，在我看来，在95％的现代哈希表案例中，这种方式过于简化，动态系统表现不理想。

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

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

有一个很好的做法是预先计算一些主要哈希表大小的子集，在运行时使用二进制搜索在它们之间进行选择。看到 列表双哈希容量和解释， QHash能力。或者，甚至使用 直接查找，这是非常快的。

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

是的，只有某些类型需要，见上文。