c - C中的杜鹃散列

Question

有人在 C 中实现了Cuckoo 散列吗？如果有一个开源的非 GPL 版本就完美了！

既然亚当在他的评论中提到了它，有谁知道它为什么用得不多？仅仅是实施的问题，还是良好的理论特性在实践中没有实现？

score 7 · Accepted Answer

正如其他答案所指出的那样，最简单的杜鹃哈希表确实要求该表为半空。然而，这个概念已经被推广到d - ary cuckoo 散列，其中每个键有d个可能的嵌套位置，而不是简单版本中的 2 个位置。

可接受的负载系数随着d的增加而迅速增加。只有d =3，您已经可以使用大约 75% 的完整表。缺点是您需要d 个独立的哈希函数。我是 Bob Jenkins 为此目的的散列函数的粉丝（请参阅http://burtleburtle.net/bob/c/lookup3.c），您可能会发现它在布谷鸟散列实现中很有用。

score 6 · Accepted Answer

Cuckoo 散列在学术界之外相对未使用（除了硬件缓存，它有时会借用想法，但并没有真正完全实现）。它需要一个非常稀疏的哈希表才能获得良好的插入时间——您确实需要将 51% 的表留空才能获得良好的性能。因此，它要么速度快，占用大量空间，要么速度慢，有效利用空间——绝不是两者兼而有之。其他算法既节省时间又节省空间，尽管仅考虑时间或空间时它们比杜鹃差。

这是杜鹃哈希表的代码生成器。检查生成器的许可证以验证输出是否为非 GPL。应该是，但无论如何都要检查。

-亚当

score 5 · Accepted Answer

5

http://www.mpi-inf.mpg.de/~sanders/programs/cuckoo/

高温高压

于 2008-10-27T14:13:11.320 回答

score 3 · Accepted Answer

尽管这是一个老问题，但有人可能仍然感兴趣:)

本文描述了在 GPU (CUDA/OpenCL) 上实现并行 d-ary cuckoo hash。它描述得很好，根据描述实现它非常容易。如果您对此主题感兴趣，通常值得一读。（不过，您需要 ACM 登录。）

score 2 · Accepted Answer

我不能说软件，但杜鹃散列肯定用于硬件并且变得非常流行。网络设备的主要供应商一直在研究布谷鸟哈希，有些已经在使用它。Cuckoo 哈希的吸引力当然来自于恒定的查找时间，但也来自于几乎恒定的插入时间。

尽管插入理论上可以是无限的，但实际上它可以限制为表中行数的 O(log n)，并且在测量时，插入时间平均约为 1.1*d 内存访问。这仅比绝对最小值多出 10%！内存访问通常是网络设备的限制因素。

独立的散列函数是必须的，正确选择它们是困难的。祝你好运。

score 1 · Accepted Answer

IO 语言有一个，在 PHash.c 中。你可以在 Github 上找到IO 的代码。IO 是 BSD 许可的。

score 1 · Accepted Answer

我看到了利用率的重点，但这是我尝试这种特殊哈希方案的原因。如果我错过了什么，请告诉我。

据我所知，创建动态字典的哈希表的可能替代方法是（平衡）二叉树和跳过列表。只是为了讨论，让我们从 key 和 value 类型中抽象出来，假设我们将通过void *.

对于二叉树，我将拥有：

struct node {
  void *key;
  void *value;
  struct node *left;
  struct node *right;
}

因此，假设指针具有相同的大小s，要存储n 个项目，我将需要 4 s字节。

跳过列表几乎与节点中的平均指针数为 2 相同。

在哈希表中，我将拥有：

struct slot {
  void *key;
  void *value;
}

因此，每个项目只需要存储 2 s个字节。如果负载因子为 50%，要存储n 个项目，我将需要与树相同的 4 s字节。

对我来说这似乎并不算太糟糕：cuckoo 哈希表将占用与二叉树大致相同的内存量，但会给我 O(1) 的访问时间而不是 O(log n)。

不计算保持树平衡的复杂性以及在节点中存储平衡信息可能需要的附加信息。

其他散列方案可以实现更好的负载因子（比如 75% 或 80%），但不能保证最坏情况下的访问时间（甚至可能是 O(n) ）。

顺便说一句，d-ary cuckoo hashing和“ cuckoo hashing with a stash ”似乎能够增加负载因子，同时仍然保持恒定的访问时间。

Cuckoo hashing 对我来说似乎是一种有价值的技术，我认为它已经被探索过了；这就是我的问题的原因。

score 1 · Accepted Answer

根据“onebyone”的评论，我已经实现并测试了几个版本的 Cuckoo 散列以确定真正的内存需求。

经过一些实验后，声称您不必在表几乎 50% 满之前重新启动的说法似乎是正确的，尤其是在实施“存储”技巧的情况下。

问题是当你扩大表格时。通常的方法是将其大小增加一倍，但这会导致新表的利用率仅为 25%！

事实上，假设哈希表有 16 个槽，当我插入第 8 个元素编号时，我会用完好的槽，必须重新计算。我将它加倍，现在桌子上有 32 个插槽，其中只有 8 个被占用，这是 75% 的浪费！

这是获得“恒定”检索时间（就访问/比较次数的上限而言）所付出的代价。

不过，我设计了一个不同的模式：从大于 1 的 2 的幂开始，如果表有 n 个插槽并且 n 是 2 的幂，则添加 n/2 个插槽，否则添加 n/3 个插槽：

+--+--+
|  |  |                             2 slots
+--+--+

+--+--+--+
|  |  |  |                          3 slots
+--+--+--+ 

+--+--+--+--+
|  |  |  |  |                       4 slots
+--+--+--+--+

+--+--+--+--+--+--+
|  |  |  |  |  |  |                 6 slots
+--+--+--+--+--+--+

+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |           8 slots
+--+--+--+--+--+--+--+--+

等等

再加上仅在表 50% 满时才会发生重新刷新的假设，这导致在重新刷新后表将只有 66% 空（1/3）而不是 75% 空（1/4）（即最坏的情况）。

我还发现（但我仍然需要检查数学）每次放大 sqrt(n)，浪费的空间渐近接近 50%。

当然，减少内存消耗的代价是最终需要的 reash 数量的增加。唉，没有什么是免费的。

如果有人感兴趣，我将进一步调查。

c - C中的杜鹃散列

8 回答 8

Related

Reference