散列表和处理冲突

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 -