0%

认识布隆过滤器

【题目】

不安全的黑名单包含 100 亿个黑名单网页,每个网页的 URL 最多占用 64B。现在想要实现
一个网页过滤系统,利用该系统可以根据网页的 URL 判断该网页是否在黑名单上,请设计该
系统。

【要求】

1、该系统允许有万分之一以下的判断失误率

2、使用额外的空间不要超过 30GB

【难度】

★★☆☆

【解答】

如果把黑名单中所有的 URL 通过数据库或哈希表保存下来,就可以对每条 URL 进行查询,
但是每个 URL 有 64B,数量是 100 亿个,所以至少需要 640GB 的空间,不满足条件2。

如果面试者遇到网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等题目,又看到
系统容忍一定程度的失误率,但是对空间要求比较严格,那么很可能是面试官希望面试者
具备布隆过滤器的知识。一个布隆过滤器精确地代表一个集合,并可以精确判断一个元素
是否在集合中。注意,只是精确代表和精确判断,到底有多精确呢?完全在于你具体的设计,
但想做到完全正确是不可能的。布隆过滤器的优势在于使用很少的空间就可以将准确率做
到很高的程度,该结构有 Burton Howard Bloom 于 1970 年提出。

首先介绍哈希函数 (散列函数) 的概念。哈希函数的输入域可以是非常大的范围,比如,
任意一个字符串,但是输出域是固定的范围,假设为 S,并且具有如下的性质:

  1. 典型的哈希函数都有无线的输入值域
  2. 当给哈希函数传入相同的输入值时,返回值是一样的
  3. 当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,这是当然的。
    因为输出域为 S,所以会有不同的输入值对应在 S 中的一个元素上。
  4. 最重要的性质是很多不同的输入值得到的返回值会均匀地分布在 S 上。

第 13 点性质是哈希函数的基础,第 4 点性质是评价一个哈希函数的关键,不同的输
入值得到的返回值越均匀地分布在 S 上,哈希函数就越优秀,并且这种均匀的分布与输入
值出现的规律无关。比如, “aaa1”、“aaa2”、“aaa3” 三个输入值比较类似,但是经过
优秀的哈希函数计算后的结果应该相差非常大。读者只用记清哈希函数的性质即可,有兴趣
的读者可以了解一些哈希函数经典的实现,比如 MD5 和 SHA1 算法,如果一个优秀的哈希
函数能够做到很多不同的输入值所得到的返回值非常均匀地分布在 S 上,那么将所有的返回
值对 m 取余(%m),可以认为所有的返回值会均匀地分布在 0
m-1的空间上。这是显而易见
的。

接下来介绍一下社么是布隆过滤器。假设有一个长度为 m 的bit类型的数组,即数组中的每
一个位置只占一个 bit,如我们所知,每一个 bit 只有 0 和 1 两种状态,如下图所示。