详解布隆过滤器的原理、优缺点

详解布隆过滤器的原理、优缺点什么是布隆过滤器?本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilisticdatastructure),特点是高效地插入和查询,可以用来告诉你“某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。HashMap的问题讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

什么是布隆过滤器?

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
在这里插入图片描述

HashMap 的问题

讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:
在这里插入图片描述
如果我们要映射一个值到布隆过滤器中(插入),我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:
在这里插入图片描述
值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

支持删除么

目前我们知道布隆过滤器可以支持 add 和 isExist 操作,那么 delete 操作可以么,答案是不可以,例如上图中的 bit 位 4 被两个值共同覆盖的话,一旦你删除其中一个值例如 “tencent” 而将其置位 0,那么下次判断另一个值例如 “baidu” 是否存在的话,会直接返回 false,而实际上你并没有删除它。

如何解决这个问题,答案是计数删除。但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。这样的话,增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。

如何选择哈希函数个数和布隆过滤器长度

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

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

布隆过滤器优点

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

布隆过滤器缺陷

  1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白
    名单,存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除,可能会存在计数回绕问题

参考博文:https://www.jianshu.com/p/2104d11ee0a2

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188699.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 腾讯云视频直播sdk开发攻略

    腾讯云视频直播sdk开发攻略视频直播这一两年在移动互联网上可以说是非常的火,各种视频直播软件层出不穷。有的通过自己的推广宣传确实火了起来,比如:映客。我之前也是在一家专门做视频直播的公司打酱油,当时对这个概念还是很模糊,后来才慢慢的了解清楚视频直播的这个概念。后来离开这家公司,到现在的公司,做了一段时间,又有需要做视频直播的需求。由于公司各方面原因,只能引用第三方的sdk,最后选择的腾讯云。所以我下面给大家讲一下开发过程

  • Verilog 流水线设计[通俗易懂]

    Verilog 流水线设计[通俗易懂]一、什么是流水线流水线设计就是将组合逻辑系统地分割,并在各个部分(分级)之间插入寄存器,并暂存中间数据的方法。目的是将一个大操作分解成若干的小操作,每一步小操作的时间较小,所以能提高频率,各小操作能并行执行,所以能提高数据吞吐率(提高处理速度)。二、什么时候用流水线设计使用流水线一般是时序比较紧张,对电路工作频率较高的时候。典型情况如下:1)功能模块之间的流水线,用乒乓buffer来交互数据。代价是增加了memory的数量,但是和获得的巨大性能提升相比,可以忽略不计。2)I/O瓶

  • Vue项目运行报错:解决webpack版本问题「建议收藏」

    Vue项目运行报错:解决webpack版本问题「建议收藏」解决“Error:Rulecanonlyhaveoneresourcesource(providedresourceandtest+include+exclude)”前面也会报错找不到webpack,在package-lock.json里查找之,发现安装的版本竟然是5.1.0,而没有更新过依赖,可以正常编译的项目里都是4.x。那基本可以确认了。步骤:先删掉node_modules和package-lock.json手动在package.json

  • android签名命令行,Android系统签名位置及命令

    android签名命令行,Android系统签名位置及命令app需要使用系统的权限在AndroidManifest.xml中声明了系统全下申明了系统权限android:sharedUserId=”android.uid.system”1.找到平台签名文件“platform.pk8”和“platform.x509.pem”文件位置android/build/target/product/security/2.签名工具“signapk.jar”位置…

  • J2EE架构师之路

    J2EE架构师之路不经意的回首,工作进入第五个年头了,发现走过了从Java程序员到J2EE架构师的历程。发现电脑上安装了各种各样的J2EE工具:JBuilder,WSAD,Eclipse,Rose,Together,Weblogic,Jtest,Optimizator,Mysql…发现电脑上保存了各种各样的OpenSource项目:Tomcat,JBoss,Ant,Hibernate,Spr

  • cloudsim仿真平台扩展的例子_云平台虚拟化技术

    cloudsim仿真平台扩展的例子_云平台虚拟化技术http://1.johnhome.sinaapp.com/?p=257幻灯片1云计算仿真框架CloudSim介绍jiangzw#ihep.ac.cn(以下为本人某次报告做的调研的PPT及其它一些实践记录,为保证清晰度,一些插入的图片较大,可在新标签页中打开)本文基于 署名3.0中国大陆 许可协议发布,未经本人许可不得转载

    2022年10月10日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号