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

Question

现在我的哈希表计数插入到哈希表的每个元素的数量。我用这个计数，总哈希表的大小，来计算所述负载因数，并且当它到达像70％，我重提它。

我想，也许我应该只使用填充计数插入元件的空插槽，而不是全部。因为我使用的碰撞方法是分离链。的因子载荷不断增加，但如果有可能留下大量空槽在哈希表的几个碰撞。

您可能会想，如果我有那么多的碰撞，也许我没有使用最好的散列方法。但是，这不是重点，我使用的是在那里，我对我的样本数据来测试他们的3和选择谁产生较少的碰撞一个知道了散列算法之一。

我的问题仍然存在。我应该保持计数的每一个元素插入，或只是在哈希表填充的空插槽的人？

Answer 1

重散列旨在减小冲突的可能性，所以系统忽略碰撞来决定何时翻版似乎弄巧成拙。

最好的可能是，如果你保持每个条目最初完全散列值（当然碰撞是由哈希，而不是确定的模电流的大小），并只计算那些由于模运算的碰撞 - 含蓄地承认，如果碰撞是由于为不同的项目相同的全散列值，没有什么换汤不换药可以做，以帮助（除非“老调重弹”，你也意味着切换到不同的哈希函数，但它看起来并不像这就是你的意思是在这里; - 。）

保持完整的哈希值也意味着更便宜的换汤不换药，因为你并不需要再次运行哈希函数（如何相关的是取决于你的散列函数是怎样的损失来计算，当然）。