谈谈布隆过滤器

先来一段官方的介绍：

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

嗯，你好像没听懂。

现在这里有一个长度为m的大数组，所有位置初始值都是0。

下图时是当m为8时的结构。（实际上，m是很大很大的）

有k个哈希函数（Hash1,Hash2,Hash3...），每个函数都会将一个输入映射成一个值，这个值便是数组上的下标。

现在输入一个值s1，用k个哈希函数分别进行运算，得到k个不同的值（r1,r2,r3...），将数组上下标为（r1,r2,r3...）的值置为1。

我们现在输入baidu，经过3个哈希函数运算后，得到1，4，7，则将数组上第1，4，7的位置上的元素置为1。

好的，我们现在继续输入一个值，例如输入tencent。同理，将3，4，8上的元素置为1。（此时第4个位置形成了覆盖）

现在，我们要测试test与yang这两个字符串，是否在（baidu，tencent）这个集合中。

我们输入test，经过三个哈希函数运算后，得到1，3，8。这个时候可以发现，这个数组上的第1，3，8位置已经被置为1了，那我们可以说，test值可能在（baidu，tencent）这个集合中。

最后，我们输入yang。此时，经过运算后，得到1，2，3。我们可以发现，第2个位置上，元素依然是0。那么，我们可以斩钉截铁得说，yang必然不在这个集合中。

当然，如果我们增大集合，继续往（baidu，tencent）中增加更多的字符串，到最后，数组上的所有位置可能都为1。这个时候，不管我们查找任意一个字符串，得出的结果都是该字符串可能存在于集合中，这样的结果没有任何意义。

因此，在实际运用中，数组的长度将会很大，哈希函数也会很多，从而提高匹配的准确性，但绝不是100%的精度，存在误判。

讲到这里，你也许对布隆过滤器有了新认识。原来布隆过滤器可以告诉我们一个字符串可能存在于一个集合中，也可以告诉我们一个字符串绝对不存在于一个集合中。注意这里的可能和绝对！

布隆过滤器说的存在，那是可能存在。但是说的不存在，那就是一定不存在。他是存在一定误判率的。

既然布隆过滤器存在误判率，那我们为啥要用它？

不同的数据结构有不同的适用场景和优缺点，我们需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。

事实上，布隆过滤器被广泛用于网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透问题。通过介绍已经知晓布隆过滤器的作用是检索一个元素是否在集合中。

可能有人认为这个功能非常简单，直接放在redis中或者数据库中查询就好了。

又或者当数据量较小，内存又足够大时，使用hashMap或者hashSet等结构就好了。

但是如果当这些数据量很大，数十亿甚至更多，内存装不下且数据库检索又极慢的情况，我们应该如何去处理？这个时候我们不妨考虑下布隆过滤器，因为它是一个空间效率占用极少和查询时间极快的算法，但是需要业务可以忍受一个判断失误率。

现在我们知道，布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么？

答案是不可以，例如在上面的图例中，第4个元素上，被baidu和tencent共同覆盖。

一旦你删除其中一个值例如 tencent ，而将第4个元素置为 0，那么下次判断另一个值例如 baidu”是否存在的话，会直接返回 false，和预期结果不符。

如何解决这个问题，答案是计数删除。但是计数删除需要存储统计数，而不是简单的全部置为1，需要进行自增操作。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。

在计数删除下，即使我们删除tencent，并将第4个元素减1，此时第四个元素还是1，依然可以判断出baidu可能存在于集合中。

什么是缓存穿透？

我们常在应用层和数据层中间加上缓存层，用于提高查询效率，保证服务可靠性等。

但是，如果此时有大量请求瞬间涌进来，查询一个自增id为负数的数据，那显然，缓存无法命中，直接打到数据库，数据库此时可能就挂掉了。

如果，我们在缓存上加一个布隆过滤器。数据库首先将数据复制一份进缓存中，将所有id通过布隆过滤器映射进一个大数组中。那么，在布隆过滤器的作用下，大量无效的请求直接被返回，无法穿透缓存。

当我们使用布隆过滤器，确定这个值必定不存在时，则完全不需要执行后续成本较高的查询操作。