C++修炼：位图和布隆过滤器

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》

1、引言       

        在计算机科学中，位图（Bitmap）和布隆过滤器（Bloom Filter）是两种高效的数据结构，广泛应用于海量数据处理、缓存系统、网络路由、垃圾邮件过滤等场景。它们能以极小的空间代价实现快速查询，但各自有不同的特点和适用场景。

本文将详细介绍：

  1. 位图（Bitmap）的原理及C++实现

  2. 布隆过滤器（Bloom Filter）的原理及C++实现

  3. 两者的对比及适用场景

2、位图 

         2.1、什么是位图

        首先大家想这样一个问题，现在给你40亿个无符号整数，怎么快速地判断某一个数是否存在？

        思路一：unordered_set存储。

        在不考虑效率的情况下，我们首先想一个问题，unordered_set能否存储下40亿个数据？

        我们开辟一个unordered_set对象，然后输出他的理论最大值：

#include<iostream>
#include<unordered_set>
using namespace std;unordered_set<size_t> s;
int main()
{cout << s.max_size() << endl;return 0;
}

        这个理论最大值和系统有关： 

(1) 32 位系统

  • 指针大小：4 字节（32 bit）

  • 最大地址空间：232=4,294,967,296232=4,294,967,296（约 4GB）

    • 这是 CPU 能寻址的内存上限，即使物理内存更大，单个进程也无法直接使用超过此限制。

  • unordered_set::max_size()：

    • 通常返回 232−1232−1（约 43 亿），因为 STL 容器的最大容量受限于地址空间。

(2) 64 位系统

  • 指针大小：8字节（64 bit）

  • 最大地址空间：264=18,446,744,073,709,551,616264=18,446,744,073,709,551,616（约 16EB，1EB = 10亿GB）

    • 理论上是天文数字，实际受操作系统和硬件限制（如 x86-64 通常用 48 bit 地址，最大 256TB）

  • unordered_set::max_size()：

    • 通常返回 264−1264−1（约 1.8×10191.8×1019），因为地址空间足够大。

        看似能容下40亿个数据，但是现实情况中真的能存储这么多吗？

        首先我们要知道，哈希表中存储的无符号整数类型大约占32到64字节，尽管元素本身只占4个字节，但是我们要存储在哈希表中，每个节点还得包含指向下一个节点的指针。再受内存对齐规则，缓存的哈希值，分配器额外开销的影响，这就导致每个无符号整数会占到32到64字节。再加上我们实际电脑内存首先，假设你的电脑有64g内存，那他最多也只能存储1到2亿个数。这可是远远不够的。

        思路二：暴力枚举

        这个思路就更不可能了，因为时间复杂度太高，肯定满足不了需求。

        思路三：排序加二分

        这个思路看似可以，但是也是受内存限制。我们想要存储40亿个数据，那么我们需要开辟的数组大小需要14.90G(大约),受内存限制，假设电脑为16G(当下主流的电脑内存大小)，我们光开机系统就已经占用的我们的内存至少%20，那么怎么可能开出来这么大的数组呢？那我们拿个大点的电脑来，64G的，就算他能存下，那么我现在说他能存下400亿个数据吗？这肯定是不可能的。那么有没有一种办法，能够更高效的，不需要大内存空间解决这个问题呢？

        接下来介绍我们的主角：位图。        

        位图（Bitmap），也称为位集合（Bitset），是一种利用二进制位（bit）来高效存储和操作数据的数据结构。它的核心思想是：

  • 每个 bit 表示一个数字是否存在（0 = 不存在，1 = 存在）。

  • 适用于海量无重复整数的存储和查询（如去重、排序、快速查找）。

         在位图中，我们每一位就能代表一个数字，如果这一位为1，那么说明这个数字存在，如果为0，就说明这个数字不存在。但是需要注意的是，位图只能存储整数。

        2.2、位图的模拟实现

        相比于之前的红黑树，哈希表，位图就简单的多了。

template<size_t N>
class bitset
{
public:bitset(){_bs.resize(N / 32 + 1);//开空间//对于小数，我们要存在下一个int中，所以+1，至于整数，我们为了统一就都+1就可以了，这样最多只浪费了一个int//也可以这样理解，这样开空间是第一个int下标为1，可以让他这样对应上。//每一位标记一个数，我们插入N个数据，需要N位，一个int类型有32（4*8）位，所以说得N/32}//插入void set(size_t x){size_t i = x / 32;//确定存在那个int中size_t j = x % 32;//确定存在哪一位_bs[i] |= (1 << j);//x映射改成1}//删除void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}
private:std::vector<int> _bs;
};

