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算法相对朴素算法的区别就是使用了多个哈希函数,而不是一个。
为了将x∈S加入到BFs中,我们需要计算x对于k个hash函数的值,并将其对应的BFs[i]位置为1,即:
对于待查询的元素y,我们同样需要将他用这k个hash函数进行映射,对于所得到的k个值,如果存在某一个值对应的BF_s[i]为0,则认为y存在集合S中,返回true,否则认为不存在,返回false。
该数据结构不支持删除。
即c是关于k的可忽略函数,即我们总是可以通过调节参数来是我们的BFs达到我们所要求的准确性。
假设我们能容忍的出错几率为\epsilon,那么整个系统的效率应当取决与m和k值的选择。
由理论可以推得m值应当满足
其中e为自然对数。
由于每一个BFs[i]被置为1的概率为
那么对于每一个返回值为true的询问,其判断失误的概率为
.当右边取最小值时,应满足关系式
如果m取上面的最优值,那么k应当满足:
对于两个由唯一(m,n,k,H)构成的,用来处理两个不同集合S_1和S_2的Bloom Filter 来说,我们可以通过将BF_{s_1}和BF_{s_2}这两个BitSet进行位与运算得到一个新的Bloom Filter BF_{s_1\cap_2}