关于BloomFilter容量的研究

一、BloomFilter的原理

BloomFilter是 一个时间和空间都非常高效的存储结构，它的基本用途是检查任意一个key（字符串）是不是在一个给定的集合（bit数组）里。基本原理是对于给定的key 计算一系列hash的值，将每一个hash的值作为索引到bit数组里去寻找相应的bit是不是为1。只有当一个key对于所有的hash值检索的结果都 是1，这个key才被认为在BloomFilter集合里面；反之，只要有一个hash值检索的结果为0，则表明该key一定不在集合中。

BloomFilter有以下特性：

1. 只能查询给定的key是否在给定的集合中， 或者在该集合中有多少个key。但不能列举出这些key。
2. 只 能被用于检索某个key是否在给定的集合中，而不能判断这个key在集合中出现几次，也不能象hash表一样给每个key关联一个value。一些扩展算 法，例如Bloomier Filter、Counting Bloom Filter等，可以用时间和空间代价换取这些特性。
3. 无法删除。一旦一个key被加入Bloom Filter后，就无法将它从中删除。Counting Bloom Filter可以以时间和空间代价实现删除操作。
4. 存 在一定的可能性，BloomFilter对于不存在于集合中的key可能返回不正确的结果，即报告其存在于集合中。这个被称之为False Positive。但是，BloomFilter报告为不存在于集合中的key则一定不存在。即它的False Negative为0。

二、最优化参数

一个Bloom Filter有以下参数：

m	bit数组的宽度（bit数）
n	加入其中的key的数量
k	使用的hash函数的个数
f	False Positive的比率

Bloom Filter的f满足下列公式：

在给定m和n时，能够使f最小化的k值为：

此时给出的f为：

本文的第一个目的是求出最佳的k使得在给定的m和f下能使n最大化，亦即得到最佳空间利用率。根据以上公式，对于任意给定的f，我们有：

n = m ln(0.6185) / ln(f)     [1]

同时，我们需要k个hash来达成这个目标：

k = - ln(f) / ln(2)                [2]

由于k必须取整数，我们在Bloom Filter的程序实现中，还应该使用上面的公式来求得实际的f：

f = (1 – e^-kn/m)^k                [3]

以上3个公式是程序实现Bloom Filter的关键公式。

下一步，我们要确定各种不同的Hash算法的实际速度。参考文献为：

http://www.burtleburtle.net/bob/hash/doobs.html