布隆过滤器（Bloom Filter）初学习

目录

1、布隆过滤器是什么

2、布隆过滤器的优缺点

3、使用场景

4、⭐基于Redis的布隆过滤器插件安装

4.1 下载布隆过滤器

4.2 创建文件夹并上传文件

4.3 安装gcc

4.4 解压RedisBloom压缩包

4.5 在解压好的文件夹下输入make

4.6 将编译的好的插件拷贝到docker redis容器中

4.7 修改配置文件，并重启Redis

4.8 查看操作日志

4.9 进入redis客户端查看，测试

4.10 常用命令：

小结

1、布隆过滤器是什么

布隆过滤器（Bloom Filter）是一种空间效率非常高的随机数据结构，用于判断一个元素是否在一个集合中。与传统的哈希表或者二叉搜索树等数据结构不同，布隆过滤器可以在空间和时间上做出很多妥协，从而实现高效的查询和插入操作。

布隆过滤器的核心思想是使用多个哈希函数来将元素映射到位数组中的多个位置上。当一个元素被加入到布隆过滤器中时，它会被多次哈希，并将对应的位数组位置设置为1。当需要判断一个元素是否在布隆过滤器中时，我们只需将该元素进行多次哈希，并检查对应的位数组位置是否都为1，如果其中有任意一位为0，则说明该元素不在集合中；如果所有位都为1，则说明该元素可能在集合中（因为有可能存在哈希冲突），需要进一步检查。

示例图：

图片来源：https://baijiahao.baidu.com/s?id=1760676476679974031&wfr=spider&for=pc

2、布隆过滤器的优缺点

布隆过滤器是一种概率型数据结构，用于快速判断一个元素是否存在于一个集合中。它具有以下优点和缺点：

优点：

  1. 高效的查询速度：布隆过滤器的查询时间复杂度是O(1)，即使在大规模数据集中也能快速判断一个元素是否存在。
  2. 空间效率高：相比于其他数据结构，布隆过滤器所需的空间通常较小。它利用位数组和哈希函数来表示元素的存在状态，因此占用的内存相对较少。
  3. 支持高并发场景：由于布隆过滤器的查询操作是无锁的，并且不需要访问磁盘或网络，因此适用于高并发的场景。

缺点：

  1. 可能出现误判：布隆过滤器存在一定的误判率，即可能将不存在的元素误判为存在。这是由于哈希函数的冲突和位数组的碰撞造成的。误判率随着数据量的增加而增加，可以通过调整哈希函数个数和位数组大小来降低误判率，但不能完全消除。
  2. 不支持删除操作：布隆过滤器设计初衷是用于判断元素是否存在，而不支持删除操作。一旦一个元素被添加到布隆过滤器中，就无法从布隆过滤器中删除。如果需要删除元素，需要使用其他数据结构辅助操作。
  3. 对内存敏感：布隆过滤器对内存的使用非常敏感。为了降低误判率，需要增加位数组的大小和哈希函数的个数，这会增加内存的消耗。在内存资源有限的情况下，需要权衡空间和误判率。

综上所述，布隆过滤器适用于对查询速度要求高、对误判率可以容忍的场景，但需要注意其不支持删除操作和对内存敏感的特点。在实际应用中，需要根据具体需求和数据规模来选择是否使用布隆过滤器。

3、使用场景

常见的使用场景包括：

  1. 网页黑名单过滤：将恶意网站的 URL 存储到布隆过滤器中，当用户访问时，可以快速判断该网站是否为恶意网站，从而进行拦截或提示。

  2. 垃圾邮件过滤：将已知的垃圾邮件的特征（如发件人、主题、内容等）存储到布隆过滤器中，当新邮件到来时，可以快速判断是否为垃圾邮件，从而进行过滤。

  3. ⭐缓存穿透问题解决：当缓存中不存在某个键值对时，可以先通过布隆过滤器判断该键是否存在，如果不存在，则直接返回空值，避免了对数据库等后端存储的不必要查询，从而提高了系统的性能。 

图片来源：Redis6-雪崩、击穿、穿透、分布式锁 - 知乎

图片来源：什么是布隆过滤器？ - 知乎

需要注意的是，布隆过滤器的误判率是无法避免的，因此在使用时需要根据具体场景进行权衡和调整。

4、⭐基于Redis的布隆过滤器插件安装

4.1 下载布隆过滤器

首先需要安装完成Redis（安装过程略），然后布隆过滤器便可以作为一个插件加载到Redis服务器直接使用。

Linux版本：https://github.com/RedisBloom/RedisBloom/archive/v2.2.4.tar.gz

4.2 创建文件夹并上传文件

4.3 安装gcc

4.4 解压RedisBloom压缩包

4.5 在解压好的文件夹下输入make

4.6 将编译的好的插件拷贝到docker redis容器中

4.7 修改配置文件，并重启Redis

43 # loadmodule /path/to/my_module.so

44 # loadmodule /path/to/other_module.so

45

46 loadmodule /usr/local/etc/redis/redisbloom.so

