布隆过滤器(Bloom Filter)

这篇具有很好参考价值的文章主要介绍了布隆过滤器(Bloom Filter)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.引言

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间也会呈现线性增长,最终达到瓶颈。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(logn),O(1)。这种时候,布隆过滤器就是一种比较好的解决方案了。

2.什么是布隆过滤器

布隆过滤器(Bloom Filter)其实是基于bitmap的一种应用, 1970 年由布隆提出。它由一个很长的二进制比特数组和一系列哈希函数构成,用于高效地检索数据是否存在。通俗的说可以把布隆过滤器理解为一个集合,我们可以往里面添加值,并且能判断某个值是否在里面。当布隆过滤器告诉我们某个值存在时,其实这个值只是有可能存在;可是它说某个值不存在时,那这个值就真的不存在。

3.工作机制

布隆过滤器(Bloom Filter)

如图1 所示,初始化比特数组的值全为0,长度m=23,并假设有k=3个能把数据均匀映射到值域为 [0,m) 的哈希函数,经过一系列添值操作后,数组的值会散乱地被赋为1。我们先将数据a、b、c放入布隆过滤器,对a、b、c各自分别使用三个哈希函数得到映射值(即比特数组索引下标)。再根据下标将比特数组对应的值置为1,从而表示这三个数据已经存在。

然后我们用两个不曾被布隆过滤器标记的数据d、e模拟布隆过滤器的筛选过程。同样要使用前文设定的3个哈希函数,经散列得到比特数组索引下标,然后按下标查询得到对应的数组值。如果说3个索引值里出现了至少一个值为0,那么可以肯定的说这个数据肯定不存在,比如d。但是也会出现e这种情况,查得的值均为1,但是e明明不存在。其实出现这种情况的原因很好理解:那些被置为 1 的位置也可能是由于其他元素的操作而改变的。所以布隆过滤器存在假正率(False Positive)。

4.时间复杂度 空间复杂度

时间复杂度:在查找过程里,取值过程是直接查找,但是取值的次数等于哈希函数的个数成,所以时间复杂度为O(k),k为哈希函数的个数。另外哈希计算可以使用硬件加速,故查找效率很高。

空间复杂度:存储上,假设比特数组长度为m=10000000,则申请的内存大小为10000000bit=1250000B=1220.703125KB≈1.20MB≈0.001164GB。这在动辄内存8G起步的设备上,其实占用很小。

 5.正确率和容错

首先对False positive概率进行推导:

假设 Hash 函数以等概率条件选择并设置比特数组中的某一位,m 是该位数组的大小,k 是 Hash 函数的个数,那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是:

布隆过滤器(Bloom Filter)

 那么在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是:

布隆过滤器(Bloom Filter)

如果我们插入了 n 个元素,那么某一位仍然为 "0" 的概率是:

布隆过滤器(Bloom Filter)

因而该位为 "1"的概率是:

布隆过滤器(Bloom Filter)

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1",但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positive),该概率由以下公式确定:

布隆过滤器(Bloom Filter)

其实上述结果是在假定由每个 Hash 计算出需要设置的位(bit) 的位置是相互独立为前提计算出来的,不难看出,随着 m (比特数组大小)的增加,False Positive的概率会下降,同时随着插入元素个数 n 的增加,False Positive的概率又会上升,对于给定的m,n,如何选择Hash函数个数 k 由以下公式确定:

布隆过滤器(Bloom Filter)

此时False Positive的概率为:

布隆过滤器(Bloom Filter)

而对于给定的False Positive概率 p,如何选择最优的位数组大小 m 呢,

布隆过滤器(Bloom Filter)

上式表明,比特数组的大小最好与插入元素的个数成线性关系。

对于布隆过滤器不会漏报,但可能误报这个情况,我们当然希望准确度越高越好。

布隆过滤器(Bloom Filter)
 false positive rate under various m/n and k combinations

 从上图可以看出,数据冗余量越大,哈希函数越多,错误率越低。但是总体来看,错误率控制在1%以内

确定了正确率的问题后,接下来就是关键的容错了,怎么容错才算完美,既能解决问题,又能照顾容错成本呢?一方面由于布隆过滤器使用多个哈希函数进行处理,所以生成的值正常会均匀分布,数据不均衡从而造成数据稀疏时成本较高的问题就不存在了;另一方面,虽然说数据量增大超过预先设计的最大值也会对布隆过滤器造成影响,但是影响并不是很严重,除非差别过于巨大。因为实际数据量增大后,只会影响到上图m/n的值,带来的影响只是略微影响到布隆过滤器的正确率。

6.优点

  • 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
  • 哈希函数相互之间没有关系,方便硬件并行运算
  • 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
  • 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
  • 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
  • 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

7.使用场景

布隆过滤器被广泛用于数据量庞大的情况下的查询、去重等业务,比如:

  • 黑名单过滤
  • 垃圾邮件过滤
  • 爬虫判重系统
  • 推荐系统去重
  • 缓存穿透
  • 区块链的SPV支付
  • Web拦截器
  • ……

8.缺点

  • 有误判率,即存在假正率,即不能准确判断元素是否在集合中
  • 不能获取元素本身
  • 一般情况下不能从布隆过滤器中删除元素
  • 随着使用的时间越来越长,因为不能删除,存进里面的元素越来越多,占用内存越来越多,误判率越来越高,最后不得不重置。
  • 如果采用计数方式删除,可能会存在计数回绕问题
  • 数据量过于庞大时,计算机内存也会进行频繁的页面置换(这个其实不独属于布隆过滤器的缺点) 

