【C++】26. 哈希扩展1—— 位图

Ronin305

发布于 2025-12-22 12:33:43

1360

文章被收录于专栏：我的博客我的博客

1. 位图

1.1 位图简介

位图(Bitmap)是一种利用二进制位来存储和表示数据的数据结构，主要用于高效地表示和操作大量数据的存在性信息。每个二进制位(bit)可以表示某个元素的存在(1)或不存在(0)，因此具有极高的空间效率。

1.2 位图相关面试题

题目描述：给定40亿个不重复的无符号整数(未排序)，如何快速判断某个无符号整数是否在这40亿个数中。(本题为腾讯/百度等公司的经典面试题)

解题思路分析

暴力遍历法：
- 直接顺序查找整个数据集
- 时间复杂度：O(N)
- 问题：对于40亿数据量来说效率太低，可能需要数十秒的查找时间
排序+二分查找法：
- 先排序(O(N*logN))，再使用二分查找(O(logN))
- 总时间复杂度：O(N*logN) + O(logN)
- 深入分析：
  - 内存占用计算：假设使用32位无符号整数存储
  - 每个整数占4字节(32位)
  - 40亿个整数 = 4,000,000,000 × 4 bytes ≈ 16GB
  - 普通计算机的内存通常为8GB或16GB，无法全部加载到内存中
  - 二分查找要求数据必须在内存中保持有序，无法有效处理硬盘文件
位图解决方案：
- 观察：数据存在与否只需要表示两种状态(存在/不存在)
- 可以使用单个二进制位(bit)来表示：
  - 1：表示存在
  - 0：表示不存在
- 设计思路：
  - 对于无符号32位整数，取值范围为0到4,294,967,295(约42.9亿)
  - 需要约42.9亿个bit位
  - 内存计算：4,294,967,295 bits ≈ 512MB(因为8 bits = 1 byte，1024 bytes = 1KB，1024KB = 1MB)
  - 现代计算机完全可以容纳512MB的数据结构

1.3 位图的设计及实现

位图（Bitmap）本质上是一个采用直接定址法的哈希表，它将每个整数映射到一个bit位，通过这个bit位的状态（0或1）来表示该整数是否存在。位图通常提供以下核心接口：

set(x)：将第x位置1
reset(x)：将第x位置0
test(x)：检测第x位是否为1

在C/C++实现中需要特别注意，由于没有直接的bit数据类型，我们需要使用整数类型（如int或char）作为存储单元，并通过位运算来操作具体bit位。具体实现方案如下：

存储结构选择：通常使用vector<int>作为底层容器，每个int元素（假设32位系统）可以表示32个bit位。
地址计算规则： 对于给定的整数x：
- i = x / 32：确定x位于第几个int元素
- j = x % 32：确定x位于该int元素的第几位例如：x=35时，i=1（第二个int），j=3（第3位）
操作方式：
- 设置存在：将对应bit位置为1
- 查询存在：检查对应bit位是否为1
- 清除存在：将对应bit位置为0
应用场景：
- 大规模数据去重
- 快速存在性检查
- 布隆过滤器的基础结构
- 数据库索引优化
优势：
- 极低的空间复杂度(O(n) bits)
- 常数时间(O(1))的查询和插入操作
- 适合处理海量数据的存在性问题
局限性：
- 当数据范围过大而实际数据稀疏时，可能浪费空间
- 只能表示存在与否，不能存储额外信息
- 对于非整数数据需要额外的哈希处理

代码实现

namespace RO
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bs.resize(N / 32 + 1);
		}

		// x映射的位标记成1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] |= (1 << j);
		}

		// x映射的位标记成0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] &= (~(1 << j));
		}

		// x映射的位是1返回真
		// x映射的位是0返回假
		bool test(size_t x)
		{
            assert(x < N);// 避免越界
			size_t i = x / 32;
			size_t j = x % 32;

			return (_bs[i] & (1 << j)) != 0;
		}
	private:
		vector<int> _bs;
	};
}

代码结构解析

1. 命名空间与类模板

namespace RO {
    template<size_t N>  // N: 需要管理的总比特位数
    class bitset { ... };
}

namespace RO：防止命名冲突
模板参数 N：表示位图需要管理的总比特位数

