我对哈希表做了一些研究，并且我一直遵循经验法则，即当存在一定数量的条目（最大数量或通过负载因子（例如 75%））时，应该扩展哈希表。
几乎总是建议将哈希表的大小加倍（或加倍加 1，即 2n+1）。然而，我一直没能找到一个很好的理由。
为什么要加倍大小，而不是增加 25%，或者增加到下一个素数或下一个 k 个素数（例如，3）的大小？
我已经知道，选择一个质数作为初始哈希表大小通常是一个好主意，至少如果您的哈希函数使用通用哈希等模数的话。我知道这就是为什么通常建议执行 2n+1 而不是 2n （例如，http://www.concentric.net/~Ttwang/tech/hashsize.htm http://www.concentric.net/~Ttwang/tech/hashsize.htm)
然而，正如我所说，我还没有看到任何真正的解释为什么加倍或加倍加一实际上是一个不错的选择，而不是选择新哈希表大小的其他方法。
（是的，我读过有关哈希表的维基百科文章:)http://en.wikipedia.org/wiki/Hash_table http://en.wikipedia.org/wiki/Hash_table
例如，如果调整大小是通过恒定增量进行的，则哈希表不能声明“摊销恒定时间插入”。在这种情况下，调整大小的成本（随着哈希表的大小而增长）将使一次插入的成本与要插入的元素总数成线性关系。由于随着表的大小调整大小变得越来越昂贵，因此必须“越来越少地”进行调整才能保持插入的摊余成本不变。
大多数实现允许平均存储桶占用增长到调整大小之前预先固定的界限（0.5 到 3 之间的任何位置，这些都是可接受的值）。根据此约定，在调整大小后，平均存储桶占用量将变为该范围的一半。通过加倍调整大小可将平均存储桶占用率保持在宽度 *2 的范围内。
小注：由于统计聚类，如果您希望多个存储桶最多有一个元素（查找的最大速度，忽略缓存大小的复杂影响），则必须将平均存储桶占用率低至 0.5，或者高达3 如果您想要最少数量的空桶（对应于浪费的空间）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
