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

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 什么是布隆过滤器?如何实现布隆过滤器?

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

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

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

1.布隆执行过程

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

  1. 在 Redis 中创建一个位数组,用于存储布隆过滤器的位向量。
  2. 初始化多个哈希函数,并将每个哈希函数的计算结果对应的位数组位置设置为 1。
  3. 添加元素到布隆过滤器时,对元素进行多次哈希计算,并将对应的位数组位置设置为 1。
  4. 查询元素是否存在时,对元素进行多次哈希计算,并检查对应的位数组位置是否都为 1。

    2.布隆使用场景

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

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

  6. 缓存穿透:可以用布隆过滤器来过滤掉恶意请求或请求不存在的数据,避免对后端存储的频繁访问。
  7. 网络爬虫的 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,其中包含的内容有:Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。

相关文章
ThreadLocal实现登录(保存用户登录信息)
ThreadLocal可以将用户信息保存在线程中,当请求结束后我们在把保存的信息清除掉。这样我们才开发的时候就可以直接从全局的ThreadLocal中很方便的获取用户信息。 使用ThreadLocal,可以在同一线程中很方便的获取用户信息,不需要频繁的传递session对象。
3194 1
ThreadLocal实现登录(保存用户登录信息)
|
Linux Shell 数据安全/隐私保护
Centos 7如何修改密码
修改CentOS7 ROOT密码非常简单,只需登录系统,执行命令passwd回车即可,但是如果忘记ROOT,无法登录系统,该如何去重置ROOT用户的密码呢?
2002 0
Centos 7如何修改密码
|
8月前
|
SQL 关系型数据库 MySQL
MySQL 中的全文索引:强大的文本搜索利器
MySQL 的全文索引是一种用于快速搜索大量文本数据的特殊索引。它通过对文本内容进行分析(如分词、去除停用词等)并构建倒排索引,实现高效查找。创建全文索引使用 `CREATE FULLTEXT INDEX`,搜索时使用 `MATCH AGAINST` 语句。适用于 `CHAR`、`VARCHAR`、`TEXT` 等字段,但需注意性能影响和正确使用搜索语法。
241 22
|
8月前
|
机器学习/深度学习 计算机视觉 网络架构
YOLOv11改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 StarNet,超级精简高效的轻量化模块
YOLOv11改进策略【模型轻量化】| 替换骨干网络 CVPR-2024 StarNet,超级精简高效的轻量化模块
577 19
|
存储 NoSQL Java
面试官:项目中如何实现布隆过滤器?
面试官:项目中如何实现布隆过滤器?
203 1
面试官:项目中如何实现布隆过滤器?
|
11月前
|
存储 架构师 Java
内存溢出原因与解决方案(4大主流方案详解)
本文详解内存溢出(OOM)的原因及解决方案。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
内存溢出原因与解决方案(4大主流方案详解)
|
缓存 监控 数据安全/隐私保护
|
存储 安全 Java
深入解析 Java 中的 Synchronized:原理、实现与性能优化
深入解析 Java 中的 Synchronized:原理、实现与性能优化
442 1
布隆过滤器(Bloom Filter)的原理和实现
布隆过滤器(Bloom Filter)的原理和实现
189 0
|
前端开发 Java Maven
SpringMVC之初识SpringMVC和项目创建
【1月更文挑战第18天】 一、SpringMVC简介 1、什么是MVC 2、什么是SpringMVC 3、SpringMVC的特点 二、SpringMVC项目创建步骤 1、创建maven工程 a>添加web模块 b>打包方式:war c>引入依赖 2、配置web.xml a>默认配置方式 b>扩展配置方式 3、创建请求控制器 4、创建springMVC的配置文件 5、测试HelloWorld a>实现对首页的访问 b>通过超链接跳转到指定页面
223 0