调整哈希表的大小有意义吗？什么时候？

Question

我的哈希表实现有一个函数，当负载达到约70％时调整表的大小。我的哈希表是用单独的链进行碰​​撞实现的。

是否有意义，我应该在任何时候调整哈希表的大小，还是应该让它保持原样？否则，如果我在负载为70％时增加尺寸（差不多是两倍，实际上我遵循这个：http://planetmath.org/encyclopedia/GoodHashTablePrimes.html），当负载变为30％或更低时，是否应该调整它的大小？

Answer 1

你是在编写一般用途的散列表，还是有特定的目的呢？我建议不要为了一般实现而调整较小的尺寸。这将使你的表格变得简单并且在经常填充和清空表格的情况下防止内存抖动。如果最终遇到散列表需要缩小的情况，请在该时间点扩展它。

Answer 2

如果内存很便宜，请保持独立。如果内存昂贵，请按照您的建议重新调整歇斯底里。完成后，分析结果以确保其表现良好并且没有做出愚蠢的事情。

Answer 3

如果您有一个高质量的散列函数（见here），则散列表不必具有素数长度。你可以使它们成为两个幂，这大大加快了索引计算的速度。

为什么这与这个问题有关？因为当你缩小两次幂的哈希表时，你可以将所有的条目保留在下半部分的位置，并简单地将链接列表添加到槽i（从上半部分）到槽i - n/2的链接列表中。