        核心操作只有三个，插入，删除，判断。

        插入操作首先计算这个数应该存放在哪一个区块中，然后把这个数模32，确定他存在哪一位，接着通过二进制运算把他存下来。

        删除操作也是先判断删除的数存在哪一位，在通过二进制操作把他改为0。

        查找操作也是同理。

        现在解决上面的问题就很简单了。开辟空间时我们直接传入-1，开辟出来42亿九千万（约等于）个数据，然后对于给定的四十亿个数据进行set就行了。

        传-1是因为size_t类型的参数传-1实际上值就成了（1LL<<32-1），也就是三十二位全是1。这个值我们经常使用。

        2.3、C++库中的位图

        在C++库中也有一份位图，库中的位图实现的功能更多一些，但是总体来说主要的还是上面这三个。

        但是库里面的位图有一个小bug。就是我们开辟空间时不能传-1，如果传-1程序会崩掉。

#include<iostream>
#include<bitset>
using namespace std;
const int INF = (1LL << 32) - 1;
bitset<INF> s;//如果传-1会在运行是崩掉
int main()
{	for (int i = 1;i <= 10000;i++){s.set(i);}cout<<s.test(100)<<endl;return 0;
}

        2.4、twobitset

        现在看这样一个问题：⼀个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数。

        如果只有一个位图，我们只能判断他在不在。如果想要记录次数的话我们需要多个位图。

        由于他这里次数不超过2，我们使用两个位图，来模拟二进制数就可以了。我们可以通过两个位图记录0,1,10,11这四个数。

template<size_t N>
class twobitset
{//标记出现次数为0,1,2,3
public:void set(size_t x){//检测之前出现的次数并对他进行++bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){_bs2.set(x);}else if (!bit1 && bit2){_bs1.set(x);}else if (bit1 && !bit2){_bs1.set(x);//重新set一次也没事_bs1.set(x);}}//返回数字int get_count(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){return 0;}else if (!bit1 && bit2){return 1;}else if (bit1 && !bit2){return 2;}else if (bit1 && bit2){return 3;}}
private:bitset<N> _bs1;bitset<N> _bs2;
};

 测试代码：

void test_twobitset()
{twobitset<100> tbs;//100为我们要存入的数字的最大值int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}for (size_t i = 0; i < 100; ++i){//cout << i << "->" << tbs.get_count(i) << endl;if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2){cout << i << " ";}}
}void test_bitset1()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bitset<100> bs1;bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i)){cout << i << " ";}}
}

3、布隆过滤器

        倘若我们想要判断是否存在的数据不是整形，那么位图就不适用了，我们有没有什么办法来快速判断在大量数据中某一个特定的数据是否存在呢？

      3.1、什么是布隆过滤器

        布隆过滤器（Bloom Filter）是由 Burton Howard Bloom 在 1970 年提出的一种概率型数据结构，用于高效判断某个元素是否存在于集合中。它的特点是：

  • 空间效率极高（比哈希表更省内存）。

  • 查询速度极快（时间复杂度 O(k)，k 为哈希函数数量）。

  • 存在一定的误判率（可能误判“存在”，但不会误判“不存在”）。

       也就是说，布隆过滤器如果判断一个元素存在，那么这个判断可能不准确，但是如果判断某个元素不存在，这个元素是一定不存在的，也就是判断是准确的。那么为什么布隆过滤器会有这样的缺点呢？

        布隆过滤器的工作原理是把一个数据，通过多个不同的哈希函数，映射到位图中。

 

        那么假设我们存储了图中两个值，假如现在来了第三个元素，我们想要检测第三个元素在不在，这第三个元素映射的三个值恰好和已经存在的两个值有重合，那么此时的判断就成了存在，固然是不准确的。

         并且这种哈希冲突是无法解决的，我们只能通过合理使用哈希函数，尽可能降低哈希冲突。

        3.2、布隆过滤器的误导率

                这部分内容有几个公式，至于这些公式怎么推出来的大家如果感兴趣的话可以自己搜索一下，公式的推导对数学功底有一定要求。

        布隆过滤器的误判率：

        在k一定的情况下，当n增加时，误判率增加，m增加时，误判率减少。

        当    时，误判率最低。

        期望的误判率p和插入数据个数n确定的情况下，再把上面的公式带入误判率公式可以得到，通过期望的误判率和插入数据个数n得到bit长度：

        3.3、布隆过滤器的代码实现

        我们选取三个比较权威的哈希函数来实现布隆过滤器。需要注意的是我们实现布隆过滤器用的是上面我们自己实现的位图，不是库里的。

