goole在Guava框架中直接实现了Bloom Filter,使得我们不用再根据Bloom Filter的原理自行实现。
创建Bloom Filter
Bloom Filter提供了四个静态的create方法来创造实例:
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);
上述四种方式中都调用了一个统一的create方法:
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
// 参数含义:
// funnel 指定布隆过滤器中存的是什么类型的数据,有:IntegerFunnel,LongFunnel,StringCharsetFunnel。
// expectedInsertions 预期需要存储的数据量
// fpp 误判率,默认是 0.03。
Bloom Filter中的数组空间大小、hash函数的个数都由参数expectedInsertions 、fdd共同确定:
long numBits = optimalNumOfBits(expectedInsertions, fpp);
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)));
}
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int)Math.round((double)m / (double)n * Math.log(2.0D)));
}
使用
Bloom Filter中包含put、mightContain方法,添加元素和判断元素是否存在。
filter.put(value);
filter.mightContain(value);
google直接给我们提供一个现成的bloom Filter,直接包含了数组长度和hash函数个数的确定方法,进而免去了构造Bloom Filter时我们自己不好确定的两个参数。
最后把guava的maven放上来共有缘人使用(这里面使用的是最新的版本,大家使用的时候也可以根据自己的需求更改):
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>20.0</version>
</dependency>