什么是布隆过滤器?如何使用?

news/2024/11/22 18:12:42/

欢迎搜索

文章目录

  • 一、布隆过滤器简介
  • 二、布隆过滤器的结构
  • 三、布隆过滤器应用
  • 四、布隆过滤器的优缺点
  • 五、布隆过滤器实战
  • 六、总结

Redis缓存穿透可以通过布隆过滤器进行解决,那么什么是布隆过滤器呢?请往下看。

通常你判断某个元素是否存在用的是什么?

很多人想到的是HashMap。
确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

一、布隆过滤器简介

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中

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

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。 –引自《维基百科,自由的百科全书》

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure)高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。

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

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

二、布隆过滤器的结构

图片

根据定义,布隆过滤器可以检查值是 “可能在集合中” 还是 “绝对不在集合中”。“可能” 表示有一定的概率,也就是说可能存在一定为误判率。那为什么会存在误判呢?下面我们来分析一下具体的原因。
布隆过滤器(Bloom Filter)本质上是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为 0,如下图所示。

图片

为了将数据项添加到布隆过滤器中,我们会提供 K 个不同的哈希函数,并将结果位置上对应位的值置为 “1”。在前面所提到的哈希表中,我们使用的是单个哈希函数,因此只能输出单个索引值。而对于布隆过滤器来说,我们将使用多个哈希函数,这将会产生多个索引值。

图片

如上图所示,当输入 “semlinker” 时,预设的 3 个哈希函数将输出 2、4、6,我们把相应位置 1。假设另一个输入 ”kakuqo“,哈希函数输出 3、4 和 7。你可能已经注意到,索引位 4 已经被先前的 “semlinker” 标记了。此时,我们已经使用 “semlinker” 和 ”kakuqo“ 两个输入值,填充了位向量。当前位向量的标记状态为:

图片

当对值进行搜索时,与哈希表类似,我们将使用 3 个哈希函数对 ”搜索的值“ 进行哈希运算,并查看其生成的索引值。假设,当我们搜索 ”fullstack“ 时,3 个哈希函数输出的 3 个索引值分别是 2、3 和 7:

图片

从上图可以看出,相应的索引位都被置为 1,这意味着我们可以说 ”fullstack“ 可能已经插入到集合中。事实上这是误报的情形,产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。

那么我们如何选择哈希函数个数和布隆过滤器长度
很显然,过小的布隆过滤器很快所有的bit位均为1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

图片

如何选择适合业务的 k 和 m 值呢,幸运的是,布隆过滤器有一个可预测的误判率(FPP):

图片

n 是已经添加元素的数量;
k 哈希的次数;
m 布隆过滤器的长度(如比特数组的大小);

极端情况下,当布隆过滤器没有空闲空间时(满),每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ,并且 m 需要远远大于 n 。
实际情况中,布隆过滤器的长度 m 可以根据给定的误判率(FFP)的和期望添加的元素个数 n 的通过如下公式计算:

图片

了解完上述的内容之后,我们可以得出一个结论:当我们搜索一个值的时候,若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“,那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“,则只能说该搜索的值可能存在集合中。

三、布隆过滤器应用

在实际工作中,布隆过滤器常见的应用场景如下:

  • 网页爬虫对 URL 去重,避免爬取相同的 URL 地址;
  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
  • Google Chrome 使用布隆过滤器识别恶意 URL;
  • Medium 使用布隆过滤器避免推荐给用户已经读过的文章;
  • Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

除了上述的应用场景之外,布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据,这样每次服务调用都会到数据库中进行查询,如果这类请求比较多的话,就会导致数据库压力增大,这样缓存就失去了意义。

利用布隆过滤器我们可以预先把数据查询的主键,比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候,我们先判断该 ID 是否存在,若存在的话,则进行下一步处理。若不存在的话,直接返回,这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决,我们只能将其控制在一个可以容忍的范围内。

四、布隆过滤器的优缺点

优点
相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

k和m相同,使用同一组散列函数的两个布隆过滤器的交并运算可以使用位操作进行。

缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

五、布隆过滤器实战

布隆过滤器有很多实现和优化,由 Google 开发著名的 Guava 库就提供了布隆过滤器(Bloom Filter)的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器,只需要引入以下坐标:

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

复制代码在导入 Guava 库后,我们新建一个 BloomFilterDemo 类,在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器,接着我们初始化 1 百万条数据到过滤器中,然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中:

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;public class BloomFilterDemo {public static void main(String[] args) {int total = 1000000; // 总数量BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);// 初始化 1000000 条数据到过滤器中for (int i = 0; i < total; i++) {bf.put("" + i);}// 判断值是否存在过滤器中int count = 0;for (int i = 0; i < total + 10000; i++) {if (bf.mightContain("" + i)) {count++;}}System.out.println("已匹配数量 " + count);}
}

当以上代码运行后,控制台会输出以下结果:

已匹配数量 1000309

很明显以上的输出结果已经出现了误报,因为相比预期的结果多了 309 个元素,误判率为:

309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

如果要提高匹配精度的话,我们可以在创建布隆过滤器的时候设置误判率 fpp:

BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);

在 BloomFilter 内部,误判率 fpp 的默认值是 0.03:

// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {return create(funnel, expectedInsertions, 0.03D);
}

