布穀鳥哈希：什麼是散列函數中檢測碰撞的最佳方法？

Question

我實現了基於杜鵑哈希的哈希映射。 我的散列函數採用long類型的任何長度和返回鍵的值。要將鍵匹配到我的數組大小n，我需要鍵％n。

我正在考慮以下情形：

• 與關鍵A.key到位置A.key％N
• 查找值B與關鍵A.key

插入值A所以對於這個例子，我得到了A值的條目，並且沒有識別出B值甚至沒有被插入。如果我的散列函數爲兩個不同的值返回相同的鍵，就會發生這種情況碰到不同的鑰匙但碰到相同的位置是沒有問題的。

檢測這些碰撞的最佳方法是什麼？ 如果原始值相等，每次插入或搜索項目時都需要檢查嗎？

Answer 1

與大多數散列方案一樣，在布穀散列中，散列碼告訴你在表中查找問題元素的位置，但期望的是將表鍵和值存儲在表中，以便在返回存儲的值，您首先檢查存儲在該插槽中的密鑰與您正在查找的密鑰。這樣，如果您爲兩個對象獲取相同的散列碼，則可以確定哪個對象存儲在該插槽中。