位图与布隆过滤器深度剖析

位图与布隆过滤器深度剖析

目录

位图与布隆过滤器深度剖析

一、位图 (Bitmap)

二、布隆过滤器 (Bloom Filter)

三、 结合位图与布隆过滤器的最佳实践


在处理大数据和进行高性能查找时,传统的数据结构如数组、链表等可能无法满足效率和空间上的需求。位图和布隆过滤器是两种用于解决特定问题的数据结构,它们以空间换时间的策略在各种场景中展现出高效性。本文将详细分析这两种数据结构的原理、实现及最佳实践。

一、位图 (Bitmap)

 1. 定义与原理

位图是一种使用位数组来表示一个集合的数据结构。每个位代表集合中的一个元素,如果该位为0,则表示对应的元素不在集合中;如果为1,则表示元素在集合中。位图通常用于处理大量整数的集合,尤其是当这些整数在一个较小的范围内时,它可以节省大量的存储空间。

2. 应用场景

- 大数据集的去重操作
- 磁盘空间的分配
- 网络地址管理

3. 代码示例


#include <stdint.h>
#include <stdlib.h>

// 初始化位图
void bitmap_init(struct bitmap *bmp, int size) {
    bmp->size = size;
    bmp->bits = calloc(sizeof(uint8_t), (size + 7) / 8);
}

// 设置位图中的某个位
void bitmap_set(struct bitmap *bmp, int index) {
    int byte_index = index / 8;
    int bit_index = index % 8;
    bmp->bits[byte_index] |= 1 << bit_index;
}

// 清除位图中的某个位
void bitmap_clear(struct bitmap *bmp, int index) {
    int byte_index = index / 8;
    int bit_index = index % 8;
    bmp->bits[byte_index] &= ~(1 << bit_index);
}

// 检查位图中的某个位是否被设置
int bitmap_test(struct bitmap *bmp, int index) {
    return bmp->bits[index / 8] & (1 << (index % 8));
}

// 位图数据结构
struct bitmap {
    size_t size;
    uint8_t *bits;
};
```

 4. 性能与优化

位图的操作通常非常快,因为它们只涉及简单的位操作。但是,位图不支持随机访问,只能按位顺序访问。此外,位图的空间效率取决于集合的大小和整数的范围。

二、布隆过滤器 (Bloom Filter)

 1. 定义与原理

布隆过滤器是一种概率型数据结构,用于测试一个元素是否是集合的成员。它可能会产生假阳性(即错误地认为一个不存在的元素存在于集合中),但不会产生假阴性(即正确地识别不存在的元素)。布隆过滤器通过使用多个哈希函数对元素进行哈希并存储结果来实现这一点。

 2. 应用场景

- 大规模数据集的快速成员检测
- 垃圾邮件过滤
- 缓存穿透预防

3. 代码示例


import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_num):
        self.size = size
        self.hash_num = hash_num
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, string):
        for seed in range(self.hash_num):
            result = mmh3.hash(string, seed) % self.size
            self.bit_array[result] = 1

    def lookup(self, string):
        for seed in range(self.hash_num):
            result = mmh3.hash(string, seed) % self.size
            if self.bit_array[result] == 0:
                return "Nope"
        return "Probably"

# 初始化布隆过滤器
bf = BloomFilter(500000, 7)
# 添加元素
bf.add("test")
# 查询元素
print(bf.lookup("test"))  # 输出:Probably
print(bf.lookup("test2"))  # 输出:Nope
```

4. 性能与优化

布隆过滤器的性能取决于其大小、哈希函数的数量和质量。增加过滤器的大小可以减少假阳性的概率,但会增加内存消耗。增加哈希函数的数量也可以降低假阳性率,但会增加计算成本。选择合适的哈希函数对于减少冲突至关重要。

三、 结合位图与布隆过滤器的最佳实践

