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

【C++篇】位图与布隆过滤器

article 2025/2/4 15:50:54

目录

一，位图

1.1，位图的概念

1.2，位图的设计与实现

1.5，位图的应用举例

1.4，位图常用应用场景

 二，布隆过滤器

2.1，定义：

 2.2，布隆过滤器的实现

2.3， 应用场景

三，海量数据处理问题

3.1，10亿个整数求最大的前100个数

3.2，给两个文件，分别有100亿个query（查询字符串），我们只有1G内存，如何找到两个文件交集？

一，位图

1.1，位图的概念

位图是一种高效的数据结构，通过二进制位（0或1）的数组来高效存储和操作数据，常用于标记状态或处理大规模数据。

位图的优缺点：

优点：增删查改快，节省空间

缺点：只适用于整形

核心特性

  • 空间高效：每个元素仅占1 bit，适合处理海量数据（如去重、统计）。

  • 快速操作：支持位运算（与、或、异或等）进行高效查询和修改。

1.2，位图的设计与实现

位图本质是一个直接定址法的哈希表，每个整型值映射一个bit位。

 核心接口：

对于一个 整形值x。计算x对应的bit位：i=x/32，j=i%32，得到x在第i个整形的第j个bit位。

对于一个 整形值x。要将它放入到数据中，只需将x对应的bit位由0置为1。 

对于一个 整形值x，将它从数据中删除，只需将x对应的bit位由1置为0.

判断一个值x存不存在

代码：

//N空间大小，比特位
template<size_t N>
class bitset
{
public:
	bitset()
	{
		_bs.resize(N / 32 + 1);
	}
	//将x位置的bit值 置为1
	void set(const int& x)
	{
		//第i个整型的第j个bit位
		size_t i = x / 32;
		size_t j = x % 32;
		_bs[i] |= (1 << j);
	}
	//删除x位置
	//将x位置的bit值 置为0
	void reset(const int& x)
	{
		//第i个整型的第j个bit位
		size_t i = x / 32;
		size_t j = x % 32;
		_bs[i] &= (~(1 << j));
	}
	//判断x值在不在
	bool test(const int& x)
	{
		//第i个整型的第j个bit位
		size_t i = x / 32;
		size_t j = x % 32;
		return _bs[i] & (1 << j);
	}
private:
	std::vector<int> _bs;
};

1.5，位图的应用举例

(1) 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中。

40亿数据量太大，如果将40亿个int数据变量完全存储到内存中 可不得了，可以采用40亿个位来存储这些数据的状态。

首先遍历这40亿个数，在位图中将对应的位置为1，再对于给出的数，进行判断即可。

(2) 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

使用2个位图，每个数分配2个位图，用这两个位图来表示存储状态，00表示不存在，01表示出现一次，10表示多次，11无意义

代码示例：


    template<size_t N>
    class twobitset
    {
    public:
        //添加x
        void set(const int& x)
        {
            bool bit1 = bs1.test(x);
            bool bit2 = bs2.test(x);
            //出现0次->出现1次
            if (!bit1 && !bit2)//00->01
            {
                bs2.set(x);
            }
            //出现1次->出现2次
            else if (!bit1 && bit2)//01-> 10
            {
                bs1.set(x);
                bs2.reset(x);
            }
            //出现2次->出现多次
            else if (bit1 && !bit2)//10 ->11
            {
                bs2.set(x);
            }
        }
        //获取x的出现次数
        int getcount(const int& x)
        {
            bool bit1 = bs1.test(x);
            bool bit2 = bs2.test(x);

            if (!bit1 && !bit2)//00
            {
                return 0;
            }
            else if (!bit1 && bit2)//01
            {
                return 1;
            }
            else if (bit1 && !bit2)//10 
            {
                return 2;
            }
            else
            {
                return 3;
            }
        }
    private:
        bitset<N> bs1;
        bitset<N> bs2;
    };

1.4，位图常用应用场景

  • 去重与存在性检查：
    例如，统计10亿用户中哪些已注册，仅需约120MB内存（109÷8≈125MB109÷8≈125MB）。

  • 布隆过滤器（Bloom Filter）：
    利用多个哈希函数和位图实现概率型数据存在性判断。

  • 数据库索引：
    快速筛选满足条件的记录（如性别为“男”的用户）。

  • 内存管理：
    操作系统用位图标记内存页的分配状态。

 二，布隆过滤器

2.1，定义：

有一些场景，由大量数据需要判断是否存在，而这些数据不是整形，比如string，就不能使用位图了，这些场景就需要布隆过滤器来解决。利用多个哈希函数和位图实现，哈希函数内容见上篇文章【哈希表】。

 核心原理

  • 位数组（Bit Array）：长度为 m 的二进制数组，初始全为0。

  • 哈希函数集合：k个独立的哈希函数，每个函数将元素映射到位数组的某个位置。

以string类型为例：

而这种冲突是无法避免的，因为位图中只存储了状态，即0或1，无法改变。所以我们只能做到降低冲突概率，对于一个字符串，让它映射到多个位置上。经过k个哈希函数的转化，映射到k个位置，将这k位置都置为1。在查找时也是如此，经过k个哈希函数，k个位置都为1，才能说明该数据存在，否则就是与其他位置存在冲突，导致几个位置位1，几个位置为0，说明该数据不存在。

布隆过滤器优缺点：

 2.2，布隆过滤器的实现

