布隆过滤器和布谷鸟过滤器详解
今天和大家分享下布隆过滤器和布谷鸟过滤器
一.布隆过滤器
1.简单介绍
布隆过滤器是用于检索一个元素是否在一个集合中的算法,是一种用空间换时间的查询算法。
2.实现原理
布隆过滤器的存储结构是一个bitmap结构,初始值都是0,如下图所示:
当需要存储一个数据的时候,会通过多次(这里假设为3次)hash函数运算之后,计算出3个hash值,然后将计算出的这3个hash值当做坐标,将数组对应的坐标数据由0改成1,以此来标记这个数据已经存储在数组中了。如下图所示:
等到需要查询数据是否在数组中时,就通过hash计算出对应的坐标,判断是否全都为1,如果都为1数据就可能存在,如果有一个为0,则数据一定不存在。
- 为什么这里说可能存在能,因为可能会出现hash碰撞的情况,不同的数据经过hash函数运算之后,计算出来的hash坐标却相同,导致数据本来不存在数组中,但是这里却判断存在,因此布隆过滤器会出现误判的情况,但是概率会很低,误判的概率和设置的hash运算次数是成反比的。
如下图所示:
Data和Data2的hash值一样,但是Data数据存在,Data2不存在,在判断Data2的时候,布隆过滤器就会判断Data2也存在,由此产生误判。
这里有个很有意思的网站,大家可以自己动手去看下数据存储的具体过程:https://www.jasondavies.com/bloomfilter/网站内容如下:
总的来说,布隆过滤器的判断:存在->可能存在,不存在->一定不存在。
- 根据上述特性,布隆过滤器在很多场景下,可以帮我们判断大部分的判断请求。因此较多用于高并发的场景下使用,比如处理缓存击穿、用户视频推荐等场景。
3. 布隆过滤器的缺点
- 误判:
上文已经说明一点了,就是布隆过滤器会产生误判,在此就不过多赘述了。- 当数组过大时,查询效率不高:
因为布隆过滤器的判断方式是根据多次hash值判断的,当数组过大,那么hash值的跨度可能就越大,跨度大就是不连续,那么CPU的缓存命中率就会变低,就会影响查询效率。- 布隆过滤器不能删除元素:
因为不同的数据可能会计算出相同的hash值,因此我们如果要删除某个元素,可能也会影响其他的元素的判断。在这个限制条件下,当数据量大的时候,就会导致很多的垃圾数据。并且数据量越大,误判率也就会越高。
二.布谷鸟过滤器
1.简单介绍
布谷鸟过滤器可以说是一个增强版的布隆过滤器,可以删除元素,查询效率更高,空间利用率更高。
2.实现原理
布谷鸟过滤器不同于布隆过滤器主要有两点改动:
- hash算法:
在布谷鸟过滤器中,数组中存储的是每个元素的"指纹信息",也就是hash运算之后的几个bit位。查询数据的时候,就是看看对应的位置上有没有对应的“指纹”信息,删除数据的时候,也只是抹掉该位置上的“指纹”而已。- 由于指纹是对元素进行 hash 计算得出的,那么必然会出现 hash 碰撞的问题,也就是“指纹”相同的情况,也就是会出现误判的情况,所以这点和布隆过滤器一样。
布谷鸟过滤器的hash算法是基于布谷鸟哈希算法做了改进,计算公式如下:
fp = fingerprint(x)
h1 = hash(x)
h2 = h1 ^ hash(fp) // 异或
- 在上列公式可以看出,h2的位置是根据h1的位置计算出来的,也就是说我们知道了其中一个位置,就可以直接获取到另外一个位置,不需要再做全量的hash运算。因为使用的异或运算,所以这两个位置具有对偶性。这也是提高查询效率的一个点。
只要保证 hash(fp) !=0,那么就可以确保 h2!=h1,也就可以确保不会出现自己踢自己的死循环问题了。- 这里还有个注意点:就是hash运算的时候,并没有对值进行长度取模运算,那么他是如何保证计算出来hash坐标,一定是在数组长度范围内呢?这就说到布谷鸟过滤器的一个限制条件了,那就是强制数组的长度必须是 2 的指数倍
这个限制带来的好处就是,进行异或运算时,可以保证计算出来的下标一定是落在数组中的。
布谷鸟过滤器对布隆过滤器的另一个优化点就是存储结构:
- 布谷鸟过滤器的存储结构是每个坐标下的空位是多个,不同于布隆过滤器的一个空位。如下图所示:
布谷鸟过滤器会记录每个元素的两个hash位置,每个位置下都会有多个空位,空位内存储的就是元素的“指纹信息”。
- 布谷鸟过滤器添加元素的流程是这样的:
布谷鸟过滤器会先计算出元素对应的指纹信息,然后对元素进行hash运算,计算出元素的第一个存储坐标,该坐标下存在四个空位,如果四个空位中有空闲的,就将该元素的指纹信息存进去;如果没有空位,就会根据指纹和第一个hash坐标进行异或运算,计算出第二个坐标,如果第二个坐标下有空位,就将该元素的指纹信息存进去;如果还没有空位,那么该元素就会随机将一个空位中的指纹信息挤出,然后自己存进去,被挤出的指纹信息会计算出自己的第二个坐标,然后判断是否有空位,重复上述操作,直到达到一个阀值,布谷鸟过滤器返回false或进行扩容处理。
流程如下所示:
数据Data想要存储到布谷鸟过滤器中,首先会计算出h1和h2两个存储坐标,结果发现两个坐标的空位都已经“满员”了,此时会随机挤掉一个元素的指纹信息,假设挤掉了h1坐标的指纹3,然后指纹3会找自己的第二个坐标,然后判断是否有空位,有空位就存到第二个坐标下,如下图:
扩容:如果数组过小,会发生循环挤兑的情况,就可以设置最大挤兑次数,如果超过该次数,进行扩容,重新计算每个指纹的位置。
当 hash 函数固定为 2 个的时候,如果一个下标只能放一个元素,那么空间利用率是 50%。如果为 2,4,8 个元素的时候,空间利用率分别是 84%,95%,98%,可以发现空间利用率飙升。
3.布隆过滤器的缺点
- 删除不完美,存在误删的概率。删除的时候知识删除了一份指纹副本,并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
- 插入复杂度比较高。随着插入元素的增多,复杂度会越来越高,因为存在桶满,踢出的操作,所以需要重新计算,但综合来讲复杂度还是常数级别。
- 存储空间的大小必须为2的指数的限制让空间效率打了折扣。
- 同一个元素最多插入kb次,(k指哈希函数的个数,b指的是坐标下能装指纹的个数也可以说是坐标下桶的尺寸大小)如果布谷鸟过滤器支持删除,则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器,其中重复插入会导致计数器溢出。
相关文章:

