一布隆过滤器简介

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的相似于 Set 的数据结构。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个汇合中，但检索的后果并不是很准确，数据质变大的就会产生误判情景，但布隆过滤器的都是能过滤掉曾经存在的内容，所以误判的状况就是不在布隆过滤器中的数据有可能误判为曾经存在，这个性能在某些场景下很有用。

布隆过滤器应用场景

布隆过滤器最大的作用就是大数据量下的去重性能，所以常常应用在如下场景

• 举荐零碎，比方商品，新闻举荐，去除曾经举荐过的新闻或商品；
• 网页爬虫对 URL 去重，防止爬取雷同的 URL 地址；
• 大数据状况下，从邮件中断定垃圾邮箱；

二布隆过滤器原理简介

布隆过滤器是由一串很长的二进制向量组成，能够将其看成一个二进制数组；寄存 0 或者 1，默认都是 0；

增加数据

向布隆过滤器中增加一个元素 key 时，通过多个 hash 函数计算多个 hash 值，并将对应地位的值置为 1；因为不同的 key 就有不同 1 的地位，用于辨别 key；然而但数据量大的时候，就会呈现雷同 key 被几个 hash 函数 hash 后的值一样，所以会呈现误差；

布隆过滤器应用 contain 办法判断元素是否在过滤器中达到去重成果 ；

三实现形式

3.1guava 库实现

增加 guava 依赖

<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>

实现：

@Test
public void contextLoads() {
// 总数量 1W
int total = 10000;
// 设置过滤器
BloomFilter<CharSequence> bf =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// 初始化 1W 条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put(“ 常识追寻者 ” + i);
}
// 判断值是否存在过滤器中
int count = 0;
// 插入 2w 条数据进行去重校验
int addCount = 2*total;
for (int i = 0; i < addCount; i++) {
if (bf.mightContain(“ 常识追寻者 ” + i)) {
count++;
}
}
System.out.println(“ 匹配数量 ” + count);
}

控制台输入匹配数量大于 1w，所以能起到过滤反复数据的作用；

匹配数量 10294

调节 fpp 误判率能够实现比拟准确的过滤

294/2w=0.0147

fpp 默认是 0.03d, 设置为 0.0147d

BloomFilter<CharSequence> bf =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total,0.0147d);

匹配后果如下

匹配数量 10143

3.2redis 实现形式

redis 4.0 版本才反对布隆过滤器

redis 实现形式应用指令 bf.add 增加元素，bf.exists 查问元素是否存在；数据量小的时候看不出来具体差异

127.0.0.1:6379> bf.add codeding h1
(integer) 1
127.0.0.1:6379> bf.add codeding h2
(integer) 1
127.0.0.1:6379> bf.add codeding h3
(integer) 1
127.0.0.1:6379> bf.exists codeding h1
(integer) 1
127.0.0.1:6379> bf.exists codeding h2
(integer) 1
127.0.0.1:6379> bf.exists codeding h3
(integer) 1
127.0.0.1:6379> bf.exists codeding h4
(integer) 0

应用 Redisson 实现，版本 3.x 以上

<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.11.4</version>
</dependency>

如果是 springboot

<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.10.1</version>
</dependency>

实现代码

@Test
public void test2(){
Config config = new Config();
config.useSingleServer().setAddress(“redis://ip:port”);
config.useSingleServer().setPassword(“ 明码 ”);
// 结构 Redisson
RedissonClient redisson = Redisson.create(config);
// 获取布隆过滤器
RBloomFilter<String> bloomFilter = redisson.getBloomFilter(“userList”);
// 初始化布隆过滤器：预计元素为 1wL, 误差率为 3%
// 总数量 100
long total = 100L;
bloomFilter.tryInit(total,0.03);
// 初始化 1W 条数据到过滤器中
for (int i = 0; i < total; i++) {
bloomFilter.add(“zszxz” + i);
}
int count = 0;
// 200 条数据进行去重校验
long addCount = 2*total;
for (int i = 0; i < addCount; i++) {
if (bloomFilter.contains(“zszxz” + i)) {
count++;
}
}
// 匹配数量 108
System.out.println(“ 匹配数量 ” + count);
}

匹配数量为 108，比 100 多了 8 条；也能够通过调整误差率实现较为准确的过滤；

关注常识追寻者，获取 2020 版面试题一份