布隆过滤器(Bloom Filter)

文章目录

  • 1. 定义
  • 2. 核心原理
    • 2.1 数据结构
    • 2.2 操作流程
    • 2.3 扩容
  • 3. 优缺点
    • 3.1 优点
    • 3.2 缺点
  • 4. 使用场景
    • 4.1 适用场景
    • 4.2 不适用场景
  • 5. 手写布隆过滤器

1. 定义

布隆过滤器(Bloom Filter)是一种概率型数据结构,用于快速判断一个元素是否属于某个集合。

2. 核心原理

2.1 数据结构

  • 位数组(Bit Array):长度为 m 的二进制数组,初始所有位为 0。
  • 哈希函数:使用 k 个独立的哈希函数(Hash Function),每个函数将元素映射到位数组的某个位置。

2.2 操作流程

  1. 添加元素
    • 将元素通过 k 个哈希函数映射到位数组的 k 个位置。
    • 将这些位置的二进制位设为 1
  2. 查询元素
    • 将元素通过 k 个哈希函数映射到位数组的 k 个位置。
    • 如果所有位置的值均为 1,则认为元素可能存在于集合中。
    • 如果有任意位置为 0,则元素一定不存在于集合中。

2.3 扩容

布隆过滤器的大小是固定的,当添加更多的元素时,位数组中的位会逐渐被填满,导致哈希碰撞的概率增大,从而导致误判率升高。因此,当布隆过滤器的误判率超过了预期时,就需要进行扩容。

方案 1:分层布隆过滤器(Layered Bloom Filter)

  • 核心思想:创建多个独立的布隆过滤器层,每层容量逐渐增大(如翻倍),当一层饱和后启用下一层。
  • 操作流程
    • 插入:新元素仅添加到当前活跃层。
    • 查询:从最新层向旧层逐层检查,一旦某层返回“可能存在”即停止。
    • 扩容:当当前层达到容量阈值时,新建一个更大的层(如容量翻倍)。
  • 优点
    • 无需重新哈希旧数据。
    • 查询延迟可控(通常只需查最新几层)。
  • 缺点:空间利用率低(旧层可能稀疏)。
  • 适用场景:数据量逐步增长且容忍一定空间冗余的场景(如日志去重)。

方案2:可扩展布隆过滤器(Scalable Bloom Filter)
可扩展布隆过滤器(Scalable Bloom Filter) 是一种可以根据数据量的增长动态扩展存储空间并控制误判率的布隆过滤器。与传统的固定大小的布隆过滤器不同,可扩展布隆过滤器在数据集增加时可以自动创建新的布隆过滤器,并调整存储容量和哈希函数的数量,从而保持较低的误判率,并逐步适应数据量的增加。

  • 每个布隆过滤器的误判率控制:在设计时,可扩展布隆过滤器会考虑每个布隆过滤器的误判率,并通过增加位数组的大小来控制误判率。例如,初始布隆过滤器可能会有一定的误判率,随着新过滤器的加入,整体的误判率会降低。
  • 哈希函数的调整:每次扩展布隆过滤器时,哈希函数的数量和类型也可能会发生变化。新的布隆过滤器可能使用不同数量的哈希函数,来进一步减少哈希碰撞。
  • 元素的插入:当新元素插入时,布隆过滤器会先检查当前的布隆过滤器。如果当前布隆过滤器已满或误判率达到阈值,则会将元素插入下一个更大的布隆过滤器。

方案3:级联布隆过滤器
设计目标是 在数据增长时动态扩容,并通过多个布隆过滤器实现渐进式的扩展。使用多个布隆过滤器链式连接,每个布隆过滤器承担不同的数据量。每当某个布隆过滤器达到其容量极限时,新的元素就会被插入到下一个布隆过滤器。

方案4:并行布隆过滤器

  • 可以维护多个独立的布隆过滤器,随着数据增长,当一个过滤器填满后,新加入的数据放入新的布隆过滤器中。
  • 查询时,需要对所有布隆过滤器进行查询,只有当所有的过滤器都表明元素可能不存在时,才能确定元素肯定不在集合中。

3. 优缺点

3.1 优点

  • 空间效率极高:存储海量数据时占用内存远小于哈希表。
  • 查询速度快:插入和查询的时间复杂度均为 O(k),与数据量无关。
  • 保密性:存储的是哈希值而非原始数据,适合敏感数据场景。

3.2 缺点

  • 存在误判率:无法保证100%准确性。

