概念

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。

它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

特点

优点：

• 时间复杂度低，增加和查询元素的时间复杂为O(N)（N为哈希函数的个数，通常情况比较小）
• 保密性强，布隆过滤器不存储元素本身
• 存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）

缺点：

• 有一定的误判率，但是可以通过调整参数来降低
• 无法获取元素本身
• 很难删除元素（删除元素会导致误判率升高）

特点：

• 布隆过滤器判断存在，不一定存在；判断不存在，则一定不存在

如何使用

原理

布隆过滤器时一种专门用来解决去重问题的高级数据结构。

实质就是一个大型位数组和几个不同的无偏Hash函数（无偏表示分布均匀）。由一个初值都为0的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在。但和HyperLogLog一样，它也存在一定的误判概率。

添加/查询key

• 添加key

  使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置为1就完成了添加操作。

• 查询key

  只要有其中一位是0就表示这个key不存在，如果都是1，则不一定存在对应的key。

  存在哈希冲突，位上的1不一定是由这个key产生的。

正是基于布隆过滤器的快速检测特性，我们可以把数据写入数据库时，使用布隆过滤器做个标记。当缓存缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去数据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询Redis和布隆过滤器，而不会积压到数据库，也就不会影响数据库的正常运行。布隆过滤器可以使用Redis实现，本身就能承担较大的并发访问压力。

使用场景

• 解决缓存穿透问题，和Redis结合bitmap使用
• 黑名单校验，识别垃圾邮件
• 解决新闻推荐过的不再推荐
• …