C中的杜鹃哈希

有人在C中实现了Cuckoo散列吗？如果有一个开源,非GPL版本,它将是完美的!

亚当在他的评论中提到它,任何人都知道它为什么用得不多？这只是一个实施问题还是在实践中没有实现好的理论属性？

正如其他答案所指出的那样,最简单的cuckoo哈希表确实要求表是半空的.然而,这一概念已经推广到d进制杜鹃散列,其中每个键ð可能的地方筑巢,如简单的版本而不是2位.

随着d增加,可接受的负载系数迅速增加.仅对于d = 3,您已经可以使用大约75%的全表.缺点是,你需要d独立的哈希函数.我是Bob Jenkins为此目的的哈希函数的粉丝(请参阅http://burtleburtle.net/bob/c/lookup3.c),您可能会发现它在布谷鸟哈希实现中很有用.

杜鹃散列在学术界之外相对未被使用(除了硬件缓存,有时从中借鉴,但并未真正完全实现).它需要一个非常稀疏的哈希表来获得插入的好时间 - 你真的需要将51%的表空为空以获得良好的性能.因此它既快又占用大量空间,或者减速并有效利用空间 - 从来没有.其他算法既有时间和空间效率,但只考虑时间或空间时它们比杜鹃更差.

这是一个用于cuckoo哈希表的代码生成器.检查生成器的许可证以验证输出是非GPL.它应该是,但无论如何检查.

-亚当

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

HTH