误判的根本原因在于位共享,多个不同的元素可能会被哈希到同一个位置(即哈希碰撞)。因此,即使某个元素并未被添加到布隆过滤器中,也有可能由于哈希碰撞导致查询时返回“可能存在”的结果。这就是布隆过滤器的误判(假阳性)问题。
哈希碰撞的发生是不可避免的,因为布隆过滤器使用有限大小的位数组来存储信息,而哈希函数将大量不同的元素映射到这个有限的空间中,可能会导致不同元素的哈希值映射到相同的位置,这就造成了误判。

例如
元素A的哈希位为1、3、5。
元素B的哈希位为3、7、9。
位3被AB共享。

在这里插入图片描述

  • 无法删除元素:经典布隆过滤器不支持删除(需使用变体如Counting Bloom Filter)。

布隆过滤器的位数组是共享的,多个元素可能会在相同的位置上被设置为1,因此在删除时,无法确定某个具体元素的哈希值映射到的位是否仅仅属于该元素,这就会导致删除操作无法正确执行,影响其他元素的查询。
解决方案Counting Bloom Filter。将位数组中的每个二进制位替换为计数器(如4-bit计数器)。插入元素时,计数器递增;删除元素时,计数器递减。

代价:
空间占用增加(例如4-bit计数器使空间扩大4倍),且计数器溢出可能导致误删。

上图中,若直接删除A(将位1、3、5置0),会导致B的哈希位3被错误清除,后续查询B时会被误判为不存在。

  • 哈希函数依赖:性能高度依赖哈希函数的质量和数量。

4. 使用场景

4.1 适用场景

  • 缓存系统:快速判断请求数据是否在缓存中,避免查询数据库。
  • 防止重复推荐:判断用户是否已经看过某内容。
  • 爬虫去重:判断URL是否已被爬取。
  • 垃圾邮件过滤:快速判断邮件地址是否为垃圾邮件发送者。
  • 分布式系统:如HBase、Cassandra中用布隆过滤器减少磁盘查找。

4.2 不适用场景

  • 要求零误判:如金融交易验证。
  • 需要删除元素:需改用其他变体结构。

5. 手写布隆过滤器

目前 MurmurHash 函数作为布隆过滤器的 hash 函数是使用得比较多的,所以以下内容也会采用这种函数。MurmurHash 是一种高效且具有良好分布性质的哈希函数,通常用于哈希表、布隆过滤器等场景。它的性能较好,且碰撞较少。
GuavaGoogle 提供的一个 Java 开源库,包含了许多常用的工具类和数据结构,包括 集合框架、缓存、并发工具、哈希算法 等,其中就包括了 布隆过滤器(BloomFilter)的实现。可以使用其中的 Hashing.murmur3_128() 方法来创建 MurmurHash 实例。

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>33.0.0-jre</version>
</dependency>
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import com.google.common.hash.Funnels;import java.nio.charset.Charset;
import java.util.BitSet;
import java.util.function.Function;public class SimpleBloomFilter<T> {private final BitSet bitSet;      // 位数组private final int bitSetSize;     // 位数组的大小private final int numHashes;      // 哈希函数的数量private final HashFunction[] hashFunctions; // 哈希函数// 构造函数,初始化布隆过滤器public SimpleBloomFilter(int expectedElements, double falsePositiveRate) {// 计算位数组的大小this.bitSetSize = optimalBitSetSize(expectedElements, falsePositiveRate);this.numHashes = optimalNumHashes(expectedElements, bitSetSize);this.bitSet = new BitSet(bitSetSize);this.hashFunctions = createHashFunctions(numHashes);}// 向布隆过滤器添加元素public void add(T element) {for (HashFunction hashFunction : hashFunctions) {int hash = hashFunction.newHasher().putObject(element, Funnels.stringFunnel(Charset.defaultCharset())).hash().asInt();int bitIndex = Math.abs(hash % bitSetSize);  // 将哈希值映射到位数组的索引位置bitSet.set(bitIndex);  // 将该位置设置为1}}// 检查元素是否可能在布隆过滤器中public boolean mightContain(T element) {for (HashFunction hashFunction : hashFunctions) {int hash = hashFunction.newHasher().putObject(element, Funnels.stringFunnel(Charset.defaultCharset())).hash().asInt();int bitIndex = Math.abs(hash % bitSetSize);  // 将哈希值映射到位数组的索引位置if (!bitSet.get(bitIndex)) {return false;  // 如果某个位置是0,说明该元素一定不在布隆过滤器中}}return true;  // 否则,返回可能存在}// 计算最佳的位数组大小private static int optimalBitSetSize(int expectedElements, double falsePositiveRate) {return (int) Math.ceil((expectedElements * Math.log(falsePositiveRate)) / Math.log(1.0 / Math.pow(2, Math.log(2))));}// 计算需要的哈希函数数量private static int optimalNumHashes(int expectedElements, int bitSetSize) {return (int) Math.round((bitSetSize / expectedElements) * Math.log(2));}// 创建多个哈希函数private HashFunction[] createHashFunctions(int numHashes) {HashFunction[] functions = new HashFunction[numHashes];for (int i = 0; i < numHashes; i++) {// 使用不同的盐值(即种子值)来生成不同的哈希函数functions[i] = Hashing.murmur3_128(i);  // 使用 MurmurHash 作为基础}return functions;}// 测试布隆过滤器public static void main(String[] args) {// 创建一个预计存储 1000 个元素,误判率为 0.01 的布隆过滤器SimpleBloomFilter<String> bloomFilter = new SimpleBloomFilter<>(1000, 0.01);// 向布隆过滤器添加元素bloomFilter.add("apple");bloomFilter.add("banana");bloomFilter.add("orange");// 测试是否包含元素System.out.println(bloomFilter.mightContain("apple"));  // trueSystem.out.println(bloomFilter.mightContain("banana")); // trueSystem.out.println(bloomFilter.mightContain("orange")); // trueSystem.out.println(bloomFilter.mightContain("grape"));  // false}
}

