布谷鸟过滤器
布谷鸟过滤器的论文《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 计算，那么必然会出现“指纹”相同的情况，也就是会出现误判的情况。
没有存储原数据，所以牺牲了数据的准确性，但是只保存了几个 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 的大佬提出来的东西。
我写这些东西的时候，就想看看大佬到底长什么样子。
但是神奇的事情发生了，我在墙内墙外翻了个底朝天，居然没有找到大佬的任何一张照片。
我的寻找，止步于发现了这个网站：
这个问题应该是在 9 年前就被人问出来了，也就是 2012 年的时候：
确实是在网上没有找到关于 Burton Howard Bloom 的照片。
真是一个神奇又低调的大佬。
有可能是一个倾国倾城的美男子吧。
最后说一句（求关注）
才疏学浅，难免会有纰漏，如果你发现了错误的地方，可以在后台提出来，我对其加以修改。
感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。
我是 why，一个主要写代码，经常写文章，偶尔拍视频的程序猿。
还有，欢迎关注我呀。
