目录
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下:
文章来源:https://www.toymoban.com/news/detail-407818.html
9、总结
- 误差率需要根据具体的业务需求进行设置
- 误差率越小,所占用的空间就越大,需要的哈希函数也就越多
原因:文章来源地址https://www.toymoban.com/news/detail-407818.html
- 因为在一个hash函数下,只有一个函数对数据进行计算,hash值重复概率会很大,当多个hash函数计算同一个数据时,由于每个hash函数是相互隔离的(hash算法不同),因此重复的概率也随之减少。
- hash函数越多,计算出的hash值也就越多,hash值越多,对应的二进制数据也就越多,所有占用的空间也就越大
到了这里,关于布隆过滤器讲解及基于Guava BloomFilter案例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!