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

1. 位图

1.1 位图简介

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

1.2 位图相关面试题

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

解题思路分析

1. 暴力遍历法：

   • 直接顺序查找整个数据集
   • 时间复杂度：O(N)
   • 问题：对于40亿数据量来说效率太低，可能需要数十秒的查找时间

2. 排序+二分查找法：

   • 先排序(O(N*logN))，再使用二分查找(O(logN))
   • 总时间复杂度：O(N*logN) + O(logN)
   • 深入分析：
     • 内存占用计算：假设使用32位无符号整数存储
     • 每个整数占4字节(32位)
     • 40亿个整数 = 4,000,000,000 × 4 bytes ≈ 16GB
     • 普通计算机的内存通常为8GB或16GB，无法全部加载到内存中
     • 二分查找要求数据必须在内存中保持有序，无法有效处理硬盘文件

3. 位图解决方案：

   • 观察：数据存在与否只需要表示两种状态(存在/不存在)
   • 可以使用单个二进制位(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位。具体实现方案如下：

1. 存储结构选择： 通常使用vector<int>作为底层容器，每个int元素（假设32位系统）可以表示32个bit位。

2. 地址计算规则： 对于给定的整数x：

   • i = x / 32：确定x位于第几个int元素
   • j = x % 32：确定x位于该int元素的第几位 例如：x=35时，i=1（第二个int），j=3（第3位）

3. 操作方式：

   • 设置存在：将对应bit位置为1
   • 查询存在：检查对应bit位是否为1
   • 清除存在：将对应bit位置为0

4. 应用场景：

   • 大规模数据去重
   • 快速存在性检查
   • 布隆过滤器的基础结构
   • 数据库索引优化

5. 优势：

   • 极低的空间复杂度(O(n) bits)
   • 常数时间(O(1))的查询和插入操作
   • 适合处理海量数据的存在性问题

6. 局限性：

   • 当数据范围过大而实际数据稀疏时，可能浪费空间
   • 只能表示存在与否，不能存储额外信息
   • 对于非整数数据需要额外的哈希处理

代码实现

namespace RO
{template<size_t N>class bitset{public:bitset(){_bs.resize(N / 32 + 1);}// x映射的位标记成1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}// x映射的位标记成0void 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: 00000000std::bitset<8> bs2(0b10101010); // 二进制初始化: 10101010std::bitset<8> bs3("11110000"); // 字符串初始化: 11110000std::cout << "bs1: " << bs1 << "\n"; // 00000000std::cout << "bs2: " << bs2 << "\n"; // 10101010std::cout << "bs3: " << bs3 << "\n\n"; // 11110000// 设置位bs1.set(3);     // 设置第3位(从0开始): 00001000bs1.set();       // 设置所有位: 11111111// 重置位bs1.reset(2);   // 重置第2位: 11111011bs1.reset();     // 重置所有位: 00000000// 翻转位bs2.flip(1);    // 翻转第1位: 10101000 -> 10101010 -> 10101000? 实际: 10101000bs2.flip();      // 翻转所有位: 10101000 -> 01010111std::cout << "After operations:\n";std::cout << "bs1: " << bs1 << "\n"; // 00000000std::cout << "bs2: " << bs2 << "\n\n"; // 01010111// 访问位std::cout << "bs3[0]: " << bs3[0] << "\n"; // 0 (最右边是最低位)std::cout << "bs3[4]: " << bs3[4] << "\n"; // 1std::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"; // 4std::cout << "total bits: " << bs3.size() << "\n\n";     // 8// 位操作std::bitset<8> bs4(0b11001100);std::cout << "bs3 & bs4: " << (bs3 & bs4) << "\n"; // 11000000std::cout << "bs3 | bs4: " << (bs3 | bs4) << "\n"; // 11111100std::cout << "bs3 ^ bs4: " << (bs3 ^ bs4) << "\n"; // 00111100std::cout << "~bs3: " << (~bs3) << "\n\n";         // 00001111// 类型转换std::cout << "bs3 to ulong: " << bs3.to_ulong() << "\n"; // 240std::cout << "bs3 to string: " << bs3.to_string() << "\n"; // 11110000std::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 位图相关考察题目

1. 查找唯一出现的整数
   给定100亿个整数，如何找到只出现一次的整数？

   • 解决方案：虽然数据量庞大，但整数范围有限，可以创建2^32位的位图进行标记处理，方法与前面的题目类似。

2. 寻找文件交集
   两个文件各含100亿个整数，在1G内存限制下，如何找出它们的交集？

   • 解决方案：将数据分别加载到两个位图结构中，通过遍历比较，同时存在于两个位图中的数值即为交集。

3. 统计低频出现整数
   在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;}}
}

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

运行结果：