goole在Guava框架中直接實(shí)現(xiàn)了Bloom Filter,使得我們不用再根據(jù)Bloom Filter的原理自行實(shí)現(xiàn)。
創(chuàng)建Bloom Filter
Bloom Filter提供了四個(gè)靜態(tài)的create方法來創(chuàng)造實(shí)例:
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);
上述四種方式中都調(diào)用了一個(gè)統(tǒng)一的create方法:
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
// 參數(shù)含義:
// funnel 指定布隆過濾器中存的是什么類型的數(shù)據(jù)胯陋,有:IntegerFunnel鳖粟,LongFunnel,StringCharsetFunnel翁授。
// expectedInsertions 預(yù)期需要存儲(chǔ)的數(shù)據(jù)量
// fpp 誤判率救湖,默認(rèn)是 0.03愧杯。
Bloom Filter中的數(shù)組空間大小、hash函數(shù)的個(gè)數(shù)都由參數(shù)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直接給我們提供一個(gè)現(xiàn)成的bloom Filter跌前,直接包含了數(shù)組長(zhǎng)度和hash函數(shù)個(gè)數(shù)的確定方法,進(jìn)而免去了構(gòu)造Bloom Filter時(shí)我們自己不好確定的兩個(gè)參數(shù)陡舅。
最后把guava的maven放上來共有緣人使用(這里面使用的是最新的版本抵乓,大家使用的時(shí)候也可以根據(jù)自己的需求更改):
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>20.0</version>
</dependency>