Bloom Filter 数据结构的原理分析
时间：2007-02-01 来源：guoxi
Bloom Filter 数据结构广泛地应用于网络技术中，它是由 Burton Bloom 在 1970 年提出来的。它的优点是可以有效地节省空间，缺点是不能做到精确无误，不过这个看似很郁闷的缺点却可以使用调节参数的方法有效控制，也可以通过不同的应用手段来避免差错。Bloom Filter 数据结构有很多应用，将在下一篇文章里叙述，而这篇文章将简要叙述这个算法的原理和分析。
问题定义：如何用简单节省的方法将一个集合中的所有元素表述出来？
原理：有一个集合 S = { x1, x2, ... , xn}, 用一个 n bit 的数组把这个集合表示出来。使用 k 个独立的哈希函数，将 S 中的每个元素 xi 映射到这个 n bit 的数组中的某一位上，对于 S 中的每个元素要做 k 次哈希。n bit 的数组初始化每一位为 0 。
如图所示：
0 0 0 0 0 0 0 0 0 0 0 0
x2_______________
x1________| | |
| | | | |
0 1 0 1 0 1 0 1 0 0 1 0
x2'_______________
x1'______| | |
| | | | |
0 1 0 1 0 1 0 1 0 0 1 0
从上图可见，x1 , x2 被映射到 n-bit 中，来了两个查询，x1' 和 x2' ，对这两个查询也分别做 k 个哈希映射，结果 x1' 对应的值不全是 1 ，这说明在集合S中肯定不存在和 x1' 相同的元素。而 x2' 对应的 bit 都是1，这说明 x2' 有可能存在于集合中。 但是它不存在的可能性也是有的，因为不能保证不同的元素的哈希值不同。
下面是几个关于 bloom filter 的延伸分析。
1）使用 bloom filter 可以做集合的并、交运算。只需将 n-bit 数组 OR 或 AND 就可以了。但是结果并不精确。
2）bloom filter 有时会用在描述一个变化的集合上。添加一个新的集合元素进入 bloom filter 很容易，而删除从集合中删除一个元素，却不是那么简单，因为会附带着把其他元素的信息也删除掉。为了解决这个问题，使用多个 bit 位取代使用一个 bit 位。每次映射到这个位置，就加 1 。
相关阅读 更多 +
