我们可以实现用1台杜鹃哈希？ [英] Can we implement cuckoo hashing using 1 table?

问题描述

我发现关于，他们似乎pretty的良好杜鹃哈希表。
但是，大多数的例子code，我发现这个使用2个表执行。
这似乎是我错了，因为2表可能是在不同的内存页面，我们必须获取随机地址的开销并没有真正的地方。
这难道不是可以使用1阵列，而不是2？
是它也许不可能检测到当一个元件已被踢出2倍和是时间调整大小？

I found about Cuckoo Hash tables and they seem pretty good.
But most examples code I found implement this using 2 tables.
This seems to me wrong because the 2 tables may be in different memory pages and we have overhead of fetching random addresses and have no real locality.
Is it not possible to use 1 array instead of 2?
Is it perhaps not possible to detect when an element has already been kicked out 2 times and is time for resizing?

推荐答案

要回答这个混乱的评论：不，这是不特定的语言。如果你正在考虑内存局部性，并要确保两个表接近，然后通过一次分配是要走的路（但是你分配）。在Java中，这可能会是这样：

To answer the confusion in the comments: no this is not language specific. If you're thinking about memory locality and want to ensure the two tables are close, then a single allocation is the way to go (however you allocate). In java this may look as follows:

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能够合并两个小分配到上飞一个较大的一个 - 无需你执行任何指数魔法

If this performs better than accessing into two separate arrays is dependant on your JVM however: just think about the JIT being able to merge two small allocations into a single larger one on the fly - without you having to perform any index-magic.

这篇关于我们可以实现用1台杜鹃哈希？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！