散列表和處理衝突

Question

假設散列表被表示爲大小爲7的數組。我們希望存儲由三位數組成的字符串。主散列鍵是第二個數字模7的數值。第二散列鍵是第三個數字模4的數值增加1。將以下字符串插入最初爲空的散列表：「111」，「222」，「737」，「323」和「234」。

我的響應：

• 0 - 234
• 1 - 111
• 2 - 222
• 3 - 737
• 4 - 323
• 5 -

• 6 -

• 111; 1 mod 7 = 1

• 222; 2 mod 7 = 2
• 737; 3 mod 7 = 3
• 323; 3 mod 4 + 1 = 4
• 234; 4 mod 4 + 1 = 4（0）

是否正確？

Answer 1

你可能想提一下你使用的是什麼類型的散列。我從你的描述中假設它是cuckoo hashing。如果是這種情況，則直到最後一次插入爲止。 234插入之前，你有：

0: 
1: 111 
2: 222 
3: 737 
4: 323 
5: 
6: 

試圖插入234 h1給出3 mod 7 = 3的關鍵，但3已經包含了373移動到h2我們得到4 mod 4 + 1 = 1但1已經包含111在這一點上有沒有更多的散列函數，所以我們在1插入234和111.老調重彈

0: 
1: 234 
2: 222 
3: 737 
4: 323 
5: 
6: 

散列111 h1再次給予1，h2給人1 mod 4 + 1 = 2，但2已經包含了222，所以我們店111在2和老調重彈222，等等情況下，最終你會發現所有的鍵都適合。如果它們的條目不適合（即重新插入進入無限循環），則表格需要調整大小並使用新的散列函數進行重新映射。

Answer 2

我不知道這個問題要你做的，如果還有第二哈希鍵後碰撞檢查什麼，但我認爲它是這樣的：

• 111：1 MOD 7 = 1
• 222：2模7 = 2
• 737：3模7 = 3
• 323：2模7 = 2 =>碰撞：3模4 + 1 = 3 + 1 = 4
• 234 ：3 mod 7 = 3 => Collision：4 mod 4 + 1 = 0 + 1 = 1 => Collision

如果通過一個推進第二碰撞後，其結果將是

• 0 -
• 1 - 111
• 2 - 222
• 3 - 737
• 4 - 323
• 5 - 234
• 6 -
• 7 -