布隆过滤器讲解及基于Guava BloomFilter案例

偏执的太偏执、 2023-09-25 22:36 59阅读 0赞

**目录**

1、布隆过滤器是什么

2、主要作用

3、存储过程

4、查询过程

5、布隆过滤器的删除操作

6、优点

7、缺点

8、测试误判案例

8.1、引入Guava依赖

8.2、编写测试代码

8.3、测试

8.4、BloomFilter实现原理

9、总结

--------------------

推荐博主视频，讲的很棒：[布隆过滤器详解][Link 1]

### 1、布隆过滤器是什么 ###

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

*  布隆过滤器里面就是一个二进制（**存储0和1**）的数组，下标从0开始

![1846373c0a004954b5a3bb61c4353b18.png][]

### 2、主要作用 ###

*  通过一个的hash函数，计算出数据的hash值，再把哈希值映射到数组中
 *  判断这个数据是不是存储在这个数组中，**不存在则返回0，存在则返回1**，其实就是用二进制（0和1）去表示数据是否存在这个数组中

### 3、存储过程 ###

已下面案例为例：

![19165133000748c1bf1760abe69096b0.png][]

步骤：

1.  布隆过滤器在**没有存储任何数据时，默认都是0**
2.  布隆过滤器中有3个哈希（Hash）函数（这3个哈希函数一定是互不影响的），现在传入一个"你好"的值，通过这3个哈希函数，算出对应的哈希值
3.  Hash1函数通过计算得到哈希值，对应数组中下标为3的位置，从而把数据映射至index=3处
4.  布隆过滤器会把下标为3的二进制向量改为1
5.  同理，经过其他2个哈希函数，分别存储在下标为5、7的位置，并把0改为1

### 4、查询过程 ###

还是以上面的案例为例：

步骤：

1.  布隆过滤器会根据传入的值，通过3个哈希函数计算出该值存储的下标
2.  判断该下标是否为1,为1则表示该下标存储了该值，为0则表示没有存储
3.  由于上述布隆过滤器有3个哈希函数，因此判断该值存不存在，必须满足得到的3个下标的二进制向量值**都等于**1，才能证明该值存在于该数组中，布隆过滤器返回1，**只要有一个不**等于1，则认为该数值中不存在该值，布隆过滤器返回0.

### 5、布隆过滤器的删除操作 ###

*  **在布隆过滤器中，很难进行删除操作**，如下：

![f32931a9c89041d7862079b00919ec2f.png][]

现在有2个值：

*  你好
 *  hello

1.  假设上述的2个值在经过Hash函数计算时，得到了相同的hash值（hash冲突），这时他们都存储在下标index=2的位置
2.  之后，我们需要在布隆过滤器中，移除值"你好"的数据，经过Hash函数计算出该值存储在下标为2的位置
3.  然后布隆过滤器会把该值删除，并把下标为2的二进值向量改为0
4.  这时，当我们在查询"hello"是否存在时，布隆过滤器会得到0，认为不存在
5.  也就是意味着，当多个值存储在同一处下标时，删除任意1个值，其他的值也会被删除
6.  由于布隆过滤器会**造成误删，因此布隆过滤器很难做删除操作**

![25d4482f48844065949be6f11d06ae8d.png][]

### 6、优点 ###

*  由于布隆过滤器是由二进制数组组成的数据，所**占用的空间很小**
 *  **插入和查询的速度快**：布隆过滤器会经过hash函数，计算出哈希值，再映射至数组的下标即可；时间复杂度为O(K)，K=hash函数的个数
 *  **数据的保密性好**，因为数组中存储的不是原始数据，而是0和1的二进制数据

### 7、缺点 ###

*  **很难进行删除操作**
 *  会对数据是否存在，**进行误判**：由于判断数据的hash值是可能相同的（hash冲突），对把不存在的数据的hash值，计算出于数组中已存储的哈希值相同，得到结果为1，从而造成误判

**注意：误判是无法避免的，我们只能减少误判的概率**

### 8、测试误判案例 ###

#### 8.1、引入Guava依赖 ####

*  Guava工具包是由Google提供的，里面封装了布隆过滤器，直接使用即可

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

#### 8.2、编写测试代码 ####

使用到布隆过滤器的代码都在注释中进行说明了：

package com.shuizhu.test;
    
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    import org.apache.commons.logging.Log;
    import org.apache.commons.logging.LogFactory;
    
    /**
     * @author 睡竹
     * @date 2023/4/8
     * 布隆过滤器误判率测试案例
     */
    public class BloomFilterTest {
    
        //日志，用于执行记录时间
        private static final Log log = LogFactory.getLog(BloomFilterTest.class);
        
        //模拟布隆过滤器预计存储数据的大小，这里设置为100万
        private static int size = 1000000;
        //设置 期望的误判率
        private static double error = 0.000000000001;
        /**
         *  创建布隆过滤器
         *  Integer：表示过滤器存储的是整数类型的数据
         *  Funnels.integerFunnel()：表示过滤器只对整数类型进行判断
         */
        private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, error);
        //设置样本数据为100万
        private static int total = 1000000;
    
        public static void main(String[] args) {
            //1、在布隆过滤器中，插入样本数据
            for (int i = 0; i < total; i++) {
                //使用put()插入即可
                bloomFilter.put(i);
            }
            //2、定义一个误判数据量的计量值
            int count = 0;
            //3、误判测试前，打印下一句话，用于测试误判测试时间
            log.warn("误判开始");
            /**
             * 4、添加10万个布隆过滤器中不存在的数据，用于测试误判率
             *
             *    这里直接在total的基础上，再加10万的数据
             */
            for (int i = total; i < total+100000; i++) {
                //mightContain()判断数据是否存在于布隆过滤器中
                if (bloomFilter.mightContain(i)) {
                    count++;
                    //System.out.println("数据：" + i + "误判了");
                }
            }
            log.warn("误判结束");
            //打印误判数据及耗时
            System.out.println("总共误判数为：" + count);
        }
    }

