java中BloomFilter（布隆过滤器）简单使用

简介

布隆过滤器适合大数据判重的场景，如网络爬虫中判断一个URL是否已经爬取过，判断一个用户是否在黑名单中，判断一个邮件是否是垃圾邮件，等等。
优点：占用空间小，效率高，简而言之，就是以正确率换空间和时间。
缺点：有一定的误判率，一个URL经过布隆过滤器判断没爬取过，那么一定没爬取过，一个URL经过布隆过滤器判断爬取过，可能并没有爬取过，这种情况会有误判。
布隆过滤器本身是基于位图的，是对位图的一种改进，位图在java中的实现就是BitSet。

简单使用

java中的Guava工具包提供了BloomFilter的实现。

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>27.1-jre</version>
</dependency>

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.ArrayList;
import java.util.List;

public class Client {

  public static void main(String[] args) {
    int size = 1_000_000;
    BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);
    for (int i = 0; i < size; i++) {
      bloomFilter.put(i);
    }
    for (int i = 0; i < size; i++) {
      if (!bloomFilter.mightContain(i)) {
        System.out.println("有坏人逃脱了");
      }
    }
    List<Integer> list = new ArrayList<>(1000);
    for (int i = size + 10000; i < size + 20000; i++) {
      if (bloomFilter.mightContain(i)) {
        list.add(i);
      }
    }
    System.out.println("有误伤的数量：" + list.size());
  }

}

输出结果为

有误伤的数量：330

可以看到，不会有坏人逃脱，但会有误伤，误伤率大概为3%。

这种情况下大概要使用内存为7298440bit，约0.87M。

我们将误伤率改为0.0003

BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.0003);

误伤数量为2，使用内存为16883499bit，约2.013M。

参考

BloomFilter布隆过滤器使用
Bloomfilter 的应用场景