何为布隆过滤器

问题的提出

我们有一个不安全网页的黑名单&＃xff0c;包含了100亿个黑名单网页的URL,每个网页URL最多占用64B.。

现在我们要设计一个网页过滤系统&＃xff0c;这个系统要判断该网页是否在黑名单里&＃xff0c;但是我们的空间有限&＃xff0c;只有30GB.

允许有万分之一的判断失误

布隆过滤器

我们可以把所有的URL保存起来&＃xff0c;比如放到hashmap里&＃xff0c;但是64B*100亿&＃61;640GB&＃xff0c;不符合要求。

布隆过滤器&＃xff08;Bloom Filter&＃xff09;是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法&＃xff0c;缺点是有一定的误识别率和删除困难。 

如果遇到网页黑名单系统、垃圾邮件过滤、爬虫网址判重等问题&＃xff0c;如果可以容忍一定程度的失误率&＃xff0c;那么我们就可以用布隆过滤器来解决。

哈希函数

我们先来认识一下哈希函数&＃xff08;或者说是复习&＃xff09;

1&＃xff09;

哈希函数的输入可以认为是无穷大或者是非常大的范围&＃xff0c;比如任意一个整数&＃xff08;字符串&＃xff09;&＃xff0c;而输出域是有范围的

&＃xff08;这就意味着不同的输入可能是相同的输出&＃xff09;

2&＃xff09;

当输入相同的值时&＃xff0c;返回值也相同&＃xff08;确定性&＃xff09;

3)

所有不同的输入值得到的输出&＃xff0c;均匀地分布在输出域内&＃xff0c;并且与输入值出现的规律无关。&＃xff08;这也是评价一个哈希函数是否优秀的两个重要标准&＃xff09;比如&＃xff1a;1和2相差很近&＃xff0c;但是经过优秀的哈希函数计算后&＃xff0c;他们应该差距较大。

4&＃xff09;

速度快&＃xff1a;可以认为哈希函数的计算时间是O(1)的。

布隆过滤器输入

下面就开始介绍布隆过滤器啦。

1&＃xff09;

我们准备k个哈希函数&＃xff0c;并且他们之间没有什么关系&＃xff0c;彼此独立。

那么对于同一个输入对象&＃xff08;你想的没错就是一个URL&＃xff09;&＃xff0c;经过计算出来的结果也是完全独立的没有规律的。

2&＃xff09;

我们准备一个数组&＃xff0c;长度为m&＃xff0c;只有两种状态&＃xff0c;所以我们选用bit数组名为bitmap。

3&＃xff09;

我们输入一个黑名单里的URL时&＃xff1a;把URL用每一个哈希函数计算出来&＃xff0c;结果%数组长度&＃xff08;目的是能存下呀。。。。。&＃xff09;&＃xff0c;把对应位置的bit变为1&＃xff0c;记录下来。

处理完所有URL&＃xff0c;我们的布隆过滤器就准备好啦。

布隆过滤器检查

我们如何用布隆过滤器检查某个URL是否是黑名单中的呢&＃xff1f;
同样的方法&＃xff0c;把这个值用k个哈希函数算出结果&＃xff0c;每一个结果都去bitmap里找有没有存在过&＃xff0c;只要有一个结果不存在&＃xff0c;那这个URL就肯定不是黑名单了。&＃xff08;因为之前用同样的方法&＃xff0c;bitmap变为1的那些位置和现在应该是一样的&＃xff09;

接下来就是比较佛性的事了&＃xff0c;既然有一个答案不存在&＃xff0c;这个URL就不是黑名单里的&＃xff0c;那。。。所有答案都存在&＃xff0c;就能确定它在黑名单里吗&＃xff1f;

不是的。

因为可能是其它URL算出的答案恰好把本URL的答案全都算出来过。

想到这就不禁要问了&＃xff1a;那这个数据结构有啥用&＃xff1f;不是坑爹呢&＃xff1f;

其实是有用的&＃xff0c;他的失误率是很低很低的。

他的原则就是&＃xff1a;“宁可错杀三千&＃xff0c;不可放过一个”

如何设计空间和哈希函数

首先我们应该想到&＃xff1a;数组太小的话肯定是不准确的&＃xff0c;比如&＃xff1a;

就这么小个数组&＃xff0c;存了几个URL&＃xff0c;十个地方全算出来过&＃xff0c;全成1了。

那后面判断的时候就比较坑了&＃xff0c;随便来什么URL,随便什么哈希函数&＃xff0c;算出的答案全都出现过&＃xff0c;这显然不是我们想要的。

所以&＃xff0c;我们应该知道&＃xff0c;数组过小会影响准确性。

那么我们如何根据数据量来设计数组大小和哈希函数个数呢&＃xff1f;

以本题为例&＃xff1a;

样本数&＃xff1a;100亿

失误率&＃xff1a;不超过0.01%&＃xff0c;记为p

每个样本大小&＃xff1a;64B&＃xff08;这个其实不影响布隆过滤器大小&＃xff0c;因为这是和哈希函数有关的&＃xff0c;一般的哈希函数都能接受64B的数据&＃xff0c;并且输出&＃xff0c;bitmap只需记录答案是否出现过即可&＃xff09;

布隆过滤器大小m由以下公式决定&＃xff1a;

根据公式算出m&＃61;19.19n&＃xff0c;向上取整20&＃xff0c;所以需要2000亿bit&＃61;25GB

哈希函数的个数由以下公式决定&＃xff1a;

k&＃61;14

布隆过滤器的失误率为&＃xff1a;

计算出为0.006%&＃xff0c;符合要求&＃xff0c;此题可解。

公式分析

白名单

过滤器会用错误&＃xff0c;对已经发现的错误样本可以建立白名单防止错误。

其他使用场景

• 网页爬虫对URL的去重&＃xff0c;避免爬去相同的URL地址
• 垃圾邮件过滤&＃xff0c;从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱
• 解决数据库缓存击穿&＃xff0c;黑客攻击服务器时&＃xff0c;会构建大量不存在于缓存中的key向服务器发起请求&＃xff0c;在数据量足够大的时候&＃xff0c;频繁的数据库查询会导致挂机。