引言

在介绍布隆过滤器之前我们首先引入几个场景。

场景一

在一个高并发的计数系统中，如果一个key没有计数，此时我们应该返回0，但是访问的key不存在，相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿？

有人说， 将这个key的值置为0存入缓存不就行了吗？确实，这是一个好的方案。大部分情况我们都是这样做的，当访问一个不存在的key的时候，设置一个带有过期时间的标志，然后放入缓存。不过这样做的缺点也很明显，浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中，我们需要设置很多黑名单内容。比如一个邮件系统，我们需要设置黑名单用户，当判断垃圾邮件的时候，要怎么去做。比如爬虫系统，我们要记录下来已经访问过的链接避免下次访问重复的链接。

在邮件很少或者用户很少的情况下，我们用普通数据库自带的查询就能完成。在数据量太多的时候，为了保证速度，通常情况下我们会将结果缓存到内存中，数据结构用hash表。这种查找的速度是O(1)，但是内存消耗也是惊人的。打个比方，假如我们要存10亿条数据，每条数据平均占据32个字节，那么需要的内存是64G，这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路，查询的速度是O(1)，消耗内存特别小呢？前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态（是或者不是，存在或者不存在），那么对于所存的数据完全可以用位来表示！数据本身则可以通过一个hash函数计算出一个key，这个key是一个位置，而这个key所对的值就是0或者1（因为只有两种状态），如下图：

布隆过滤器原理

上面的思路其实就是布隆过滤器的思想，只不过因为hash函数的限制，多个字符串很可能会hash成一个值。为了解决这个问题，布隆过滤器引入多个hash函数来降低误判率。

下图表示有三个hash函数，比如一个集合中有x，y，z三个元素，分别用三个hash函数映射到二进制序列的某些位上，假设我们判断w是否在集合中，同样用三个hash函数来映射，结果发现取得的结果不全为1，则表示w不在集合里面。

布隆过滤器处理流程

布隆过滤器应用很广泛，比如垃圾邮件过滤，爬虫的url过滤，防止缓存击穿等等。下面就来说说布隆过滤器的一个完整流程，相信读者看到这里应该能明白布隆过滤器是怎样工作的。

第一步：开辟空间

开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式，甚至你可以用文件来实现。

第二步：寻找hash函数

获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如BKDRHash，JSHash，RSHash等等。这些hash函数我们直接获取就可以了。

第三步：写入数据

将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。

第四步：判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

误判问题

布隆过滤器虽然很高效（写入和判断都是O(1)，所需要的存储空间极小），但是缺点也非常明显，那就是会误判。当集合中的元素越来越多，二进制序列中的1的个数越来越多的时候，判断一个字符串是否在集合中就很容易误判，原本不在集合里面的字符串会被判断在集合里面。