目录
1、布隆过滤器是什么
2、主要作用
3、存储过程
4、查询过程
5、布隆过滤器的删除操作
6、优点
7、缺点
8、测试误判案例
8.1、引入Guava依赖
8.2、编写测试代码
8.3、测试
8.4、BloomFilter实现原理
9、总结
推荐博主视频，讲的很棒：布隆过滤器详解
1、布隆过滤器是什么
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制（0和1组成的）向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
- 布隆过滤器里面就是一个二进制（存储0和1）的数组，下标从0开始
2、主要作用
- 通过一个的hash函数，计算出数据的hash值，再把哈希值映射到数组中
- 判断这个数据是不是存储在这个数组中，不存在则返回0，存在则返回1，其实就是用二进制（0和1）去表示数据是否存在这个数组中
3、存储过程
已下面案例为例：
步骤：
- 布隆过滤器在没有存储任何数据时，默认都是0
- 布隆过滤器中有3个哈希（Hash）函数（这3个哈希函数一定是互不影响的），现在传入一个"你好"的值，通过这3个哈希函数，算出对应的哈希值
- Hash1函数通过计算得到哈希值，对应数组中下标为3的位置，从而把数据映射至index=3处
- 布隆过滤器会把下标为3的二进制向量改为1
- 同理，经过其他2个哈希函数，分别存储在下标为5、7的位置，并把0改为1
4、查询过程
还是以上面的案例为例：
步骤：
- 布隆过滤器会根据传入的值，通过3个哈希函数计算出该值存储的下标
- 判断该下标是否为1,为1则表示该下标存储了该值，为0则表示没有存储
- 由于上述布隆过滤器有3个哈希函数，因此判断该值存不存在，必须满足得到的3个下标的二进制向量值都等于1，才能证明该值存在于该数组中，布隆过滤器返回1，只要有一个不等于1，则认为该数值中不存在该值，布隆过滤器返回0.
5、布隆过滤器的删除操作
-
在布隆过滤器中，很难进行删除操作，如下：
现在有2个值：
- 你好
- hello
- 假设上述的2个值在经过Hash函数计算时，得到了相同的hash值（hash冲突），这时他们都存储在下标index=2的位置
- 之后，我们需要在布隆过滤器中，移除值"你好"的数据，经过Hash函数计算出该值存储在下标为2的位置
- 然后布隆过滤器会把该值删除，并把下标为2的二进值向量改为0
- 这时，当我们在查询"hello"是否存在时，布隆过滤器会得到0，认为不存在
- 也就是意味着，当多个值存储在同一处下标时，删除任意1个值，其他的值也会被删除
- 由于布隆过滤器会造成误删，因此布隆过滤器很难做删除操作
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下，执行结果为：
- 在12ms内执行完成
- 误判数为：947（测试总数为10万）
- 真实误判率为：947 ÷ 10万 = 0.00947 ≈ 0.01 ，符合预期
<2>修改误判率为0.03：
执行结果如下：
- 在16ms内执行完成
- 误判数为：3033
- 真实误判率也与预期的0.03相近
总结：设置的误判率是能直接影响布隆过滤器最终的误判率的，误判率越低，耗时越多
问题：我们是不是把误判率设置为无限小，那么就不存在误判了呢？
<3>修改误判率为0.0000000001
该误判率比之前2个案例数值小很多，我们看下执行效果：
- 在25ms内执行完成
- 误判数为0
注意：在测试机器上是特别快的，当在高并发下，误判率越小，耗时越多，会给服务器带来性能损耗。
因此：我们需要根据具体的业务需求，设置合理的误判率
8.4、BloomFilter实现原理
以8.3中的案例：
1>在误判率为0.01下，我们debug下：
debug启动：
2>在误判率为0.03下，我们继续debug下：
3>在误判率为0.0000000001下，我们继续debug下：
9、总结
- 误差率需要根据具体的业务需求进行设置
- 误差率越小，所占用的空间就越大，需要的哈希函数也就越多
原因：
- 因为在一个hash函数下，只有一个函数对数据进行计算，hash值重复概率会很大，当多个hash函数计算同一个数据时，由于每个hash函数是相互隔离的（hash算法不同），因此重复的概率也随之减少。
- hash函数越多，计算出的hash值也就越多，hash值越多，对应的二进制数据也就越多，所有占用的空间也就越大
