https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
是否有人在C中实施 Cuckoo哈希？如果有一个开源，非GPL版本，它将是完美的！
既然亚当在评论中提到过这个问题，那么任何人都知道它为什么没用多少？这只是一个实施问题还是在实践中没有实现好的理论属性？
其他提示
正如其他答案所指出的那样，最简单的布谷鸟散列表确实要求该表为半空。但是，这个概念已经推广到 d -ary cuckoo hashing，其中每个键都有 d 可能的嵌套位置，而不是简单版本中的2个位置。 / p>
随着 d 的增加，可接受的负载系数会迅速增加。仅对于 d = 3，您已经可以使用大约75％的全表。缺点是您需要 d 独立散列函数。为此，我是Bob Jenkins的散列函数的粉丝（参见 http://burtleburtle.net /bob/c/lookup3.c ），您可能会发现它在布谷鸟哈希实现中很有用。
Cuckoo散列在学术界之外相对未被使用（除了硬件缓存，有时从中借鉴，但并未真正完全实现）。它需要一个非常稀疏的哈希表来获得插入的好时间 - 你真的需要将51％的表空为空以获得良好的性能。因此它既快又占用大量空间，或者减速并有效利用空间 - 从来都不是。其他算法既节省时间又节省空间，尽管只考虑时间或空间时它们比杜鹃更差。
以下是用于布谷鸟哈希表的代码生成器。检查生成器的许可证以验证输出是非GPL。它应该是，但无论如何都要检查。
- 亚当
即使这是一个老问题，有人可能仍然感兴趣：）
本文描述了并行d-ary cuckoo哈希的实现在GPU（CUDA / OpenCL）上。它的描述非常好，基于描述实现它非常容易。如果您对此主题感兴趣，一般值得一读。 （你需要ACM登录。）
IO语言在PHash.c中有一个。您可以在Github上找到 IO代码。 IO已获得BSD许可。
我看到了利用率这一点，但这是我尝试这种特殊散列方案的理由。如果我错过了什么，请告诉我。
据我所知，用于创建动态字典的哈希表的可能替代方案是（平衡的）二叉树和跳过列表。仅供讨论，让我们从键和值类型中抽象出来，让我们假设我们将通过 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 和“带有藏匿的杜鹃哈希＆quot;似乎能够在保持持续访问时间的同时增加负载系数。
对我来说，杜鹃哈希似乎是一种有价值的技术，我认为它已经被探索过;这就是我提问的原因。我不能说软件，但杜鹃散列当然在硬件中使用并且变得非常流行。网络设备的主要供应商一直在研究布谷鸟散列，有些已经使用过它。杜鹃散列的吸引力来自于持续的查找时间，当然还有接近恒定的插入时间。
虽然插入理论上可以是无界限的，但实际上它可以限制为表中行数的O（log n），并且在测量时，插入时间平均约为1.1 * d存储器访问。这比绝对最小值多10％！内存访问通常是网络设备的限制因素。
独立散列函数是必须的，正确选择它们很困难。祝你好运。
根据“onebyone”的评论，我已经实现并测试了几个版本的Cuckoo哈希来确定真正的内存需求。
在经过一些实验之后，声称你不需要重新计算直到桌子几乎达到50％，这似乎是真的，特别是如果“ stash ＆quot;诀窍是有效的。
问题是当你放大桌子时。通常的方法是将其尺寸加倍，但这导致新表仅使用了25％！
实际上，假设散列表有16个插槽，当我插入第8个元素编号时，我将耗尽好的插槽并且必须重新插入。我会加倍它，现在桌子是32个插槽，只占用了8个，这是75％的浪费！
这是为了获得“常数”而付出的代价。检索时间（以访问/比较次数的上限表示）。
我设计了一个不同的架构：从2的大于1的幂开始，如果表有n个槽而n是2的幂，则添加n / 2个槽，否则添加n / 3个槽：
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
等
假设只有在表格满50％时才会发生重新存在，这导致表格只有66％为空（1/3）而不是75％为空（1/4）之后一个reash（即最坏的情况）。
我也想通过（但我仍然需要检查数学）每次按sqrt（n）扩大，浪费的空间渐近接近50％。
当然，为减少内存消耗而支付的代价是最终需要的reash数量的增加。唉，没有什么是免费的。
如果有人有兴趣，我会进一步调查。
