布隆,牛逼!布谷鸟,牛逼! (3)

4.如果要求错误率小于3%,那么在许多实际应用中,它比布隆过滤器占用的空间更小。

布谷鸟过滤器的 API 无非就是插入、查询和删除嘛。

其中最重要的就是插入,看一下:

布隆,牛逼!布谷鸟,牛逼!

论文中的部分,你大概瞟一眼,看不明白没关系,我这不是马上给你分析一波吗。

插入部分的伪代码,可以看到一点布谷鸟 hash 的影子,因为就是基于这个东西来的。

那么最大的变化在什么地方呢?

无非就是 hash 函数的变化。

看的我目瞪狗呆,心想:还有这种骚操作呢?

布隆,牛逼!布谷鸟,牛逼!

首先,我们回忆一下布谷鸟 hash,它存储的是插入元素的原始值,比如 x,x 会经过两个 hash 函数,如果我们记数组的长度为 L,那么就是这样的:

p1 = hash1(x) % L

p2 = hash2(x) % L

而布谷鸟过滤器计算位置是怎样的呢?

h1(x) = hash(x),

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpfzsx.html