为了准备后天的阿里二面,现在开始学习海量数据的处理
第一个要学的就是布隆过滤器,我们先看一下布隆过滤器的应用场景
**不安全的黑名单包括100亿个黑名单网页,每个网页的URL最多占用64B.现在要实现一个网页的过滤系统,根据给出的URL,看是否在黑名单上(黑名单问题)
允许有失误率的存在,空间使用不能超过30GB.

分析

如果把所有的URL通过数据库或者哈希函数保存起来,一个是64B,100亿个就是640GB,就不能满足额外空间不超过30GB这个条件了.
对于网页黑名单系统,垃圾邮件过滤系统,爬虫的网址判重系统,又容忍一定的失误率.这个时候我们就需要用到布隆过滤器.
布隆过滤器精准的代表了一个集合,又可以精确的判断一个元素是否在集合之中.完全正确是不可能的,布隆过滤器的特点就是通过很少的空间就找到准确度很高的程度.在使用布隆过滤器之前,我们要先了解哈希函数(散列函数).它的输入域可以是很大的范围,但他的输出域就是固定的范围

• 典型的哈希函数都有无限的输入值域
• 当给哈希函数传入相同的值的时候,返回值是一样的
• 当传入不同的值,输出值可能一样,也可能不一样.这个是肯定的,毕竟输出值的域统一是S,所以不同的输入值可能会对应同一个输出值
  我们来画一张图
  图片.png
  最重要的性质就是不同的输入值会均匀的分布在输出域S上,这个也就是评价一个哈希函数优劣的关键.
  不同的值对应的返回值分布的越均匀,哈希函数就越优秀,而且这种均匀分布和规律没有关系.
  比如说对于"aa1",''aa2'',''aa3''这些相同的值,经过哈希函数的转化结果应该差距比较大.
  假设我们现在知道一个哈希函数能让不同的输入值均匀的分布在S的范围上,那么我们现在对S取模,比如说S%m,那么现在输出域就均匀的分布在0---m-1上.
  我们了解完了哈希函数,现在我们就进入正题,聊一聊到底什么是布隆过滤器.
  我们现在有一个长度为m的bit类型的数组
  图片.png
  这个这是个bit类型的数组,比特类型的,所有其中的值就是0,或者是1.然后我们假设有k个hash函数,经过这些函数的输出域都是大于等于m的,然后这些哈希函数都足够优秀,并且这些彼此独立.对于同一个输入对象,经过k个哈希函数算出来的结果也是独立的,可能相同,也可能不同,彼此独立,然后对每一个结果都取模m,然后把bit array上相应的位置置为1(涂黑).
  图片.png ,这样的话一个输入对象(一个url)就把自己放入了这个bit array中了,然后就按照这个方法处理所有的输入对象(30亿个URL).......
  最后处理完了所有的输入对象,这个时候bitMap就已经有相当多的位置被涂黑.
  这样一个布隆过滤器就生成完毕了

如果通过布隆过滤器检查URL

假设现在有一个a对象,想要检查它是否是之前的输入对象.
1.把a通过k个哈希函数算出k个值,然后把这k个值都去余,使得0----m-1上有这个k个值,然后重头戏来了
2.这个时候看看每个值对应在bit array是否是涂黑的,即是否为1,如果全部为1,说明就在这个名单之中,如果有一个是白的,则说明不在其中
说的在具体一点,a如果是输入对象,那么它对应的k个值在bit array中一定会涂黑,a一定不会漏盘
a如果是之前输入的,那么它一定可以被找到
3.然后就是漏判的情况,如果它不是之前的输入对象,但它经过k个哈希函数,对应的位置都有可能是黑的
所以,就有下面这句话

图片.png
所以当处理的URL过多时,同时bit array的长度过小时,这样的或就会是失误率变的比较大(这个很好理解,如果bit array的长度是1,那么怎么样都是涂黑的),以上就是布隆过滤器大概的分析了,然后我们就来分析一下布隆过滤器的失误率吧.
在上面的过程中,涉及到了几个变量.
一个是输入对象的个数n(100亿个),然后就是失误率p,然后就是布隆过滤器的大小k和哈希函数的个数k.(n,m,k,p)
然后就是失误率分析,一下内容都是来自于书籍<<程序员代码面试指南>>这本书
我们以本题来进行分析.黑名单样本的个数为100个,失误率不能超过0.01%,每个样本的大小为64B,单个样本的大小不会影响到布隆过滤器的大小,这个只和哈希函数有关.这儿我们就可以知道布隆过滤器的好处之一就是不用顾忌单个样本的大小
图片.png
然后就知道数组大小为25亿,哈希函数为14个,即100亿个数每一个都要经过14个哈希函数的变化,然后在25亿长度的数组中涂黑.
图片.png
步骤不再去推,因为推也看不懂.
然后就是对误判的处理,我们来看看书.
图片.png