布隆过滤器和布谷鸟过滤器详解
今天和大家分享下布隆过滤器和布谷鸟过滤器 一.布隆过滤器 1.简单介绍 布隆过滤器是用于检索一个元素是否在一个集合中的算法,是一种用空间换时间的查询算法。 2.实现原理 布隆过滤器的存储结构是一个bitmap结构,初始值都是0,如下图所示&am…...
WebGIS前端框架(openlayers,mapbox,leaflet)图形图像底层渲染原理分析
学了这么多的框架,做了这么多的项目,你是否清楚你使用的GIS框架(mapbox,open layers,cesium,leaflet)底层到底是什么原理?是否清楚哪些所谓的地图影像,矢量图形,图标,图像动画等是如何渲染到网页上的?这篇文章就大家解读一下WebGIS的底层原理。 首先说说历史,有时…...

AcWing语法基础课笔记 第五章 C++中的字符串
第五章 C中的字符串 字符串是计算机与人类沟通的重要手段。 ——闫学灿 字符与整数的联系——ASCII码 每个常用字符都对应一个-128~127的数字,二者之间可以相互转化: 常用ASCII值:’A’-‘Z’ 是65~90,’a’-‘z’…...

抓包工具Charles(一)-下载安装与设置
无论是在测试、开发工作中,抓包都是很重要、很常用的技能。Charles作为一款抓包工具,能够满足大部分的工作需求。 文章目录一、下载地址二、安装三、安装根证书(电脑)四、设置五、抓包附录:[零基础入门接口功能测试教程…...

SpringBoot09:Swagger
什么是Swagger? ①是一个API框架 ②可以在线自动生成 RestFul 风格的API文档,实现API文档和API定义同步更新 ③可以直接运行、在线测试 API 接口 ④支持多种语言(Java、PHP等) 官网:API Documentation & Desi…...
Git 常用命令
笔记-git命令1、名词2、基本操作3、分支操作1、名词 master: 默认开发分支origin: 默认远程版本库Index / Stage: 暂存区Workspace: 工作区Repository: 仓库区 (或本地仓库)Remote: 远程仓库 2、基本操作 配置级别 -local (默认,高级优先…...

查看jdk安装路径,在windows上实现多个java jdk的共存解决办法,安装java19后终端乱码的解决
查看jdk安装路径, 在windows上实现多个java jdk的共存解决办法, 安装java19后终端乱码的解决 目录 一、查看jdk(java开发工具包)安装路径的方法 二、在windows上实现多个java jdk的共存 (1)、安装好多…...
链表数据结构
用途: 链表是一种用于计算机中存储与组织数据的结构,链表将数据以节点的形式串联起来,其存储的容量大小可以动态伸缩。 结构: typedef struct {int data; /*当前节点的数据*/node *next;/*下一个节点的指针*/node *last;/*上一个…...

汽车DTC故障内码与标准故障码的解析与转换
目录 一、故障内码与标准故障码的解析 (1)故障内码的信息格式与解析 (2)故障内码中DTC状态的解析 (3)故障内码与标准故障码之间的对应关系 二、故障内码与标准故障码的转换代码 一、故障内码与标准故障…...

零基础学习测试还是开发?
软件测试作为IT行业的刚需职位,其实是非常适合0基础的小白同学加入学习的但是具体选择测试还是开发还是要看你个人的兴趣爱好以及学习能力,对哪个感兴趣,哪个能学的会就选择哪个就可以了 平时说起程序员印象中大都是做Java、做前端、做后端&…...

如何加入new bing候补名单
如何加入new bing候补名单 我们都知道现在最新版edges中已经提示我们可以加入new bing候补名单,但国内环境下无法正常加入new bing候补名单,这篇文章讲告诉你如何绕过限制加入new bing候补名单 下载配置 HeaderEditor 插件 下载地址microsoftedge.mic…...

中国天气——西风带环流和寒潮
中国天气——西风带环流和寒潮 一. 西风环流概述 1. 概念 西风带:中高纬度地区平均水平环流在对流层盛行西风,称之为西风带西风带波动:西风带围绕极涡沿纬圈运动,平均而言表现为冬季三槽三脊,夏季四槽四脊ÿ…...

2022黑马Redis跟学笔记.实战篇(四)
2022黑马Redis跟学笔记.实战篇 四4.3.秒杀优惠券功能4.3.1.秒杀优惠券的基本实现一、优惠卷秒杀1.1 全局唯一ID1.2 Redis实现全局唯一Id1.3 添加优惠卷1.4 实现秒杀下单4.3.2.超卖问题4.3.3.基于乐观锁解决超卖问题1. 悲观锁2. 乐观锁3. 乐观锁解决超卖问题4.4 秒杀的一人一单限…...

Allegro中如何删除多余D码操作指导
Allegro中如何删除多余D码操作指导 用Allegro做PCB设计的时候,在最后输出生产文件的时候,必须清除多余的D码,不让多余的D码出现在D码文件中,类似下图 如何清除多余D码,具体操作如下 点击Tools点击Padstack...

学生投票系统-课后程序(JAVA基础案例教程-黑马程序员编著-第三章-课后作业)
【案例3-4】学生投票系统 记得 关注,收藏,评论哦,作者将持续更新。。。。 【案例介绍】 案例描述 某班级投票竞选班干部,班级学生人数为100人,每个学生只能投一票。 本任务要求,编程实现一个投票程序&…...
初始化一个列表python
1.初始化递增的list: list1 list(range(10)) #print list1 #[0,1,2,...,9] 2.初始化每项为0的一维数组: list2 [0] * 5 #print list2 #[0,0,0,0,0] 3.初始化固定值的一维数组: initVal 1 listLen 5 list3 [ initVal for i in range(5)] …...
【electron】webview嵌入页面发送消息给父级页面
场景需求: 嵌入页面操作时,通知父级页面 涉及知识点: contextBridge 嵌入页面可使用暴露的对象ipc-message 监听嵌入页面发送的消息webview preload 嵌入页面运行加载的脚本 问题(两种方式) 使用监听ipc-message需…...

Whids:一款针对Windows操作系统的开源EDR
关于Whids Whids是一款针对Windows操作系统的开源EDR,该工具所实现的检测引擎基于先前的 Gene项目构建,并专门设计可以根据用户定义的规则匹配Windows事件。 功能特性 1、为社区提供一款功能强大且开源的Windows EDR; 2、支持检测规则透明化…...

初级调色转档CameraRaw
一级调色 还原-曝光-色彩-细节-质感 修图的范围 整体(掌握基本面板)——局部(曲线)——具象(混色器) 修片最开始的准备工作 看直方图:明暗跟色彩的数据表 分析图片是否存在以下问题: 1.曝光…...

Mybatis源码(3) - Executor执行过程 | 一级缓存 | 二级缓存
0. 前言:1. CachingExecutor#query:1.1. BoundSql:1.2. CacheKey:1.3. 二级缓存:1.4. 一级缓存:2. JDBC过程执行:3. 结果集处理:4. Mybatis的一级缓存、二级缓存区别:0. …...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...

高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...

循环语句之while
While语句包括一个循环条件和一段代码块,只要条件为真,就不断 循环执行代码块。 1 2 3 while (条件) { 语句 ; } var i 0; while (i < 100) {console.log(i 当前为: i); i i 1; } 下面的例子是一个无限循环,因…...

多模态学习路线(2)——DL基础系列
目录 前言 一、归一化 1. Layer Normalization (LN) 2. Batch Normalization (BN) 3. Instance Normalization (IN) 4. Group Normalization (GN) 5. Root Mean Square Normalization(RMSNorm) 二、激活函数 1. Sigmoid激活函数(二分类&…...
python数据结构和算法(1)
数据结构和算法简介 数据结构:存储和组织数据的方式,决定了数据的存储方式和访问方式。 算法:解决问题的思维、步骤和方法。 程序 数据结构 算法 算法 算法的独立性 算法是独立存在的一种解决问题的方法和思想,对于算法而言&a…...