了解布隆过滤器原理以及 Guava 的 BloomFilter 使用

假设遇到这样一个问题:要求判断某个网址 URL 是否在一个 20 亿的网址 URL 集合中,并且需在给定内存空间(比如:500M)内快速判断出。

可能很多人首先想到的会是使用 HashSet,因为HashSet 基于 HashMap,理论上时间复杂度为:O(1)。达到了快速的目的,但是空间复杂度呢?URL 字符串通过 Hash 得到一个 Integer 的值,Integer 占 4 个字节,那 20 亿个 URL 理论上需要:20 亿 *4/1024/1024/1024=7.45G 的内存,不满足空间复杂度的要求。

这里就引出本文要介绍的“布隆过滤器”。

何为布隆过滤器

百科上对布隆过滤器的介绍是这样的:

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。
它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

是不是描述的比较抽象?那就直接了解其原理吧!

还是以上面的例子为例:

哈希算法得出的 Integer 的哈希值最大为:Integer.MAX_VALUE = 2147483647,意思就是任何一个 URL 的哈希都会在 0~2147483647 之间。

那么可以定义一个 2147483647 长度的 byte 数组,用来存储集合所有可能的值。为了存储这个 byte 数组,系统只需要:2147483647/8/1024/1024=256M

比如:某个 URL(X)的哈希是 2,那么落到这个 byte 数组在第二位上就是 1,这个 byte 数组将是:000….00000010,重复的,将这 20 亿个数全部哈希并落到 byte 数组中。

判断逻辑:

如果 byte 数组上的第二位是 1,那么这个 URL(X)可能存在。为什么是可能?因为有可能其它 URL 因哈希碰撞哈希出来的也是 2,这就是误判。

但是如果这个 byte 数组上的第二位是 0,那么这个 URL(X)就一定不存在集合中。

多次哈希:

为了减少因哈希碰撞导致的误判概率,可以对这个 URL(X)用不同的哈希算法进行 N 次哈希,得出 N 个哈希值,落到这个 byte 数组上,如果这 N 个位置没有都为 1,那么这个 URL(X)就一定不存在集合中。

Guava 的 BloomFilter

Guava 框架提供了布隆过滤器的具体实现:BloomFilter,使得开发不用再自己写一套算法的实现。

创建 BloomFilter

BloomFilter 提供了几个重载的静态 create 方法来创建实例:

1
2
3
4
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);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions);

最终还是调用:

1
2
3
4
5
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
// 参数含义:
// funnel 指定布隆过滤器中存的是什么类型的数据,有:IntegerFunnel,LongFunnel,StringCharsetFunnel。
// expectedInsertions 预期需要存储的数据量
// fpp 误判率,默认是 0.03。

BloomFilter 里 byte 数组的空间大小由 expectedInsertionsfpp 参数决定,见方法:

1
2
3
4
5
6
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

真正的 byte 数组维护在类:BitArray中。

使用

最后通过:putmightContain 方法,添加元素和判断元素是否存在。

算法特点

  • 因使用哈希判断,时间效率很高。空间效率也是其一大优势。
  • 有误判的可能,需针对具体场景使用。
  • 因为无法分辨哈希碰撞,所以不是很好做删除操作。

使用场景

  • 黑名单
  • URL 去重
  • 单词拼写检查
  • Key-Value 缓存系统的 Key 校验
  • ID 校验,比如订单系统查询某个订单 ID 是否存在,如果不存在就直接返回。