一布隆过滤器简介

布隆过滤器（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版面试题一份