在实际应用中,位图和布隆过滤器可以结合使用以达到最佳的空间和时间效率。例如,在处理大量数据的去重问题时,可以先使用布隆过滤器快速判断元素是否可能存在于集合中,然后再使用位图进行精确的存储和查询。这种组合可以在保持低误报率的同时,有效地减少内存使用和提高查询速度。 

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

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

相关文章

如何使用Transformer-TTS语音合成模型

1、技术原理及架构图 ​ Transformer-TTS主要通过将Transformer模型与Tacotron2系统结合来实现文本到语音的转换。在这种结构中&#xff0c;原始的Transformer模型在输入阶段和输出阶段进行了适当的修改&#xff0c;以更好地处理语音数据。具体来说&#xff0c;Transformer-TT…

【Docker】新手教程的第一个demo:Wordpress

1 任务简单介绍 WordPress是什么&#xff1a; 是一个常用博客软件简单易部署&#xff0c;只需要两个容器&#xff08;业务容器 数据库容器&#xff09; 本文借鉴博客&#xff0c;使用自建 WordPress 容器方法在Docker上部署Wordpress&#xff0c;本地环境为Mac时使用该博客…

C语言leetcode刷题笔记2

C语言leetcode刷题笔记2 第4题&#xff1a;283.移动零互换直接移动 第5题&#xff1a;122.买卖股票的最佳时机‖递归&#xff08;超时&#xff09;动态规划贪心算法 第6题&#xff1a;49.字母异位词分组优化 第4题&#xff1a;283.移动零 给定一个数组 nums&#xff0c;编写一…

分布式事务Seata使用

我们要学习seata&#xff0c;首先需要具备如下技术储备&#xff1a; 数据库事务的基本知识&#xff1b;maven工具的使用&#xff1b;熟悉SpringCloudAlibaba技术栈&#xff1b;掌握SpringDataJPA简单使用&#xff1b; 一. Seata基本概念 1.seata是什么 Seata是阿里巴巴中间…

C++ 动态内存管理

例如&#xff1a;动态内存和释放单个数据的存储区 一 用new运算符初始化单个数据的存储区 举例

pytest + yaml 框架 - 参数化读取文件路径优化

针对小伙伴提出参数化时读取外部文件&#xff0c;在项目根路径运行没问题&#xff0c;但是进入到项目下子文件夹运行用例&#xff0c;就会找不到文件问题做了优化。 关于参数化读取外部文件相关内容参考前面这篇pytest yaml 框架 -25.参数化数据支持读取外部文件txt/csv/json/…

LeetCode 257. 二叉树的所有路径

LeetCode 257. 二叉树的所有路径 1、题目 题目链接&#xff1a;257. 二叉树的所有路径 给你一个二叉树的根节点 root &#xff0c;按 任意顺序 &#xff0c;返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root…

C++:内存管理

C:内存管理 一、C/C内存分布二、C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free三、C内存管理方式1.new/delete操作内置类型2.new和delete操作自定义类型 四、operator new与operator delete函数&#xff08;重点&#xff09;五、new和delete的实现原理1.内置…

Unity曲线插件Dreamteck Splines生成曲线Mesh

一、需求 脱离编辑器&#xff0c;运行时添加点&#xff0c;动态生成管道、线缆等曲线Mesh。 二、Dreamteck Splines简单运用 这方面资料不多&#xff0c;只有官方文档全英参考&#xff0c;而且又介绍得不详细。 2个重要组件介绍&#xff1a; SplineComputer&#xff1a; 最…

系统运维(虚拟化)

1.VLAN VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。 每个VLAN是一个广播域&#xff0c;VLAN内的主机间可以直接通信&#xff0c;而VLAN间则不能直接互通。这样&#xff0c;广播报…

987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果

解法&#xff1a; 一棵二叉树是完全二叉树的条件是&#xff1a; 对于任意一个结点&#xff0c;如果它有右子树而没有左子树&#xff0c;则这棵树不是完全二叉树。 如果一个结点有左子树但是没有右子树&#xff0c;则这个结点之后的所有结点都必须是叶子结点。 如果满足以上条…

