algorithm - 为什么哈希表扩展通常通过将大小加倍来完成？

Question

我对哈希表做了一些研究，我一直在运行经验法则，当有一定数量的条目时(最大值或通过 75% 之类的负载因子)，哈希表应该被扩展.

几乎总是，建议将哈希表的大小加倍(或加倍加 1，即 2n+1)。但是，我一直没能为此找到充分的理由。

为什么要将大小加倍，而不是将其增加 25%，或者将其增加到下一个素数或下 k 个素数(例如，3)的大小？

我已经知道，选择素数作为初始哈希表大小通常是个好主意，至少如果您的哈希函数使用模数(例如通用哈希)。我知道这就是为什么通常建议使用 2n+1 而不是 2n(例如 http://www.concentric.net/~Ttwang/tech/hashsize.htm )

但是，正如我所说，我还没有看到任何真正的解释，说明为什么加倍或加倍加一实际上是一个不错的选择，而不是选择新哈希表大小的其他方法。

(是的，我已经阅读了关于哈希表的维基百科文章:) http://en.wikipedia.org/wiki/Hash_table

Answer 1

例如，如果调整大小是按恒定增量进行的，则哈希表不能声明“摊销的恒定时间插入”。在那种情况下，调整大小的成本(随着哈希表的大小而增长)将使一次插入的成本与要插入的元素总数成线性关系。由于随着表的大小调整大小变得越来越昂贵，因此必须“越来越少地”发生以保持插入的摊销成本不变。

大多数实现允许平均桶占用增长到一个边界，直到在调整大小之前预先固定(0.5 到 3 之间的任何值，这些都是可接受的值)。按照这个约定，在调整大小后，平均存储桶占用量变为该范围的一半。通过加倍调整大小使平均桶占用保持在宽度 *2 的范围内。

子注:由于统计聚类，如果您希望许多桶最多有一个元素，则必须将平均桶占用率低至 0.5(忽略缓存大小的复杂影响的最大查找速度)，或者如果您想要最少数量的空桶(对应于浪费的空间)，则可高达 3。