这是 why 的第 86 篇原创文章

在晚期文章外面我已经写过布隆过滤器：

哎，这糟糕透顶的排版，一言难尽 …….

其实写文章和写代码一样。

看到一段辣眼睛的代码，正想口吐芳香：这是哪个煞笔写的代码？

后果定睛一看，代码上写的作者竟然是本人。

甚至还不敢相信，还要关上看一下 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 插入之后，图就变成了这样：

下面这个图其实起源就是论文外面：

这种相似于套娃的解决形式看是可行，然而总是有呈现循环踢出导致放不进 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 计算，那么必然会呈现“指纹”雷同的状况，也就是会呈现误判的状况。

没有存储原数据，所以就义了数据的准确性，然而只保留了几个 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 的照片。

真是一个神奇又低调的大佬。

有可能是一个倾国倾城的美男子吧。

最初说一句（求关注）

满腹经纶，难免会有纰漏，如果你发现了谬误的中央，能够在后盾提出来，我对其加以批改。

感谢您的浏览，我保持原创，非常欢送并感谢您的关注。

我是 why，一个次要写代码，常常写文章，偶然拍视频的程序猿。

还有，欢送关注我呀。