一、什么是布隆过滤器
布隆过滤器（英语：Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器的特点：
- 如果布隆过滤器判断元素在集合中存在, 不一定存在.
- 如果布隆过滤器判断不存在, 则一定不存在.
二、布隆过滤器的原理
当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
简单来说就是准备一个长度为 m 的位数组并初始化所有元素为 0，用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。当布隆过滤器保存的元素越多，被置为 1 的 bit 位也会越来越多，元素 x 即便没有存储过，假设哈希函数映射到位数组的三个位都被其他值设置为 1 了，对于布隆过滤器的机制来讲，元素 x 这个值也是存在的，也就是说布隆过滤器存在一定的误判率。
三、底层数据结构
布隆过滤器由一个BitMap组成。所谓的BitMap，本质上就是一个数组。与寻常数组不同的是，BitMap一个数组元素占一个bit，这一特性决定了BitMap能够极大地节省空间。
在位图的场景下使用多个哈希函数来降低冲突即就是布隆过滤器的思想，其最大的特点就是：对一个对象使用多个哈希函数。其查询有个特点，就是即使任何两个元素的哈希值不冲突，查询对象的K个位置的值都是1，查询结果为存在，这个结果也可能是错误的，这就是布隆过滤器的容错率。
使用布隆过滤器可以快速检索是否存在，但是当哈希函数特别多的时候，容错率会增大，因此也要控制哈希函数的个数。计算哈希函数个数的数学公式：哈希函数K=（m/n)*In(2).其中m是bit数组长度，n为要存入对象的个数。【实际上，当哈希函数个数为1，且数组长度足够，布隆过滤器就可以退化成一个位图。位图是只有一个特殊的哈希函数，且没有被压缩长度的布隆过滤器】
四、使用场景
布隆过滤器常见的应用场景如下：
- 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
- Google Chrome 使用布隆过滤器识别恶意 URL；
- Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。 除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
五、布隆过滤器删除
对于布隆过滤器无法直接删除，但也有带引用计数的布隆过滤器，存的不是0和1，而是一个计数。所有的设计都是一个trade-off(权衡取舍)。
为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。布谷鸟过滤器用更低的空间开销解决了布隆过滤器不能删除元素的问题，做到了更好的效果：
- 支持动态的添加和删除元素
- 提供了比传统布隆过滤器更高的查找性能，即使在接近满的情况下（比如空间利用率达到 95% 的时候）
- 比起商过滤器它更容易实现
- 如果要求误判率低于3%，它比布隆过滤器有更低的空间开销
