概念
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
和HashMap对比
我们常用HashMap来检索一个元素是否在一个集合中，但是当这个集合很大时，比如上亿、十亿的场景，这就会给我们带来空间上的问题；这个时候用到布隆过滤器（Bloom Filter）就可以很好的帮助我们解决这个问题。
基本思想
- 布隆过滤器里有一个初始状态都为0的数组；
- 集合中的元素经过
N个散列函数计算出元素在数组当中的位置，并且将数组中对应位置的0改成1； - 如果此时需要判断元素X是否存在，那么元素X也会经过这N个散列函数的运算而得到数组中的若干个位置，如果得到的若干个位置中的值
均为1，那么则证明元素X很可能存在与集合当中，反之则证明元素X一定不存在于集合当中。
注意：这若干个位置均为1，也只能表明可能存在，并非一定存在。
原因：
- 如果根据同一个哈希函数得到的哈希值不同，那么这两个哈希值的原始输入值肯定不同。
- 如果根据同一个哈希函数得到的两个哈希值相等，两个哈希值的原始输入值有可能相等，有可能不相等。
优缺点
优点
在空间和时间方面，都有着巨大的优势。因为不是存完整的数据，是一个二进制向量，能节省大量的内存空间，时间复杂度方面，由于计算时是根据散列函数计算查询的，那么假设有N个散列函数，那么时间复杂度就是O(N)；同时在存储元素时存储的不是元素本身，而是二进制向量，所以在一些对保密性要求严格的场景有一定优势。
缺点
存在一定的误判（存进布隆过滤器里的元素越多，误判率越高）；不能删除布隆过滤器里的元素，随着使用的时间越来越长，因为不能删除，存进里面的元素越来越多，导致占用内存越来越多，误判率越来越高，最后不得不重置。
应用场景
- 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
- Google Chrome 使用布隆过滤器识别恶意 URL；
- Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找；
- 解决缓存穿透：利用布隆过滤器我们可以预先把数据查询的主键，比如用户ID或文章ID缓存到过滤器中。当根据ID进行数据查询的时候，我们先判断该ID是否存在，若存在的话，则进行下一步处理。若不存在的话，直接返回，这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。
