布隆过滤器(Bloom Filter)

@[TOC](布隆过滤器(Bloom Filter))

（1）什么是布隆过滤器

（1）布隆过滤器的简单介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

可以把布隆过滤器理解为一个set集合，我们可以通过add往里面添加元素，通过contains来判断是否包含某个元素。由于本文讲述布隆过滤器时会结合Redis来讲解，因此类比为Redis中的Set数据结构会比较好理解，而且Redis中的布隆过滤器使用的指令与Set集合非常类似

（2）布隆过滤器的优点

（1）时间复杂度低，增加和查询元素的时间复杂为O(N)，（，每个哈希函数的时间复杂度为O(1)，N为哈希函数的个数，通常情况比较小）
（2）保密性强，布隆过滤器不存储元素本身，只在数组中存储二进制数据0或者1来证明数据是否存在
（3）存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）

（3）布隆过滤器的缺点

（1）有点一定的误判率，但是可以通过调整参数来降低
（2）无法获取元素本身
（3）很难删除元素

（2）布隆过滤器的使用场景

（1）通常判断某个元素是否存在
很多会后想到的是HashMap，确实可以把值映射到HashMap的Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是HashMap的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦数据量达到上亿的时候，那HashMap占据的内存大小就很大了。

如果想判断一个元素是不是在一个集合里，一般想到的是把集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的数量增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述十年后总结构的检索时间复杂度分别为O(n)，O(log n)，O(1)。

（2）布隆过滤器的不同之处

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数把这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大概）知道集合中有没有这个元素了。如果这些点有任何一个0，则被检索的元素一定不存在。如果都是1，则被检索的元素很可能在。
本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure）高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

当你往简单数组或列表中插入新数据时，将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话，当你需要在数组或列表中搜索相应值的时候，你必须遍历已有的集合。若集合中存在大量的数据，就会影响数据查找的效率。

针对这个问题，你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值，然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的，当你需要判断列表中是否存在该值时，只需要对值进行哈希处理并在相应的索引位置进行搜索即可，这时的搜索速度是非常快的。

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在（误判），**利用这个判断是否存在的特点可以做很多有趣的事情。

（1）解决Redis缓存穿透问题（面试重点）
（2）邮件过滤，使用布隆过滤器来做邮件黑名单过滤
（3）对爬虫网址进行过滤，爬过的不再爬
（4）解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
（5）HBase\RocksDB\LevelDB等数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求

（3）布隆过滤器的原理

（1）数据结构

（1）基本数据结构
布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
一个大型位数组（二进制数组）：
（2）多个无偏hash函数
无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图，其中k1、k2代表增加的元素，a、b、c即为无偏hash函数，最下层则为二进制数组。

（3）使用布隆过滤器的过程
二进制数组中使用0和1表示是否存在。

例如在存放”你好“这个字段的时候，会通过多个hash函数分别计算出多个不同的哈希值，不同的哈希值对应数组的下标值，并且把对应下标的二进制数据改为1。
在查找数据的时候，依然通过多个hash函数分别计算出多个不同的哈希值，如果所有哈希值对应数组中下标中的二进制值都为1，那么就可以证明存在”你好“这个数据，如果有至少一个二进制值为0， 就证明不存在。

（2）空间计算

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。

计算关系：
（1）错误率越低，位数组越长，控件占用较大
（2）错误率越低，无偏hash函数越多，计算耗时较长

在线布隆过滤器计算的网址：https://krisives.github.io/bloom-calculator/

（3）增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1
（1）通过k个无偏hash函数计算得到k个hash值
（2）依次取模数组长度，得到数组索引
（3）将计算得到的数组索引下标位置数据修改为1

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.
如图所示：

（4）查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：
（1）通过k个无偏hash函数计算得到k个hash值
（2）依次取模数组长度，得到数组索引
（3）判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

（1）为何产生误判
关于误判，其实非常好理解，hash函数在怎么好，也无法完全避免hash冲突，也就是说可能会存在多个元素计算的hash值是相同的，那么它们取模数组长度后的到的数组索引也是相同的，这就是误判的原因。

