Guava框架中Bloom Filter的使用

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>
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容