何时调整哈希表的大小？

Question

在各种哈希表实现中，我看到过“魔数”，用于可变哈希表何时应该调整大小（增长）。通常，这个数字在分配的插槽中添加值的65％至80％之间。我假设权衡是更高的数字会导致更多的冲突，较低的数字少于使用更多的内存。

我的问题是这个数字是如何得出的？它是任意的吗？基于测试吗？还是基于其他逻辑？

- Nick Van Brunt

Answer 1

大多数人至少从书中的数字开始（例如 Knuth 第三卷），这些数字是通过测试产生的。根据情况，有些人可能会在之后进行测试，并进行相应的调整，但据我所见，这些人可能只是少数。正如我在先前的答案中概述的那样，“正确”的数字也在很大程度上取决于如何解决冲突。不管是好是坏，这个事实似乎被广泛忽视了--人们经常不选择特别适合他们使用的冲突解决方案的数字。

另一方面，在我的测试中发现的另一个观点是它只有在很少情况下会产生很大的差异。您可以选择一个相当广泛的数字范围，并获得相似的总体速度。主要问题是要小心避免将数字推得太高，特别是如果您正在使用类似线性探测的冲突解决方案。

- Jerry Coffin

Answer 2

我认为您不想考虑表有多满（总桶数中有多少个桶具有值），而是要考虑找到新项目的位置可能需要多少次冲突。

我几年前读过一些编译器书籍（无法记住标题或作者），建议仅使用链接列表，直到您拥有超过10到12个项目。这似乎支持超过10个冲突意味着重新调整大小。 Icon中集合和表的动态哈希设计与实现建议，在该算法中，平均哈希链长度为5（碰撞的平均数量）足以触发重新哈希。测试支持这一点，但我不确定是否正确地阅读了论文。

看起来调整大小的条件主要是测试结果。

- user208139

---

调整大小如何减少碰撞次数？更长数组的哈希函数仍将保持不变，因此相同的键仍会发生碰撞，对吗？ - Core_Dumped

@Core_Dumped - 是的，哈希函数保持不变，哈希表中项目的哈希值也保持不变。但是桶的长度会改变，因此项目所在的桶也会改变。重新调整大小意味着更改数组（通常是）的桶的长度，然后重新将哈希表中的所有项目分配到各个桶中。每个桶的链长度平均下降，这意味着发生冲突的次数减少了。 - user208139

Answer 3

这取决于键的情况。如果您知道您的哈希函数对所有可能的键都是完美的（例如，使用gperf），那么您就知道只会有很少的冲突，因此数量更高。

但大多数情况下，除了它们是文本之外，您对键不知道太多信息。在这种情况下，您必须猜测，因为您甚至没有测试数据来提前了解您的哈希函数的运行方式。

所以你希望最好的结果。如果您的哈希函数对键非常糟糕，那么您将有很多冲突，并且增长点永远无法达到。在这种情况下，所选数字是无关紧要的。

如果您的哈希函数足够好，则应该仅创建很少的冲突（少于50％），因此65％到80％之间的数字似乎是合理的。

话虽如此：除非您的哈希表必须是完美的（=巨大的大小或许多访问），否则不要费心。如果您有十个元素，考虑这些问题是浪费时间。

- Aaron Digulla

Answer 4

据我所知，这个数字是基于经验测试的启发式算法。

如果哈希值的分布相当好，那么魔术负载因子通常在70%左右，就像你所说的那样。较小的负载因子意味着你浪费了空间，但没有真正的好处；较高的负载因子意味着你将使用更少的空间，但需要花费更多的时间处理哈希冲突。

（当然，如果你知道你的哈希值完全分布均匀，那么你的负载因子可以达到100%，你仍然不会浪费空间或者出现哈希冲突。）

- LukeH

Answer 5

碰撞高度依赖于数据和使用的哈希函数。

大部分数值都基于启发式或关于哈希值正常分布的假设。(据我所知，对于可扩展哈希表，约70%的值是典型的，但总有可能构造出这样的数据流，使得你得到更多/更少的碰撞)

- p4553d