01背景假如需要过滤某些不安全网页 ， 现有100亿个黑名单页面 ， 每个网页的URL最多占用64字节 。现要设计一种网页过滤系统 ， 可以根据网页的URL判断该网页是否在黑名单上 ， 要求该系统允许有万分之一以下的判断错误率 ， 并且使用的额外空间不要超过30G 。可以采用如下几种方案：
1、将访问过的URL保存到数据库
每次需要过滤网页就需要启用一个数据库select查询 ， 且当数据量变得非常庞大后 ， 关系型数据库查询的效率会变得很低 。
2、用HashSet将访问过的URL保存起来
那只需接近O(1)的代价就可以查到一个URL是否被访问过了 。但是内存消耗太大 。
3、URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库
字符串经过MD5散列处理后的信息摘要长度只有128Bit ， SHA-1处理后也只有160Bit ， 因此方法3比方法2节省了好几倍的内存 。
4、BitMap方法
建立一个BitSet ， 将每个URL经过一个哈希函数映射到某一位 。消耗内存是相对较少的 ， 但缺点是单一哈希函数发生冲突的概率太高 。
02概述Bloom Filter(布隆过滤器)是一种多哈希函数映射的快速查找算法 。它是一种空间高效的概率型数据结构 ， 通常应用在一些需要快速判断某个元素是否属于集合 ， 但是并不严格要求100%正确的场合 。布隆过滤器的优势在于 ， 利用很少的空间可以做到精确率较高 。
哈希表与布隆过滤器：
哈希表也能用于判断元素是否在集合中 ， 但是Bloom Filter只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题 。Bloom Filter可以插入元素 ， 但是不可以删除已有元素 。集合中的元素越多 ， 误报率越大 ， 但是不会漏报 。
03原理如果想判断一个元素是不是在一个集合中 ， 一般想到的方法是暂存数据 ， 然后查找判定是否存在集合中 。这种方法在数据量比较小的情况下适用 ， 但是几个中元素较多的时候 ， 检索速度就会越来越慢 。可以利用Bitmap：只要检查对应点是不是1就可以知道集合中有没有这个数 。Bloom filter可以看做是对bitmap的扩展 。只是使用多个hash映射函数 ， 从而减低hash发生冲突的概率 。
算法如下:
1、创建m（m=28）位的bitset ， 初始化为0 ， 选中k（k=3）个不同的哈希函数；
2、第 i 个hash函数对字符串str哈希的结果记为 h(i,str) ， 范围是（0,m-1）；
3、将字符串记录到bitset的过程（即插入）：对于一个字符串str ， 分别记录h(1,str) ， h(2,str)… ， h(k,str) ， 然后将bitset的h(1,str) ， h(2,str)… ， h(k,str)位置1 ， 也就是将一个a映射到bitset的k个二进制位；
4、检查字符串是否存在（即查找）：对于字符串astr ， 分别计算h(1,str)、h(2,str) ， … ， h(k,str) ， 然后检查bitset的第h(1,str) ， h(2,str) ， … ， h(k,str) 位是否为1：
若其中任何一位不为1则可以判定str一定没有被记录过；
若全部位都是1 ， 则“认为”字符串str存在；
但是若一个字符串对应的Bit全为1 ， 实际上是不能100%的肯定该字符串被Bloom Filter记录过的（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况 ， 称为false positive ；
推荐阅读
- 投影仪原理,自制投影仪如何最清晰
- MySQL filesort原理及优化
- 蜂鸣器电路,五款蜂鸣器驱动电路原理图
- 尿素滤网的位置
- 内墙隔断的原理是什么
- 自动门工作原理图 自动门工作原理
- 第2版 闪存技术、产品和原理全面解析
- 主动式平衡杆什么原理
- 数控是什么,工作原理是什么
- 漂移是什么原理