🎬 个人主页：HABuo

📖 个人专栏：《C++系列》《Linux系列》《数据结构》《C语言系列》《Python系列》《YOLO系列》

⛰️ 如果再也不能见到你，祝你早安，午安，晚安

目录

📚一、位图概念

📖1.位图是什么，解决什么问题？

📖2.位图模拟实现

📚二、布隆过滤器概念

📖1.布隆过滤器是什么，解决什么问题？

📖2.布隆过滤器模拟实现

📚三、海量数据处理的面试题

📖1.位图应用

📖2.布隆过滤器

📖3.哈希切割

📚四、总结

前言：

前面我们了解学习了哈希及其哈希表，哈希表是日常生活中使用较多的一个数据结构，今天我们就用哈希来解决面试当中常见的一类题型----海量数据处理，到底怎么用哈希处理这类问题呢？让我们一探究竟！

本章重点:

本篇文章着重讲解哈希的应用的两个容器，一个是位图，一个是布隆过滤器，并且模拟实现它们。最后会讲解如何使用这两个容器来解决一些海量数据相关的面试问题

📚一、位图概念

📖1.位图是什么，解决什么问题？

我们从一道面试题开始：

用 std::set 或 std::unordered_set？

  • 一个整数占4字节（32位），40亿个就是约 4e9 * 4 bytes ≈ 14.9 GB。内存消耗巨大！

用位图！

  • 它的核心思想是：用一个比特位（bit）来标记某个元素是否存在。

  • 如果这个比特位是1，表示元素存在；是0，表示不存在。

  • 对于40亿个不重复的整数，我们只需要 2^32 个比特位（因为32位无符号整数的范围是0到2^32-1，约42.9亿）。

  • 计算一下内存：2^32 bits = 2^29 bytes = 512 MB。从14.9GB降到512MB！这就是位图的魅力。

因此位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。

例如：判断1~22中哪些数据是存在的，只需要用三个整型也就是24个比特位的空间

📖2.位图模拟实现

模板参数N代表位图的大小

位图有三个主要的接口函数:

  1. set: 将一个数据放入位图中
  2. reset:将一个数据从位图中删掉
  3. test:检测一个数据在不在位图中

先将位图框架写出来，我们用一个char来当作一个基本单元（即有8个比特位）

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
	bit_set()
	{
		_bit.resize(N / 8 + 1);//+1的目的是为了后面几个数如映射1-10的数，那么10/8=1，
                                //9-10来了映射哪个位置
	}
	void set(size_t x)//将第x位变成1
	{}
	void reset(size_t x)//将第x位由1变0
	{}
	bool test(size_t x)
	{}
private:
	vector<char> _bit;
};

在写set,reset等函数时，要先清楚一点，那就是char类型的数组一个元素8个比特位，所以我们需要确定两个位置:一是此数据在哪一个数组元素中，二是此数据对应此元素的第几个比特位下面我们画个图来推导一下公式:

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
	bit_set(){
		_bit.resize(N / 8 + 1);
	}
	void set(size_t x)//将第x位变成1
	{
		//x/8->在第几个char
		//x%8->在这个char的第几个比特位
		size_t i = x / 8;
		size_t j = x % 8;
		_bit[i] |= (1 << j);//将x对应的比特位变成1
	}
	void reset(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		_bit[i] &= ~(1 << j);//将x对应的比特位变成0
	}
	bool test(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		return _bit[i] & (1 << j);
	}
private:
	vector<char> _bit;
};

位图小结：

  • 核心思想： 用比特位标记状态，极大节省空间。

  • 适用场景： 数据是密集分布的整数，且范围相对不大。

  • 不适用场景：

    1. 数据不是整数（如字符串）。

    2. 数据是整数，但范围非常大且稀疏（比如只有1和10亿两个数，你却要开10亿/8≈125MB的数组，浪费严重）。

📚二、布隆过滤器概念

📖1.布隆过滤器是什么，解决什么问题？

