概念
它是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。
算法原理
当你往简单数组或列表中插入新数据时，将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话，当你需要在数组或列表中搜索相应值的时候，你必须遍历已有的集合。若集合中存在大量的数据，就会影响数据查找的效率。
针对这个问题，你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值，然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的，当你需要判断列表中是否存在该值时，只需要对值进行哈希处理并在相应的索引位置进行搜索即可，这时的搜索速度是非常快的。
布隆过滤器（Bloom Filter）本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，如下所示。
| Bloom Filter | 0 | 0 | 0 | 0 | 0 | 0 |
|---|---|---|---|---|---|---|
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
为了将数据项添加到布隆过滤器中，我们会提供 K 个不同的哈希函数，并将结果位置上对应位的值置为 “1”。
例如hello经过运算将得到索引位置为2，4，5
| Bloom Filter | 0 | 1 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
例如world经过运算得到位置为3，4，5，结合hello后整个过滤器如下：
| Bloom Filter | 0 | 1 | 1 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
我们可以得出一个结论，当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。
应用场景
- 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
- Google Chrome 使用布隆过滤器识别恶意 URL；
- Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找
- 解决缓存穿透的问题。
参考资料：
[1]https://zhuanlan.zhihu.com/p/94433082
版权声明：本文为博主原创文章，欢迎转载，转载请注明作者、原文超链接，感谢各位看官!!!
本文出自：monkeyGeek
座右铭：生于忧患，死于安乐
欢迎志同道合的朋友一起交流、探讨！
monkeyGeek