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时出错的概率是最小的。

简单实现

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 ↩︎