位图很好，但它只能处理整数。如果我们想判断一个字符串（比如一个单词）是否在一个海量集合中，该怎么办？你可能会想到用哈希表，但海量字符串的哈希表依然占用巨大内存。这时，布隆过滤器就登场了。

布隆过滤器提出

因此布隆过滤器概念：

布隆过滤器是由布隆在1970年提出的 一种紧凑型的、比较巧妙的概 率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

查找字符"美团"是否存在时,会找到这三个绿色的位置,看看是否都为1.

但是聪明的你一定会想到，如果字节跳动和腾讯两个干起来了，有了相同的业务，部分映射到了同样的位置怎么办?没法办，正是因为布隆过滤器映射到了几个位置才使得多个字符串映射到同一位置的可能性降低，但是不能杜绝，这也是它的缺陷，因此布隆过滤器是不支持删除的。如下图所示：

如何降低误判率？

  1. 增加位数组大小： 位数组越大，比特位越稀疏，冲突概率越低。

  2. 增加哈希函数个数： 哈希函数越多，一个元素需要匹配的位就越多，偶然全部匹配的概率就越低。（但也不是越多越好，太多会导致位数组很快被填满）

拓展阅读：详解布隆过滤器的原理，使用场景和注意事项

📖2.布隆过滤器模拟实现

首先,布隆过滤器的底层也是位图,所以只需封装一层即可实现一个布隆过滤器!

但实现布隆过滤器有几个关键：

  • 一个字符串映射几个位置?
  • 怎样把字符串转换为整数?

一般而言,一个字符串映射的越多,那么误判率就越低,但是映射过多会导致不同的字符串映射到相同的位置,所以一般映射三个位置,并且将字符串转换为整数也就需要三种不同的方法,我在网上找了一些字符串转整数的算法,请看下面的代码:

//三个不同的字符串映射成整数的函数
struct HashBKDR
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};
struct HashAP
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			if ((i & 1) == 0)
				hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
		}
		return hash;
	}
};
struct HashDJB
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
			hash += (hash << 5) + ch;
		return hash;
	}
};

将这三个仿函数传入类,用于字符串转整型

// N表示准备要映射N个值
template<size_t N,
	class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class Bloom_Filter
{
public:
	void set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits->set(hash1);
		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits->set(hash2);
		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits->set(hash3);
	}

	bool test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!_bits->test(hash1))
			return false; // 准确的
		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!_bits->test(hash2))
			return false; // 准确的
		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!_bits->test(hash3))
			return false;  // 准确的
		return true; // 可能存在误判
	}

	void reset(const K& key)//支持删除操作的话,可能会把其他数据对应的映射值删除
	{}
private:
	const static size_t _ratio = 5;//开的空间越大,误判率越小
	std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;//标准库中的位图是在栈上开辟的静态数组,过大会栈溢出
};

布隆过滤器小结：

  • 核心思想： 使用 k 个哈希函数将一个元素映射到位数组中的 k 个点。通过检查这 k 个点是否都为1来判断元素是否存在。

  • 优点： 空间效率和时间效率都极高。

  • 缺点： 有误判率，且不支持删除操作（因为删除一个元素设置的位可能会影响到其他元素）。

  • 适用场景：

    • 缓存穿透问题：防止恶意查询不存在的key直接打到数据库。

    • 爬虫URL去重：已爬过的URL不再爬。

    • 安全领域：判断一个弱密码是否在已知的弱密码库里。

📚三、海量数据处理的面试题

📖1.位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

分析：
判断一个值在不在？只需要两种状态，所以使用一个位就可以了
这里我们要找出只出现1次的整数，出现0次的，出现1次的，出现2次及以上的。这里需要三种状态，也就是说每个值使用2个位表示就可以。

出现0次：00
出现1次：01
出现2次及以上：10

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

方案1：将其中一个文件1的整数映射到一个位图中，读取另外一个文件2中的整数，判断在在不在位图，在就是交集。消耗500M内存
方案2：将文件1的整数映射到位图1中，将文件2的整数映射到位图2中，然后将两个位图中的数按位与。与之后为1的位就是交集。消耗内存1G。

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

