Bloom Filter算法及应用

小鱼儿 2022-09-17 08:29 165阅读 0赞

**1. 引言**  
问题：有1000瓶药，但是其中有一瓶是有毒的，小白鼠吃了24小时后就会死掉，请问，在24小时找出有毒的药物，最少需要多少只小白鼠？  
答案是：10只，一只小白鼠可以表示2种状态，2^10可以表示1024种状态  
分析可参考：http://lzj0470.iteye.com/blog/657579  
通过二进制向量组来扩展描述的状态，Bloom Filter(BF)算法也是利用这个思想，其本质是上是一个**很长的二进制向量和一系列随机映射函数**

**2. 概述**  
问题：**快速**判断一个元素是否在一个集合中  
解决方法：一般来说，我们会用HASH表来存储集合中的数据，好处是快速准确，缺点是存储效率低，在海量数据时一般服务器无法存储。  
BF是针对哈希表存储效率低的问题，而衍生出来的一种算法。  
其通过利用二进制数组来描述一个集合，来判断一个元素是否属于这个集合  
**优点是：快速查找，并具有非常高的存储效率**  
**缺点是：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合**

**3. 算法描述**  
BF包含：  
1)一个m位的二进位数组，每一位初始化时置为0  
2)k个相互独立的hash函数  
算法：  
针对一个n个元素的集合，通过k个hash函数，将集合中的每个元素都映射到二进位数组中，映射到的位置置为1  
例如：对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1  
在判断某个元素P是否在这个集合时，通过对P应用k次hash函数，判断其对应所有的位置都是1，如果是则认为P是集合中的元素，否则不是。

**4. 最优位数组m大小及hash函数个数**  
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，如何根据输入元素个数n，确定位数组m的大小及hash函数个数是一个非常重要的问题。  
经过一些复杂的证明（可参考相关文档），可以得到：  
1）当hash函数个数k=(ln2)\*(m/n)时错误率最小  
2）在错误率不大于E的情况 下，m至少要等于n\*lg(1/E)才能表示任意n个元素的集合，但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)\*lge 大概就是nlg(1/E)的1.44倍

**5. 应用**  
有10亿个url，如何判断一个新的url是否在这个url的集合中？  
一个url平均长度为52，如果用Hash表解决的话，由于Hash表的存储效率一般只有50%，因此10个url大概需要100G内存，一般服务器无法存储。  
使用BF，要求错误率小于万分之一。  
此时，输入元素n=10亿，最大错误率E=0.0001  
可计算出：m=nlg(1/E)\*1.44=57.6亿，大概需要7.2亿（57.6亿/8）个字节，即720M内存。  
Hash函数个数：k=(ln2)\*(m/n)  大概4个Hash函数

**6.总结**  
BF通过牺牲一定的错误率来保证时间和空间（鱼与熊掌，不可兼得），目前被广泛应用于海量数据处理及数据库系统中。  
例如，在Big table和Cassandra中，都使用BF作为索引结构。  
P.S 针对BF的错误识别问题，可以通过建立白名单的方式解决。