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

Question

我已经对哈希表进行了一些研究,并且我一直遵循经验法则,当有一定数量的条目(最大或通过75%的加载因子)时,应该扩展哈希表.

几乎总是,建议是将哈希表的大小加倍(或加倍加1,即2n + 1).但是,我没有找到一个很好的理由.

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

我已经知道,选择一个初始哈希表大小是一个素数通常是一个好主意,至少如果你的哈希函数使用模数,如通用哈希.我知道这就是为什么通常建议做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如果您想要最少数量的空桶(对应于浪费的空间).

Answer 2

我在这个网站上读过关于增长战略的非常有趣的讨论......再也找不到了.

虽然2常用,但已经证明它不是最好的价值.一个经常被引用的问题是它不能很好地处理分配器方案(通常分配两个块的功率),因为它总是需要重新分配,而较小的数字实际上可能在同一个块中重新分配(模拟就地增长)因此更快.

因此,例如,在对邮件列表进行广泛讨论之后,VC++标准库使用增长因子1.5(理想情况下,如果使用首先适合的内存分配策略,则应该是黄金数字).这里解释了推理:

如果任何其他矢量实现使用2以外的增长因子,我会感兴趣,并且我还想知道VC7是使用1.5还是2(因为我这里没有那个编译器).

技术上有理由偏好1.5到2 - 更具体地说,更喜欢小于的值1+sqrt(5)/2.

假设您正在使用第一个适合的内存分配器,并且您逐渐附加到向量.然后每次重新分配时,分配新内存,复制元素,然后释放旧内存.这留下了一个空白,最终能够使用那个记忆会很好.如果向量增长太快,它对于可用内存总是太大.

事实证明,如果增长因素是>= 1+sqrt(5)/2,那么新的记忆将永远对于已经留下的洞来说太大了; 如果是的话< 1+sqrt(5)/2,新的记忆最终会适合.所以1.5小到足以让内存被回收.

当然,如果增长因素是>= 2新记忆对于迄今为止留下的洞来说总是太大了; 如果是的话< 2,新的记忆最终会适合.大概原因(1+sqrt(5))/2是......

• 初始分配是s.
• 第一次调整大小是k*s.
• 第二个调整大小k*k*s,它将适合孔iff k*k*s <= k*s+s,即iffk <= (1+sqrt(5))/2

......这个洞可以尽快回收.

它可以通过储存其先前的大小来生长纤维蛋白.

当然,它应该根据内存分配策略进行调整.