1010: 折半查找的实现

解法&#xff1a; #include<iostream> #include<vector> using namespace std; void solve() {int n;cin >> n;vector<int> vec(n);for (int& x : vec) cin >> x;int x;cin >> x;int l 0, r n-1, cnt 0;while (l < r) {cnt;int…

Ubuntu22.04下安装kafka_2.12-2.6.0并运行简单实例

目录 一、版本信息 二、安装Kafka 1. 将Kafka安装包移到下载目录中 2. 安装Kafka并确保hadoop用户对Kafka目录有操作权限 三、启动Kafka并测试Kafka是否正常工作 1. 启动Kafka 2. 测试Kafka是否正常工作 一、版本信息 虚拟机产品&#xff1a;VMware Workstation 17 Pro…

一套C语言开发的 PACS影像系统源码 PACS系统的基本概念、系统业务流程

PACS系统基本概念 PACS&#xff0c;全称 Picture Archiving and Communication Systems&#xff0c;中文意为影像归档和通信系统。它是应用于医院影像科室的一种系统&#xff0c;主要任务是把日常产生的各种医学影像&#xff08;包括核磁&#xff0c;CT&#xff0c;超声&#…

Faststone Capture:高效屏幕捕获神器评测【AI写作】

首先&#xff0c;这篇文章是基于笔尖AI写作进行文章创作的&#xff0c;喜欢的宝子&#xff0c;也可以去体验下&#xff0c;解放双手&#xff0c;上班直接摸鱼~ 按照惯例&#xff0c;先介绍下这款笔尖AI写作&#xff0c;宝子也可以直接下滑跳过看正文~ 笔尖Ai写作&#xff1a;…

Java毕设之基于SpringBoot的在线拍卖系统

运行环境 开发语言:java 框架:springboot&#xff0c;vue JDK版本:JDK1.8 数据库:mysql5.7(推荐5.7&#xff0c;8.0也可以) 数据库工具:Navicat11 开发软件:idea/eclipse(推荐idea) 系统详细设计 管理员功能模块 管理员登录&#xff0c;管理员通过输入用户名、密码、角色等信…

AI日报:干翻AI PC!苹果M4芯片首发;GoEnhance可生成粘土风格视频;DeepSeek-V2模型已在魔搭社区开源

欢迎来到【AI日报】栏目!这里是你每天探索人工智能世界的指南&#xff0c;每天我们为你呈现AI领域的热点内容&#xff0c;聚焦开发者&#xff0c;助你洞悉技术趋势、了解创新AI产品应用。 新鲜AI产品点击了解&#xff1a;AIbase - 智能匹配最适合您的AI产品和网站 1、干翻AI …

Zip压缩归档库-libzip介绍

1.简介 libzip是一个C库&#xff0c;用于读取、创建和修改zip格式的压缩文件。它支持从zip文件中读取、写入、添加和删除文件&#xff0c;还支持密码保护的zip文件。libzip是跨平台的&#xff0c;可以在多种操作系统上使用&#xff0c;包括Linux、Windows和macOS。 常用接口介…

【Ping】Windows 网络延迟测试 ping 、telnet、tcping 工具

ping 命令 属于网络层的ICMP协议&#xff0c;只能检查 IP 的连通性或网络连接速度&#xff0c; 无法检测IP的端口状态。 telnet telnet命令&#xff0c;属于应用层的协议&#xff0c;用于远程登录&#xff0c;也可用于检测IP的端口状态。但是功能有限&#xff0c;只能检测一时…

【OpenHarmony 实战开发】 做一个 loading加载动画

本篇文章介绍了如何实现一个简单的 loading 加载动画&#xff0c;并且在文末提供了一个 demo 工程供读者下载学习。作为一个 OpenHarmony 南向开发者&#xff0c;接触北向应用开发并不多。北向开发 ArkUI 老是改来改去&#xff0c;对笔者这样的入门选手来说学习成本其实非常大&…
最新文章