【算法】布隆过滤器（BloomFilters）

描述布隆过滤器的功能以及如何使用 guava 的布隆过滤器

前言

为了判断一个元素是否在一个集合里，通常的做法是用 List， Set， HashMap 等容器保存集合的元素，然后在判断元素是否在集合里。然而当数据量非常大时，内存可能无法保存所有的元素集合。这时可以考虑用布隆过滤器实现。

实现

布隆过滤器使用一个 bit 向量或者说 bit 数组实现，它先将集合的元素散列到 bit 数组上。当要判断元素是否在集合里时，先计算元素的散列值，如果散列值不在 bit 数组上，则该元素一定不在集合里，如果散列值在 bit 数组上，则该元素可能会在集合里。

要实现一个布隆过滤器，首先要选择适当的 bit 数组长度，然后选择多个散列函数。对于每个要加入到集合的元素，用各个散列函数分别计算出散列值，然后 bit 数组对应的下标置 1。例如考虑一个长度是 8 的 bit 数组用于过滤域名。对于 “baidu”，有 3 个不同的散列函数，计算出来的散列值分别是 1，4，7，则 bit[1], bit[4], bit[7] 分别置为 1，对于“google”，散列值分别是 2，4，5，则 bit[1]，bit[4]，bit[5] 分别置为 1。

要测试“yahoo”是否在集合里时，可以计算“yahoo”的散列值，如果是 1，2，7（即不是所有散列值都在 bit 数组），则说明这个元素不在集合里，反之则有可能在集合里

布隆过滤器演示

布隆过滤器特点

节省空间
布隆过滤器不需要存储数据本身，只需要保存 bit
高效
插入和查询都是 O(k)
可并行计算
各个散列函数之前独立，可以并行计算散列值
存在假阳性
假阳性率即布隆过滤器误报的概率

随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值即使不在集合里，也有可能因为它的散列值在 bit 数组里而被判断里在集合里存在。所以布隆过滤器有一定的误报率，这个误报率和 hash 算法的次数 H，以及数组长度 L 都有关。
不能删除
由于散列值可能有重合的情况，所以 bit 数组的值是不能置 0 的，即布隆过滤器不能进行删除操作，否则可能删除一个元素会变成删除两个元素

假阳性率（false positive probability）的计算

假设散列函数选择位数组中的比特时，都是等概率的，即数据均匀分布

bit 数组长度为 m 时，布隆过滤器的散列函数会将某个特定的 bit 置 1，插入元素后，某个 bit 仍然为 0 的概率是

1 - 1/m

现在有 k 个散列函数，并插入 n 个元素，则该 bit 仍然为 0 的概率是

1	(1 - 1/m) ^ (k * n)

则它被置为 1 的概率是

1	1 - (1 - 1/m) ^ (k * n)

当插入 n 个元素后，用一个不存在于集合的元素来检测，误报率为

1	(1 - (1 - 1/m) ^ (k * n)) * k

当 n 比较大时，可以近似得到假阳性率为

1	(1 - e ^ (-kn/m)) ^ k

结论是

m 越大，假阳率越低
n 越大，假阳率越高

利用 guava 的布隆过滤器做过滤功能

示例


public static void main(String[] args) {
  // 创建一个布隆过滤器
  BloomFilter<String> bloomFilter = BloomFilter.create(
    Funnels.stringFunnel(Charset.defaultCharset()),
    1000);

  // 插入元素
  bloomFilter.put("baidu");
  bloomFilter.put("google");

  // 检查元素是否存在
  System.out.println(bloomFilter.mightContain("yahoo"));  // false
  System.out.println(bloomFilter.mightContain("google")); // true
}

BloomFilter 包含 4 个关键成员

// bit 数组
private final BitArray bits;

// 散列函数的个数
private final int numHashFunctions;

// Funnel 接口实现类的实例，它用于将任意类型 T 的输入数据转化为 Java 基本类型的数据
// 这里是会转化为 byte
private final Funnel<? super T> funnel;

// 散列策略
private final Strategy strategy;

BloomFilter 的构造方法是私有的，要构建 BloomFilter 对象就要用 create 方法创建，有几个重载形式，如下

// 不对外暴露
static <T> BloomFilter<T> create(
  Funnel<? super T> funnel, // Funnel 接口实现类的实例
  long expectedInsertions, // bit 数组的长度
  double fpp, // 假阳率
  Strategy strategy // 散列策略
);

// fpp 是 0.03
// strategy 是 BloomFilterStrategies.MURMUR128_MITZ_64
public static <T>
BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions);

public static <T>
BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions);

// strategy 是 BloomFilterStrategies.MURMUR128_MITZ_64
public static <T>
BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp);

public static <T>
BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp);

BloomFilterStrategies 枚举中定义了两种散列策略，都基于 MurmurHash 算法，分别是 MURMUR128_MITZ_32 和 MURMUR128_MITZ_64，前者是一个简化版 MurmurHash（默认也是它）