为什么哈希表扩展通常是将大小加倍？

Question

我对哈希表进行了一些研究，发现一个经验法则是当哈希表中有一定数量的条目（无论是最大值还是通过负载因子比如75％）时，哈希表应该扩展。

几乎总是建议将哈希表的大小加倍（或加倍再加1，即2n + 1）。然而，我没有找到一个好的原因来解释这样做的理由。

为什么要将大小加倍，而不是增加25％，或者增加到下一个素数的大小，或者下k个素数的大小（例如三）？

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

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

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

- Chirael

---

我认为这个问题背后的根本问题可以用更通用的方式表达，不仅仅是哈希表特有的问题。比如说："为什么许多集合通过将其内部数组大小加倍来调整大小？" 要获得一个很好的解释，请参见Pete Kirkham的答案：https://dev59.com/l3M_5IYBdhLWcg3wUxfF#1426065 - Andras Vass

Answer 1

如果哈希表的大小增量是固定的，那么哈希表就无法宣称具有“平摊常数时间插入”的特性。在这种情况下，重新调整大小的成本（随着哈希表大小的增加而增长）将使得一个插入操作的成本与要插入的总元素数量呈线性关系。由于重新调整大小随着表格大小的增加变得越来越昂贵，所以为了保持插入的平摊成本恒定，必须越来越少地进行调整大小操作。

大多数实现允许平均桶占用率在调整大小之前增长到预先确定的界限（在0.5到3之间都是可以接受的值）。按照这个惯例，在重新调整大小之后，平均的桶占用率将变为这个界限的一半。倍增调整大小方法可以保持平均桶占用率在宽度为*2的带内。

注：由于统计聚类的原因，如果您希望许多桶最多只有一个元素（忽略缓存大小的复杂影响），则必须将平均桶占用率设定为0.5；如果您想要最小化空桶的数量（对应浪费的空间），则必须将平均桶占用率设定为3或更高。

- Pascal Cuoq

---

@andras 对的。1.5和3只是合理值的示例，可以在这些值之间使用加倍策略来使负载因子变化。我选择了我熟悉的编程语言中常用的值，但它们并没有特别之处。 - Pascal Cuoq

@andras 我修改了表述。如果您出于好奇心查看了它，.Net 和 Java 的值是什么？ - Pascal Cuoq

@andras 因为这样，摊销插入时间在实践中将被重新调整大小的成本所支配（当您重新调整大小时，必须再次计算所有存储值的哈希）。当然，您可以使用1.5或3，因子2恰好以可接受的方式平衡各种成本。这纯粹是启发式的，任何> 1的因子都会给出相同的渐近复杂度。即使您知道自己要追求什么样的内存/速度权衡，也没有最优值，因为一切都取决于提供的哈希和相等函数的成本。 - Pascal Cuoq

@andras 嗯，如果你深究的话，是的，一方面是由于众多调整大小操作所需的时间，另一方面是调整大小后浪费的空间。你为什么要删除 .Net 和 Java 中带有数值的评论呢？ - Pascal Cuoq

@andras，新版本较差真是太糟糕了，因为我根据你的建议进行了（反复）编辑。你有没有考虑过编辑自己的答案，以便向我们阐述你对哈希表的看法？顺便说一句，随意投票支持这个答案。 - Pascal Cuoq

Answer 2

我曾在这个网站上读到一篇非常有趣的关于增长策略的讨论，但是现在找不到了。

虽然 2 是常用的增长因子，但已经证明它并不是最好的值。一个常被引用的问题是，它不能很好地处理分配器方案（通常会分配二次幂大小的块），因为它总是需要重新分配，而较小的数字可能实际上在同一个块中被重新分配（模拟原地增长），因此速度更快。

例如，VC++ 标准库在邮件列表上进行了广泛讨论后使用了增长因子 1.5（如果使用第一适配内存分配策略，则理想情况下应该是黄金比例），其中推理在此处解释：here：

我想知道是否有其他向量实现使用了除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，当且仅当k*k*s <= k*s+s时适应该空洞，即当且仅当k <= (1+sqrt(5))/2时适用。

...该空洞可以尽快回收。

它可以通过存储其先前的大小，以斐波那契方式增长。

当然，它应该根据内存分配策略进行定制。

- Matthieu M.

---

这是哪个实现版本？你能提供讨论链接吗？ - Praxeolitic

@Praxeolitic：我有一只金鱼的记忆，所以很遗憾，我无法准确地记得6年前（已经！）我想表达什么。话虽如此，查询（Google）显示2003年在comp.lang.c++.moderated上进行了讨论，当时Dirkumware（VC++）已经使用了1.5的向量。2004年在gcc上进行了一次关于从2到1.5的转换的讨论，但考虑到这个2013年的主题，那时候没有什么变化。 - Matthieu M.

很好，我以前没有看到过那个黄金数字参数。对于像我这样觉得comp.lang.c++.moderated线程令人困惑的人，这个解释更加详细。 - Praxeolitic

@Praxeolitic：不错的链接！我个人现在想知道，在使用大小桶（具有桶之间自定义增长因子）的现代分配器（如jemalloc/tcmalloc）中，1.5是否仍然比2更好；这有点不太清楚。如果可以使用C++11和平凡的移动构造函数，则可能可以使用realloc将项目保留在相同的大小桶中...但实际上我们在这里看到的是std::allocator设计的限制=>当您请求N字节的内存时，它不仅应该给您至少N字节的内存块，还应该告诉块包含多少字节。 - Matthieu M.

让我们看看Facebook的FBVector中一些逻辑，可以在这里的computePushBackCapacity函数下找到。当它很小（实际上只是增长因子为2）时，首先根据桶大小增加，然后在中等大小时增加1.5，最后再次增加2（我猜是为了使用整个内存页）。 - Praxeolitic

Answer 3

哈希容器翻倍大小的一个特定原因是，如果容器容量始终是2的幂，则可以使用位移运算符而不是通用模数将哈希转换为偏移量。对于相同的原因，模运算是一种缓慢的操作，即整数除法缓慢。 （当然，在程序中使用整数除法是否“缓慢”取决于其他正在进行的内容，但它肯定比其他基本整数算术运算缓慢。）

- Praxeolitic

Answer 4

扩展任何类型的集合时，将内存翻倍是一种经常使用的策略，以防止内存碎片化并减少频繁重新分配的次数。正如你所指出的，有时可能存在使用素数个元素的原因。当了解你的应用程序和数据时，你还可以预测元素数量的增长，并选择比翻倍更大或更小的增长因子。

在库中找到的通用实现就是这样：通用实现。它们必须专注于在各种不同情况下成为一个合理的选择。当了解上下文时，几乎总是可能编写一个更专业、更高效的实现。

- Anders Abel

Answer 5

如果你不知道最终会使用多少个对象（假设为N），
通过将空间翻倍，最多只需进行log₂N次重新分配。

我认为如果选择一个适当的初始“n”，你可以增加
在后续的重新分配中，2*n + 1会产生质数的几率。

- Nick Dandoulakis

Answer 6

对于数组/ArrayList的实现，扩大大小的原因与翻倍的原因相同，请参见此答案。

- Pete Kirkham