Redis中的布隆过滤器与布谷鸟过滤器,你了解多少?
Java技术迷
共 4415字,需浏览 9分钟
· 2022-06-27
点击关注公众号,Java干货及时送达
作者:等不到的口琴
来源:cnblogs.com/Courage129/p/14337466.html
大家都知道,在计算机中,IO一直是一个瓶颈,很多框架以及技术甚至硬件都是为了降低IO操作而生,今天聊一聊过滤器,先说一个场景:
我们业务后端涉及数据库,当请求消息查询某些信息时,可能先检查缓存中是否有相关信息,有的话返回,如果没有的话可能就要去数据库里面查询,这时候有一个问题,如果很多请求是在请求数据库根本不存在的数据,那么数据库就要频繁响应这种不必要的IO查询,如果再多一些,数据库大多数IO都在响应这种毫无意义的请求操作,那么如何将这些请求阻挡在外呢?过滤器由此诞生:
布隆过滤器
布隆过滤器的问题
布隆过滤器增强版
布谷鸟过滤器
查询性能弱
、空间利用效率低
、不支持反向操作
(删除)以及不支持计数
。为啥要取名布谷鸟呢?
布谷鸟哈希
最简单的布谷鸟哈希结构是一维数组结构,会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空,那么就可以将元素直接放进去。但是如果这两个位置都满了,它就不得不「鸠占鹊巢」,随机踢走一个,然后自己霸占了这个位置。
p1 = hash1(x) % l
p2 = hash2(x) % l
布谷鸟哈希的问题
布谷鸟过滤器
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 异或
p1 = p2 ^ hash(fp)
hash(fp) != 0
就可以确保 p1 != p2
,如此就不会出现自己踢自己导致死循环的问题。评论
真高!比亚迪员工爆料比亚迪在越南的薪资水平:基本工资480万,全勤奖35万,交通补助20万,餐补110万,每周6天,每天10小时
上一篇:某大公司为逼迫员工离职,竟然把他的工位安排到厕所旁,没想到他直接开始记录领导的如厕时间,还发到公司大群...对此,你怎么看?--完--PS:欢迎在留言区留下你的观点,一起讨论提高。如果今天的文章让你有新的启发,欢迎转发分享给更多人。全文完,感谢你的耐心阅读。如果你还想看到我的文章,请一定给本
开发者全社区
0
太敢穿了!透视纱裙!性感火辣的身材
绝了呀今天的厂花:吴宣仪1995年1月26日,吴宣仪出生于海南省海口市,中国内地流行乐女歌手、影视演员。2016年2月,吴宣仪随宇宙少女发行首张迷你专辑正式出道。2018年4月,她参加《创造101》综艺选秀,获得第二名,成功加入火箭少女101组合。吴宣仪的颜值一直备受称赞,她的五官立体精致,皮肤白皙
逆锋起笔
0
某大公司为逼迫员工离职,竟然把他的工位安排到厕所旁,没想到他直接开始记录领导的如厕时间,还发到公司大群...
上一篇:字节的跳动职级与薪资(2024年)我们与公司间的合作,宛如两艘船只在茫茫大海上相互依靠,共同抵御风浪,携手驶向成功的彼岸。然而,当航向开始产生分歧,或是波涛汹涌的风浪改变了我们的初衷,我们或许应当冷静地选择和平分手,而非在风雨中硬撑。最近,一位网友的遭遇引起了广大职场人的关注和热议。这位网友
开发者全社区
0
金融研究 | 使用Python测量关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0
我看阿里的年终奖总算发了!
到4月底了,这两天看朋友圈,发现阿里的年终奖终于发了,问了问老同学,也从网上检索了不少信息,基本搞清楚了阿里今年的年终奖情况。近来来阿里一些集团对绩效等级做了较大的调整,以前的旧绩效系统中,绩效分为3.25、3.5、3.75、4和5五个等级,其中4和5是较高绩效等级,较少见。而且之前3.5绩效内部划
公子龙
0
一女子与一男子在阳台上打扑克,被邻居偷拍后...
近日网络上又发生了一起疑似黄色谣言的事件:一女子与一男子在阳台上打扑克,被邻居偷拍后上传到网上,引发广泛舆论讨论。根据网传视频显示,一名穿着吊带睡衣的女子与一名光着上身的男性在阳台上交谈,随后开始打起扑克牌。这一幕被邻居拍下并上传至网络后,引发了许多网友的关注和猜测,其中大部分涉及到了不当的假设。当
逆锋起笔
0
CVPR 2024|大视觉模型的开山之作!无需任何语言数据即可打造大视觉模型
↑ 点击蓝字 关注极市平台作者丨科技猛兽编辑丨极市平台极市导读 本文提出一种序列建模 (sequential modeling) 的方法,不使用任何语言数据,训练大视觉模型。>>加入极市CV技术交流群,走在计算机视觉的最前沿本文目录1 序列建模打造大视觉模型(来自 U
极市平台
1
金融研究(更新) | 使用Python构建关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0