例如”hello“和”你好“的哈希值是相同的，那么对应的就是同一个下标的二进制值，如果此时已经存入了”你好“而没有存”hello“，其实在查询的时候也会得到存在”hello“的结果，这样也就产生了误判。所有能查到的不一定存在，查不到的一定不存在。

（2）如果减小误判的概率
调用guava包中的BloomFilter，设置参数，下面有案例

（5）修改元素

（6）删除元素

布隆过滤器对元素的删除不太支持，目前有一些变形的特定布隆过滤器支持元素的删除！关于为什么对删除不太支持，其实也非常好理解，hash冲突必然存在，删除肯定是很难的！

（4）redis集成布隆过滤器

（5）redis中布隆过滤器指令使用

（1）bf.add：添加单个元素，成功返回1

127.0.0.1:6379> bf.add name liziba
(integer) 1
1
2

（2）bf.madd：添加多个元素

127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
1) (integer) 1
2) (integer) 1
3) (integer) 1
1
2
3
4

（3）bf.exists：判断元素是否存在，存在则返回1，不存在返回0

127.0.0.1:6379> bf.mexists name liziba
1) (integer) 1
1
2

（4）bf.mexists：判断多个元素是否存在，存在的返回1，不存在的返回0

127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
1) (integer) 1
2) (integer) 1
3) (integer) 0
1
2
3
4

（6）Java本地内存使用布隆过滤器

使用布隆过滤器的方式有很多，还有很多大佬自己手写的，我这里使用的是谷歌guava包中实现的布隆过滤器，这种方式的布隆过滤器是在本地内存中实现。

（1）引入pom依赖

<dependency>
  <groupId>com.google.guavagroupId>
  <artifactId>guavaartifactId>
  <version>29.0-jreversion>
dependency>
1
2
3
4
5

（2）编写测试代码

package com.lizba.bf;
 
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
/**
 * 

 *        布隆过滤器测试代码
 * 
 *
 * @Author: Liziba
 * @Date: 2021/8/29 14:51
 */
