我们可以使用 1 table 实现布谷鸟哈希吗？

Question

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

Answer 1

好吧，所有形式的散列都是对缓存的谋杀。

无论如何，您都可以轻松地将两者合二为一 table。但是你怎么知道你是在第一个散列函数上还是在第二个散列函数上呢？选项是将其作为元数据添加到每个存储桶中，或者通过运行第一个哈希函数找出它，看看你是否得到了当前位置，只有当你在第一个时才运行第二个.这要么需要额外的 space，要么需要运行个哈希函数。

将 table 拆分为 2 可以更有效地解决该问题。从统计上讲，无论 table 是否被拆分，您都需要相同数量的桶来存储相同数量的东西。所以你的整个哈希 table 变小了。

Answer 2

回答评论中的困惑：不，这不是特定于语言的。如果您正在考虑内存局部性并希望确保两个表接近，那么单个分配是可行的方法（无论您如何分配）。在 java 中，这可能如下所示：

class TwoTables {
    private static final int SIZE_TABLE_FIRST = 11, SIZE_TABLE_SECOND = 29;

    public TwoTables() {
        m_buffer = new int[SIZE_TABLE_FIRST + SIZE_TABLE_SECOND];
    }

    // consider similar setters...

    public int getFirst(int key) {
        return m_buffer[toIndex(hashFirst(key), SIZE_TABLE_FIRST, 0)];
    }

    public int getSecond(int key) {
        return m_buffer[toIndex(hashSecond(key), SIZE_TABLE_SECOND, SIZE_TABLE_FIRST)];
    }

    private static int toIndex(int hash, int mod, int offset) {
        return hash % mod + offset;
    }

    private static int hashFirst(int key) { return ...; }
    private static int hashSecond(int key) { return ...; }

    private final int[] m_buffer;
}

如果这比访问两个单独的数组执行得更好，则取决于您的 JVM：只需考虑一下 JIT 能够即时将两个小分配合并为一个更大的分配 - 而无需执行任何索引-魔法。

Answer 3

是的。

http://www.spoj.com/problems/CUCKOO/

您可以在 spoj 上查看此问题，我们需要使用单个散列 table 和两个散列函数来解决此问题。

Answer 4

你绝对可以用一个散列 table 做布谷鸟散列table；也就是说，每个对象的两个位置只是单个散列中的位置 table.

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

然而，如果你想保证布谷鸟循环期间的单个哈希计算，有一个简单的解决方案：而不是使用 H0(k) 和H1(k)作为两个位置，用H0(k) 和 H0(k) xor H 1(k)。（如果H1独立于H0，那么 H0 xor H1, 所以xor 不影响散列值的分布。）通过此修改，您始终可以通过将当前位置与 H 进行异或运算来找到 <code>k 的 "the other position" 1(k)，所以循环中只需要一次散列计算。

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

我们可以使用 1 table 实现布谷鸟哈希吗？

Can we implement cuckoo hashing using 1 table?

algorithm

optimization

data-structures

hash

hashtable