200214-Guava BloomFilter 使用手册
by 一灰灰

2020-02-14

开源 / Guava

6 分钟读完 (大约 842 个字) 0次访问

200214-Guava BloomFilter 使用手册

文章目录

I. BloomFilter
1. 1. 基本知识点
2. 2. Guava 示例
II. 其他

在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，接下来我们简单看一下使用姿势

引入依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>xxx</version>
</dependency>

api讲解

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

// 创建，请注意第二个参数表示数组长度，第三个表示错误率
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

实例

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

@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

@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. 一灰灰Blog： https://liuyueyi.github.io/hexblog

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

2. 声明

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

微博地址: 小灰灰Blog
QQ：一灰灰/3302797840

3. 扫描关注

一灰灰blog

QrCode

# BloomFilter, Guava

支付宝

微信

一灰灰Blog

Java,Python,DBA, 主旨服务器，兼职全栈

Wuhan, China

文章

523

分类

101

标签

122

关注我