我发现了有关杜鹃哈希表的表，它们看起来还不错。
但是我发现的大多数示例代码都是使用2个表实现的。
在我看来，这是错误的，因为2个表可能位于不同的内存页中，并且我们有获取随机地址的开销，并且没有实际的位置。
不能使用1个数组而不是2个数组吗？
是否可能无法检测到何时元素已被踢出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是否能够将两个小的分配动态合并到一个较大的单个分配中，而无需执行任何索引魔术。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句