输出:
在这里插入图片描述

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Build错误:Cannot determine build data storage root for project 和 无法加载主类的解决办法的经验分享

Build错误&#xff1a;Cannot determine build data storage root for project 解决方案与经验分享 1. 引言 查看错误信息 “Cannot determine build data storage root for project”的含义&#xff1a; 这是一个关于构建项目时遇到的常见错误。错误信息表明构建工具无法确定…

2025年02月26日Github流行趋势

项目名称&#xff1a;aibrix 项目地址url&#xff1a;https://github.com/vllm-project/aibrix项目语言&#xff1a;Jupyter Notebook历史star数&#xff1a;2234今日star数&#xff1a;881项目维护者&#xff1a;Jeffwan, varungup90, brosoul, nwangfw, kr11项目简介&#xf…

理解大模型的量化

1. 什么是量化 量化是大模型领域中的一项关键技术&#xff0c;它通过降低模型参数的精度&#xff0c;将浮点数转换为整数或者定点数&#xff0c;从而实现模型的压缩和优化。 这样做的目的主要是减少模型的存储需求、加快推理速度&#xff0c;并且降低模型的计算复杂度&#xf…

构建逻辑思维链(CoT)为金融AI消除幻觉(保险理赔篇)

在上一篇文章中&#xff0c;我们介绍了如何利用亚马逊云科技的Amazon Bedrock GuardRails自动推理检查为金融行业的AI应用提升准确性&#xff0c;消除幻觉。在本案例中&#xff0c;我们将探讨一个利用AI副主保险公司评估长期护理保险理赔审核的场景。 自动推理检查配置 在本方…

上传securecmd失败

上传securecmd失败 问题描述&#xff1a;KES V8R6部署工具中&#xff0c;节点管理里新建节点下一步提示上传securecmd失败&#xff0c;如下&#xff1a; 解决办法&#xff1a; [rootlocalhost ~]# yum install -y unzip 上传的过程中会解压&#xff0c;如果未安装unzip依赖包…

蓝桥杯 5.字符串

蓝桥杯 5.字符串 文章目录 蓝桥杯 5.字符串KMP&字符串哈希Manacher编程138-148字典树基础01Trie编程149-155 KMP&字符串哈希 KMP算法 字符串匹配算法, 用于匹配**模式串P(短)和文本串S(长)**中出现的所有位置, 例如, S “ababac”, P “aba”, 那么出现的所有位置就…

TEMU标签超简单制作方法,三步快速合成TEMU标签

这个标签编辑工具使用方法很简单&#xff0c;零基础小白也能合成TEMU标签/跨境合规标签。 第一步&#xff1a;选择一个符合需求的标签 这个工具提供了非常多的标签模板&#xff0c;选择一个自己编辑即可。 第二步&#xff1a;编辑标签内容 提供了超多自定义编辑功能&…

ChatGPT入驻Safari,AI搜索时代加速到来

