Java中的布隆过滤器,你知道吗?
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash Table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n)、O(logn)、O(1)。
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。
图片
检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。
图片
接下来,我们看下在Java中怎么使用。
单机版:Guava
首先引入依赖:
com.google.guava
guava
33.2.1-jre
然后使用Guava中的BloomFilter类开始实现:
@Test
public void testBloomFilter() {
final List itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");
// 创建布隆过滤器
BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100, 0.01);
// 当前元素数量为0
Assertions.assertEquals(0, bloomFilter.approximateElementCount());
// 向布隆过滤器中插入数据
for (String item : itemsToInsert) {
bloomFilter.put(item);
}
// 当前元素数量为4
Assertions.assertEquals(4, bloomFilter.approximateElementCount());
// 测试已插入的数据
for (String item : itemsToInsert) {
Assertions.assertTrue(bloomFilter.mightContain(item), "Item should be in the Bloom Filter: " + item);
}
// 测试未插入的数据
final List itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
for (String item : itemsNotInserted) {
Assertions.assertFalse(bloomFilter.mightContain(item), "Item should not be in the Bloom Filter: " + item);
}
}
Guava实现的是单机版,虽然提供了文件写出的功能,可以将文件分发到分布式系统中,但是这种方式只能是补充。推荐只在单机场景中使用Guava的布隆过滤器。
如果想要在分布式服务中使用,可以选择Redission。
分布式版:Redission
引入依赖:
org.redisson
redisson
3.11.5
使用Docker在本地启一个Redis服务,用来验证:
docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
然后编码测试:
@Test
public void testBloomFilter() {
// 使用Docker本地启动一个Redis服务用来测试:
// docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
// 生成key是 myBloomFilter 的存储
// 会生成两个key,"myBloomFilter"、"{myBloomFilter}:config"
// "myBloomFilter"是string类型,布隆过滤器的主存
// "{myBloomFilter}:config"是hash结构,存储元信息,比如大小size、期望容量expectedInsertions、误报率falseProbability、使用的哈希函数数量hashIterations等。
RBloomFilter bloomFilter = Redisson.create(config)
.getBloomFilter("myBloomFilter");
// 初始化布隆过滤器,定义期望容量和误报率
bloomFilter.tryInit(1000000, 0.01);
// 准备一些测试数据
final List itemsToInsert = Arrays.asList("apple", "banana", "cherry", "elderberry");
// 向布隆过滤器中插入数据
for (String item : itemsToInsert) {
bloomFilter.add(item);
}
// 测试已插入的数据
for (String item : itemsToInsert) {
Assertions.assertTrue(bloomFilter.contains(item), "Item should be in the Bloom Filter: " + item);
}
// 测试未插入的数据
final List itemsNotInserted = Arrays.asList("grape", "orange", "peach", "quince", "raspberry");
for (String item : itemsNotInserted) {
Assertions.assertFalse(bloomFilter.contains(item), "Item should not be in the Bloom Filter: " + item);
}
}
使用Redission的RBloomFilter,会根据布隆过滤器名字在Redis中生成两个key,比如上面代码的名字是“myBloomFilter”,生成的配置为:
- "myBloomFilter"是string类型,布隆过滤器的主存,用来存储二进制数组;
- "{myBloomFilter}:config"是hash结构,存储元信息,比如大小size、期望容量expectedInsertions、误报率falseProbability、使用的哈希函数数量hashIterations等。