【算法】布隆过滤器

应用场景：

网页黑名单系统；

垃圾邮件过滤系统；

爬虫的网址判断重复系统；

容忍一定程度的失误率；

对空间要求较严格；

概念：

布隆过滤器可以精确的代表一个集合，可以精确判断某一元素是否在此集合里。

精确程度由用户的具体设计决定，做到100%的精确是不可能的。其优势在于：利用很少的空间可以做到精确率较高。

原理和过程：

Bloom Filter

用途： 判断一个元素是否在一个集合中、检查一个英语单词是否正确拼写；

原理： 位数组与Hash函数的联合使用。是一个包含m位的位数组，每位初始化为0，有k个不同的hash函数，可将集合元素映射到位数组的某一位。插入元素需根据k个hash函数得到k个位，置为1。查询时判断这k个位（有0则该元素肯定不在集合中，都为1则该元素有可能在集合中）

优点： 有良好的空间效率和时间效率，插入、查询O(n)，安全性高（不保存元素本身）

缺点： 正确率低，有可能不在集合中的元素在位数组查询的位得到都为1。

分析优点（空间效率和失误率）：

假设不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64字节，现在需要生成一个网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上。要求系统有万分之一以下的失误率，并且额外空间不超过30G。

方法一：直接使用哈希表，此时需要的空间为：64字节*100亿=> 640G空间

方法二：布隆过滤器：计算m=20n = 2000亿， 即20G空间。且失误率也降低。（因为m向上取整）

最后

以上就是淡然世界为你收集整理的【算法】布隆过滤器的全部内容，希望文章能够帮你解决【算法】布隆过滤器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。