2月25日&#xff0c;人工智能领域巨头OpenAI宣布了一项重磅更新&#xff1a;为其广受欢迎的ChatGPT应用新增Safari浏览器扩展功能&#xff0c;并支持用户将ChatGPT设置为Safari地址栏的默认搜索引擎。这一举措标志着OpenAI在将ChatGPT整合进用户日常网络浏览体验方面迈出了重要…

auto.js例子之WebView多页面浏览器

"ui";ui.layout(<vertical><horizontal id"webs" layout_weight"1"></horizontal><button id"one" text"第一个" /><button id"two" text"第二个" /><button id"…

创建虚拟环境的方法

虚拟环境 python解释器 第三方包&#xff1b; 在系统中&#xff0c;一个虚拟环境就是一个文件夹&#xff0c;改动文件夹名字不行&#xff0c;因为已经写入了部分脚本中&#xff0c;如activate等启动程序中&#xff1b; Virtualenv 安装&#xff1a;pip install virtualenv…

SQL注入(order by,limit),seacms的报错注入以及系统库的绕过

一、若information_schema被过滤了&#xff0c;应该如何绕过 简介&#xff1a; information_schema 是一个非常重要的系统数据库&#xff0c;它在SQL标准中定义&#xff0c;并且被许多关系型数据库管理系统&#xff08;RDBMS&#xff09;如MySQL、PostgreSQL等支持。这个库提供…

HAL库串口发送函数 加 接收函数

数据类型 一个字节8个比特位&#xff0c;串口发送函数的第三个参数&#xff0c;写入的是数据的数量&#xff0c;以字节为单位。 ​/* exact-width signed integer types */ typedef signed char int8_t; typedef signed short int int16_t; typedef signed…

Linux:进程信号(二.信号的保存与处理、递达、volatile关键字、SIGCHLD信号)

目录 1.信号保存 1.1递达、未决、阻塞等概念 1.2再次理解信号产生与保存 1.3信号集操作函数 sigset_t类型 sigemptyset() 函数 sigismember()函数 sigaddset ()函数 sigdelset() 函数 sigprocmask()系统调用 sigpending()系统调用 2.信号的处理/递达 2.1信号处理时…

【JavaEE】SpringMVC获取HTTP中的元素

目录 一、获取URL中的参数PathVariable二、上传⽂件RequestPart三、获取Cookie/Session3.1 HttpServletRequest和 HttpServletResponse3.2 获取Cookie3.2.1 使用HttpServletRequest3.2.2 使用注解CookieValue 3.3 设置session3.4 获取session3.4.1 使用HttpServletRequest3.4.2…

React低代码项目:用户登陆

吐司问卷&#xff1a;用户登陆 Date: February 17, 2025 4:12 PM (GMT8) JWT **概念&#xff1a;**登陆成功后&#xff0c;服务端返回一个 token JWT组成&#xff1a; JWT 由三个部分组成&#xff1a;头部&#xff08;Header&#xff09;、载荷&#xff08;Payload&#xf…

集合与反射

一、集合体系 集合一共分为两部分&#xff1a;Collection&#xff08;单列集合&#xff09;每个元素&#xff08;数据&#xff09;只包含一个值。 Map&#xff08;双列集合&#xff09;每个元素包含两个值&#xff08;键值对&#xff09;。 二、ArrayList和LinkedList的区别 数…

ubuntu:桌面版磁盘合并扩容

下载gparted磁盘编辑器 apt-get install gparted 打开gparted 更改目标分区大小 当遇到这个报错时&#xff0c;需要在命令行执行原分区的挂载指令 查看该分区信息 记住该目录&#xff0c;并在命令行执行 mount -o remount -rw /# 示例&#xff1a;mount -o remount -rw /v…

全国各省山峰分布SHP数据详解及其在科学研究与旅游规划中的应用

一、引言 在中国这片广袤无垠的土地上&#xff0c;山峰作为自然界的壮丽景观&#xff0c;不仅构成了大地的骨架&#xff0c;更承载着丰富的自然资源和深厚的文化底蕴。 全国各省山峰分布SHP数据&#xff0c;作为一种地理信息系统&#xff08;GIS&#xff09;中的矢量数据格式…

向量数据库milvus部署

官方文档 Milvus vector database documentationRun Milvus in Docker (Linux) | Milvus DocumentationMilvus vector database documentation 按部署比较简单&#xff0c;这里说一下遇到的问题 一&#xff1a;Docker Compose 方式部署 1、镜像无法拉取,(docker.io被禁) …

Java 基础面试题

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…