2. 构造函数

bitset() {
    _bs.resize(N / 32 + 1);  // 计算所需int个数
}

内存分配：计算存储 N 位所需的最少 int 数量
- 示例：若 N = 100，则需 100/32 + 1 = 4 个 int（共 128 位）

3. 成员变量

private:
    vector<int> _bs;  // 底层存储数组

每个 int 元素管理 32 个比特位

4. 关键操作函数

(1) `set(x)` - 将第 `x` 位设为 1

void set(size_t x) {
    size_t i = x / 32;  // 定位数组下标
    size_t j = x % 32;  // 定位int内的比特位置
    _bs[i] |= (1 << j); // 将对应比特位置1
}

操作示例：x = 37
- i = 37/32 = 1（第2个int）
- j = 37%32 = 5（该int的第5位）
- 1 << 5 = 0b0000'0000'0010'0000
- 执行按位或操作设置位

(2) `reset(x)` - 将第 `x` 位设为 0

void reset(size_t x) {
    size_t i = x / 32;
    size_t j = x % 32;
    _bs[i] &= (~(1 << j));  // 将对应比特位置0
}

关键步骤：
- ~(1 << j) 生成掩码（目标位为0，其余为1）
- 通过按位与操作清除目标位

(3) `test(x)` - 检查第 `x` 位是否为 1

bool test(size_t x) {
    assert(x < N);// 避免越界
    size_t i = x / 32;
    size_t j = x % 32;
    return (_bs[i] & (1 << j)) != 0;
}

原理：用按位与操作提取目标位，非0即表示该位为1

测试

void test1()
{
	RO::bitset<100> bs;
	//cout << sizeof(bs) << endl;

	bs.set(32);
	bs.set(33);

	bs.reset(33);
	bs.set(34);

	cout << bs.test(31) << endl;
	cout << bs.test(32) << endl;
	cout << bs.test(33) << endl;
	cout << bs.test(34) << endl;
	cout << bs.test(35) << endl;
}

运行结果：

1.4 C++库中的位图 bitset

https://legacy.cplusplus.com/reference/bitset/bitset/

可以看到核心接口还是set/reset/和test，当然后面还实现了一些其他接口，如to_string将位图按位转成01字符串，再包括operator[]等支持像数组一样访问修改每个位

使用示例：

#include <iostream>
#include <bitset>
#include <string>

int main() {
    // 创建位图 - 8位
    std::bitset<8> bs1;             // 默认全0: 00000000
    std::bitset<8> bs2(0b10101010); // 二进制初始化: 10101010
    std::bitset<8> bs3("11110000"); // 字符串初始化: 11110000
    
    std::cout << "bs1: " << bs1 << "\n"; // 00000000
    std::cout << "bs2: " << bs2 << "\n"; // 10101010
    std::cout << "bs3: " << bs3 << "\n\n"; // 11110000

    // 设置位
    bs1.set(3);     // 设置第3位(从0开始): 00001000
    bs1.set();       // 设置所有位: 11111111
    
    // 重置位
    bs1.reset(2);   // 重置第2位: 11111011
    bs1.reset();     // 重置所有位: 00000000
    
    // 翻转位
    bs2.flip(1);    // 翻转第1位: 10101000 -> 10101010 -> 10101000? 实际: 10101000
    bs2.flip();      // 翻转所有位: 10101000 -> 01010111
    
    std::cout << "After operations:\n";
    std::cout << "bs1: " << bs1 << "\n"; // 00000000
    std::cout << "bs2: " << bs2 << "\n\n"; // 01010111

    // 访问位
    std::cout << "bs3[0]: " << bs3[0] << "\n"; // 0 (最右边是最低位)
    std::cout << "bs3[4]: " << bs3[4] << "\n"; // 1
    std::cout << "bs3.test(0): " << bs3.test(0) << "\n\n"; // 0

    // 查询位图状态
    std::cout << "bs3 any bit set? " << bs3.any() << "\n";   // 1 (true)
    std::cout << "bs3 no bit set? " << bs3.none() << "\n";   // 0 (false)
    std::cout << "all bits set? " << bs3.all() << "\n";      // 0 (false)
    std::cout << "number of set bits: " << bs3.count() << "\n"; // 4
    std::cout << "total bits: " << bs3.size() << "\n\n";     // 8

    // 位操作
    std::bitset<8> bs4(0b11001100);
    std::cout << "bs3 & bs4: " << (bs3 & bs4) << "\n"; // 11000000
    std::cout << "bs3 | bs4: " << (bs3 | bs4) << "\n"; // 11111100
    std::cout << "bs3 ^ bs4: " << (bs3 ^ bs4) << "\n"; // 00111100
    std::cout << "~bs3: " << (~bs3) << "\n\n";         // 00001111

    // 类型转换
    std::cout << "bs3 to ulong: " << bs3.to_ulong() << "\n"; // 240
    std::cout << "bs3 to string: " << bs3.to_string() << "\n"; // 11110000
    std::cout << "bs3 to string with '*' and '-': " 
              << bs3.to_string('*', '-') << "\n"; // ****----

    return 0;
}