4.8 查看操作日志

4.9 进入redis客户端查看，测试

4.10 常用命令：

  1. bf.add：添加元素
  2. bf.madd：批量添加元素
  3. bf.exists：检索元素是否存在
  4. bf.mexists：检索多个元素是否存在
  5. bf.reserve：自定义布隆过滤器，设置key，error_rate和initial_size

小结

由于布隆过滤器不需要存储元素本身，而只需要存储元素的哈希值，因此它的空间效率非常高。同时，由于布隆过滤器使用多个哈希函数来减少哈希冲突的概率，因此它的查询效率也比较高。但是，布隆过滤器存在一定的误判率，即有可能将不在集合中的元素误判为在集合中，这是由于哈希冲突和位数组大小等因素造成的。因此，在使用布隆过滤器时，需要根据具体情况来选择合适的哈希函数个数和位数组大小，以控制误判率。

参考：

硬核｜Redis 布隆（Bloom Filter）过滤器原理与实战

布隆过滤器 Bloom Filter - 知乎

什么是布隆过滤器？ - 知乎

Redis6-雪崩、击穿、穿透、分布式锁 - 知乎

感谢阅读，码字不易，多谢点赞！如有不当之处，欢迎反馈指出，感谢！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/106970.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

火柴排队.

火柴排队.

题意：给两列火柴，可以交换任意相邻的火柴，使得（ai-bi)^2的和最小，求最小交换次数。 分析：使得（ai-bi)^2的和最小，即a^2-2abb^2的和最小，那么使得2ab最大，就可…
阅读更多...
荣电集团与钕希科技签署全面战略合作

荣电集团与钕希科技签署全面战略合作

10月26日，荣电集团（以下简称荣电）与钕希科技南京有限公司（以下简称钕希科技）今天在合肥市签署全面战略合作协议，联合进军混合现实（Mixed Reality，以下简称MR）空间计算高科…
阅读更多...
爬虫批量下载科研论文（SciHub）

爬虫批量下载科研论文（SciHub）

系列文章目录 利用 eutils 实现自动下载序列文件 提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 系列文章目录前言一、获取文献信息二、下载文献PDF文件参考 前言 大家好✨，这里是bio🦖。…
阅读更多...
底层驱动day8作业

底层驱动day8作业

代码&#xff1a; //驱动程序 #include<linux/init.h> #include<linux/module.h> #include<linux/of.h> #include<linux/of_gpio.h> #include<linux/gpio.h> #include<linux/timer.h>struct device_node *dnode; //unsigned int gpiono; …
阅读更多...
【云原生】portainer管理多个独立docker服务器

【云原生】portainer管理多个独立docker服务器

目录 一、portainer简介 二、安装Portainer 1.1 内网环境下&#xff1a; 1.1.1 方式1&#xff1a;命令行运行 1.1.2 方式2&#xff1a;通过compose-file来启动 2.1 配置本地主机&#xff08;node-1&#xff09; 3.1 配置其他主机&#xff08;被node-1管理的节点服务器&…
阅读更多...
RabbitMQ基础

RabbitMQ基础

目录 RabbitMQ的可靠性投递 确保消息正确地发送至 RabbitMQ 确保消息接收方消费了消息 流程分析 1.生产者发送消息给Broker 2.交换机路由消息到队列 3.消息存储在队列 4.消费者订阅并消费消息 三个重要概念 RabbitMQ集群模式 RabbitMQ的可靠性投递 在 RabbitMQ 中&a…
阅读更多...
TS中类型别名和接口区别

TS中类型别名和接口区别

在很多场景下&#xff0c;interface 和 type都能使用&#xff0c;因此两者在很多时候会被混淆&#xff1a; 接口可以通过之间的继承&#xff0c;实现多种接口的组合 使用类型别名也可以实现多种的&#xff0c;通过&连接,有差异&#xff1a; 子接口中不能重新覆盖父接口中…
阅读更多...
迭代器的封装与反向迭代器

迭代器的封装与反向迭代器

一、反向迭代器 在list模拟实现的过程中&#xff0c;第一次接触了迭代器的封装&#xff0c;将list的指针封装成了一个新的类型&#xff0c;并且以迭代器的基本功能对其进行了运算符重载 反向迭代器是对正向迭代器的封装&#xff0c;并且体现了泛型编程的思想&#xff0c;任意…
阅读更多...
0基础学习PyFlink——用户自定义函数之UDAF

0基础学习PyFlink——用户自定义函数之UDAF

大纲 UDAF入参并非表中一行&#xff08;Row&#xff09;的集合计算每个人考了几门课计算每门课有几个人考试计算每个人的平均分计算每课的平均分计算每个人的最高分和最低分 入参是表中一行&#xff08;Row&#xff09;的集合计算每个人的最高分、最低分以及所属的课程计算每课…
阅读更多...
中文编程工具免费版下载，中文开发语言工具免费版下载

中文编程工具免费版下载，中文开发语言工具免费版下载

