我们能否使用一张表来实现cuckoo哈希？

Question

我了解到关于Cuckoo哈希表的内容，它们似乎非常优秀。
但是我发现大多数示例代码都使用两个表来实现。
这对我来说似乎是错误的，因为这两个表可能位于不同的内存页中，我们需要获取随机地址并且没有真正的局部性。
难道不能使用1个数组来代替2个吗？
也许无法检测元素已经被踢出2次并且需要调整大小吗？

- Jim

---

你可以在同一块内存中分配这两个表，即进行一次分配，以确保空间局部性。 - BeyelerStudios

很简单，只需分配一个表，然后将其切成两半即可。 - harold

另外请注意，今天的系统中L1高速缓存的大小为几KB（例如查阅当前英特尔微架构），因此有足够的空间容纳多个内存页面 - 需要索引到少量页面也不应该是问题。 - BeyelerStudios

@BeyelerStudios：这是一种特定于语言的问题吗？例如，我感兴趣的Java就不能这样做。 - Jim

@harold：我在想，如果只使用一个表，可能无法检测到元素的第二次驱逐。 - Jim

Answer 1

你可以使用一个哈希表来实现cuckoo哈希表，也就是说，每个对象的两个位置仅是单个哈希表中的位置。唯一需要解决的小问题是在cuckoo清理循环期间如何决定要用哪个位置来存储被清除的键。当然，你可以尝试一个位置，如果第一个位置与实际位置相同，则使用另一个位置。可以使用 SIMD 并行计算两个散列值，因此这种策略的成本可能很小。但是，如果你想在 cuckoo 循环期间保证单个哈希计算，则有一个简单的解决方案：不要使用 H0(k) 和 H1(k) 作为两个位置，而是使用 H0(k) 和 H0(k) xor H1(k)。通过这种修改，你可以通过将当前位置与 H1(k) 进行异或来始终找到 k 的“另一个位置”，因此在循环中只需要进行一次哈希计算。

虽然这使你可以使用单个哈希表，甚至可能简化代码，但几乎没有证据表明它会改善算法的操作。在我的有限测试中，它似乎会将循环迭代次数增加40-50％。（需要强调的是，在绝大多数情况下，新键可以在根本不进入循环的情况下插入表中，因此增加的循环次数在实际执行时间中几乎是不可感知的。）

- rici

---

抱歉回答晚了。我在研究布谷鸟哈希时偶然发现了这个问题，而这个答案似乎很相关。 - rici

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能够在运行时将两个小型分配合并为一个较大的分配，而无需您进行任何索引魔法。

- BeyelerStudios

---

但是为什么索引计算会比访问另一个内存页中的另一个数组更具开销呢？ - Jim

@Jim，就像其他许多性能问题一样：您需要在您的系统上进行测量。特别是在使用虚拟机进行索引和跨页访问时，JIT生成指令的具体方式将产生重大影响-而不是您对这些指令应该如何生成的想法。 - BeyelerStudios

但是，“你必须在你的系统上进行测量”是什么意思？哪个系统？应该使用什么样的系统来测试通用数据结构？ - Jim

Answer 3

是的。

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

你可以在SPOJ上检查这个问题，我们需要使用一个哈希表和两个哈希函数来解决这个问题。

- ymdatta

Answer 4

好的，所有类型的哈希都会对缓存造成影响。

无论如何，您可以轻松地将两个表合并为一个表。但是，您怎么知道您正在使用第一个哈希函数还是第二个哈希函数？选项是将其添加为每个桶的元数据，否则通过运行第一个哈希函数来找出，并查看是否已到达当前位置，如果在第一个上，则运行第二个。这要求额外的空间，或者运行更多的哈希函数。

将表分成2部分更有效地解决了这个问题。从统计上讲，无论表格是否被拆分，都需要相同数量的桶来存储相同数量的内容。因此，整个哈希表变得更小。

- btilly

---

两个哈希函数是否有可能在某些元素和数组大小上发生冲突，因此不使用两个表是不可避免的？ - Jim

所有形式的哈希都会对缓存造成很大的压力。就我所了解的，开放地址法并没有你提到的这个问题。 - Jim

@Jim 在插入操作中，总存在插入会创建循环的可能性，因此您必须使用两个新哈希函数重新构建表。无论是使用一个表还是两个表，这都是真实情况。至于哈希会破坏缓存，我说了“全部”，我是真的指全部。第一步是计算哈希函数并跳转到内存块中的伪随机位置。如果该块大于缓存，则可能会破坏缓存。具体例子。在许多使用情况下，具有大量数据的BTree平均每次查找少于一个磁盘查找。相同大小的哈希值始终进行查找。 - btilly

@btilly，我可以对这个说法进行辩论：“所有形式的哈希都会对缓存造成很大的影响”。 1）根据帕累托原则，一小部分条目占据了主要访问量的重要位置，因此在最接近的缓存中。 2）也就是说，除了扫描连续块的内存之外，任何其他操作都会“摧毁缓存”，没有建设性的作用。 3）进行一次随机访问和两次随机访问之间的差别非常大。 这使得线性哈希比双哈希更有效。 - leventov

@leventov 顺便说一下。1）是的，会有热门页面。但通常情况下，您将拥有一个带有1个键/值对的页面很受欢迎，并且其余部分被拖入缓存以驱逐其他内容。一遍又一遍。这不是高速缓存想要处理的方式。2）令人惊讶的复杂访问模式可以很好地与高速缓存配合使用。我提供了BTree。请参阅http://en.wikipedia.org/wiki/Cache-oblivious_algorithm获得更多示例。3）您做得更糟糕并不意味着您做得很好。 - btilly