当前位置：首页 > news >正文

布隆过滤器（Bloom Filter）

news 来源：原创 2025/8/21 1:15:41

布隆过滤器是一种概率型数据结构，用于快速判断一个元素是否可能在集合中存在。它的核心特点是：

节省空间：相比哈希表，布隆过滤器占用的存储空间非常小。
高效查询：查询时间复杂度为 (O(k))，其中 (k) 是哈希函数的数量，远小于传统数据结构。
允许误判：可能出现假阳性（False Positive），即误判某个元素存在，但实际不存在。不会出现假阴性（False Negative），即不会漏报已插入的元素。

布隆过滤器的工作原理

布隆过滤器的核心是一个位数组（bit array），通常初始化为全 0，并配合多个哈希函数一起工作。

插入元素：
- 使用 ( k ) 个哈希函数对元素进行哈希计算，得到 ( k ) 个不同的索引位置。
- 在位数组中，将这 ( k ) 个索引对应的位设为 1。
查询元素是否存在：
- 使用相同的 ( k ) 个哈希函数计算查询元素的索引位置。
- 检查这些索引位置的位：
  - 如果全部是 1，则可能存在（但不确定，存在误判）。
  - 如果有任意一个是 0，则一定不存在（不会误判）。
删除元素（不可行）：
- 由于不同元素可能映射到相同的位置，无法简单地将位数组中的某个位置重置为 0，否则可能会影响其他元素的判断。
- 解决方案：计数布隆过滤器（Counting Bloom Filter），用计数数组代替位数组，每次插入+1，删除-1。

布隆过滤器 vs 其他数据结构

数据结构	查询时间复杂度	空间占用	是否可能误判	是否支持删除
哈希表	(O(1))	高	否	是
红黑树	(O(\log n))	中等	否	是
布隆过滤器	(O(k))	低	是（假阳性）	否（普通布隆）

布隆过滤器的应用场景

缓存击穿防护（如 Redis 缓存）：
- 先查询布隆过滤器，如果不存在，则直接返回，不查询数据库，减少数据库压力。
- 如果可能存在，则再去查询数据库，防止缓存穿透。
黑名单过滤（如垃圾邮件过滤、恶意 IP 拦截）：
- 提前将黑名单数据存入布隆过滤器，收到请求时先检查布隆过滤器，若不存在直接放行，提高查询效率。
去重检查（如搜索引擎爬虫）：
- 记录已经访问过的 URL，防止重复爬取相同的页面，节省带宽和计算资源。
区块链和数据库去重（如比特币网络）：
- Bitcoin 网络使用布隆过滤器优化交易信息同步，提高同步效率。

如何优化布隆过滤器

选择合适的哈希函数数量 ( k )：
- 过少会导致误判率上升，过多会增加计算开销。最优 ( k ) 计算公式：
  [
  k = \ln(2) \times \frac{m}{n}
  ]
  其中 ( m ) 是位数组大小，( n ) 是元素个数。
控制误判率：
- 位数组大小 ( m ) 与元素个数 ( n ) 的比例影响误判率：
  [
  p = \left(1 - e^{{\frac{-kn}{m}}\right)}k
  ]
- 通过调整位数组大小 ( m ) 和哈希函数个数 ( k ) 来优化误判率。
使用变种布隆过滤器：
- 计数布隆过滤器：支持删除操作。
- 分层布隆过滤器（Scaling Bloom Filter）：解决动态增长的问题。
- 分区布隆过滤器（Partitioned Bloom Filter）：减少哈希冲突，提高查询性能。

布隆过滤器在 Java 中的实现