在重新设置误判率为 0.0002 之后,我们重新运行程序,这时控制台会输出以下结果:

已匹配数量 1000003

复制代码通过观察以上的结果,可知误判率 fpp 的值越小,匹配的精度越高。当减少误判率 fpp 的值,需要的存储空间也越大,所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

六、总结

本文主要介绍的布隆过滤器的概念和常见的应用场合,在实战部分我们演示了 Google 著名的 Guava 库所提供布隆过滤器(Bloom Filter)的基本使用,同时我们也介绍了布隆过滤器出现误报的原因及如何提高判断准确性。最后为了便于大家理解布隆过滤器,我们介绍了一个简易版的布隆过滤器 SimpleBloomFilter。

在这里插入图片描述
JVM内存泄漏和内存溢出的原因
JVM常用监控工具解释以及使用
Redis 常见面试题(一)
ClickHouse之MaterializeMySQL引擎(十)
三种实现分布式锁的实现与区别
线程池的理解以及使用

号外!号外!

最近面试BAT,整理一份面试资料,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。想获取吗?如果你想提升自己,并且想和优秀的人一起进步,感兴趣的朋友,可以在扫码关注下方公众号。资料在公众号里静静的躺着呢。。。

点击下方微信公众号

  • 喜欢就收藏
  • 认同就点赞
  • 支持就关注
  • 疑问就评论

一键四连,你的offer也四连

————————————————

本文作者:Java技术债务
原文链接:https://www.cuizb.top/myblog/article/1644224367
版权声明: 本博客所有文章除特别声明外,均采用 CC BY 3.0 CN协议进行许可。转载请署名作者且注明文章出处。


http://www.ppmy.cn/news/529346.html

相关文章

瑞尔集团通过上市聆讯:半年亏4.6亿 淡马锡与高瓴是股东

雷递网 雷建平 2月28日报道 口腔诊所——瑞尔集团有限公司&#xff08;简称&#xff1a;“瑞尔集团”&#xff09;日前通过聆讯&#xff0c;准备在香港上市。 半年期内亏损4.64亿 瑞尔集团是一家提供高端口腔医疗服务的企业。自1999年成立以来&#xff0c;在过往十年当中&#…

何为布隆过滤器

问题的提出 我们有一个不安全网页的黑名单&#xff0c;包含了100亿个黑名单网页的URL,每个网页URL最多占用64B.。 现在我们要设计一个网页过滤系统&#xff0c;这个系统要判断该网页是否在黑名单里&#xff0c;但是我们的空间有限&#xff0c;只有30GB. 允许有万分之一的判断…

神奇的利克瑞尔数:196 【大数加法】【回文数】

微信搜索&#xff1a;编程笔记本 微信搜索&#xff1a;编程笔记本 微信搜索&#xff1a;编程笔记本 点击上方蓝字关注我&#xff0c;我们一起学编程 欢迎小伙伴们分享、转载、私信、赞赏 今天要跟小伙伴们分享神奇的数字&#xff1a;196。 在介绍这个神奇的数字之前&#xff0c…

allure简介

allure介绍 allure是一个轻量级&#xff0c;灵活的&#xff0c;支持多语言的测试报告工具 多平台的&#xff0c;奢华的report框架 可以为dev/qa提供详尽的测试报告、测试步骤、log 也可以为管理层提供high level统计报告 java语言开发的&#xff0c;支持pytest,javaScript,PHP等…

布隆过滤器说明

本文参考&#xff1a;布隆过滤器详解__瞳孔的博客-CSDN博客_布隆过滤器 布隆过滤器以及python实现_追光的鲲的博客-CSDN博客_python布隆过滤器 目录 一、概述 二、布隆过滤器原理 2.1 原理 2.2 误判率 2.3 特性 2.4 添加元素步骤 2.5 查询元素步骤 2.6 布隆过滤器的使…

瑞尔齿科×UB Store | RPA破解医疗业务痛点

如今&#xff0c;医疗行业正经历剧变&#xff0c;无论是政策环境还是病患需求&#xff0c;都在快速变化。随着智能自动化技术的深入发展&#xff0c;医疗行业也掀起了应用RPA技术的热潮。 瑞尔齿科 瑞尔齿科&#xff0c;中国高端齿科服务行业领先品牌&#xff0c;成立于1999年&…

瑞尔集团再度冲刺港股:半年亏4.6亿 淡马锡与高瓴是股东

雷递网 雷建平 7月5日报道 口腔诊所——瑞尔集团有限公司日前再次向港交所递交招股书&#xff0c;准备在香港上市。 半年期内亏损4.64亿 瑞尔集团是一家提供高端口腔医疗服务的企业。自1999年成立以来&#xff0c;在过往十年当中&#xff0c;瑞尔集团号称已服务患者超过630万人…

瑞尔集团冲刺港交所上市:2021财年亏损约6亿元,负债规模飙升

日前&#xff0c;口腔企业瑞尔集团有限公司&#xff08;下称“瑞尔集团”&#xff09;公开向港交所递交招股书&#xff0c;准备在港交所主板上市&#xff0c;摩根士丹利和瑞银为其联席保荐人。 据了解&#xff0c;瑞尔集团旗下运营两大品牌&#xff0c;分别为瑞尔齿科和瑞泰口…