哈希表和处理冲突

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 模 7 = 2
• 737； 3 模 7 = 3
• 323； 3 模 4 + 1 = 4
• 234； 4 mod 4 + 1 = 4 (0)

这是正确的吗？

Answer 1

您可能想提及您正在使用什么类型的哈希。根据您的描述，我认为它是 cuckoo 哈希。如果是这种情况，直到最后一次插入为止都没有问题。在插入 234 之前，您有：

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

尝试使用 h1 插入 234 会得到 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:

用 h1 哈希 111 再次得到 1，h2 得到 1 mod 4 + 1 = 2，但是 2 已经包含 222，所以我们将 111 存储在 2 处并重新散列 222 等。在这种情况下，最终您会发现所有键都适合。在它们的条目不全部适合的情况下（即重新插入进入无限循环），需要调整表的大小并使用新的哈希函数重新哈希。

Answer 2

我不确定如果检查辅助哈希键后仍然存在冲突，这个问题希望您做什么，但我认为它是这样的：

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

如果在第二次碰撞后前进 1，结果将为

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