为什么散列表扩展通常是通过加倍大小来完成的？
我已经做了一些关于散列表的研究，并且按照经验法则运行，当有一定数量的条目时（无论是最大值还是通过75％的加载因子），散列表都应该被扩展。
几乎总是build议将散列表的大小加倍（或加1，即2n + 1）。 但是，我一直没有find一个很好的理由。
为什么要扩大一倍，而不是增加25％，或者增加到下一个素数或下一个素数（如三个）的大小？
我已经知道，select一个初始哈希表大小是一个好主意，至less如果你的哈希函数使用通用哈希等模数。 而且我知道这就是为什么通常build议做2n + 1而不是2n（例如http://www.concentric.net/~Ttwang/tech/hashsize.htm ）
然而，正如我所说，我还没有看到任何真正的解释，为什么加倍或加一加实际上是一个不错的select，而不是其他一些方法为新的散列表select一个大小。
（是的，我读过哈希表维基百科的文章:) http://en.wikipedia.org/wiki/Hash_table
如果例如resize是一个固定的增量，那么哈希表就不能声明“分期偿还时间插入”。 在这种情况下，resize的成本（与散列表的大小一起增长）将使得一个插入的成本在要插入的元素总数中为线性。 由于resize随着表格的大小变得越来越昂贵，为了保持插入的成本不变，必须“越来越less”地进行调整。
在resize（0.5到3之间的任何值，这些都是可接受的值）之前，大多数实现允许平均存储桶占用增长到预先确定的界限。 按照这个惯例，在调整平均水桶占用量之后，就变成了这个水平的一半。 通过加倍resize，将平均桶占用率保持在宽度* 2的范围内。
子logging：由于统计聚类，如果您想要多个存储桶最多只有一个元素（查找忽略高速caching大小的复杂影响的最大速度），则必须将平均存储桶占用率降至0.5， 3如果你想要最小数量的空桶（相当于浪费的空间）。
我曾经在这个网站上看过有关增长策略的非常有趣的讨论，只是找不到它。
虽然2是常用的，但已经certificate它不是最好的价值。 一个经常被引用的问题是，它不能很好地处理分配器scheme（通常分配两个块的功率），因为它总是需要重新分配，而较小的数目实际上可能在同一个块中被重新分配（模拟就地增长）从而更快。
因此，例如，在对邮件列表进行广泛的讨论之后， VC++标准库使用的增长因子为1.5 （理想情况下，如果使用的是首选内存分配策略，应该是黄金数字）。 推理在这里解释。
当然，它应该适应内存分配策略。
在扩展任何types的集合时加倍内存是一种经常使用的策略，用于防止内存碎片，不必经常重新分配。 正如你指出的，可能有理由有一个素数的元素。 在了解您的申请和数据时，您也可以预测元素数量的增长，从而select另一个（更大或更小）增长因子，而不是增加一倍。
在库中find的一般实现就是：一般的实现。 他们必须专注于在各种不同的情况下作出合理的select。 在了解上下文时，几乎总是可以编写一个更专业，更高效的实现。
相同的推理适用于vector / ArrayList实现的两倍，请参阅此答案 。
如果容器容量总是2的幂，那么容量加倍的一个原因是，如果容器容量总是2的乘方，那么不用通用模数来将散列值转换为偏移量，而是可以通过位移来获得相同的结果。 模数是一个缓慢的操作，同样的原因，整数除法是缓慢的。 （整数除法在程序中的任何其他情况下是否是“慢”，当然是与情况有关，但肯定比其他基本整数algorithm慢）。
如果你不知道最终会使用多less个对象 （让我们说N），
通过加倍的空间，你会做logging2 N重新分配最多。
我假设，如果你select一个适当的初始“n”，你增加了几率
2 * n + 1将在随后的重新分配中产生素数。
