Bloom Filter 用来快速查找某个元素在不在集合中的算法,但不保证100%正确,有一定概率的误判(False Positive), 也就是判断结果是在集合中的话,存在一定几率其实元素不在集合中。但是不会又漏判(False Negative),就是判断结果不在几何中的话,那这个元素肯定不在集合中。

加入元素

用1个长度为 m 的 BitSet,每一位初始化为0,然后选择 k 个 hash 函数,每个 hash 函数的结果在0-(m-1)之间。调用每一个 hash 函数,把 hash 结果对应的 bit 位置为1.

检查元素

和加入元素时一样,调用每个 hash 函数,如果每一个对应的位都是1,那么认为元素存在于集合中(不是100%)。只要有1位不为1,则认为肯定不存在于这个集合中。

删除元素

删除元素会影响到其他元素,因为不同元素的 hash 函数会有碰撞。可以把每个 bit 改为一个计数器来实现删除元素。

参数选择

哈希函数个数k,位数组大小m,加入的元素数量n。对于给定的m、n,当 k = ln(2) * m / n 1时出错的概率是最小的。

简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package set;
import java.util.BitSet;

public class BloomFilter {
private BitSet bs;
private static final int DEFAULT_SIZE = 1 << 25;
private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };

public BloomFilter() {
bs = new BitSet(DEFAULT_SIZE);
}

public void add(String str) {
for (int seed : seeds)
bs.set(hash(str, seed));
}

public boolean contains(String str) {
for (int seed : seeds) {
if (!bs.get(hash(str, seed))) return false;
}
return true;
}

public int hash(String str, int seed) {
int result = 0;
for (int i = 0; i < str.length(); i++) {
result = seed * result + str.charAt(i);
}
return (DEFAULT_SIZE - 1) & result;
}

public static void main(String[] args) {
BloomFilter bf = new BloomFilter();
bf.add("hello");
bf.add("hello1");
bf.add("hello2");
System.out.println(bf.contains("hello3"));
}
}
  1. http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html ↩︎