网易首页 > 网易号 > 正文 申请入驻

什么是布隆过滤器?如何实现布隆过滤器?

0
分享至

布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它基于位数组和多个哈希函数的原理,可以高效地进行元素的查询,而且占用的空间相对较小,如下图所示:

根据 key 值计算出它的存储位置,然后将此位置标识全部标识为 1(未存放数据的位置全部为 0),查询时也是查询对应的位置是否全部为 1,如果全部为 1,则说明

数据是可能存在的,否则一定不存在

也就是说,如果

布隆过滤器说一个元素不在集合中,那么它一定不在这个集合中;但如果它说一个元素在集合中,则有可能是不存在的(存在误差)

1.布隆执行过程

布隆过滤器的具体执行步骤如下:

在 Redis 中创建一个位数组,用于存储布隆过滤器的位向量。

初始化多个哈希函数,并将每个哈希函数的计算结果对应的位数组位置设置为 1。

添加元素到布隆过滤器时,对元素进行多次哈希计算,并将对应的位数组位置设置为 1。

查询元素是否存在时,对元素进行多次哈希计算,并检查对应的位数组位置是否都为 1。

2.布隆使用场景

布隆过滤器的主要使用场景有以下几个:

大数据量去重

:可以用布隆过滤器来进行数据去重,判断一个数据是否已经存在,避免重复插入。

缓存穿透

:可以用布隆过滤器来过滤掉恶意请求或请求不存在的数据,避免对后端存储的频繁访问。

网络爬虫的 URL 去重

:可以用布隆过滤器来判断 URL 是否已经被爬取,避免重复爬取。

3.如何实现布隆过滤器?

在 Redis 中不能直接使用布隆过滤器,但我们可以通过 Redis 4.0 版本之后提供的 modules (扩展模块) 的方式引入,它的实现步骤如下。

① 打包RedisBloom插件

git clone https://github.com/RedisLabsModules/redisbloom.git

cd redisbloom

make # 编译redisbloom

编译正常执行完,会在根目录生成一个 redisbloom.so 文件。

② 启用RedisBloom插件

重新启动 Redis 服务,并指定启动 RedisBloom 插件,具体命令如下:

redis-server redis.conf --loadmodule ./src/modules/RedisBloom-master/redisbloom.so

③ 创建布隆过滤器

创建一个布隆过滤器,并设置期望插入的元素数量和误差率,在 Redis 客户端中输入以下命令:

BF.RESERVE my_bloom_filter 0.01 100000

④ 添加元素到布隆过滤器

在 Redis 客户端中输入以下命令:

BF.ADD my_bloom_filter leige

⑤ 检查元素是否存在

在 Redis 客户端中输入以下命令:

BF.EXISTS my_bloom_filter leige

课后思考

以上我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?欢迎评论区留下您的实现方案。

