?

原理

?

Bloom filter是一种hash算法，可以认为该算法的目的是高效地判断某个元素是否在一个特定集合中。

?

该算法涉及到三种数据类型：

?

? ? -- 数据集合S

? ? -- 一个数组，该数组的元素类型是bit，记为A

? ? -- k个hash函数，每个Hash函数记为Hk

?

初始情况下，bit数组所有元素为0。

?

插入一个元素时，将每个hash函数Hk应用到到该元素，产生k个值。可以用取模的方法将这k个值映射到数组A的k个位置，并将这k个位置上的值置为1。

?

例如，我们有三个hash函数，数组的长度是10。插入一个元素时，数组的状态可能是这样的：

?

? ? ? ? ? ? ? ? ?X

? ? ? ? ? ? ? ? ?|

? ? ? ? ? ? ? ? ?V

? ? ? H1(X) ? H2(X) ? H3(X)

? ? ? ? ? ? ? ? ?|

? ? ? ? ? ? ? ? ?v

+---------------------------------------+

| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | ? ?bit array

+---------------------------------------+

?

下面，我们的问题是判断另外一个元素Y是否在集合中。将所有的hash函数应用到Y，产生k个位置，我们检查数组A上的这k个位置上的值。如果有至少一个位置的值是0，那么Y肯定不在集合中。

?

问题是，如果所有的位置上的值都为1，我们能得到什么结论？

?

我们不能确定Y是否一定在集合中，Y可能在，也可能不在。

?

所以，通过Bloom filter我们得到一个元素不在集合的结论是正确的。

?

应用

?

BigTable和Cassandra使用Bloom filter快速判断某个key不在文件中。Cassandra论文中这样描述：

?

When a disk

lookup occurs we could be looking up a key in multiple files

on disk. In order to prevent lookups into files that do not

contain the key, a bloom filter, summarizing the keys in

the file, is also stored in each data file and also kept in

memory. This bloom filter is first consulted to check if the

key being looked up does indeed exist in the given file.

?

当查找一个key时，会发生磁盘扫描。为了提高效率，我们不会扫描不存在某个key的文件。为了做到这一点，一个bloom filter维护了某个数据文件的所有key信息，并且这个bloom filter也持久化在数据文件。可以优先利用这个bloom filter判断这个key是否在该数据文件中，这样，不保存这个key的数据文件就不会被查找。

?

?

?

?

?