Java 中可以使用 Guava 提供的 BloomFilter 组件：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;public class BloomFilterExample {public static void main(String[] args) {// 预计存入 100 万个元素，误判率 1%BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1_000_000, 0.01);// 添加元素bloomFilter.put(123);bloomFilter.put(456);// 查询元素System.out.println(bloomFilter.mightContain(123)); // trueSystem.out.println(bloomFilter.mightContain(789)); // 可能是 false 或 true（误判）}
}

总结

✅ 适用于大规模数据的快速查询，节省存储空间，防止缓存穿透等问题。
✅ 支持高效查询，但存在一定误判率，不适用于严格一致性的场景。
❌ 不能删除元素（普通布隆），删除需要额外扩展（如计数布隆过滤器）。

布隆过滤器是一种非常实用的数据结构，在大数据、分布式系统、缓存系统、反垃圾处理等场景中广泛应用。

布隆过滤器（Bloom Filter）

布隆过滤器是一种概率型数据结构，用于快速判断一个元素是否可能在集合中存在。它的核心特点是： 节省空间：相比哈希表，布隆过滤器占用的存储空间非常小。高效查询：查询时间复杂度为 (O(k))，其中 (k) 是哈希…...

编程日记 2025/8/21 1:15:41

2025-03-10 学习记录--C/C++-C语言易错点大总结

C语言易错点大总结一、strlen(strs) 使用错误 ⭐️ 若strs 是一个指针数组（const char* strs[]），则不可用strlen(strs) 计算 strs 的长度，因为 strlen 是用于计算字符串的长度，而不是数组的长度。解决方法 &…...

编程日记 2025/8/21 1:15:34

康谋应用 | 基于多传感器融合的海洋数据采集系统

在海洋监测领域，基于无人艇能够实现高效、实时、自动化的海洋数据采集，从而为海洋环境保护、资源开发等提供有力支持。其中，无人艇的控制算法训练往往需要大量高质量的数据支持。然而，海洋数据采集也面临数据噪声和误差、数据融合…...

编程日记 2025/8/21 1:13:54

SpringMVC （二）请求处理

目录章节简介一请求处理（初级） eg:请求头二请求处理（进阶） eg:请求体三获取请求头四获取Cookie 五级联封装六使用RequestBoby封装JSON对象七文件的上传八获取整个请求 HttpEntity 九原生请求 Spring…...

编程日记 2025/8/21 1:15:35

数据结构——单链表list

前言：大家好😍，本文主要介绍数据结构——单链表目录一、单链表二、使用步骤 1.结构体定义 2.初始化 3.插入 3.1 头插 3.2 尾插 3.3 按位置插四.删除 4.1头删 4.2 尾删 4.3 按位置删 4.4按值删五统计有效值个数六销毁…...

编程日记 2025/8/21 1:09:53

课程《Deep Learning Specialization》

在coursera上，Deep Learning Specialization 课程内容如下图所示： Week2 assignment, Logistic Regression....

编程日记 2025/8/21 1:15:32

低版本 Linux 系统通过二进制方式升级部署高版本 Docker

一、背景： 在一些 Linux 系统中，由于系统自带的软件源版本较低，或者因网络、权限等限制无法直接通过源文件来升级到最新版本的 Docker。这种情况下，采用二进制方式升级部署高版本 Docker 就成为一种有效的解决方案。下面将详…...

编程日记 2025/8/21 1:15:32

线索二叉树构造及遍历算法

线索二叉树构造以及遍历算法线索二叉树（中序遍历版）构造线索二叉树构造双向线索链表遍历中序线索二叉树线索二叉树（中序遍历版） 中序遍历找到对应结点的前驱（土方法） #mermaid-svg-eunGO5d2GhjLxCn5 {fo…...

编程日记 2025/8/21 1:13:57

3. 自定义类型****

目录 1. 内存对齐（必考） 如何计算？ 为什么要内存对齐？ 2. 联合 2.1 联合的定义 2.2 联合的特点 1. 内存对齐（必考） 结构体内存对齐是一个特别热门的考点。如何计算？ 第一个成员在与结构…...

编程日记 2025/8/21 1:15:35

Redis Sentinel (哨兵模式)深度解析：构建高可用分布式缓存系统的核心机制

一、传统主从复制的痛点在分布式系统架构中，Redis 作为高性能缓存和数据存储解决方案，其可用性直接关系到整个系统的稳定性。传统的主从复制架构虽然实现了数据冗余，但在面临节点故障时仍存在明显缺陷： 手动故障转移&#xf…...

编程日记 2025/8/21 1:11:55

deepseek本地部署

deepseek本地部署哈喽，兄弟们！大家可以想象一下，如果有一个超级聪明的人机大脑，能帮你解答任何问题，从复杂的数学难题到编程代码，再到那些让你头疼的写作任务，它都能轻松搞定。这不是科幻电影里的场景，而是DeepSeek带来的现实奇迹！DeepSeek，这个名字听起来就充满了…...

编程日记 2025/8/21 1:15:34

责任链模式的C++实现示例

核心思想责任链模式是一种行为设计模式，允许多个对象都有机会处理请求，从而避免请求的发送者与接收者之间的耦合。请求沿着处理链传递，直到某个对象处理它为止。解决的问题解耦请求发送者与处理者：请求的发送者无需知道具…...

编程日记 2025/8/21 1:05:42

【蓝桥杯python研究生组备赛】003 贪心

题目1 股票买卖给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易&…...

编程日记 2025/8/21 1:01:38

Banana Pi 与瑞萨电子携手共同推动开源创新:BPI-AI2N

2025年3月11日， Banana Pi 开源硬件平台很高兴宣布，与全球知名半导体解决方案供应商瑞萨电子（Renesas Electronics）正式达成技术合作关系。此次合作标志着双方将在开源技术、嵌入式系统和物联网等领域展开深度合作，为全…...

编程日记 2025/8/21 1:11:54

【算法工具】HDL: 基于摘要统计数据的高维连锁不平衡分析软件

## 前言在基因组研究中，连锁不平衡(Linkage Disequilibrium, LD)分析是理解遗传变异之间关联的关键步骤。然而，当面对高维数据时，传统分析方法往往面临巨大计算挑战。今天为大家介绍一款强大的工具——HDL (High-Dimensional Linkage diseq…...

编程日记 2025/8/21 1:07:51

虚拟展览馆小程序：数字艺术与文化展示的新形式探索

虚拟展览馆小程序：数字艺术与文化展示的新形式探索一、传统展览的痛点：物理空间的局限与数字化的必然在传统的艺术与文化展览中，观众往往需要跨越地理距离、排队数小时才能进入展馆，而许多珍贵展品因保护需求无法长期展出。数据显示，全球90%以上的博物馆藏品常年沉睡于…...

编程日记 2025/8/20 13:27:08

docker 搭建alpine下nginx1.26/mysql8.0/php7.4环境

docker 搭建alpine下nginx1.26/mysql8.0/php7.4环境 docker-compose.yml services:mysql-8.0:container_name: mysql-8.0image: mysql:8.0restart: always#ports:#- "3306:3306"volumes:- ./etc/mysql/conf.d/mysql.cnf:/etc/mysql/conf.d/mysql.cnf:ro- ./var/log…...

编程日记 2025/8/20 16:34:25

java项目之基于ssm的在线学习系统（源码+文档）

项目简介在线学习系统实现了以下功能： 该系统可以实现论坛管理，通知信息管理，学生管理，回答管理，教师管理，教案管理，公告信息管理，作业管理等功能。 💕💕作…...

编程日记 2025/8/21 1:15:33

macOS 安装配置 iTerm2 记录

都说 macOS 里替换终端最好的就是 iTerm2 ，这玩意儿还是开源的，所以就也根风学习一下，但全是英文的挺麻烦，所以这里记录一下自己的设置，以最简单的安装及设置为主，想要更酷炫、更好看的还请自己百度吧&…...

编程日记 2025/8/20 23:55:08

矩阵分析-浅要理解（深度学习方向）

梯度分析与最优化在深度学习的任务中，我们所期望的是训练一个神经网络，使得预测结果与真实标签之间的误差最小化，这可以近似看作是一个提供梯度下降等优化找到全局最优解的凸优化问题。奇异值分解在信息工程领域，对数据处理的…...

编程日记 2025/8/21 1:11:57

Odoo 18 中的自动字段和预留字段

Odoo 18 中的自动字段和预留字段作为一个开源平台，Odoo 的价值在于其使用和开发的灵活性、可扩展性和经济性。虽然 Odoo 本身主要用 Python 和 JavaScript 编写，但其作为开源 ERP 系统的价值超越了特定编程语言的范畴，为各行各业的企业提供了…...

编程日记 2025/8/21 1:13:55

【操作系统安全】任务1：操作系统部署

目录一、VMware Workstation Pro 17 部署二、VMware Workstation 联网方式三、VMware 虚拟机安装流程四、操作系统介绍五、Kali 操作系统安装六、Windows 系统安装七、Windows 系统网络配置八、Linux 网络配置 CSDN 原创主页：不羁https://blog.csd…...

编程日记 2025/8/21 1:07:50

Linux：自动化构建-make/Makefile

1.背景一个工程中的源文件不计数，其按类型、功能、模块分别放在若干个目录中，makefile定义了一系列的规则来指定，哪些文件需要先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至于进行更复杂的功能操作…...

编程日记 2025/8/20 17:11:56

maven wrapper的使用

写在前面考虑这样的场景，张三创建了一个maven项目使用了3.9版本，当李四下载下来去开发配置的却是3.6版本，此时李四就不得不再去配置一个3.9版本的maven，为了解决这个问题，maven引入了maven wrapper的机制&#xff08…...

编程日记 2025/8/20 2:34:04

DB-GPT-0.7版本win11安装，最新版本，安装方式变更了

之前两天折腾要死，只因为安装了旧版本问题太多，现在安装最新版本快速开始_V0.7.0 语雀 DB-GPT 0.7.0 部署教程 - yyhhyys blog DB-GPT 0.7.0 与 DeepSeek 集成使用指南 - yyhhyys blog 首先代码结构换了，python包管理工作也换了&#xf…...

编程日记 2025/8/21 1:15:40

树莓集团落子海南，如何重构数字产业生态体系

树莓集团在海南的布局，是其整体商业战略中的关键一环。这背后，是对政策机遇、产业协同、以及区域优势的深度考量。政策机遇海南自贸港建设带来前所未有的政策红利，包括贸易、投资、资金等方面的自由便利。树莓集团紧抓这一机遇&#xff0…...

编程日记 2025/8/21 1:15:38

Spring Boot 项目部署启动异常问题分析与解决：主类缺失与依赖冲突的分析

Spring Boot 项目部署启动异常问题分析与解决在近期的 Spring Boot 项目部署工作中，遭遇了一起典型的启动异常状况。经过多维度的深入排查以及细致的调试，最终确定问题的根源在于打包插件配置与依赖管理的综合影响。以下将详细阐述整个问题的分析过程以及对应的解决办法。 …...

编程日记 2025/8/21 1:07:50

共享内存(System V)——进程通信

个人主页：敲上瘾-CSDN博客进程通信： 匿名管道：进程池的制作（linux进程间通信，匿名管道... ...）-CSDN博客命名管道：命名管道——进程间通信-CSDN博客目录一、共享内存的原理二、信道的建立 …...

编程日记 2025/8/20 12:13:24

考研数学非数竞赛复习之Stolz定理求解数列极限

在非数类大学生数学竞赛中，Stolz定理作为一种强大的工具，经常被用来解决和式数列极限的问题，也被誉为离散版的’洛必达’方法，它提供了一种简洁而有效的方法，使得原本复杂繁琐的极限计算过程变得直观明了。本文&#x…...

编程日记 2025/8/21 1:11:54

12 DHCP的内容和HTTP的改良

一、回顾计算机分配相关身份网络号、主机号网络号内的主机识别局部网通信网关不同网络的通信DNS服务器域名解析因特网通信二、DHCP协议建议学习前看这个视频，14分钟，所有的知识点都有，很容易理解 1、理解 DHCP 的全称是 Dynam…...

编程日记 2025/8/21 1:03:40

多光谱相机数据采集过程中常见仪器

1.BF1515多光谱相机 2.VIX-N220推扫式可见光近红外高光谱相机覆盖光谱范围：400-1000nm； 光谱分辨率：2nm； 设备配套软件：VIX-N220、XuanDo(用于调节相机推扫速度)； 镜头调节所需材料：黑色条…...

编程日记 2025/8/21 1:05:41

【调研】olmOCR解析PDF

测试用例： olmOCR GOT-OCR 将最底下没有文字的部分，可能是样式解析出重复 olmOCR GOT-OCR 无重复重复速度上，olmOCR效果更快效果上，olmOCR解析得到的内容排版更加清晰整齐，而且对于6份GOT-OCR有重复的测…...

编程日记 2025/8/21 1:03:40

蓝桥杯随笔练——二分模板

答案 #include <bits/stdc.h> //洛谷2249 using namespace std;const int N 1e610; int n,m; int a[N];int Array_Search(int a[],int len,int x) {int L 0,R len1;while(L1 < R){int mid (RL) >> 1;if(a[mid] < x ) L mid;else R mid;}if(a[R] x) r…...

编程日记 2025/8/21 1:03:40

【Golang】第三弹----运算符

笔上得来终觉浅,绝知此事要躬行 🔥 个人主页：星云爱编程 🔥 所属专栏：Golang 🌷追光的人，终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章一、运算符介绍运算符是一…...

编程日记 2025/8/21 1:05:43

MongoDB 聚合管道速成教程

一、引言 MongoDB 的聚合管道（Aggregation Pipeline）是一种强大的数据处理工具，它允许你对文档进行一系列的操作，如过滤、转换、分组和聚合等。聚合管道由多个管道组成，每个管道对输入的文档进行特定的处理&#xff0…...

编程日记 2025/8/21 1:15:37

「JavaScript深入」二进制数据处理详解「Blob、File、FileReader、ArrayBuffer、Typed Arrays、DataView」

二进制数据处理详解 1. Blob（Binary Large Object）Blob 的特性创建 BlobBlob 主要方法Blob 的应用 2. FileFile 对象的属性获取 File 对象 3. FileReader创建 FileReader主要方法主要事件文件上传与读取内容示例文件分块读取示例 4. ArrayBuffer 与 Type…...

编程日记 2025/8/21 1:01:39

信号处理之插值、抽取与多项滤波

信号处理之插值、抽取与多项滤波一、问题背景插值(Interpolation)与抽取(Decimation)是数字信号处理中采样率转换的核心操作： 插值：在信号中插入新样本以提高采样率（ L L L倍）抽取：按比例 M M M降低采样率&#xf…...

编程日记 2025/8/21 1:09:52

关于WPS的Excel点击单元格打开别的文档的两种方法的探究

问题需求目录和文件结构如下： E:\Dir_Level1 │ Level1.txt │ └─Dir_Level2│ Level2.txt│ master.xlsx│└─Dir_Level3Level3.txt现在要在master.xlsx点击单元格进而访问Level1.txt、Level2.txt、Level3.txt这些文件。方法一：“单元格右键…...

编程日记 2025/8/21 1:07:49

蓝桥 2109统计子矩阵

问题描述给定一个NM 的矩阵 A, 请你统计有多少个子矩阵 (最小 11, 最大 NM) 满足子矩阵中所有数的和不超过给定的整数 K ? 输入格式第一行包含三个整数 N,M 和 K. 之后 NN 行每行包含 M 个整数, 代表矩阵 A. 输出格式一个整数代表答案。样例输入 3 4 10 1 2 3 4 5…...

编程日记 2025/8/21 1:03:39

AF3 make_fixed_size函数解读

AlphaFold3 data_transforms 模块的 make_fixed_size 函数的作用是将输入的蛋白质特征字典 protein 中的各个特征张量调整为固定大小。这是为了确保在批量处理时，所有特征张量的形状一致，从而避免形状不匹配的问题。源代码： import itertools import torch from src.con…...

编程日记 2025/8/21 1:03:42

前端模块管理新思路：如何使用 Import Maps

前言前端开发中，我们常常需要使用各种库和模块来构建功能丰富的应用。在传统方式中，管理这些库和模块的引用可能会有些繁琐。幸运的是，Import Maps 的出现为我们提供了一种更简洁和高效的解决方案。今天我们就来聊聊如何使用 Import Maps。…...

编程日记 2025/8/21 0:57:33

交换机、路由器、网关、MAC地址——从入门到实战

你是否好奇，当你在手机上点击一个网页链接时，数据是如何从你的设备“飞”到千里之外的服务器并返回的？背后离不开交换机、路由器、网关和MAC地址的默契配合。本文用通俗语言实战场景，带你彻底搞懂这些网络核心组件，从此…...

编程日记 2025/8/20 18:48:13

【江协科技STM32】ADC数模转换器-学习笔记

ADC简介 ADC（Analog-Digital Converter）模拟-数字转换器ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量，建立模拟电路到数字电路的桥梁，ADC是一种将连续的模拟信号转换为离散的数字信号的设备或模块12位逐次逼近型…...

编程日记 2025/8/16 12:46:26

LanceDB快速入门之基本操作与API一览

LanceDB可以以多种方式运行可以嵌入到现有后端（如您的 Django、Flask、Node.js 或 FastAPI 应用程序）中直接从如 Jupyter 笔记本等客户端应用程序中用于分析工作负载部署为远程无服务器数据库安装 Python： pip install lancedbTypeScrip…...

编程日记 2025/8/17 17:29:46

Spring Boot 整合 Redis

以下是 Spring Boot 整合 Redis 的指南，涵盖配置、基本操作、高级用法及常见问题解决。 1. 添加依赖在 pom.xml 中添加 Spring Data Redis 和连接池依赖： <dependency><groupId>org.springframework.boot</groupId><artifactId&…...

编程日记 2025/8/19 14:01:39