【布隆过滤器（Bloom Filter）基本概念与原理、Bloom Filter优点与缺点、以及应用场景】

布隆过滤器（Bloom Filter）基本概念与原理、Bloom Filter优点与缺点、以及应用场景

Bloom Filter 基本概念

布隆过滤器是1970年由一个叫布隆的小伙子提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

Bloom Filter 原理

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

那么就会有人问了，Bloom Filter和Bit-Map有什么不同呢？

Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。如下图所示:

Bloom Filter优点与缺点

世界上没有完美的人或者事，技术也一样，Bloom Filter可以快速的找到某一个数是否存在并且能很好的帮我们解决缓存穿透的问题，但是带来的问题就是牺牲了判断的准确率、删除的便利性。

优点

它的优点是空间效率和查询时间都远远超过一般的算法。

缺点:

1. 存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
2. 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。

Bloom Filter 应用场景

1. 解决缓存穿透问题，快速的判断某一个数是否存在
2. 垃圾邮件地址过滤
3. 爬虫URL地址去重
4. Google著名的分布式数据库Bigtable以及Hbase使用了布隆过滤器来查找不存在的行或列，以及减少磁盘查找的IO次数
5. 文档存储检查系统也采用布隆过滤器来检测先前存储的数据
6. Goole Chrome浏览器使用了布隆过滤器加速安全浏览服务

总结

关于布隆过滤器基本概念与原理、Bloom Filter优点与缺点、以及应用场景就先介绍到这里，当然关于布隆过滤器相关的知识还有很多内容并没有讲到，这个就需要你先看懂这些，然后再一步深入学习。如果对你有帮助，就留下你的小关注吧！