Bloom Filters简介
Bloom Filters简介
简介
Bloom Filter(又叫布隆过滤器)是由B.H.Bloom在1970年提出的一种多哈希函数映射的快速查找算法。该算法的原名叫：“Space/time trade-offs in hash coding with allowable errors”，即一种允许一定容错率的哈希算法，因为在实际应用中经常有这样的情况：普通hash算法相对高额的空间消耗承受不住过大的数据，而实际上对询问的正确性要求又不大。在这种情况下Bloom Filter的时空优越性就体现出来了。 为了说明Bloom Filter存在的重要意义，举一个实例： 假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。比较靠谱的方法是建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。这个方法显然很合理，但是当数据量变得非常庞大的时候单一哈希函数发生冲突的概率太高。若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍！显然不符合实际。而事实上在这种应用中，少抓了几个网页的代价是很小的，所以其实并没有特别的必要来保证询问的完美正确性。 Bloom Filter算法相对朴素算法的区别就是使用了多个哈希函数，而不是一个。
初始化
- 创建一个m位BitSet，下标为[0,m-1]，将所有位初始化为0。
- 选择k个独立的均匀分布的的哈希函数H =\{h_0\ h_1\ ... h_{k-1}\}，每一个h_i函数映射的值域在[0,m-1]中均匀分布。
- 我们将一个Bloom Filter 用一个(m,n,k,H)四元数表示，将需要查询的集合用S表示，将对于集合S的Bloom Filter 用BF_s表示，将那个BitSet中的第i位用BF_s[i]表示。
加值
为了将x∈S加入到BFs中，我们需要计算x对于k个hash函数的值，并将其对应的BFs[i]位置为１，即：
查询
对于待查询的元素y，我们同样需要将他用这k个hash函数进行映射，对于所得到的k个值，如果存在某一个值对应的BF_s[i]为０，则认为y存在集合S中，返回true，否则认为不存在，返回false。
删除
该数据结构不支持删除。
正确性
即c是关于ｋ的可忽略函数，即我们总是可以通过调节参数来是我们的BFs达到我们所要求的准确性。
参数选择
假设我们能容忍的出错几率为\epsilon，那么整个系统的效率应当取决与m和k值的选择。
数组大小m值的确定
由理论可以推得m值应当满足
其中ｅ为自然对数。
哈希函数数目k值的确定
由于每一个BFs[i]被置为１的概率为
那么对于每一个返回值为true的询问，其判断失误的概率为
.当右边取最小值时，应满足关系式
如果m取上面的最优值，那么ｋ应当满足:
其他操作
对于两个由唯一(m,n,k,H)构成的，用来处理两个不同集合S_1和S_2的Bloom Filter 来说，我们可以通过将BF_{s_1}和BF_{s_2}这两个BitSet进行位与运算得到一个新的Bloom Filter BF_{s_1\cap_2}