散列表：我应该增加碰撞时的元素数吗？

Question

现在我的哈希表计算插入到哈希表中的每个元素的数量。我用这个计数和总散列表大小来计算加载因子，当它达到70％时，我重新调整它。

我在想，也许我应该只计算插入的元素与填充空插槽，而不是所有的人。导致我使用的碰撞方法是单独的链接。因子负荷持续增加，但是如果可能有少量碰撞在哈希表上留下大量空闲时隙。

您可能正在考虑如果我有这么多的碰撞，也许我没有使用最好的散列方法。但那不是重点，我使用了其中一种已知的哈希算法，我在我的样本数据上测试了其中的3个，并选择了产生较少碰撞的那个。

我的问题仍然存在。我应该不断计算插入的每个元素，还是只填充散列表中的空插槽？

Answer 1

重整是为了减少碰撞的可能性，所以系统地忽略碰撞以决定什么时候重新搭建似乎自我毁灭。

如果您在每个条目中保留原始完整哈希值（当然碰撞是由哈希取模您的当前大小确定的），并且只计算归因于模操作的冲突 - 隐式确认如果碰撞是由于不同项目的完全散列值相同，那么没有什么可以做的帮助（除非通过“重新散布”你也意味着切换到不同的散列函数，但它看起来不像你在这里所指的那样;-)。

保留完整的哈希值还意味着更便宜的重新哈希，因为您不需要再次运行哈希函数（当然，相关程度取决于哈希函数的计算成本）。