何时调整哈希表的大小？

Question

在各种哈希表实现中,我看到了可变哈希表应该调整大小(增长)时的"幻数".通常,此数字介于每个已分配插槽的值的65%到80%之间.我假设权衡的是,更高的数字将提供更多冲突的可能性和更少的数量,以牺牲使用更多的内存为代价.

我的问题是这个数字是如何得出的？

这是武断的吗？基于测试？基于其他一些逻辑？

Answer 1

我认为你不想考虑表的"多满"(总桶数中有多少"桶"有值),而是为新物品找到一个点可能需要的冲突次数.

几年前我读了一些编译器书(不记得标题或作者),建议只使用链表,直到你有超过10到12个项目.这似乎支持超过10次碰撞意味着重新调整大小的时间.

动态系统的设计与实现.在Icon中对集合和表进行散列表明平均散列链长度为5(在该算法中,平均冲突数)足以触发重新散列.似乎测试支持,但我不确定我是否正确阅读了论文.

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

Answer 2

据猜测,大多数人至少从书中的数字开始(例如,Knuth,第3卷),这些是通过测试产生的.根据具体情况,有些人可能会在事后进行测试,并做出相应的调整 - 但从我所看到的情况来看,这些可能属于少数.

正如我在之前的回答中所概述的那样,"正确"数字也在很大程度上取决于您如何解决冲突.无论好坏,这个事实似乎被广泛忽视 - 人们经常不会选择特别适合他们使用的碰撞解决方案的数字.

OTOH,我在测试中发现的另一点是它很少会产生很大的不同.您可以在相当宽的范围内选择数字,并获得非常相似的整体速度.最重要的是要小心避免将数字推得太高,特别是如果你使用线性探测等方法进行碰撞解决.