布谷鸟哈希：什么是散列函数中检测碰撞的最佳方法？

Question

我实现了基于杜鹃哈希的哈希映射。 我的散列函数采用long类型的任何长度和返回键的值。要将键匹配到我的数组大小n，我需要键％n。

我正在考虑以下情形：

• 与关键A.key到位置A.key％N
• 查找值B与关键A.key

插入值A所以对于这个例子，我得到了A值的条目，并且没有识别出B值甚至没有被插入。如果我的散列函数为两个不同的值返回相同的键，就会发生这种情况碰到不同的钥匙但碰到相同的位置是没有问题的。

检测这些碰撞的最佳方法是什么？ 如果原始值相等，每次插入或搜索项目时都需要检查吗？

Answer 1

与大多数散列方案一样，在布谷散列中，散列码告诉你在表中查找问题元素的位置，但期望的是将表键和值存储在表中，以便在返回存储的值，您首先检查存储在该插槽中的密钥与您正在查找的密钥。这样，如果您为两个对象获取相同的散列码，则可以确定哪个对象存储在该插槽中。