下图中 ：

k代表哈希函数的个数

m为布隆过滤器的大小

n为插入的元素个数。

通过观察误判率的公式可得：在k一定的情况下，当n增加时，误判率增加，当m增加时，误判率越小。也就是哈希函数一定的情况下，插入元素越多时，误判率增加，布隆过滤器长度越长时，误判率减小。令X=m/n，可得，X越大，误判率越小。

//哈希函数
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;
	}
};

//布隆过滤器
//M布隆过滤器的长度
//N插入元素个数
//X=M/N 越大，误判率越小
template<size_t  N,size_t X=5,
	class k=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;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}
	//可能存在误判
	bool test(const k& key)
	{
		//只要一个位置为0，就不存在
		size_t hash1 = Hash1()(key) % M;
		if (_bs.test(hash1) == 0)
			return false;
		size_t hash2 = Hash2()(key) % M;
		if (_bs.test(hash2) == 0)
			return false;
		size_t hash3 = Hash3()(key) % M;
		if (_bs.test(hash3) == 0)
			return false;

		return true;
	}
private:
	static const int M = N * X;
	bitset<M> _bs;
};

2.3， 应用场景

  1. 缓存穿透防护：

        在分布式缓存系统中，布隆过滤器可以⽤来解决缓存穿透的问题。缓存穿透是指恶意用户请求⼀个不 存在的数据，导致请求直接访问数据库，造成数据库压力过⼤。布隆过滤器可以先判断请求的数据是 否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询。

  2. 爬虫去重：

       在爬虫系统中，为了避免重复爬取相同的URL，可以使⽤布隆过滤器来进行URL去重。爬取到的URL可 以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略，避免重复的网络请求和数据处理。

  3. 对数据库查询提效：

      在数据库中，布隆过滤器可以用来加速查询操作。例如：一个app要快速判断一个电话号码是否注册 过，可以使用布隆过滤器来判断一个用户电话号码是否存在于表中，如果不存在，可以直接返回不存 在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认。

  4. 垃圾邮件过滤：

       在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件 的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从而提高过滤的效率。

布隆过滤器通过牺牲一定的准确性，在海量数据去重、快速过滤等场景中展现了不可替代的优势，是分布式系统和大数据处理的基石技术之一。

三，海量数据处理问题

3.1，10亿个整数求最大的前100个数

本题是topk问题，用堆解决，建一个100个数的小堆，让这10亿个整数分别与堆顶元素比较，如果大于堆顶元素，就交换，再调整堆。最后最大的前100个就保存在小堆中。

3.2，给两个文件，分别有100亿个query（查询字符串），我们只有1G内存，如何找到两个文件交集？

解法一：使用布隆过滤器存储文件1，再遍历文件2，看布隆过滤器中是否存在，存在就是交集。

解法二：

哈希切分，首先内存的访问速度远大于硬盘，大文件放到内存搞不定，那么我们可以考虑切分为

文件，再放进内存处理。

本质是相同的query在哈希切分过程中，一定进入的同一个小文件Ai和Bi，不可能出现A中的的 query进入Ai，但是B中的相同query进入了和Bj的情况，所以对Ai和Bi进行求交集即可，不需要Ai 和Bj求交集。

 哈希切分的问题就是每个⼩⽂件不是均匀切分的，可能会导致某个小文件很大内存放不下。我们细 细分析⼀下某个小文件很⼤有两种情况：1.这个小文件中⼤部分是同一个query。2.这个小文件是 有很多的不同query构成，本质是这些query冲突了。针对情况1，其实放到内存的set中是可以放 下的，因为set是去重的。针对情况2，需要换个哈希函数继续二次哈希切分。所以我们遇到大 于1G小文件，可以继续读到set中找交集，若set.insert时抛出了异常(set插⼊数据抛异常只可能是 申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函数进行二次哈希切分。


http://www.kler.cn/a/531263.html

相关文章：

  • K8S集群架构及主机准备
  • Hive:窗口函数(1)
  • 【PyTorch】7.自动微分模块：开启神经网络 “进化之门” 的魔法钥匙
  • LeetCode 404.左叶子之和
  • SpringBoot 整合 SpringMVC：SpringMVC的注解管理
  • 记录 | 基于MaxKB的仿小红书旅游文章AI制作（含图文、视频）
  • 毫秒级响应的VoIP中的系统组合推荐
  • 【DeepSeek背后的技术】系列一：混合专家模型（MoE）
  • 从零开始实现一个双向循环链表：C语言实战
  • Java多线程——对象的组合
  • FPGA|例化生成的PLL功能IP核
  • 为什么在Rust中要用Struct和Enum组织数据？
  • MySQL锁类型（详解）
  • React+Cesium基础教程（003）：加载3D建筑物和创建标签
  • 利用deepseek参与软件测试 基本架构如何 又该在什么环节接入deepseek
  • Pathformer3D: A 3D Scanpath Transformer for 360° Images（浅看）
  • Simula语言的物联网
  • pycharm 中的 Mark Directory As 的作用是什么？
  • C++11新特性之constexpr
  • Machine Learning Engineering Open Book 机器学习工程开放书
  • 八、Spring Boot 日志详解
  • 带负权值的图如何计算最短路径？
  • w190工作流程管理系统设计与实现
  • Nginx反向代理 笔记250203
  • web-SQL注入-CTFHub
  • 55【ip+dns+域名关系】