#pragma once
#include"BitSet.h"
#include<string>
struct HashFuncBKDR
{// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》// 一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子为31。size_t operator()(const std::string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};struct HashFuncAP
{// 由Arash Partow发明的一种hash算法。  size_t operator()(const std::string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶数位字符{hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));}else              // 奇数位字符{hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}}return hash;}
};struct HashFuncDJB
{// 由Daniel J. Bernstein教授发明的一种hash算法。 size_t operator()(const std::string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};template<size_t N,size_t X=6,class K=std::string,class Hash1=HashFuncBKDR,class Hash2=HashFuncAP,class Hash3=HashFuncDJB>
class BloomFilter
{
public://插入void Set(const K& key){//调用临时对象的()size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;//通过三种映射方式映射出三个值，然后set到图里面_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (!_bs.test(hash1)){return false;}size_t hash2 = Hash2()(key) % M;if (!_bs.test(hash2)){return false;}size_t hash3 = Hash3()(key) % M;if (!_bs.test(hash3)){return false;}return true;}double getFalseProbability(){//套公式计算冲突率double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);return p;}private:static const size_t M = N * X;bitset<M> _bs;
};void TestBloomFilter2()
{//如果插入长的字符，在检测这个字符的子串，可能会误判srand(time(0));const size_t N = 1000000;BloomFilter<N> bf;//BloomFilter<N, 3> bf;//BloomFilter<N, 10> bf;std::vector<std::string> v1;std::string url = "猪八戒";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.Set(str);}// v2跟v1是相似字符串集（前缀一样），但是后缀不一样v1.clear();for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999999 + i);v1.push_back(urlstr);}size_t n2 = 0;for (auto& str : v1){if (bf.Test(str)) // 误判{++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集  前缀后缀都不一样v1.clear();for (size_t i = 0; i < N; ++i){//string url = "zhihu.com";string url = "孙悟空";url += std::to_string(i + rand());v1.push_back(url);}size_t n3 = 0;for (auto& str : v1){if (bf.Test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}

        通过测试代码可以打得出我们的理论误判率和实际误判率是非常接近的。

        默认的布隆过滤器不支持删除。因为在两个元素映射的值有冲突的情况下，删除一个元素就会影响另一个元素。

 3.4、布隆过滤器的应用场景

        布隆过滤器有很多应用场景，我们简单说两个。首先是数据库查询优化。我们可以通过数据库，优化磁盘查询时间。在查询前先用布隆过滤器判断数据是否可能存在于磁盘，若过滤器返回“不存在”，则直接跳过磁盘访问。

        另外布隆过滤器可以做缓存穿透防护。当有人恶意请求大量不存在的 key时，会导致缓存失效，直接冲击数据库。我们可以用布隆过滤器把所有合法的key存储起来，请求key时，现在布隆过滤器中判断此key是否存在。

        布隆过滤器还有很多使用场景，不一一列举了，感兴趣的可以自己搜索一下：

场景核心需求为什么用布隆过滤器？
数据库查询优化减少磁盘 IO快速过滤不可能存在的 key
缓存穿透防护防止恶意请求击穿数据库内存高效，查询速度快
爬虫 URL 去重避免重复抓取节省内存，比哈希表更省空间
垃圾邮件过滤快速拦截已知垃圾邮件比传统黑名单更高效
大数据去重流式数据去重低内存占用，适合高吞吐场景
CDN 边缘缓存减少回源查询快速判断内容是否在中心服务器

        好了，今天的内容就分享到这，我们下期再见！

 

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

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

相关文章

Java大厂后端技术栈故障排查实战：Spring Boot、Redis、Kafka、JVM典型问题与解决方案

Java大厂后端技术栈故障排查实战：Spring Boot、Redis、Kafka、JVM典型问题与解决方案

Java大厂后端技术栈故障排查实战&#xff1a;Spring Boot、Redis、Kafka、JVM典型问题与解决方案 引言 在互联网大厂&#xff0c;Java后端系统往往承载着高并发、高可用和复杂业务需求。系统架构日益复杂&#xff0c;涵盖微服务、缓存、消息队列、数据库等多种组件&#xff0…
阅读更多...
交叉编译tcpdump工具

交叉编译tcpdump工具

1.导出交叉编译工具链 export PATH$PATH:/opt/rockchip/gcc-linaro-6.3.1-2017.05-x86_64_arm-linux-gnueabihf/bin 下载源码包libpcap-1.10.5&#xff0c;配置、并编译安装。 github仓库地址 ./configure --hostarm-linux CCarm-linux-gnueabihf-gcc --prefix$PWD/install …
阅读更多...
Pytest Fixture 是什么？

Pytest Fixture 是什么？

Fixture 是什么&#xff1f; Fixture 是 Pytest 测试框架的核心功能之一&#xff0c;用于为测试函数提供所需的依赖资源或环境。它的核心目标是&#xff1a; ✅ 提供测试数据&#xff08;如模拟对象、数据库记录&#xff09; ✅ 初始化系统状态&#xff08;如配置、临时文件&a…
阅读更多...
【深度剖析】流处理系统性能优化：解决维表JOIN、数据倾斜与数据膨胀问题

【深度剖析】流处理系统性能优化：解决维表JOIN、数据倾斜与数据膨胀问题

目录 前言：为什么你的流处理作业总是慢？ 一、维表JOIN优化：从普通连接到高性能查询 1.1 时态表的双面性 1.2 Lookup Join 优化 1.3 多表JOIN优化策略 二、数据倾斜：单分区也会遇到的隐形杀手 2.1 单分区数据倾斜 2.2 热点键打散技术 2.3 时间窗口预聚合 三、数据…
阅读更多...
Codeforces Round 1028 (Div. 2)（ABC）

Codeforces Round 1028 (Div. 2)（ABC）

A. Gellyfish and Tricolor Pansy 翻译&#xff1a; 水母和小花在玩一个叫 “决斗 ”的游戏。 水母有 a HP&#xff0c;花花有 b HP。 它们各有一个骑士。水母的骑士有 c HP&#xff0c;而花花的骑士有 d HP。 他们将进行一轮游戏&#xff0c;直到其中一方获胜。对于 k1、2、.…
阅读更多...
数字创新智慧园区建设及运维方案

数字创新智慧园区建设及运维方案

该文档是 “数字创新智慧园区” 建设及运维方案，指出传统产业园区存在管理粗放等问题，“数字创新园区” 通过大数据、AI、物联网、云计算等数字化技术，旨在提升园区产业服务、运营管理水平，增强竞争力，实现绿色节能、高效管理等目标。建设内容包括智能设施、核心支撑平台、…
阅读更多...
缓存一致性协议的影响

缓存一致性协议的影响

在操作系统中&#xff0c;线程切换相比进程切换更轻量级的关键原因之一是 缓存&#xff08;Cache&#xff09;的有效性&#xff0c;尤其是对 CPU 缓存&#xff08;如 L1/L2/L3&#xff09;和 TLB&#xff08;Translation Lookaside Buffer&#xff09;的影响。以下从缓存角度详…
阅读更多...
六月一日python-AI代码

六月一日python-AI代码

python 运行 import turtle as t # 导入turtle库并简称为t&#xff0c;用于图形绘制 import random # 导入random库&#xff0c;用于随机数生成t.delay(0) # 设置绘图延迟为0&#xff0c;加快绘图速度 colors ["red", "blue", "gr…
阅读更多...
58、辣椒种植学习

58、辣椒种植学习

辣椒&#xff08;学名&#xff1a;Capsicum annuum&#xff09;属于茄科辣椒属&#xff0c;是一种重要的蔬菜兼调味作物&#xff0c;具有较高的经济价值和营养价值。其果实富含维生素C、辣椒素等成分&#xff0c;既可鲜食&#xff0c;也可加工成干辣椒、辣椒粉、辣椒酱等产品&a…
阅读更多...
C语言进阶--程序的编译（预处理动作）+链接

C语言进阶--程序的编译（预处理动作）+链接

1.程序的翻译环境和执行环境 在ANSI C标准的任何一种实现中&#xff0c;存在两种不同的环境。 第一种是翻译环境&#xff1a;将源代码转换为可执行的机器指令&#xff08;0/1&#xff09;; 第二种是执行环境&#xff1a;用于实际执行代码。 2.详解编译链接 2.1翻译环境 程…
阅读更多...
微调大模型：什么时候该做，什么时候不该做？

微调大模型：什么时候该做，什么时候不该做？

目录 一、什么是“微调”&#xff1f;你真的需要它吗&#xff1f; 二、什么时候不该微调&#xff1f; &#x1f6ab; 不该微调的 5 个典型场景&#xff1a; 1. 通用问答、闲聊、常识类内容 2. 企业内部问答 / 文档助手 3. 想要通过微调“学会格式” 4. 没有大量高质量标…
阅读更多...
微深节能 码头装卸船机定位与控制系统 格雷母线

微深节能 码头装卸船机定位与控制系统 格雷母线

微深节能码头装卸船机定位与控制系统&#xff1a;格雷母线技术赋能港口作业智能化升级 在现代化港口散货装卸作业中&#xff0c;装卸船机是连接船舶与陆域运输的核心枢纽设备。传统装卸船机依赖人工操作&#xff0c;存在定位偏差大、动态协同难、安全风险高等痛点。微深节能基于…
阅读更多...
如何检查popover气泡组件样式？调试悬停元素CSS样式的解决方案

如何检查popover气泡组件样式？调试悬停元素CSS样式的解决方案

1. 问题 当我们要检查这种弹出层的CSS样式时&#xff0c;会发现特别棘手&#xff0c;因为鼠标移走就消失了。如果是display:none控制的&#xff0c;可能还能找到&#xff0c;如果是用js通过v-if控制的&#xff0c;就无法调试了。 2. 解决方案 使用 setTimeout debugger 就…
阅读更多...
网络攻防技术一：绪论

网络攻防技术一：绪论

文章目录 一、网络空间CyberSpace1、定义2、基本四要素 二、网络空间安全1、定义2、保护对象3、安全属性4、作用空间 三、网络攻击1、攻击分类2、攻击过程 四、网络防护1、定义2、安全模型3、安全服务5类4、特定安全机制8种5、普遍性安全机制5种 五、网络安全技术发展简史1、第…
阅读更多...
彻底理解Spring三级缓存机制

彻底理解Spring三级缓存机制

文章目录 前言一、Spring解决循环依赖时&#xff0c;为什么要使用三级缓存&#xff1f; 前言 Spring解决循环依赖的手段&#xff0c;是通过三级缓存&#xff1a; singletonObjects&#xff1a;存放所有生命周期完整的单例对象。&#xff08;一级缓存&#xff09;earlySingleto…
阅读更多...
【 SpringCloud | 微服务 网关 】

【 SpringCloud | 微服务 网关 】

单体架构时我们只需要完成一次用户登录、身份校验&#xff0c;就可以在所有业务中获取到用户信息。而微服务拆分后&#xff0c;每个微服务都独立部署&#xff0c;这就存在一些问题&#xff1a; 每个微服务都需要编写登录校验、用户信息获取的功能吗&#xff1f; 当微服务之间调…
阅读更多...
【前端面经】字节跳动一面

【前端面经】字节跳动一面

写在前面&#xff1a;面经只是记录博主遇到的题目。每题的答案在编写文档的时候已经有问过deepseek&#xff0c;它只是一种比较普世的答案&#xff0c;要学得深入还是靠自己 Q&#xff1a;三栏布局的实现方式&#xff08;圣杯模型&#xff09;如何实现 A&#xff1a; /* 整个 …
阅读更多...
ST-GCN

ST-GCN

1.bash 安装git 在目录下右键使用git bash打开 需要安装wgetbash download_model.sh&#xff0c;下载.sh文件 wget: command not found&#xff0c;Windows系统使用git命令 下载预训练权重_sh文件下载-CSDN博客 bash tools/get_models.sh 生成了三个.pt文件
阅读更多...
计算机网络全维度解析：架构协议、关键设备、安全机制与新兴技术深度融合

计算机网络全维度解析：架构协议、关键设备、安全机制与新兴技术深度融合

计算机网络作为当今数字化社会的基石&#xff0c;其复杂性和应用广泛性远超想象。本文将从基础架构、协议体系、关键设备、安全机制到新兴技术&#xff0c;进行全方位、深层次的解析&#xff0c;并辅以实际应用场景和案例分析。 一、网络架构与分类的深度剖析 1.1 网络分类的立…
阅读更多...
大语言模型的推理能力

大语言模型的推理能力

2025年&#xff0c;各种会推理的AI模型如雨后春笋般涌现&#xff0c;比如ChatGPT o1/o3/o4、DeepSeek r1、Gemini 2 Flash Thinking、Claude 3.7 Sonnet (Extended Thinking)。 对于工程上一些问题比如复杂的自然语言转sql&#xff0c;我们可能忍受模型的得到正确答案需要更多…
阅读更多...
最新文章

Copyright @ 2022~2023