运行结果：

bitset 主要接口总结

接口	描述	示例
构造函数	创建bitset	bitset<8> bs; bitset<16> bs(0xABCD);
set()	设置所有位为1	bs.set();
set(pos)	设置特定位为1	bs.set(3);
reset()	重置所有位为0	bs.reset();
reset(pos)	重置特定位为0	bs.reset(2);
flip()	翻转所有位	bs.flip();
flip(pos)	翻转特定位	bs.flip(1);
test(pos)	检查特定位	if (bs.test(4)) {...}
operator[]	访问特定位	bs[0] = 1;
count()	统计1的数量	int ones = bs.count();
size()	获取总位数	int size = bs.size();
any()	是否有任何位为1	if (bs.any()) {...}
none()	是否没有位为1	if (bs.none()) {...}
all()	是否所有位为1	if (bs.all()) {...}
to_ulong()	转换为无符号长整型	unsigned long val = bs.to_ulong();
to_ullong()	转换为无符号长长整型	unsigned long long val = bs.to_ullong();
to_string()	转换为字符串	std::string s = bs.to_string();
位运算符	支持&, \|, ^, ~, <<, >>	bs1 & bs2 ~bs

1.5 位图相关考察题目

查找唯一出现的整数 给定100亿个整数，如何找到只出现一次的整数？
- 解决方案：虽然数据量庞大，但整数范围有限，可以创建2^32位的位图进行标记处理，方法与前面的题目类似。
寻找文件交集 两个文件各含100亿个整数，在1G内存限制下，如何找出它们的交集？
- 解决方案：将数据分别加载到两个位图结构中，通过遍历比较，同时存在于两个位图中的数值即为交集。
统计低频出现整数 在1G内存条件下，如何从100亿个整数文件中找出出现次数不超过2次的所有整数？
- 解决方案：使用两位二进制标记每个数值的状态：
  - 00：未出现
  - 01：出现1次
  - 10：出现2次
  - 11：出现超过2次
- 最终筛选出标记为01和10的数值即可。

代码实现：

使用两个位图(bitset)来记录每个元素出现的次数，用于统计元素出现频次（0次、1次、2次或2次以上）的场景。

template<size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		bool bit1 = _bs1.test(x);
		bool bit2 = _bs2.test(x);

		if (!bit1 && !bit2) // 00 -> 01
		{
			_bs2.set(x);
		}
		else if (!bit1 && bit2) // 01 -> 10
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		else if (bit1 && !bit2) // 10 -> 11
		{
			_bs2.set(x);
		}
	}

	// 返回0 出现0次数
	// 返回1 出现1次数
	// 返回2 出现2次数
	// 返回3 出现2次及以上
	int getcount(size_t 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 // 11
		{
			return 3;
		}
	}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

问题一和问题三测试：

void test_twobitset()
{
	RO::twobitset<100> tbs;
	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.getcount(i) << endl;
		if (tbs.getcount(i) == 1 || tbs.getcount(i) == 2)
		{
			cout << i << endl;
		}
	}
}

运行结果：

问题2解决办法如下代码示例：

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 << endl;
		}
	}
}

通过遍历比较，同时存在于两个位图中的数值即为交集。

运行结果：

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

存储

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度