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

详解布隆过滤器的原理、优缺点什么是布隆过滤器?本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(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)
blank

相关推荐

  • 全息投影技术的实现_自制全息投影视频素材

    全息投影技术的实现_自制全息投影视频素材今天自己亲自动手制作了一个全息投影仪,智能手机早就具备投射出全息影像的潜质,现在Mrwhosetheboss就将这段教程上传到网上,看起来简直酷极了。

  • java时间类的使用和区别

    java时间类的使用和区别java中经常使用的6大时间类:java.util.Date              日期格式:年月日时分秒java.sql.Date               日期格式:年月日java.sql.Time               日期格式:时分秒java.sql.Timestamp          日期格式:年月日时分秒纳秒    从数据库中取出来的日期一般都用getTimestamp(…

  • Git创建远程分支并提交代码到远程分支

    Git创建远程分支并提交代码到远程分支1、可以通过gitbranch-r命令查看远端库的分支情况如图所示,远程仓库只有一个master分支2、从已有的分支创建新的分支(如从master分支),创建一个dev分支但此时并没有在远程仓库上创建分支如图所示还是只有一个master分支3、建立本地到远端仓库的链接–这样代码才能提交上去使用命令行gitpush–set-…

  • jQuery全屏动画焦点图

    效果:http://hovertree.com/texiao/jqimg/3/本效果使用jquery-1.8.3.min.js,如需使用1.12.3版本,需进行修改。全部版本jQuery下载:htt

    2021年12月23日
  • Feign原理_feign基于什么协议

    Feign原理_feign基于什么协议一、feign测试代码1.服务接口上标注@FeignClient@FeignClient(“order”)publicinterfaceOrderServiceFeign{@GetMapping(“/getOrder”)StringgetOrder();}2.调用方可以直接注入然后直接调用访问@RestController@RequestMapping(“/feign”)publicclassFeignTestController{@Autow

  • 提升网页打开速度的实用方法

    提升网页打开速度的实用方法

    2021年10月16日

发表回复

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

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