中文编程工具免费版下载&#xff0c;中文开发语言工具免费版下载 中文编程工具开发的实际部分案例如下图 编程系统化课程总目录及明细&#xff0c;点击进入了解详情。 https://blog.csdn.net/qq_29129627/article/details/134073098?spm1001.2014.3001.5502
阅读更多...
栈、队列、矩阵的总结

栈、队列、矩阵的总结

栈的应用 括号匹配 表达式求值&#xff08;中缀&#xff0c;后缀&#xff09; 中缀转后缀&#xff08;机算&#xff09; 中缀机算 后缀机算 总结 特殊矩阵 对称矩阵的压缩存储 三角矩阵 三对角矩阵 稀疏矩阵的压缩存储
阅读更多...
龙芯3A5000上安装微信

龙芯3A5000上安装微信

原文链接&#xff1a;龙芯3A5000上安装微信 hello&#xff0c;大家好啊&#xff0c;今天给大家带来一篇在龙芯3A5000上安装微信的文章&#xff0c;主要给大家展示一下在龙芯架构上使用微信的情况&#xff0c;看看内置浏览器、看一看、小程序等是否能正常打开使用。 1、查看系统…
阅读更多...
Hadoop 请求数据长度 Requested Data length 超过配置的最大值

Hadoop 请求数据长度 Requested Data length 超过配置的最大值

一、问题 现象 Spark 任务速度变慢&#xff0c;也不失败。 DataNode 内存足够 CPU 负载不高 GC 时间也不长。 查看 DataNode 日志&#xff0c;发现有些日志出现很多 Netty RPC 超时。超时的 destination 是一个 NameNode 节点&#xff0c;然后查看 NameNode 节点的日志&…
阅读更多...
28 行为型模式-中介者模式

28 行为型模式-中介者模式

1 中介者模式介绍 2 中介者模式原理 3 中介者模式实现 /*** 抽象中介者**/ public interface Mediator {//处理同事对象注册与转发同事对象信息的方法void apply(String key); }/*** 具体中介者**/ public class MediatorImpl implements Mediator {Overridepublic void apply…
阅读更多...
Spring的执行流程与Bean的生命周期

Spring的执行流程与Bean的生命周期

目录 一、Spring的执行流程&#xff08;生命周期&#xff09; 二、Bean的生命周期 一、Spring的执行流程&#xff08;生命周期&#xff09; 首先在Spring的执行过程中会先启动容器&#xff0c;这里是将配置文件进行加载。根据配置文件完成Bean的实例化&#xff0c;比如是配置的…
阅读更多...
安防监控项目---boa服务器的移植

安防监控项目---boa服务器的移植

文章目录 前言一、boa服务器简介二、移植步骤三、测试结果四、A9平台移植BOA总结 前言 书接上期&#xff0c;在配置完成环境后&#xff0c;那么接下来呢还得移植两个非常关键的东西&#xff0c;一个呢时boa服务器&#xff0c;另一个呢时cgi接口&#xff0c;boa服务器能够使得我…
阅读更多...
干式电抗器的尺寸和重量对系统有什么影响？

干式电抗器的尺寸和重量对系统有什么影响？

干式电抗器是一种用于电力系统中的无功补偿设备&#xff0c;其尺寸和重量对系统有以下几方面的影响&#xff0c;干式电抗器的尺寸和重量会影响设备的安装和布置&#xff0c;较大尺寸和重量的电抗器需要更大的安装空间&#xff0c;并且可能需要额外的支撑结构。在设计系统时需要…
阅读更多...
做跨境电商你要用到的API（获取英文商品详情介绍API）

做跨境电商你要用到的API（获取英文商品详情介绍API）

item_get获取商品详情数据 支持以上网站以及亚马逊、阿里巴巴、虾皮、Lazada、速卖通等跨境电商。 获取商品返回示例 "item": {"num_iid": "60840463360","title": "Slip-On Daily Urban Walking Shoes","desc_shor…
阅读更多...
CPU眼里的C/C++: 1.3 汇编级单步调试函数执行过程

CPU眼里的C/C++: 1.3 汇编级单步调试函数执行过程

1. 目的 2. 基于 GDB 的汇编级单步调试 原始代码 #include <stdio.h>long test() {long a 1;a 2;return a; }int main() {int ret test();printf("test return %d\n", ret);return 0; }关键 gdb 命令 si 指令执行汇编级的单步调试info registers 读取寄…
阅读更多...
分布式消息队列:RabbitMQ(1)

分布式消息队列:RabbitMQ(1)

目录 一:中间件 二:分布式消息队列 2.1:是消息队列 2.1.1:消息队列的优势 2.1.1.1:异步处理化 2.1.1.2:削峰填谷 2.2:分布式消息队列 2.2.1:分布式消息队列的优势 2.2.1.1:数据的持久化 2.2.1.2:可扩展性 2.2.1.3:应用解耦 2.2.1.4:发送订阅 2.2.2:分布式消息队列…
阅读更多...
最新文章

Copyright @ 2022~2023