本文已收录到我的面试小站 [www.javacn.site](https://www.javacn.site),其中包含的内容有:Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
为什么中国人从“全民学英语”,变成悄悄“放弃”英语?

为什么中国人从“全民学英语”,变成悄悄“放弃”英语?

廖保平
2025-06-03 11:09:42
Science痛批:近3年,垃圾论文激增,92%来自中国

Science痛批:近3年,垃圾论文激增,92%来自中国

医诺维
2025-06-03 17:45:08
付辉:爆雷的车企在排队

付辉:爆雷的车企在排队

后视镜里de未来
2025-06-03 11:17:54
购房者称认购商品房不到一年同户型降200多万:销售称已退房退款,相关部门介入

购房者称认购商品房不到一年同户型降200多万:销售称已退房退款,相关部门介入

澎湃新闻
2025-06-04 07:44:29
差点以为眼花了!6月1号晚,央视主播们抛开西装,全换上中式服装

差点以为眼花了!6月1号晚,央视主播们抛开西装,全换上中式服装

小娱乐悠悠
2025-06-03 10:14:15
深圳警方通报一女子大厦高坠死亡:系轻生,排除刑事案件

深圳警方通报一女子大厦高坠死亡:系轻生,排除刑事案件

界面新闻
2025-06-03 19:35:50
女游客被蛇咬身亡后续,身份背景曝光,调查组介入,俩医院恐担责

女游客被蛇咬身亡后续,身份背景曝光,调查组介入,俩医院恐担责

奇思妙想草叶君
2025-06-03 23:56:08
樊振东赴德国打球薪资曝光!基础年薪约980万,夺冠奖金另算

樊振东赴德国打球薪资曝光!基础年薪约980万,夺冠奖金另算

梦史
2025-06-03 13:29:08
杭州滨江社工400比1,没有编制薪资瞠目,网友直呼余杭更离谱!

杭州滨江社工400比1,没有编制薪资瞠目,网友直呼余杭更离谱!

古希腊掌管松饼的神
2025-06-03 16:08:37
三亚27岁女游客疑被蛇咬伤身亡 家属:抢救3小时后医院称“没救治经验”丨封面头条

三亚27岁女游客疑被蛇咬伤身亡 家属:抢救3小时后医院称“没救治经验”丨封面头条

封面新闻
2025-06-03 19:26:08
台湾旅行团整团被卖到缅甸:3人不会用电子产品被释放

台湾旅行团整团被卖到缅甸:3人不会用电子产品被释放

大象新闻
2025-06-03 16:51:10
从4.5万/平米跌到2.5万/平米,广州海珠的金碧花园跌出新低

从4.5万/平米跌到2.5万/平米,广州海珠的金碧花园跌出新低

小人物看尽人间百态
2025-06-03 23:16:35
小沈阳演唱会下跪道歉!观众不买账,怒喊退票纷纷提前离场

小沈阳演唱会下跪道歉!观众不买账,怒喊退票纷纷提前离场

晋哥说电影
2025-06-03 15:16:22
美国不要的,中国也不要!蒋雨融事件越闹越大,网友:卖国求荣

美国不要的,中国也不要!蒋雨融事件越闹越大,网友:卖国求荣

闻识
2025-06-03 14:15:46
一场恶战打醒了俄罗斯,普京终于明白:最危险的人原来就在身边

一场恶战打醒了俄罗斯,普京终于明白:最危险的人原来就在身边

铁锤简科
2025-06-02 23:24:40
张雪峰,再不闭嘴就真的危险了

张雪峰,再不闭嘴就真的危险了

末名先生
2025-06-03 15:47:38
官方:纽约尼克斯解雇主帅希伯杜

官方:纽约尼克斯解雇主帅希伯杜

懂球帝
2025-06-04 03:19:12
英国和日本为何突然晒出南京条约和马关条约?

英国和日本为何突然晒出南京条约和马关条约?

谈芯说科技
2025-06-03 16:10:12
别急着嘲笑俄罗斯,这玩意的确不好防

别急着嘲笑俄罗斯,这玩意的确不好防

枢密院十号
2025-06-04 02:28:22
越南取消计划生育

越南取消计划生育

李东海评论
2025-06-03 23:50:21
2025-06-04 08:44:49
邵天义科普
邵天义科普
愿我们练会72变,来笑对81难。
1293文章数 206关注度
往期回顾 全部

科技要闻

雷军最新发声:YU7志在必得 详解三大护城河

头条要闻

买房不到1年同户型降200多万 男子要求调价被拒后投诉

体育要闻

从家乡的水泥球场,他一路走上欧洲之巅

娱乐要闻

黄杨钿甜新剧播出热议 制片作出回应

财经要闻

清流|中国车企到底有没有“恒大”?

汽车要闻

掷弹兵 最不像“豪华车”的豪华车

态度原创

健康
家居
数码
教育
军事航空

唇疱疹和口腔溃疡是"同伙"吗?

家居要闻

北欧氛围 清新活泼趣味

数码要闻

6月11日见!红魔电竞平板3 Pro外观公布

教育要闻

表象背后的深思:哈佛中国女留学生演讲没有迎来赞誉,却是被群嘲

军事要闻

互换各6000具士兵遗体 俄乌谈判数字细节展现冲突惨烈