需求
不安全网页的黑名单包含100亿个黑名单的网页,每个网页的URL最多占用64B.现在想要实现一个网页过滤系统,利用该系统可以根据网页的URL判断该网页是否在黑名单上,请设计该系统.
要求
1.该系统允许有万分之一以下的判断失误率
2.使用的额外空间不要超过30GB
解答篇
->思路简介:
不可以使用传统过滤方法->
如果把黑名单中所有的URL通过数据库或哈希表保存下来,就可以对每条URL进行查询,但是每个URL有64B,数量是100亿个,所以至少需要640GB的空间,不满足要求2.
大数据方法->布隆过滤器
相关题目中可能出现关键字:
1.网页黑名单\垃圾邮件过滤系统\爬虫的地址判重系统…
2.系统容忍一定程度的失误率
3.对空间要求比较严格
哈希函数(散列函数):
哈希函数的输入域可以是非常大的范围,比如->任意一个字符串.但是输出域是固定的范围,假设为S,并具有如下性质:
1.典型的哈希函数都有无限的输入值域.->字符串…
2.当给哈希函数传入相同的输入值时,返回值一样.
3.当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,这是当然的.因为输出域统一是S,所以会有不同的输入值对应在S中的一个元素上.
4.最重要的性质是很多不同的输入值对应在S中的一个元素上.
哈希函数的基础:性质1~3
优劣评价标志:性质4
->哈希函数越优秀,不同输入值所得到的返回值越均匀地分布在S上.
一些经典的哈希函数实现:MD5和SHA1算法.
·如果一个优秀的哈希函数能够做到很多不同的输入值所得到的返回值非常均匀地分布在S上,那么将所有的返回值对m取余(%m),可以认为所有的返回值也会均匀地分布在0~m-1的空间上.
布隆过滤器:
一个布隆过滤器精确地代表一个集合,并可以精确判断一个元素是否在集合中.
注意:只是精确代表和精确判断,具体精确程度在于你具体的设计,但想做到完全正确是不可能的.
优势:在于使用很少的空间就可以将准确率做到很高的程度(该结构由Burton Howard Bloom于1900年提出)
布隆过滤器实现思路:
1.假设有一个长度为m的bit类型的数组,即数组中的每一个位置只占一个bit,如我们所知,每一个bit只有0和1两种状态,如图1所示.
2.再假设一共有k个哈希函数,这些函数的输出域S都大于或等于m,并且这些哈希函数都足够优秀,彼此之间也完全独立.那么对同一个输入对象(假设是一个字符串,记为URL),经过k个哈希函数算出来的结果也是独立的,可能相同,也可能不同,但彼此独立.对算出来的每一个结果都对m取余(%m),然后在图1bit array上把相应的位置设置为1(涂黑),如图2所示.
3.我们把bit类型的数组记为bitMap.至此,一个输入对象对bitMap影响过程就结束了,也就是bitMap中的一些位置会被涂黑.接下来按照该方法处理所有的输入对象,每个对象都可能把bitMap中的一些白位置涂黑,也可能遇到已经涂黑的位置,遇到已经涂黑的位置让其继续为黑即可.处理完所有的输入对象后,可能bitMap中已经有相当多的位置被涂黑.至此,一个布隆过滤器生成完毕,这个布隆过滤器生成完毕,这个布隆过滤器代表之前所有输入对象组成的集合.
使用方法->检查阶段如何检查某一个对象是否是之前的某一个输入对象.
假设一个对象为a,想检查它是否是之前的输入对象,就把a通过k个哈希函数算出k个值,然后把k个值取余(%m),就得到在[0,m-1]范围上的k个值.接下来在bitMap上看这些位置是不是都为黑.如果有一个不为黑,说明a一定不在这个集合里.如果都为黑,说明a在这个集合里,但可能有误判.
误判原因:在生成布隆过滤器的阶段因为输入对象过多,而bitMap过小,则会导致bitMap绝大多数的位置都已经变黑.那么在检查某个元素a时,可能a对应的k个位置都是黑的,从而错误地认为a是输入对象.
*布隆过滤器的具体实现(高能!):
实现一:
已知:
n:布隆过滤器输入对象的元素个数(例如URL的个数->100亿)
p:布隆过滤器想要达到的失误率
求:
m:布隆过滤器bitMap数组的大小
k:哈希函数的个数
公式:
m = -(n * ln§)/((ln2)^2) -> 一般对计算结果向上取整
k = ln2 * (m / n)
因为我们在确定布隆过滤器大小的过程中选择了向上取整,所以还要用如下公式确定布隆过滤器真实的失误率:
p (真实) = (1 - e ^ (- (n * k) / m)) ^ k
上文需求实现:
已知:
n = 100亿
p = 0.01%
bitMap数组大小:m = 19.19 * n ,向上取整得20 * n,即需要2000亿个bit,也就是25GB.
哈希函数的个数:k = ln2 * (m / n) = 0.7 * (m / n) = 14(个)
该题可由25GB的bitMap再单独实现14个哈希函数,根据如上描述生成布隆过滤器即可.
再根据p(真实)的公式求得真实的失误率为:0.006%,低于0.01%,满足条件
布隆过滤器的失误率分析及公式推导(高能中的高能!):
分析及推导工程涉及概率论及大数定理,因笔者能力有限,后续整理…