在早期文章里面我曾经写过布隆过滤器：

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

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

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

结果定睛一看，代码上写的作者居然是自己。

甚至还不敢相信，还要打开看一下 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