hashtable - 哈希表：我应该增加碰撞时的元素计数吗？

Question

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

我在想也许我应该只计算插入的元素填充一个空插槽而不是所有它们。因为我使用的碰撞方法是单独的链接。因子负载不断增加，但如果可能存在一些冲突，则会在哈希表上留下大量空槽。

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

我的问题仍然存在。我应该继续计算插入的每个元素，还是只计算填充哈希表中空槽的元素？

Answer 1

重新散列旨在减少冲突的可能性，因此系统地忽略冲突来决定何时重新散列似乎是弄巧成拙。

最好的情况是，如果您保留每个条目的原始完整哈希值（当然，冲突是由您当前大小的哈希模确定）并仅计算由于模运算引起的冲突 - 隐含地承认如果发生冲突是由于不同项目的完整哈希值相同，因此重新散列无济于事（除非通过“重新散列”也意味着切换到不同的散列函数，但看起来这不是你的意思；-)。

保留完整的散列值也意味着更便宜的重新散列，因为您不需要再次运行散列函数（当然，这取决于散列函数的计算成本）。