Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

了解布隆过滤器

什么是布隆过滤器?

一个布隆过滤器精确地代表了一个集合。并不像哈希表那样存储原始信息,而是存储原始信息的压缩信息以节省空间,但牺牲了一定的准确度。

布隆过滤器的作用

可以精确地判断一个元素是否在这个集合中。注意只是精确代表和精确判断,到底有多精确,取决于我们自己的设计。想做到完全正确是不可能的,布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。

应用

网页黑名单系统,垃圾邮件过滤系统,爬虫的网址判重系统。即面试官考察的问题需要在一个很大数据量的应用中要求我们用有限的空间设计一个容忍一定错误率的系统。

如何生成一个布隆过滤器:

  1. 假设有一个长度为m的bit类型的数组,即数组中的每一个位置只占用一个Bit,每一个bit只有0和1。
  2. 假设一共有k个哈希函数,这些函数的输出域都大于等于m,并且这些哈希函数都已经足够优秀且彼此独立,输入一个数,分别计算出当输入为该数字时,对应的哈希函数的结果,一共有k个,每个结果都对m取余,然后在bit array上将对应的位置置为1。
  3. bit类型的数组记为bitMap,至此,一个输入对象对bitMap的影响过程就结束了,bitMap中的一些位置会被抹黑,接下来按照第2步对所有数都执行该操作,最后bitMap中很多位置都会被抹黑。

至此,一个bloom filter生成完毕,这个bloom filter 代表之前所有输入对象组成的集合。

如何检查一个数是否在布隆过滤器中

假设一个输入对象为m,我们对该输入对象通过k个哈希函数计算出k个值,然后把k个值取余,就得到在0~m-1范围的k个值,如果在bitMap上对应位置不为1,则说明一定不在布隆过滤器中。如果都为黑,则说明在这个集合里,但有可能误判

布隆过滤器的失误率分析

如果bitMap的大小m相比输入对象的个数n过小,失误率将会变大。

接下来介绍根据n的大小和我们想达到的失误率,如何确定布隆过滤器的大小m以及哈希函数的个数k。

黑名单中样本个数为100亿,记为n,失误率不超过0.01%,记为p,每个样本的大小为64B,这个信息不会影响布隆过滤器的大小,只和选择哈希函数有关,一般的哈希函数都可以接收64B的输入对象,所以使用bloom filter还有一个好处就是不用顾忌单个样本的大小,它丝毫不会影响布隆过滤器的大小

所以n=100亿,p=0.01%,布隆过滤器的大小m由以下公式决定:$ m = - \frac{n \ast (ln P) }{(ln 2)^2} $
计算出m=20*n,也就需要2000亿个bit,也就是25GB

哈希函数的个数由以下公式进行决定:$ k = ln2 \ast \frac{m}{n} $。最后计算出k = 14,但是真实失误率我们还需要重新计算。

真实失误率公式: $ (1 - e^{- \frac{n \ast k }{ m }}) $
计算出真实失误率为0.006%,比0.01%更低,由于哈希函数本身不占用什么空间,因此最主要占用空间的就是bitMap的大小,符合我们题目中的要求。

哈希函数的性质

哈希函数输入可以无限大,但是输出是固定的范围。

  1. 典型的哈希函数都有无限的输入范围。
  2. 哈希函数传入相同的输入值时,返回值也一样。
  3. 哈希函数传入不同的输入值时,返回值可能一样,可能不一样。所以会有不同的输入值对应同一个输出值。
  4. 很多不同的输入值所得到的返回值会均匀的分布在哈希函数上

另外自己查到的哈希函数还有一个特点,就是哈希函数输入可以任意大,但是输出是固定大小

评价:1-3点是哈希函数的基础,第4点性质是评价一个哈希函数优劣的关键,不同的输入经过哈希函数得到的结果越均匀分布在哈希函数上,哈希函数就越优秀,并且这种均匀分布与输入出现的规律无关。

结论:如果一个哈希函数能够根据很多不同的输入得到的返回值非常均匀的分布在S上,那么所有的返回值对m取余,可以认为所有的返回值也是均匀分布在0~m-1的空间上。

评论