#### 8.3、测试 ####

**<1>在误判率为0.01下**，执行结果为：

![42d2c3dd04c44d738798b42296cb2c78.png][]

*  在12ms内执行完成
 *  误判数为：947（测试总数为10万）
 *  真实误判率为：947 ÷ 10万 = 0.00947 **≈ 0.01** ，符合预期

**<2>修改误判率为0.03：**

![3f0ffd80da084d2e94e65c14c91270c8.png][]

**执行结果如下：**

![3cc2603038b141ab84f34659da29ca0d.png][]

*  在16ms内执行完成
 *  误判数为：3033
 *  真实误判率也与预期的0.03相近

--------------------

**总结：设置的误判率是能直接影响布隆过滤器最终的误判率的，误判率越低，耗时越多**

**问题：我们是不是把误判率设置为无限小，那么就不存在误判了呢？**

--------------------

**<3>修改误判率为0.0000000001**

![960d8ac4513d4e3c944971966635bec4.png][]

该误判率比之前2个案例数值小很多，我们看下执行效果：

![710f9939e93c4d8e86ca67d1c684fe7f.png][]

*  在25ms内执行完成
 *  误判数为0

--------------------

**注意：在测试机器上是特别快的，当在高并发下，误判率越小，耗时越多，会给服务器带来性能损耗。**

**因此：我们需要根据具体的业务需求，设置合理的误判率**

--------------------

#### 8.4、BloomFilter实现原理 ####

以8.3中的案例：

**1>在误判率为0.01下，我们debug下：**

![e19dce7821e5460e88e37e616c28470e.png][]

debug启动：

![f74c9c0ac2334cbe816635ff8873823e.png][]

**2>在误判率为0.03下，我们继续debug下：**

![2c297413dd944452afc86eaabd1279ec.png][]

**3>在误判率为****0.0000000001下，我们继续debug下：**

![e9518cf97e3a4083980117cf6adb9538.png][]

### 9、总结 ###

*  误差率需要根据具体的业务需求进行设置
 *  误差率越小，所占用的空间就越大，需要的哈希函数也就越多

原因：

1.  因为在一个hash函数下，只有一个函数对数据进行计算，hash值重复概率会很大，当多个hash函数计算同一个数据时，由于每个hash函数是相互隔离的（hash算法不同），因此重复的概率也随之减少。
2.  hash函数越多，计算出的hash值也就越多，hash值越多，对应的二进制数据也就越多，所有占用的空间也就越大

[Link 1]: https://www.bilibili.com/video/BV1zK4y1h7pA/?spm_id_from=333.999.top_right_bar_window_history.content.click&vd_source=bfeb20bb7473b49092dc36bff208b3e1
[1846373c0a004954b5a3bb61c4353b18.png]: https://img-blog.csdnimg.cn/1846373c0a004954b5a3bb61c4353b18.png
[19165133000748c1bf1760abe69096b0.png]: https://img-blog.csdnimg.cn/19165133000748c1bf1760abe69096b0.png
[f32931a9c89041d7862079b00919ec2f.png]: https://img-blog.csdnimg.cn/f32931a9c89041d7862079b00919ec2f.png
[25d4482f48844065949be6f11d06ae8d.png]: https://img-blog.csdnimg.cn/25d4482f48844065949be6f11d06ae8d.png
[42d2c3dd04c44d738798b42296cb2c78.png]: https://img-blog.csdnimg.cn/42d2c3dd04c44d738798b42296cb2c78.png
[3f0ffd80da084d2e94e65c14c91270c8.png]: https://img-blog.csdnimg.cn/3f0ffd80da084d2e94e65c14c91270c8.png
[3cc2603038b141ab84f34659da29ca0d.png]: https://img-blog.csdnimg.cn/3cc2603038b141ab84f34659da29ca0d.png
[960d8ac4513d4e3c944971966635bec4.png]: https://img-blog.csdnimg.cn/960d8ac4513d4e3c944971966635bec4.png
[710f9939e93c4d8e86ca67d1c684fe7f.png]: https://img-blog.csdnimg.cn/710f9939e93c4d8e86ca67d1c684fe7f.png
[e19dce7821e5460e88e37e616c28470e.png]: https://img-blog.csdnimg.cn/e19dce7821e5460e88e37e616c28470e.png
[f74c9c0ac2334cbe816635ff8873823e.png]: https://img-blog.csdnimg.cn/f74c9c0ac2334cbe816635ff8873823e.png
[2c297413dd944452afc86eaabd1279ec.png]: https://img-blog.csdnimg.cn/2c297413dd944452afc86eaabd1279ec.png
[e9518cf97e3a4083980117cf6adb9538.png]: https://img-blog.csdnimg.cn/e9518cf97e3a4083980117cf6adb9538.png