200214-Guava BloomFilter 使用手册

文章目录
  1. I. BloomFilter
    1. 1. 基本知识点
    2. 2. Guava 示例
  2. II. 其他
    1. 1. 一灰灰Blog: https://liuyueyi.github.io/hexblog
    2. 2. 声明
    3. 3. 扫描关注

在jdk中有一个数据结构BitSet,可以用来执行位操作,比如我们常见的统计网站在线人数、pv/uv等;但是当数据样本分布不均,可能导致较大的空间浪费;其次它更适用于正整数类型的判定,针对其他的业务场景,有点薄弱

本文将介绍BloomFilter(布隆过滤器)的相关知识点,以及Guava中BloomFilter的使用姿势

I. BloomFilter

1. 基本知识点

什么是布隆过滤器?

一个简单的理解,如下

  • 首先它同样是一个m位数组
  • 其次拥有k个独立的hash函数
  • 每塞入一个数据,上面的所有hash函数都会计算一遍,等到一个整数值index,然后将数组中,index坐标对应的值设置为1
  • 当判断一个数据是否存在时,只需要计算所有的hash函数的值,判断在数组中是否都是1,如果有一个不为1,那么必然不存在;如果全是1,则可能存在

上面的这个判断逻辑,核心点在于:

  • 判定不存在,100%正确
  • 判定存在,则不一定(可以想一想为什么?)

2. Guava 示例

Guava包中提供了一个可以直接使用的BloomFilter,接下来我们简单看一下使用姿势

引入依赖

1
2
3
4
5
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>xxx</version>
</dependency>

api讲解

一般来讲,我们只关注BloomFilter的三个方法

1
2
3
4
5
6
7
8
// 创建,请注意第二个参数表示数组长度,第三个表示错误率
com.google.common.hash.BloomFilter#create(com.google.common.hash.Funnel<? super T>, int, double)

// 添加对象
com.google.common.hash.BloomFilter#put

// 判断是否存在
com.google.common.hash.BloomFilter#mightContain

实例

一个简单的字符串使用实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void testBloom() {
// 初始化一个存储string数据的布隆过滤器,初始化大小1w, 错误率为0.1%
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 1000, 0.001);

// 添加数据
bloomFilter.put("hello world!");

// 判断是否存在,false则表示一定不存在; true表示可能存在
boolean ans = bloomFilter.mightContain("hello world!");
System.out.println(ans);

ans = bloomFilter.mightContain("hello world");
System.out.println(ans);
}

对于Guauva的BloomFilter而言,是支持普通对象的判断的,主要是借助Funnel接口来实现,下面是一个简单的case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@Test
public void testBloom2() {
BloomFilter<Map> bloomFilter = BloomFilter.create(new Funnel<Map>() {
@Override
public void funnel(Map map, PrimitiveSink primitiveSink) {
primitiveSink.putString(map.toString(), Charsets.UTF_8);
}
}, 1000, 0.001);

Map<String, String> map = new HashMap<>();
map.put("a", "b");
bloomFilter.put(map);

map.put("a", "");
bloomFilter.put(map);

// 判断是否存在,false则表示一定不存在; true表示可能存在
boolean ans = bloomFilter.mightContain(map);
System.out.println(ans);

map.put("a", "c");
ans = bloomFilter.mightContain(map);
System.out.println(ans);
}

II. 其他

1. 一灰灰Bloghttps://liuyueyi.github.io/hexblog

一灰灰的个人博客,记录所有学习和工作中的博文,欢迎大家前去逛逛

2. 声明

尽信书则不如,已上内容,纯属一家之言,因个人能力有限,难免有疏漏和错误之处,如发现bug或者有更好的建议,欢迎批评指正,不吝感激

3. 扫描关注

一灰灰blog

QrCode

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×