C语言中的布谷鸟散列

正如其他答案所指出的,最简单的布谷鸟哈希表要求表为半空。然而,这一概念已被推广到: D -二元布谷鸟散列,其中每个键都有 D 可能的嵌套位置,而不是简单版本中的2个位置。

可接受的负载系数随着时间的推移而迅速增加 D D =3时,您已经可以使用大约75%的表格。缺点是你需要 D 独立的散列函数。为此,我非常喜欢Bob Jenkins的哈希函数(参见 http://burtleburtle.net/bob/c/lookup3.c ),您可能会发现它在布谷鸟哈希实现中很有用。

布谷鸟散列在学术界之外是相对未被使用的(除了硬件缓存,硬件缓存有时借鉴了一些想法,但并没有完全实现)。它需要一个非常稀疏的哈希表来获得良好的插入时间——为了获得良好的性能,您确实需要有51%的表是空的。因此,它要么速度快,占用大量空间,要么速度慢,有效利用空间——决不能两者兼而有之。其他算法既节省时间又节省空间,尽管只考虑时间或空间时,它们比布谷鸟算法差。

这是一个 code generator for cuckoo hash tables . 检查生成器的许可证,以验证输出是否为非GPL。应该是的,但还是要检查一下。

-亚当

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

嗯

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

This paper 描述在GPU(CUDA/OpenCL)上并行d元布谷鸟哈希的实现。它的描述非常好,并且基于描述实现它非常容易。如果你对这个话题感兴趣,通常值得一读。(不过,您需要ACM登录。)

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

虽然插入理论上可以是无界的,但实际上它可以限定为表中行数的O(logn),并且当测量时,插入时间平均约为1.1*d个内存访问。这只比绝对最小值多10%!内存访问通常是网络设备的限制因素。

IO语言有一个,在PHash.c中。你可以找到 code for IO 在Github上。IO是BSD许可的。

我明白利用率的重要性,但这是我尝试这种特殊哈希方案的理由。如果我错过了什么,请告诉我。

void * .

对于二叉树,我会:

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

因此,假设指针的大小都相同 s ,储存 N 字节。

SkipList几乎等同于节点中指针的平均数量为2。

在哈希表中,我会:

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

因此,每个项目只需要2个 s 要存储的字节数。如果负载系数为50%,则存储 N 项目我将需要相同的4 s 字节作为树。

这对我来说似乎并不太糟糕:布谷鸟哈希表将占用与二叉树大致相同的内存量,但会给我O(1)访问时间,而不是O(logn)。

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

d-ary cuckoo hashing cuckoo hashing with a stash “似乎能够在保持恒定访问时间的同时增加负载系数。

布谷鸟哈希对我来说似乎是一种很有价值的技术,我认为它已经被探索过了;这就是我问题的原因。

根据“一个接一个”的评论,我已经实现并测试了几个版本的布谷鸟哈希,以确定真正的内存需求。

经过一些实验,声称在桌子几乎满了50%之前你不必重新翻动的说法似乎是正确的,特别是如果 stash “诡计被实施了。

问题是当你放大桌子的时候。通常的方法是将其大小加倍,但这导致新表的利用率仅为25%!

事实上,假设hashtable有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)。

我还计算出(但我仍然需要检查数学)每次放大sqrt(n),浪费的空间逐渐接近50%。

当然,为减少内存消耗而付出的代价是最终需要的研究次数的增加。唉,没有什么是免费的。