本题跟上面的第1题思路是一样的
本题找的不超过2次的，也就是要找出现1次和2次的
本题还是用两个位表示一个数，分为出现0次00表示，出现1次的01表示出现2次的10表示出现3次及3次以上的用11表示

📖2.布隆过滤器

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

分析：（query一般是sql查询语句或者网络请求的url等，一般是一个字符串）100亿个query占用多少空间呢？假设平均一个query30-60byte，100亿个query大约占用300-600G
方案一：将文件1中的query映射到一个布隆过滤器，读取文件2中的query，判断在不在布隆过滤器中，在就是交集。但是该方法有缺陷，就是布隆过滤器怕判断不在是准确的，判断在存在误判

方案二（精确算法）：

分析思路：这两个文件都非常大，大概在300-600G之间，也没有合适的数据结构能直接精确的找出交集。文件很大不能都放到内存中，那么我们可以把文件切分多个小文件，小文件数据加载到内存中。

切分成多少份：一般切出来一个小文件的大小能放进内存就可以。那么这里一个文件300-600G，切1000份，一个文件300-600M，这里有1G内存，所以可以搞定。

再分析：如果是平均切分，那么A0可以放到内存中存储到一个set中，那么B0-B999小文件中的数据都得跟A0比较，以此类推，A1放到内存中后，也得跟B0-B999小文件中的数据比较。可以看到这里的优势就是比较的过程放到内存中，但是这里要不断的互相比较

可以看到这里解决的优势：1、部分数据放到内存中 2、不是暴力比较，因为Ax的小文件的数据放在set中，比较效率还是能高很多

不再平均切分，哈希切分：i=hashstr(query）%1000，i是多少query就进入第Ai/Bi的小文件中，文件A、文件B分别这样处理。A和B中相同的query一定进入编号相同的Ai和Bi小文
件，所以下面只需要编号相同找交集就可以。

将Ai放小文件的数据放到一个set中，读取对应的Bi小文件中query，看在不在Ai中，在就是交集。

上面所涉及的知识就是哈希切割的内容。

2. 如何扩展BloomFilter使得它支持删除元素的操作

每个位标记成计数器
那么到底用几个位来表示计数器呢？给的位如果少了，如果多个值映射一个位置就到导致计数器溢出。比如1个byte最多计数到256，假设有260值都映射一个位置，就出问题了。
但是如果使用的更多的位映射一个位置，那么空间消耗就大了，不要忘了布隆过滤器的特点就是节省空间。

📖3.哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

分析：首先这里要做的是统计次数，同次数我们一般用kv模型的map解决，但是这里的问题是有100G数据，放不到内存中。

先创建1000个小文件A0-A999，读取IP计算出i=hashstr（IP)%1000.i是多少，IP就进入对应编号的Ai小文件。这样相同IP一定进入了同一个小文件。

map<string，int> countMap，读取Ai中的IP统计出次数，一个读完了clear，再读另一个。使用一个pair<string，int> max记录出现次数最多的IP就可以求出。
如果要找topK，那么就是用一个堆来搞定就可以。

拓展阅读知识：

一致性哈希

📚四、总结

特性 位图 布隆过滤器
存储元素 整数 任意类型（字符串、对象等）
核心结构 比特位数组 比特位数组 + 多个哈希函数
空间效率 极高 极高
时间效率 O(1) O(k)，k是哈希函数个数，是常数
确定性 100%准确 可能有误判
删除操作 支持 通常不支持（有变种支持，如计数布隆过滤器）
适用场景 密集整数集合判重 海量任意数据、允许一定误判的判重

# c++ # 哈希算法 # 算法 # 后端 # 开发语言 # c语言 # 数据结构
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

从一张商品图到正式上架：实测店匠 Shoplazza Athena，AI Agent 不只是聊天框

avatar AI Agent技术社区
cover

我测试了一个0.9B模型，它竟然能自动区分多人讲话）

avatar AI Agent技术社区
cover

【AI Agent】《2026年9月 AI Agent全栈开发技术选型专项面试宝典》

avatar AI Agent技术社区