atch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}
//计算位数组长度
//n:插入的数据条目数量
//p:期望误判率
@VisibleForTesting
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)));
}
// 计算哈希次数
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
Guava 的计算位数组长度和哈希次数和原理解析这一节展示的公式保持一致。
重点来了,Bloom filter 是如何判断元素存在的 ?
方法名就非常有 google 特色 , ”mightContain“ 的中文表意是:”可能存在“ 。方法的返回值为 true ,元素可能存在,但若返回值为 false ,元素必定不存在。
public <T extends @Nullable Object> boolean mightContain(
@ParametricNullness T object,
//Funnel 是一个接口,用于将任意类型的对象转换为字节流,
//以便用于布隆过滤器的哈希计算。
Funnel<? super T> funnel,
//用于计算哈希值的哈希函数的数量
int numHashFunctions,
//位数组实例,用于存储布隆过滤器的位集
LockFreeBitArray bits) {
long bitSize = bits.bitSize();
//使用 MurmurHash3 哈希函数计算对象 object 的哈希值,
//并将其转换为一个 byte 数组。
byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
long hash1 = lowerEight(bytes);
long hash2 = upperEight(bytes);
long combinedHash = hash1;
for (int i = 0; i < numHashFunctions; i++) {
// Make the combined hash positive and indexable
// 计算哈希值的索引,并从位数组中查找索引处的位。
// 如果索引处的位为 0,表示对象不在布隆过滤器中,返回 false。
if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) {
return false;
}
// 将 hash2 加到 combinedHash 上,用于计算下一个哈希值的索引。
combinedHash += hash2;
}
return true;
}
3 Redisson实现
Redisson 是一个用 Java 编写的 Redis 客户端,它实现了分布式对象和服务,包括集合、映射、锁、队列等。Redisson的API简单易用,使得在分布式环境下使用Redis 更加容易和高效。
1、添加Maven依赖
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.16.1</version>
</dependency>
2、配置 Redisson 客户端
@Configuration
public class RedissonConfig {
Bean
public RedissonClient redissonClient() {
Config config = new Config();
config.useSingleServer().setAddress("redis://localhost:6379");
return Redisson.create(config);
}
}
3、初始化
RBloomFilter<Long> bloomFilter = redissonClient.
getBloomFilter("myBloomFilter");
//10000表示插入元素的个数,0.001表示误判率
bloomFilter.tryInit(10000, 0.001);
//插入4个元素
bloomFilter.add(1L);
bloomFilter.add(2L);
bloomFilter.add(3L);
bloomFilter.add(4L);
4、判断数据是否存在
public boolean mightcontain(Long id) {
return bloomFilter.contains(id);
}
好,我们来从源码分析 Redisson 布隆过滤器是如何实现的 ?
public boolean tryInit(long expectedInsertions, double falseProbability) {
// 位数组大小
size = optimalNumOfBits(expectedInsertions, falseProbability);
// 哈希函数次数
hashIterations = optimalNumOfHashFunctions(expectedInsertions, size);
CommandBatchService executorService = new CommandBatchService(commandExecutor);
// 执行 Lua脚本,生成配置
executorService.eva lReadAsync(configName, codec, RedisCommands.eva l_VOID,
"local size = redis.call('hget', KEYS[1], 'size');" +
"local hashIterations = redis.call('hget', KEYS[1], 'hashIterations');" +
"assert(size == false and hashIterations == false, 'Bloom filter config has been changed')",
Arrays.<Object>asList(configName), size, hashItera