大家都知道,在计算机中,IO一直是一个瓶颈,很多框架以及技术甚至硬件都是为了降低IO操作而生,今天聊一聊过滤器,先说一个场景:
我们业务后端涉及数据库,当请求消息查询某些信息时,可能先检查缓存中是否有相关信息,有的话返回,如果没有的话可能就要去数据库里面查询,这时候有一个问题,如果很多请求是在请求数据库根本不存在的数据,那么数据库就要频繁响应这种不必要的IO查询,如果再多一些,数据库大多数IO都在响应这种毫无意义的请求操作,那么如何将这些请求阻挡在外呢?过滤器由此诞生:
- 布隆过滤器 -
布隆过滤器(Bloom Filter)大概的思路就是,当你请求的信息来的时候,先检查一下你查询的数据我这有没有,有的话将请求压给数据库,没有的话直接返回,是如何做到的呢?
如图,一个bitmap用于记录,bitmap原始数值全都是0,当一个数据存进来的时候,用三个Hash函数分别计算三次Hash值,并且将bitmap对应的位置设置为1,上图中,bitmap 的1,3,6位置被标记为1,这时候如果一个数据请求过来,依然用之前的三个Hash函数计算Hash值,如果是同一个数据的话,势必依旧是映射到1,3,6位,那么就可以判断这个数据之前存储过,如果新的数据映射的三个位置,有一个匹配不上,假如映射到1,3,7位,由于7位是0,也就是这个数据之前并没有加入进数据库,所以直接返回。
布隆过滤器的问题
上面这种方式,应该你已经发现了,布隆过滤器存在一些问题:
第一方面,布隆过滤器可能误判:
假如有这么一个情景,放入数据包1时,将bitmap的1,3,6位设置为了1,放入数据包2时将bitmap的3,6,7位设置为了1,此时一个并没有存过的数据包请求3,做三次哈希之后,对应的bitmap位点分别是1,6,7,这个数据之前并没有存进去过,但是由于数据包1和2存入时将对应的点设置为了1,所以请求3也会压倒数据库上,这种情况,会随着存入的数据增加而增加。
第二方面,布隆过滤器没法删除数据,删除数据存在以下两种困境:
一是,由于有误判的可能,并不确定数据是否存在数据库里,例如数据包3。
二是,当你删除某一个数据包对应位图上的标志后,可能影响其他的数据包,例如上面例子中,如果删除数据包1,也就意味着会将bitmap1,3,6位设置为0,此时数据包2来请求时,会显示不存在,因为3,6两位已经被设置为0。
- 布隆过滤器增强版 -
为了解决上面布隆过滤器的问题,出现了一个增强版的布隆过滤器(Counting Bloom Filter),这个过滤器的思路是将布隆过滤器的bitmap更换成数组,当数组某位置被映射一次时就+1,当删除时就-1,这样就避免了普通布隆过滤器删除数据后需要重新计算其余数据包Hash的问题,但是依旧没法避免误判。
- 布谷鸟过滤器 -
为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。相比布谷鸟过滤器，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。
查询性能弱是因为布隆过滤器需要使用多个 hash 函数探测位图中多个不同的位点，这些位点在内存上跨度很大，会导致 CPU 缓存行命中率低。
空间效率低是因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。从这一点出发，似乎布隆过滤器的空间伸缩性更强一些。
不支持反向删除操作这个问题着实是击中了布隆过滤器的软肋。在一个动态的系统里面元素总是不断的来也是不断的走。布隆过滤器就好比是印迹，来过来就会有痕迹，就算走了也无法清理干净。比如你的系统里本来只留下 1kw 个元素，但是整体上来过了上亿的流水元素，布隆过滤器很无奈，它会将这些流失的元素的印迹也会永远存放在那里。随着时间的流失，这个过滤器会越来越拥挤，直到有一天你发现它的误判率太高了，不得不进行重建。
布谷鸟过滤器在论文里声称自己解决了这个问题，它可以有效支持反向删除操作。而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。
为啥要取名布谷鸟呢?
有个成语，「鸠占鹊巢」,布谷鸟也是,布谷鸟从来不自己筑巢。它将自己的蛋产在别人的巢里，让别人来帮忙孵化。待小布谷鸟破壳而出之后，因为布谷鸟的体型相对较大，它又将养母的其它孩子（还是蛋）从巢里挤走 —— 从高空摔下夭折了。
- 布谷鸟哈希 -
最简单的布谷鸟哈希结构是一维数组结构，会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空，那么就可以将元素直接放进去。但是如果这两个位置都满了，它就不得不「鸠占鹊巢」，随机踢走一个，然后自己霸占了这个位置。
p1 = hash1(x) % l
p2 = hash2(x) % l
复制代码
不同于布谷鸟的是，布谷鸟哈希算法会帮这些受害者（被挤走的蛋）寻找其它的窝。因为每一个元素都可以放在两个位置，只要任意一个有空位置，就可以塞进去。所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空，如果空了，自己挪过去也就皆大欢喜了。但是如果这个位置也被别人占了呢？好，那么它会再来一次「鸠占鹊巢」，将受害者的角色转嫁给别人。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。
- 布谷鸟哈希的问题 -
但是会遇到一个问题，那就是如果数组太拥挤了，连续踢来踢去几百次还没有停下来，这时候会严重影响插入效率。这时候布谷鸟哈希会设置一个阈值，当连续占巢行为超出了某个阈值，就认为这个数组已经几乎满了。这时候就需要对它进行扩容，重新放置所有元素。
还会有另一个问题，那就是可能会存在挤兑循环。比如两个不同的元素，hash 之后的两个位置正好相同，这时候它们一人一个位置没有问题。但是这时候来了第三个元素，它 hash 之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。不过让三个不同的元素经过两次 hash 后位置还一样，这样的概率并不是很高，除非你的 hash 算法太挫了。
布谷鸟哈希算法对待这种挤兑循环的态度就是认为数组太拥挤了，需要扩容（实际上并不是这样）。
优化
上面的布谷鸟哈希算法的平均空间利用率并不高，大概只有 50%。到了这个百分比，就会很快出现连续挤兑次数超出阈值。这样的哈希算法价值并不明显，所以需要对它进行改良。
改良的方案之一是增加 hash 函数，让每个元素不止有两个巢，而是三个巢、四个巢。这样可以大大降低碰撞的概率，将空间利用率提高到 95%左右。
另一个改良方案是在数组的每个位置上挂上多个座位，这样即使两个元素被 hash 在了同一个位置，也不必立即「鸠占鹊巢」，因为这里有多个座位，你可以随意坐一个。除非这多个座位都被占了，才需要进行挤兑。很明显这也会显著降低挤兑次数。这种方案的空间利用率只有 85%左右，但是查询效率会很高，同一个位置上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。
所以更加高效的方案是将上面的两个改良方案融合起来，比如使用 4 个 hash 函数，每个位置上放 2 个座位。这样既可以得到时间效率，又可以得到空间效率。这样的组合甚至可以将空间利用率提到高 99%，这是非常了不起的空间效率。
布谷鸟过滤器
布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。这里过滤器牺牲了数据的精确性换取了空间效率。正是因为存储的是元素的指纹信息，所以会存在误判率，这点和布隆过滤器如出一辙。
首先布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后，它需要计算出另一个对偶位置。而计算这个对偶位置是需要元素本身的，我们来回忆一下前面的哈希位置计算公式。
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l
我们知道了 p1 和 x 的指纹，是没办法直接计算出 p2 的。
特殊的 hash 函数
布谷鸟过滤器巧妙的地方就在于设计了一个独特的 hash 函数，使得可以根据 p1 和 元素指纹 直接计算出 p2，而不需要完整的 x 元素。
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 异或
从上面的公式中可以看出，当我们知道 fp 和 p1，就可以直接算出 p2。同样如果我们知道 p2 和 fp，也可以直接算出 p1 —— 对偶性。
p1 = p2 ^ hash(fp)
所以我们根本不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。而且只需要确保 hash(fp) != 0 就可以确保 p1 != p2，如此就不会出现自己踢自己导致死循环的问题。
也许你会问为什么这里的 hash 函数不需要对数组的长度取模呢？实际上是需要的，但是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时，忽略掉低 n 位 之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。
在早期文章里面我曾经写过布隆过滤器：
哎，这糟糕透顶的排版，一言难尽.......
其实写文章和写代码一样。
看到一段辣眼睛的代码，正想口吐芬芳：这是哪个煞笔写的代码？
结果定睛一看，代码上写的作者居然是自己。
甚至还不敢相信，还要打开看一下 git 的提交记录。
发现确实是自己几个月前亲手敲出来，并且提交的代码。
于是默默的改掉。
出现这种情况我也常常安慰自己：没事，这是好事啊，说明我在进步。
好了，说正事。
当时的文章里面我说布隆过滤器的内部原理我说不清楚。
其实我只是懒得写而已，这玩意又不复杂，有啥说不清楚的？
布隆过滤器
布隆过滤器，在合理的使用场景中具有四两拨千斤的作用，由于使用场景是在大量数据的场景下，所以这东西类似于秒杀，虽然没有真的落地用过，但是也要说的头头是道。
常见于面试环节：比如大集合中重复数据的判断、缓存穿透问题等。
先分享一个布隆过滤器在腾讯短视频产品中的真实案例：
https://toutiao.io/posts/mtrvsx/preview
那么布隆过滤器是怎么做到上面的这些需求的呢？
首先，布隆过滤器并不存储原始数据，因为它的功能只是针对某个元素，告诉你该元素是否存在而已。并不需要知道布隆过滤器里面有那些元素。
当然，如果我们知道容器里面有哪些元素，就可以知道一个元素是否存在。
但是，这样我们需要把出现过的元素都存储下来，大数据量的情况下，这样的存储就非常的占用空间。
布隆过滤器是怎么做到不存储元素，又知道一个元素是否存在呢？
说破了其实就很简单：一个长长的数组加上几个 Hash 算法。
在上面的示意图中，一共有三个不同的 Hash 算法、一个长度为 10 的数组，数组里面存储的是 bit 位，只放 0 和 1。初始为 0。
假设现在有一个元素 [why] ，要经过这个布隆过滤器。
首先 [why] 分别经过三个 Hash 算法，得出三个不同的数字。
Hash 算法可以保证得出的数字是在 0 到 9 之间，即不超过数组长度。
我们假设计算结果如下：
- Hash1(why)=1
- Hash2(why)=4
- Hash3(why)=8
对应到图片中就是这样的：
这时，如果 [why] 又来了，经过 Hash 算法得出的下标还是 1,4,8，发现数组对应的位置上都是 1。表明这个元素极有可能出现过。
注意，这里说的是极有可能。也就是说会存在一定的误判率。
我们先再存入一个元素 [jay]。
- Hash1(jay)=0
- Hash2(jay)=5
- Hash3(jay)=8
此时，我们把两个元素汇合一下，就有了下面这个图片：
其中的下标为 8 的位置，比较特殊，两个元素都指向了它。
这个图片这样看起来有点难受，我美化一下：
好了，现在这个数组变成了这样：
你说，你只看这个玩意，你能知道这个过滤器里面曾经有过 why 和 jay 吗？
别说你不知道了，就连过滤器本身都不知道。
现在，假设又来了一个元素 [Leslie]，经过三个 Hash 算法，计算结果如下：
- Hash1(Leslie)=0
- Hash2(Leslie)=4
- Hash3(Leslie)=5
通过上面的元素，可以知道此时 0,4,5 这三个位置上都是 1。
布隆过滤器就会觉得这个元素之前可能出现过。于是就会返回给调用者：[Leslie]曾经出现过。
但是实际情况呢？
其实我们心里门清，[Leslie] 不曾来过。
这就是误报的情况。
这就是前面说的：布隆过滤器说存在的元素，不一定存在。
而一个元素经过某个 hash 计算后，如果对应位置上的值是 0，那么说明该元素一定不存在。
但是它有一个致命的缺点，就是不支持删除。
为什么？
假设要删除 [why]，那么就要把 1,4,8 这三个位置置为 0。
但是你想啊，[jay] 也指向了位置 8 呀。
如果删除 [why] ，位置 8 变成了 0，那么是不是相当于把 [jay] 也移除了？
为什么不支持删除就致命了呢？
你又想啊，本来布隆过滤器就是使用于大数据量的场景下，随着时间的流逝，这个过滤器的数组中为 1 的位置越来越多，带来的结果就是误判率的提升。从而必须得进行重建。
所以，文章开始举的腾讯的例子中有这样一句话：
除了删除这个问题之外，布隆过滤器还有一个问题：查询性能不高。
因为真实场景中过滤器中的数组长度是非常长的，经过多个不同 Hash 函数后，得到的数组下标在内存中的跨度可能会非常的大。跨度大，就是不连续。不连续，就会导致 CPU 缓存行命中率低。
这玩意，这么说呢。就当八股文背起来吧。
踏雪留痕，雁过留声，这就是布隆过滤器。
如果你想玩一下布隆过滤器，可以访问一下这个网站：
https://www.jasondavies.com/bloomfilter/
左边插入，右边查询：
如果要布隆过滤器支持删除，那么怎么办呢？
有一个叫做 Counting Bloom Filter。
它用一个 counter 数组，替换数组的比特位，这样一比特的空间就被扩大成了一个计数器。
用多占用几倍的存储空间的代价，给 Bloom Filter 增加了删除操作。
这也是一个解决方案。
但是还有更好的解决方案，那就是布谷鸟过滤器。
另外，关于布隆过滤器的误判率，有一个数学推理公式。很复杂，很枯燥，就不讲了，有兴趣的可以去了解一下。
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
布谷鸟 hash
布谷鸟过滤器，第一次出现是在 2014 年发布的一篇论文里面：《Cuckoo Filter: Practically Better Than Bloom》
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
但是在讲布谷鸟过滤器之前，得简单的铺垫一下 Cuckoo hashing，也就是布谷鸟 hash 的知识。
因为这个词是论文的关键词，在文中出现了 52 次之多。
Cuckoo hashing，最早出现在这篇 2001 年的论文之中：
https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf
主要看论文的这个地方：
它的工作原理，总结起来是这样的：
它有两个 hash 表，记为 T1，T2。
两个 hash 函数，记为 h1，h2。
当一个不存在的元素插入的时候，会先根据 h1 计算出其在 T1 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，则根据 h2 计算出其在 T2 表的位置，如果该位置为空则可以放进去。
如果该位置不为空，就把当前位置上的元素踢出去，然后把当前元素放进去就行了。
也可以随机踢出两个位置中的一个，总之会有一个元素被踢出去。
被踢出去的元素怎么办呢？
没事啊，它也有自己的另外一个位置。
论文中的伪代码是这样的：
看不懂没关系，我们画个示意图：
上面的图说的是这样的一个事儿：
我想要插入元素 x，经过两个 hash 函数计算后，它的两个位置分别为 T1 表的 2 号位置和 T2 表的 1 号位置。
两个位置都被占了，那就随机把 T1 表 2 号位置上的 y 踢出去吧。
而 y 的另一个位置被 z 元素占领了。
于是 y 毫不留情把 z 也踢了出去。
z 发现自己的备用位置还空着（虽然这个备用位置也是元素 v 的备用位置），赶紧就位。
所以，当 x 插入之后，图就变成了这样：
上面这个图其实来源就是论文里面（a）：
这种类似于套娃的解决方式看是可行，但是总是有出现循环踢出导致放不进 x 的问题。
比如上图中的（b）。
当遇到这种情况时候，说明布谷鸟 hash 已经到了极限情况，应该进行扩容，或者 hash 函数的优化。
所以，你再次去看伪代码的时候，你会明白里面的 MaxLoop 的含义是什么了。
这个 MaxLoop 的含义就是为了避免相互踢出的这个过程执行次数太多，设置的一个阈值。
其实我理解，布谷鸟 hash 是一种解决 hash 冲突的骚操作。
如果你想上手玩一下，可以访问这个网站：
http://www.lkozma.net/cuckoo_hashing_visualization/
当踢来踢去了 16 （MaxLoop）次还没插入完成后，它会告诉你，需要 rehash 并对数组扩容了：
布谷鸟 hash 就是这么一回事，一场踢来踢去的游戏。
接着，我们看布谷鸟过滤器。
布谷鸟过滤器
布谷鸟过滤器的论文《Cuckoo Filter: Practically Better Than Bloom》开篇第一页，里面有这样一段话。
直接和布隆过滤器正面刚：我布谷鸟过滤器，就是比你屌一点。
上来就指着别人的软肋怼：
标准的布隆过滤器的一大限制是不能删除已经存在的数据。如果使用它的变种，比如 Counting Bloom Filter，但是空间却被撑大了 3 到 4 倍，巴拉巴拉巴拉......
而我就比较骚了：
这篇论文将要证明的是，与标准布隆过滤器相比，我支持删除，在空间或性能上并不需要更高的开销。
我，布谷鸟过滤器是一个实用的数据结构，提供了四大优势：
- 1.支持动态的新增和删除元素。
- 2.提供了比传统布隆过滤器更高的查找性能，即使在空间接近满的情况下（比如空间利用率达到 95% 的时候）。
- 3.比诸如商过滤器（quotient filter，另一种过滤器）之类的替代方案更容易实现。
- 4.如果要求错误率小于 3%，那么在许多实际应用中，它比布隆过滤器占用的空间更小。
布谷鸟过滤器的 API 无非就是插入、查询和删除嘛。
其中最重要的就是插入，看一下：
论文中的部分，你大概瞟一眼，看不明白没关系，我这不是马上给你分析一波吗。
插入部分的伪代码，可以看到一点布谷鸟 hash 的影子，因为就是基于这个东西来的。
那么最大的变化在什么地方呢？
无非就是 hash 函数的变化。
看的我目瞪狗呆，心想：
首先，我们回忆一下布谷鸟 hash，它存储的是插入元素的原始值，比如 x。
x 会经过两个 hash 函数，如果我们记数组的长度为 L，那么就是这样的：
- p1 = hash1(x) % L
- p2 = hash2(x) % L
非常容易理解，是我认知范围内的东西。
而布谷鸟过滤器计算位置是怎样的呢？
- h1(x) = hash(x),
- h2(x) = h1(x) ⊕ hash(x’s fingerprint).
我们可以看到，计算 h2（位置2）时，对 x 的 fingerprint 进行了一个 hash 计算。
“指纹”的概念一会再说，我们先关注位置的计算。
这题就稍微有点超纲了，我慢慢说。
上面算法中的异或运算确保了一个重要的性质：位置 h2 可以通过位置 h1 和 h1 中存储的“指纹”计算出来。
说人话就是：只要我们知道一个元素的位置（h1）和该位置里面存储的“指纹”信息，那么我们就可以知道该“指纹”的备用位置（h2）。
因为使用的异或运算，所以这两个位置具有对偶性。
由于具有对偶性，那么其实我们只要知道其中的任意一个位置，就能知道对应的另外一个位置。
只要保证 hash(x’s fingerprint) !=0，那么就可以确保 h2!=h1，也就可以确保不会出现自己踢自己的死循环问题。
另外，为什么要对“指纹”进行一个 hash 计算之后，在进行异或运算呢？
论文中给出了一个反证法：如果不进行 hash 计算，假设“指纹”的长度是 8bit，那么其对偶位置算出来，距离当前位置最远也才 256。
为啥，论文里面写了：
因为如果“指纹”的长度是 8bit，那么异或操作只会改变当前位置 h1(x) 的低 8 位，高位不会改变。
就算把低 8 位全部改了，算出来的位置也就是我刚刚说的：最远 256 位。
所以，对“指纹”进行哈希处理可确保被踢出去的元素，可以重新定位到哈希表中完全不同的存储桶中，从而减少哈希冲突并提高表利用率。
然后这个 hash 函数还有个问题你发现了没？
它没有对数组的长度进行取模，那么它怎么保证计算出来的下标一定是落在数组中的呢？
这个就得说到布谷鸟过滤器的另外一个限制了。
其强制数组的长度必须是 2 的指数倍。
2 的指数倍的二进制一定是这样的：10000000...（n个0）。
这个限制带来的好处就是，进行异或运算时，可以保证计算出来的下标一定是落在数组中的。
这个限制带来的坏处就是：
- 布谷鸟过滤器：我支持删除操作。
- 布隆过滤器：我不需要限制长度为 2 的指数倍。
- 布谷鸟过滤器：我查找性能比你高。
- 布隆过滤器：我不需要限制长度为 2 的指数倍。
- 布谷鸟过滤器：我空间利用率也高。
- 布隆过滤器：我不需要限制长度为 2 的指数倍。
- 布谷鸟过滤器：我烦死了，TMD！
接下来，说一下“指纹”。
这是论文中第一次出现“指纹”的地方。
“指纹”其实就是插入的元素进行一个 hash 计算，而 hash 计算的产物就是几个 bit 位。
布谷鸟过滤器里面存储的就是元素的“指纹”。
查询数据的时候，就是看看对应的位置上有没有对应的“指纹”信息：
删除数据的时候，也只是抹掉该位置上的“指纹”而已：
由于是对元素进行 hash 计算，那么必然会出现 hash 碰撞的问题，也就是“指纹”相同的情况，也就是会出现误判的情况。
没有存储原数据，所以牺牲了数据的准确性，但是只保存了几个 bit，因此提升了空间效率。
说到空间利用率，你想想布谷鸟 hash 的空间利用率是多少？
在完美的情况下，也就是没有发生哈希冲突之前，它的空间利用率最高只有 50%。
因为没有发生冲突，说明至少有一半的位置是空着的。
除了只存储“指纹”，布谷鸟过滤器还能怎么提高它的空间利用率的呢？
看看论文里面怎么说的：
前面的 (a)、(b) 很简单，还是两个 hash 函数，但是没有用两个数组来存数据，就是基于一维数组的布谷鸟 hash ，核心还是踢来踢去，不多说了。
重点在于 (c)，对数组进行了展开，从一维变成了二维。
每一个下标，可以放 4 个元素了。
你可以理解为之前一个下标是一个圆板凳，上面只能放一个屁股。
而现在你可以把一个下标看成一个四方桌，可以坐四个人，打麻将了。
这样一个小小的转变，空间利用率从 50% 直接到了 98%：
我就问你怕不怕？
上面截图的论文中的第一点就是在陈诉这样一个事实：
当 hash 函数固定为 2 个的时候，如果一个下标只能放一个元素，那么空间利用率是 50%。
但是如果一个下标可以放 2，4，8 个元素的时候，空间利用率就会飙升到 84%，95%，98%。
到这里，我们明白了布谷鸟过滤器对布谷鸟 hash 的优化点和对应的工作原理。
看起来一切都是这么的完美。
各项指标都比布隆过滤器好，主打的是支持删除的操作。
但是真的这么好吗？
当我看到论文第六节的这一段的时候，沉默了：
对重复数据进行限制：如果需要布谷鸟过滤器支持删除，它必须知道一个数据插入过多少次。不能让同一个数据插入 kb+1 次。其中 k 是 hash 函数的个数，b 是一个下标的位置能放几个元素。
比如 2 个 hash 函数，一个二维数组，它的每个下标最多可以插入 4 个元素。那么对于同一个元素，最多支持插入 8 次。
例如下面这种情况：
why 已经插入了 8 次了，如果再次插入一个 why，则会出现循环踢出的问题，直到最大循环次数，然后返回一个 false。
怎么避免这个问题呢？
我们维护一个记录表，记录每个元素插入的次数就行了。
虽然逻辑简单，但是架不住数据量大呀。你想想，这个表的存储空间又怎么算呢？
想想就难受。
如果你要用布谷鸟过滤器的删除操作，那么这份难受，你不得不承受。
最后，再看一下各个类型过滤器的对比图吧：
还有，其中的数学推理过程，不说了，看的眼睛疼，而且看这玩意容易掉头发。
荒腔走板
你知道为什么叫做“布谷鸟”吗？
布谷鸟，又叫杜鹃。
《本草纲目》有这样的记载：“鸤鸠不能为巢，居他巢生子”。这里描述的就是杜鹃的巢寄生行为。巢寄生指的是鸟类自己不筑巢，把卵产在其他种类鸟类的巢中，由宿主代替孵化育雏的繁殖方式，包括种间巢寄生（寄生者和宿主为不同物种）和种内巢寄生（寄生者和宿主为同一物种）。现今一万多种鸟类中，有一百多种具有巢寄生的行为，其中最典型的就是大杜鹃。
就是说它自己把蛋下到别的鸟巢中，让别的鸟帮它孵小鸡。哦不，孵小鸟。
小杜鹃孵出来了后，还会把同巢的其他亲生鸟蛋推出鸟巢，好让母鸟专注于喂养它。
我的天呐，这也太残忍了吧。
但是这个“推出鸟巢”的动作，不正和上面描述的算法是一样的吗？
只是我们的算法还更加可爱一点，被推出去的鸟蛋，也就是被踢出去的元素，会放到另外一个位置上去。
我查阅资料的时候，当我知道布谷鸟就是杜鹃鸟的时候我都震惊了。
好多诗句里面都有杜鹃啊，比如我很喜欢的，唐代诗人李商隐的《锦瑟》：
锦瑟无端五十弦，一弦一柱思华年。
庄生晓梦迷蝴蝶，望帝春心托杜鹃。
沧海月明珠有泪，蓝田日暖玉生烟。
此情可待成追忆，只是当时已惘然。
自古以来。对于这诗到底是在说“悼亡”还是“自伤”的争论就没停止过。
但是这重要吗？
对我来说这不重要。
重要的是，在适当的时机，适当的气氛下，回忆起过去的事情的时候能适当的来上一句：“此情可待成追忆，只是当时已惘然”。
而不是说：哎，现在想起来，很多事情没有好好珍惜，真TM后悔。
哦，对了。
写文章的时候我还发现了一件事情。
布隆过滤器是 1970 年，一个叫做 Burton Howard Bloom 的大佬提出来的东西。
我写这些东西的时候，就想看看大佬到底长什么样子。
但是神奇的事情发生了，我前前后后，花了几天，墙内墙外翻了个底朝天，居然没有找到大佬的任何一张照片。
我的寻找，止步于发现了这个网站：
https://www.quora.com/Where-can-one-find-a-photo-and-biographical-details-for-Burton-Howard-Bloom-inventor-of-the-Bloom-filter
这个问题应该是在 9 年前就被人问出来了，也就是 2012 年的时候：
确实是在网上没有找到关于 Burton Howard Bloom 的照片。
真是一个神奇又低调的大佬。
有可能是一个倾国倾城的美男子吧。