下面列举几个基于标准Bloom Filter的小技巧：

 

1.         求两个集合的并。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，那么要求表示S₁和S₂并集的Bloom Filter，只要将S₁和S₂的位数组进行“或”操作即可得到结果。

 

2.         将Bloom Filter“对折”。 如果想将一个Bloom Filter的大小缩小一半，那么只需将Bloom Filter的位数组分成两半进行“或”操作，得到的结果即为所求。在查找某一元素时，需要将哈希后的索引地址的最高位屏蔽掉。

 

3.         通过0的数目估计集合元素个数。在第一篇文章Bloom Filter概念和原理中，我们提到过：位数组中0的比例非常集中地分布在它的数学期望值m (1 - 1/m)^kn的附近，其中m为位数组的大小，k为哈希函数的个数，n为Bloom Filter所表示集合的元素个数。根据上式，知道了0的个数就可以很容易推断n的大小。

 

4.         通过内积估计集合交集元素个数。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，下面我们来看第i位在两个Bloom Filter同时被置为1的概率。要让某一位同时被置为1，只有两种可能：要么它是被S₁∩S₂中的元素设置的，要么分别是被S₁ – (S₁∩S₂)和S₂ - (S₁∩S₂)中的元素设置的。因此第i位在两个Bloom Filter同时被置为1的概率为：

|S|表示S中元素的个数，k表示哈希函数的个数，m表示位数组的大小。经过化简，再乘以m，得到两个位数组内积的数学期望值为：

如果不知道|S₁|和|S₂|，可以用3中的方法根据0的个数估计出它们的大小。最后，根据上式，我们在知道内积的情况下就可以很容易推断| S₁∩S₂|的大小。

 

5.         表示全集。很简单，将位数组设为全1就可以表示全集了，因为查找任何一个元素都会得到肯定的结果。

Counting Bloom Filter

 

从前面几篇对Bloom Filter的介绍可以看出，标准的Bloom Filter是一种很简单的数据结构，它只支持插入和查找两种操作。在所要表达的集合是静态集合的时候，标准Bloom Filter可以很好地工作，但是如果要表达的集合经常变动，标准Bloom Filter的弊端就显现出来了，因为它不支持删除操作。

 

Counting Bloom Filter的出现解决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个小的计数器（Counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。下一个问题自然就是，到底要多占用几倍呢？

 

 

我们先计算第i个Counter被增加j次的概率，其中n为集合元素个数，k为哈希函数个数，m为Counter个数（对应着原来位数组的大小）：

上面等式右端的表达式中，前一部分表示从nk次哈希中选择j次，中间部分表示j次哈希都选中了第i个Counter，后一部分表示其它nk – j次哈希都没有选中第i个Counter。因此，第i个Counter的值大于j的概率可以限定为：

上式第二步缩放中应用了估计阶乘的斯特林公式：

在Bloom Filter概念和原理一文中，我们提到过k的最优值为(ln2)m/n，现在我们限制k ≤ (ln2)m/n，就可以得到如下结论：

如果每个Counter分配4位，那么当Counter的值达到16时就会溢出。这个概率为：

这个值足够小，因此对于大多数应用程序来说，4位就足够了。

 

 关于Counting Bloom Filter最早的论文：Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol