哈希表:我应该增加冲突时的元素计数吗？

Question

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

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

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

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

Answer 1

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

最好是在每个条目中保留原始的完整散列值(冲突当然是由模为您当前大小的散列值确定的)，并且只计算由于模运算而导致的冲突--隐含地承认，如果冲突是由于不同项的完全相同的散列值造成的，那么重新散列就无能为力了(除非“重新散列”也意味着切换到不同的散列函数，但它看起来不是您在这里的意思；-)。

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