9.总结

总体来说,布隆过滤器是一个很有意思的数据结构,空间效率和查询时间都远远超过一般的算法。目前已经在业务中广泛使用,比如常用的redis里已经集成了布隆过滤器。本篇只是就最基本的布隆过滤器做了介绍,在具体应用中,布隆过滤器还有更多的有趣的功能和进一步改进的数据结构。朋友们可以亲自coding一下,比如尝试一下redis的布隆过滤器,或者尝试给布隆过滤器实现删除数据的功能等等。


9.Reference

布隆过滤器 - 维基百科,自由的百科全书 (wikipedia.org)

hash 算法原理及应用漫谈 (qq.com)

详解布隆过滤器的原理、优缺点_一只快乐的野指针吼的博客-CSDN博客_布隆过滤器原理

布隆过滤器,这一篇给你讲的明明白白-阿里云开发者社区 (aliyun.com)

布隆过滤器及其使用场景 - Master HaKu - 博客园 (cnblogs.com)

Redis布隆过滤器(原理+图解) (biancheng.net)

布隆过滤器(Bloom Filter)详解 - 李玉龙 - 博客园 (cnblogs.com)

Merkle Tree、Merkle Proof、SPV安全性分析、Bloom过滤器_真·skysys的博客-CSDN博客

简化的支付验证(SPV)和布隆过滤器(bloom fliter)

"不靠谱"的布隆过滤器是怎么成为大数据世界中的韦小宝的?

布隆过滤器踩坑日记文章来源地址https://www.toymoban.com/news/detail-482961.html

到了这里,关于布隆过滤器(Bloom Filter)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 位图以及布隆过滤器

    本文主要讲解哈希思想的实际应用,位图和布隆过滤器。 讲解位图之前我们先来解答这样一道腾讯的面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 很多人立马就想到了用哈希表或者红黑树,因为足够

    2024年02月08日
    浏览(53)
  • 布隆过滤器详解

    本文全部代码地址 布隆过滤器是一种高效的数据结构,用于判断一个元素是否存在于一个集合中.它的主要优点是速度快,空间占用少,因此在需要快速判断某个元素是否在集合中的场合得到广泛引用. 布隆过滤器就是 一个大型的位数组和几个不一样的无偏hash函数. 所谓无偏就是

    2023年04月22日
    浏览(54)
  • Redis----布隆过滤器

    目录 背景 解决方案 什么是布隆过滤器 布隆过滤器的原理 一些其他运用 比如我们在观看新闻或者刷微博的时候,会不停地给我们推荐新的内容,我们发现几乎没有重复的,说明后台已经进行了去重处理,基于如何去重,Redis给出了高效的方案---布隆过滤器 1.记录已经浏览过

    2024年02月09日
    浏览(38)
  • 算法~布隆过滤器

    布隆过滤器(Bloom Filter)是一种高效的概率数据结构,用于判断一个元素是否存在于集合中。它基于位数组和多个哈希函数,并具有以下特点: Bloom Filter 是一个基于概率的数据结构:它只能告诉我们一个 元素绝对不在集合内 或 可能在集合内 快速查询:布隆过滤器具有快速

    2024年02月05日
    浏览(47)
  • 布隆过滤器的原理

    布隆过滤器是一种用于检索一个元素是否在一个集合中的数据结构,具有高效的查询性能和较小的内存占用。 布隆过滤器的底层实现主要涉及以下几个步骤: 初始化数组: 首先,初始化一个比较大的数组,数组中的元素用二进制表示,初始值都为0。 Hash计算: 当一个新的元

    2024年01月18日
    浏览(40)
  • 布隆过滤器及其应用

    布隆过滤器是一种数据结构,具有快速插入和查找的特性,能确定某个字符串一定存在或者可能存在。布隆过滤器有着高效的空间利用率,它不存储具体数据,只存储数据的关键标识,所以占用的空间较小。它的查询结果可能会存在一定误差,但是误差总体可控,同时不支持

    2024年02月03日
    浏览(44)
  • 解释一下布隆过滤器原理

    锁屏面试题百日百刷,每个工作日坚持更新面试题。请看到最后就能获取你想要的,接下来的是今日的面试题: 1.解释一下布隆过滤器原理 在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是

    2023年04月10日
    浏览(51)
  • 哈希的应用——布隆过滤器

    上一篇文章,我们学习了位图,位图在某些场景下是非常适用的,非常快捷方便。 但是,在文章的最后,我们也提出了位图的一些缺陷——比如位图只能映射整型数据,其它类型的数据则不行。 因为位图里面的元素去映射的其实就是下标嘛,而下标的话都是整型啊。 那有没

    2024年02月09日
    浏览(42)
  • Java实现布隆过滤器

    背景: 为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据

    2024年02月01日
    浏览(48)
  • 布隆过滤器:原理与应用

    本文已收录至GitHub,推荐阅读 👉 Java随想录 微信公众号:Java随想录 原创不易,注重版权。转载请注明原作者和原文链接 目录 布隆过滤器简介 fpp 布隆过滤器原理 布隆过滤器的特点 布隆过滤器使用 布隆过滤器中的数据可不可以删除 布隆过滤器应该设计为多大 布隆过滤器应

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包