一、布隆过滤器

​ 在说布谷鸟过滤器之前，有必要先简要介绍一下布隆过滤器，它可以判断在一个存储表中是否含有某个元素(e)。底层中使用bitmap实现，其初始值为0。存储某个数据时，会有多次(示例中为3次)hash运算，将运算结果作为坐标，将对应的bit位改为1，由此标记它是否存在于表中。当几次哈希的结果中有一次不为1，都判断元素不存在。

布隆过滤器

​ 一些问题：布隆过滤器不支持删除，且计算坐标时对应多个不同位点，效率低下。

这个网站可以直观地观察布隆过滤器插入数据的过程。

二、布谷鸟过滤器

为啥要叫这个名？

​ 布谷鸟交配后，雌性布谷鸟就准备产蛋了，但它却不会自己筑巢。它会来到像知更鸟、刺嘴莺等那些比它小的鸟类的巢中，移走原来的那窝蛋中的一个，用自己的蛋来取而代之。相对于它的体形来说，它的蛋是偏小的，而且蛋上的斑纹同它混入的其他鸟的蛋也非常相似，所以不易被分辨出来。如果不是这样，它的蛋肯定会被扔出去。

一种鸠占鹊巢的策略，最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，此时

  • 如果两个位置都为为空则将key随机存入其中一个位置
  • 如果只有一个位置为空则存入为空的位置
  • 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置

当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个踢出阈值，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。

​ 切入正题，布谷鸟过滤器可以说是增强版的布隆过滤器，由桶（bucket）数组组成，一个桶中可以有多个条目。如下图中，单个桶T1或T2都有d个条目，每个条目拥有d个指纹的位置，每个指纹大小为5bits。此时每个桶大小是5*d bits。

布布谷鸟过滤器

插入

与布谷鸟散列略有不同。在数组中存储的是指纹，也就是hash之后的bit位，查询的时候主要是看对应位置上有没有对应的指纹信息。伪码如下：

1
2
3
fp = fingerprint(x)
h1 = hash(x)
h2 = h1 ^ hash(fp)// 异或运算

h2的位置是根据h1的位置计算出来的，也就是说我们知道了其中一个位置，就可以直接获取到另外一个位置，不需要再做全量的hash运算。因为使用的异或运算，所以这两个位置具有对偶性。这也是提高查询效率的一个点。只要保证 hash(fp) !=0，那么就可以确保 h2!=h1，也就可以确保不会出现自己踢自己的死循环问题了。

这里还有个注意点：就是hash运算的时候，并没有对值进行长度取模运算，那么他是如何保证计算出来hash坐标，一定是在数组长度范围内呢？这就说到布谷鸟过滤器的一个限制条件了，那就是强制数组的长度必须是 2 的指数倍
这个限制带来的好处就是，进行异或运算时，可以保证计算出来的下标一定是落在数组中的。