散列表：我應該增加碰撞時的元素數嗎？

Question

現在我的哈希表計算插入到哈希表中的每個元素的數量。我用這個計數和總散列表大小來計算加載因子，當它達到70％時，我重新調整它。

我在想，也許我應該只計算插入的元素與填充空插槽，而不是所有的人。導致我使用的碰撞方法是單獨的鏈接。因子負荷持續增加，但是如果可能有少量碰撞在哈希表上留下大量空閒時隙。

您可能正在考慮如果我有這麼多的碰撞，也許我沒有使用最好的散列方法。但那不是重點，我使用了其中一種已知的哈希算法，我在我的樣本數據上測試了其中的3個，並選擇了產生較少碰撞的那個。

我的問題仍然存在。我應該不斷計算插入的每個元素，還是隻填充散列表中的空插槽？

Answer 1

重整是爲了減少碰撞的可能性，所以系統地忽略碰撞以決定什麼時候重新搭建似乎自我毀滅。

如果您在每個條目中保留原始完整哈希值（當然碰撞是由哈希取模您的當前大小確定的），並且只計算歸因於模操作的衝突 - 隱式確認如果碰撞是由於不同項目的完全散列值相同，那麼沒有什麼可以做的幫助（除非通過「重新散佈」你也意味着切換到不同的散列函數，但它看起來不像你在這裏所指的那樣;-)。

保留完整的哈希值還意味着更便宜的重新哈希，因爲您不需要再次運行哈希函數（當然，相關程度取決於哈希函數的計算成本）。