algorithm - 我们可以使用 1 个表实现布谷鸟哈希吗？

Question

我找到了关于 Cuckoo Hash tables 的信息而且它们看起来还不错。
但我发现的大多数示例代码都是使用 2 个表来实现的。
这在我看来是错误的，因为这两个表可能位于不同的内存页中，而且我们有获取随机地址的开销并且没有真正的位置。
不能使用 1 个数组而不是 2 个吗？
是否可能无法检测到某个元素何时已被踢出 2 次以及何时需要调整大小？

Answer 1

你绝对可以用一个哈希表做一个布谷鸟哈希表；也就是说，每个对象的两个位置只是单个哈希表中的位置。

唯一要解决的小问题是如何在布谷鸟逐出循环中决定将两个位置中的哪一个用于逐出的 key 。当然，如果第一个位置与实际位置相同，您可以只尝试一个位置并使用另一个位置。应该可以使用 SIMD 并行计算两个哈希值，因此这种策略的成本可能很小。

但是，如果您想在布谷鸟循环期间保证单个哈希计算，有一个简单的解决方案:而不是使用 H<sub>0</sub>(k)和 H<sub>1</sub>(k)作为两个位置，使用 H<sub>0</sub>(k)和 H<sub>0</sub>(k) <b>xor</b> H<sub>1</sub>(k) . (如果H<sub>1</sub>独立于H<sub>0</sub>，那么H<sub>0</sub> <b>xor</b> H<sub>1</sub>也是独立的，所以异或不影响散列值的分布。)通过这种修改，你总是可以找到k的“其他位置”。通过将当前位置与 H<sub>1</sub>(k) 进行异或运算，因此循环中只需要一次哈希计算。

虽然这允许您使用单个哈希表，甚至可以简化代码，但没有很多证据表明它改进了算法的操作。在我的有限测试中，它似乎将循环迭代次数增加了 40-50%。 (虽然需要强调的是，在绝大多数情况下，根本不进入循环就可以向表中插入一个新的key，所以循环次数的增加在实际执行时几乎察觉不到。)