4.如果要求错误率小于3%,那么在许多实际应用中,它比布隆过滤器占用的空间更小。
布谷鸟过滤器的 API 无非就是插入、查询和删除嘛。
其中最重要的就是插入,看一下:
论文中的部分,你大概瞟一眼,看不明白没关系,我这不是马上给你分析一波吗。
插入部分的伪代码,可以看到一点布谷鸟 hash 的影子,因为就是基于这个东西来的。
那么最大的变化在什么地方呢?
无非就是 hash 函数的变化。
看的我目瞪狗呆,心想:还有这种骚操作呢?
首先,我们回忆一下布谷鸟 hash,它存储的是插入元素的原始值,比如 x,x 会经过两个 hash 函数,如果我们记数组的长度为 L,那么就是这样的:
p1 = hash1(x) % L
p2 = hash2(x) % L
而布谷鸟过滤器计算位置是怎样的呢?
h1(x) = hash(x),