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

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

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-19 12:18:23
戒烟的惊人效果!研究发现:戒烟10年以上,死亡率接近从未吸烟者

戒烟的惊人效果!研究发现:戒烟10年以上,死亡率接近从未吸烟者

39健康网
2025-06-18 17:31:08
富士康从越南拉回大量设备和模具:大量企业停工,原因不仅是没电

富士康从越南拉回大量设备和模具:大量企业停工,原因不仅是没电

浩舞默画
2025-06-19 07:25:03
张怡宁参加婚礼哭了,64岁丈夫一直咳嗽,看着很老,还是袁立前任

张怡宁参加婚礼哭了,64岁丈夫一直咳嗽,看着很老,还是袁立前任

一娱三分地
2025-06-11 20:53:37
王思聪与懒懒环球旅行到法国了,红裙和自信并肩而行,美极了

王思聪与懒懒环球旅行到法国了,红裙和自信并肩而行,美极了

阿废冷眼观察所
2025-06-18 08:41:09
刘国中在山西、甘肃、宁夏调研时强调  毫不放松巩固拓展好脱贫攻坚成果  分层分类优化完善常态化帮扶政策

刘国中在山西、甘肃、宁夏调研时强调  毫不放松巩固拓展好脱贫攻坚成果  分层分类优化完善常态化帮扶政策

新华社
2025-06-19 17:41:14
梅婷北京豪宅内景曝光,十个人住一栋别墅,屋里有些杂乱

梅婷北京豪宅内景曝光,十个人住一栋别墅,屋里有些杂乱

比利
2025-06-19 18:02:49
伊朗为什么不敢出动苏35轰炸以色列?

伊朗为什么不敢出动苏35轰炸以色列?

阿龙聊军事
2025-06-19 20:48:09
继韩国越南之后,巴基斯坦也贴出中文标语,句句戳中国游客的心

继韩国越南之后,巴基斯坦也贴出中文标语,句句戳中国游客的心

侃侃儿谈
2025-05-05 09:49:14
赖昌星狂砸100万,让董文华陪一晚,最终葬送了自己的后半生

赖昌星狂砸100万,让董文华陪一晚,最终葬送了自己的后半生

苏大强专栏
2024-09-12 07:46:15
再见哈登!快船正式退出,祖巴茨交易条件曝光!

再见哈登!快船正式退出,祖巴茨交易条件曝光!

运筹帷幄的篮球
2025-06-19 13:33:59
全球各国平均乳房大小地图

全球各国平均乳房大小地图

日本物语
2025-06-05 21:14:32
高考一百多分进名校!母女两代!那尔那茜的外公是谁?

高考一百多分进名校!母女两代!那尔那茜的外公是谁?

霹雳炮
2025-06-18 23:32:55
浙江小伙彩票中5.6亿,一夜暴富,10年后却说:彩票毁了我

浙江小伙彩票中5.6亿,一夜暴富,10年后却说:彩票毁了我

风到腰弯
2025-06-19 17:37:40
你以为是上火,实际却是癌症!出现5种症状,一定要提高警惕

你以为是上火,实际却是癌症!出现5种症状,一定要提高警惕

华庭讲美食
2025-06-18 13:10:44
女子炫耀一家8口不上班,每月花销3万,5年生3娃,还要试管拼四胎

女子炫耀一家8口不上班,每月花销3万,5年生3娃,还要试管拼四胎

葡萄说娱
2025-06-19 11:07:30
美军倾巢而出支援以色列!特朗普没料到,中俄不声不响干了件大事

美军倾巢而出支援以色列!特朗普没料到,中俄不声不响干了件大事

博览历史
2025-06-19 10:53:26
发现了没有,凡是选择燃油车的人,他们基本都有这三种情况

发现了没有,凡是选择燃油车的人,他们基本都有这三种情况

小嵩
2025-06-11 10:04:46
兜兜转转还是你!41岁白百何首次晒二胎,原来二婚老公依旧还是他

兜兜转转还是你!41岁白百何首次晒二胎,原来二婚老公依旧还是他

深析古今
2025-06-18 23:26:02
杨紫《国色芳华2》6月底播出,同档对打刘宇宁新剧

杨紫《国色芳华2》6月底播出,同档对打刘宇宁新剧

一盅情怀
2025-06-18 18:53:29
2025-06-19 21:47:00
邵天义科普
邵天义科普
愿我们练会72变,来笑对81难。
1293文章数 206关注度
往期回顾 全部

科技要闻

罗永浩数字人爆火,可怕的不是5500万GMV

头条要闻

普京:俄罗斯曾主动提出共研防空系统 但伊朗不感兴趣

体育要闻

22年,云南足球走出了一条自己的路

娱乐要闻

章子怡“吃蛋糕”戏在全网爆火

财经要闻

“已经崩盘了”!Labubu黄牛价腰斩

汽车要闻

5.99万起/空间大续航长 纯电小车凯翼拾月Mate上市

态度原创

房产
健康
亲子
手机
公开课

房产要闻

预定爆款!江东CBD+海中,海口这一国企大盘,即将引爆市场!

呼吸科专家破解呼吸道九大谣言!

亲子要闻

换个视角去看原来如此美好!

手机要闻

OPPO Find X9 Pro:三摄影像方案曝光!小屏版:或延期至2026!

公开课

李玫瑾:为什么性格比能力更重要?