介绍

Bloom Filter，布隆过滤器是基于bit数组的一种数据结构，可以验证一个元素可能存在，或者一定不存在。

原理图示

通过k个哈希函数将元素映射到一个位数组的k个点，并设置为1。当查询一个元素是否存在，只用看对应位数组k个点的值即可。

相比传统Set校验，极大节省了存储空间。理想情况下，64byte的url映射到1个bit上，只占用原来的1/(64*1024)空间。

为什么“可能存在”

当查找jd.com是否存在时，由于哈希冲突导致误判得到了存在的结果。

可以通过提高转换后的位元素分散度来降低误判率；

• 增加位数组大小
• 增加哈希函数个数

删除元素

传统的Bloom Filter由于哈希冲突不支持删除操作，但Counting Bloom Filter的出现为此提供了可能。

Counting Bloom Filter将位数组每一位拓展成一个计数器，删除时在k个点位减1即可。

相比传统的会占用几倍的空间，且不能保证一定能正确删除，因为删除的前提是存在但得不到保证，参考为什么“可能存在”。

应用场景

• 避免缓存击穿
• 网页URL去重
• 垃圾邮件检测

Java Demo

基于JDK的BitSet的简单示例；

public class BloomFilter<T> {

    /**
     * JDK位数组，底层是long数组
     */
    private BitSet bitSet;

    public BloomFilter(int bitLen) {
        bitSet = new BitSet(bitLen);
    }

    private int hash1(T t) {
        return Math.abs(t.hashCode() % bitSet.size());
    }

    private int hash2(T t) {
        return Math.abs(t.hashCode() * 2 % bitSet.size());
    }

    /**
     * 插入元素
     */
    public void add(T t) {
        bitSet.set(hash1(t));
        bitSet.set(hash2(t));
    }

    /**
     * 判断是否存在
     */
    public boolean contains(T t) {
        return bitSet.get(hash1(t))
                && bitSet.get(hash2(t));
    }
}

Guava

业界权威Guava已经实现，可控制误报率；

BloomFilter<Integer> bloomFilter = BloomFilter.create(
        Funnels.integerFunnel(),
        // 预计数据量
        100000000,
        // 误报率
        0.001);
// 插入数据
for (int i = 0; i < 100000000; i++) {
    bloomFilter.put(i);
}
// 判断是否存在
System.out.println(bloomFilter.mightContain(-1));
System.out.println(bloomFilter.mightContain(1));

redis bitmap

也可以通过Redis的setbit、getbit和bitcount几个相关的bitmap命令来实现，业界Redisson已是权威；

public class RedissonBloomFilter {

    public static void main(String[] args) {
        // 构造Redisson
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);
        // 初始化(预计数据量，误报率)
        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("urlList");
        bloomFilter.tryInit(100000000L, 0.001);
        // 插入元素
        bloomFilter.add("baidu.com");
        bloomFilter.add("qq.com");
        // 判断是否存在
        System.out.println(bloomFilter.contains("jd.com"));
    }
}

参考

• 详解布隆过滤器的原理，使用场景和注意事项