初识布隆过滤器
1.先看一个问题
假如你的服务后台存储有大量数据，通过缓存提高查询效率，当缓存中不存某条记录再去数据库中查询，这就可以大大减少对数据库的请求压力。但是有一天某黑客构建大量不存在于缓存中的 key 发起缓存穿透攻击，在QPS足够高的情况下，有可能会把数据库压跨，这种情况下该怎么办呢？
2.布隆过滤器闪亮登场
上面这个场景使用布隆过滤器最适合不过了，因为我们只要知道某个 key 对应的记录不存在于数据库就行了，恰好布隆过滤器就是为了解决这个问题而生。
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它由一个很长的二进制数组和一系列哈希函数组成。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询效率都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：
如果我们要把一个key映射到布隆过滤器中，就需要利用所有哈希函数对这个key进行映射，得到一系列的哈希值，把这些哈希值当成数据下标，把下标对应的数组元素置为1。
假设现在对对肯德基的菜单进行构建布隆过滤器：
首先，现在我们把“汉堡”这个key映射到布隆过滤器中，通过哈希函数映射的结果为1和7，我们现在把对应的bit元素标志为1。
Ok，我们现在再存一个值 “鸡腿”，如果哈希函数返回2和5的话，图继续变为：
接着我们想要查询某个key是不是在布隆过滤器中，只需要再通过哈希函数或者一系列的哈希值，然后把这些哈希值作为数组下标查看对应的元素是否为1。
这里有两种情况：
（1）不是所有位置都为1，肯定不在布隆过滤器中。
瞧，如果我们要查询“可乐“这个key是否在布隆过滤器中的时候，发现通过哈希函数2映射的结果对应的bit位不是1，这种情况就可以确定“可乐”一定不在布隆过滤器中。利用这一点就可以解决上面提到的缓存穿透的问题。
（2）所有位置的bit位都是1，可能在布隆过滤器中。
如果我们要查询“鸡肉卷”这个key是不是在布隆过滤器中的时候，发现通过哈希函数获得的哈希值所对应的bit都被置为1了，那这个值是不一定在布隆过滤器中的，为什么呢？
这就是布隆过滤器的缺点之一：存在误判。
3.布隆过滤器缺点
为什么会存在误判呢？
因为哈希函数可能是存在冲突的。在发生冲突的情况下，如果刚好所有的值都被置为1了，就会产生误判。为了能做到在时间和空间上的高效率，布隆过滤器牺牲了判断的准确率。所以对于不能接受误判的业务场景，通常需要在通过布隆过滤器之后再做一层判断。
为什么删除困难呢？ 另外布隆过滤器还有一个缺点就是删除比较困难，假如要删除一个key的话，不能简单的把这个key映射到的bit位都简单的置为0，因为哈希冲突的情况下，会影响其它key的判断。如果要删除的话，可以参考Counting Bloom Filter。
4.如何控制布隆过滤器的准确率
首先。布隆过滤器如果太小的话， bit 很快就会被全置为1，不论查询什么，结果都是“可能存在”，就起不到过滤效果了。所以布隆过滤器的长度会直接影响准确率，长度越长，准确率越高。
另外，哈希函数的个数也会影响布隆过滤器的准确率。哈希函数越多的话，一是增加了哈希计算的耗时，二是对每个key进行映射的时候，被置为1的bit位也就越多，也会很快就把布隆过滤器打满。
假设我们的预估数据量为n，期望的误判率为fpp的话，bit数组大小和哈希函数个数k可以通过以下公式计算得到：
TODO
5.布隆过滤器的其他使用场景
知道了布隆过滤器了特点，那么我们很容易想到布隆过滤器的用武之地不止防止缓存穿透，还有很多其他的使用场景。
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
爬虫过滤已抓到的URL就不再抓，可用过滤；
使用布隆过滤器避免推荐给用户已经读过的资讯（文章/视频）等。
参考文献
[1] 漫画：什么是布隆过滤器