public class BloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000000;
    /** 误判率 */
    private static Double fpp = 0.01;
    /** 布隆过滤器 */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
 
    public static void main(String[] args) {
        // 插入 1千万数据
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }
 
        // 用1千万数据测试误判率
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions *2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("一共误判了：" + count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

（3）测试结果

误判了100075次，大概是expectedInsertions（1千万）的0.01，这与我们设置的 fpp = 0.01非常接近。

（4）参数说明

在guava包中的BloomFilter源码中，构造一个BloomFilter对象有四个参数：
（1）Funnel funnel：数据类型，由Funnels类指定即可
（2）long expectedInsertions：预期插入的值的数量
（3）fpp：错误率
（4）BloomFilter.Strategy：hash算法

（5）fpp&expectedInsertions

（1）当expectedInsertions=10000000&&fpp=0.01时，位数组的大小numBits=95850583，hash函数的个数numHashFunctions=7

（2）当expectedInsertions=10000000&&fpp=0.03时，位数组的大小numBits=72984408，hash函数的个数numHashFunctions=5

（3）当expectedInsertions=100000&&fpp=0.03时，位数组的大小numBits=729844，hash函数的个数numHashFunctions=5

（4）总结
1-当预计插入的值的数量不变时，偏差值fpp越小，位数组越大，hash函数的个数越多。但是fpp越小，占用的空间越大，计算的时间也就越久，效率就越差。
2-当偏差值不变时，预计插入的中的数量越大，位数组越大，hash函数并没有变化（注意这个结论只是在guava实现的布隆过滤器中的算法符合，并不是说所有的算法都是这个结论，我做了多次测试，确实numHashFunctions在fpp相同时，是不变的！）

（7）Java集成redis使用布隆过滤器

Redis经常会被问道缓存击穿问题，比较优秀的解决办法是使用布隆过滤器，也有使用空对象解决的，但是最好的办法肯定是布隆过滤器，我们可以通过布隆过滤器来判断元素是否存在，避免缓存和数据库都不存在的数据进行查询访问！在如下的代码中只要通过bloomFilter.contains(xxx)即可，这里演示的还是误判率！

（1）引入pom依赖

<dependency>
  <groupId>org.redissongroupId>
  <artifactId>redisson-spring-boot-starterartifactId>
  <version>3.16.0version>
dependency>
1
2
3
4
5

（2）编写测试代码

package com.lizba.bf;
 
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
 
/**
 * 

 *      Java集成Redis使用布隆过滤器防止缓存穿透方案
 * 
 *
 * @Author: Liziba
 * @Date: 2021/8/29 16:13
 */
public class RedisBloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000;
    /** 误判率 */
    private static Double fpp = 0.01;
 
    public static void main(String[] args) {
        // Redis连接配置，无密码
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.211.108:6379");
        // config.useSingleServer().setPassword("123456");
 
        // 初始化布隆过滤器
        RedissonClient client = Redisson.create(config);
        RBloomFilter<Object> bloomFilter = client.getBloomFilter("user");
        bloomFilter.tryInit(expectedInsertions, fpp);
 
        // 布隆过滤器增加元素
        for (Integer i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
 
        // 统计元素
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions*2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println("误判次数" + count);
 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

（3）测试成果

（8）布隆过滤器解决redis缓存穿透的问题

（1）问题描述

例如一个请求到达redis时，发现redis没有这个值，那么这个请求就会去访问数据库。但是如果是恶意的大量的请求一个根据不应该存在的值，那么就会有大量的请求直接到打到数据库上，则就是redis的缓存穿透问题。

（2）解决思路

（1）直接用redis存一个过期时间就可以，当通过某一个key去查询数据的时候，如果对应在数据库中的数据都不存在，我们将此key对应的value设置为一个默认的值，比如“NULL”，并设置一个缓存的失效时间，这时在缓存失效之前，所有通过此key的访问都被缓存挡住了。后面如果此key对应的数据在DB中存在时，缓存失效之后，通过此key再去访问数据，就能拿到新的value了。

（2）解决的目的就是防止大量的请求直接到数据库请求一些不存在的数据，那么就在redis和数据库之间加一个布隆过滤器，在过滤器中保存数据库经常被查询的数据，请求到这里会先在过滤器里判断是否存在请求的值，如果存在才会去访问数据库

（3）解决方案

（1）在pom中引入依赖：

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.11.1</version>
</dependency>
1
2
3
4
5

（2）编写相关配置类

/**
 *
 *  
Redisson配置类
 *
 *
 *
 * @author ysw
 * @date 2022-01-12
 */
@Configuration
public class RedissonConfig {

    @Value("${spring.redis.host:99.248.217.222}")
    private String host;
    @Value("${spring.redis.port:6379}")
    private String port;

    @Bean
    public RedissonClient redissonClient() {
        Config config = new Config();
        // redis为单机模式
        // starter依赖进来的redisson要以redis://开头，其他不用
        config.useSingleServer()
                .setAddress("redis://" + host + ":" + port);
        return Redisson.create(config);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（3）布隆过滤器demo

@Slf4j
@SpringBootTest(webEnvironment = SpringBootTest.WebEnvironment.RANDOM_PORT)
public class RedissonBloomFilter {
    @Resource(name = "redissonClient")
    private RedissonClient redissonClient;

    @Test
    public void bloomFilterDemo(){
        RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("bloom-filter");
        //初始化，容器10000.容错率千分之一
        bloomFilter.tryInit(10000,0.001);
        //添加10000个
        for (int i = 0; i < 10000; i++) {
            bloomFilter.add("YuShiwen" + i);
        }
        //用来统计误判的个数
        int count = 0;
        //查询不存在的数据一千次
        for (int i = 0; i < 1000; i++) {
            if (bloomFilter.contains("xiaocheng" + i)) {
                count++;
            }
        }
        System.out.println("判断错误的个数："+count);
        System.out.println("YuShiwen9999是否在过滤器中存在："+bloomFilter.contains("YuShiwen9999"));
        System.out.println("YuShiwen11111是否在过滤器中存在："+bloomFilter.contains("YuShiwen11111"));
        System.out.println("预计插入数量：" + bloomFilter.getExpectedInsertions());
        System.out.println("容错率：" + bloomFilter.getFalseProbability());
        System.out.println("hash函数的个数：" + bloomFilter.getHashIterations());
        System.out.println("插入对象的个数：" + bloomFilter.count());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32