Bitmap位图算法通过五种优化方案高效处理海量整型数据去重与查找：一、std::vector紧凑实现；二、uint64_t数组手动位运算提升吞吐；三、分段Bitmap应对稀疏大范围；四、mmap支持百亿级只读位图；五、std::atomic封装保障并发安全。

如果您需要在C++中高效处理海量整型数据的去重与查找，Bitmap位图算法是一种空间与时间兼顾的经典方案。以下是该算法的设计实现与性能优化步骤：

一、基于std::vector的紧凑位图实现

利用std::vector的特化实现，每个布尔值仅占用1比特，极大压缩内存开销，适用于已知数据范围且为非负整数的场景。

1、定义Bitmap类，内部使用std::vector存储位数组，容量根据最大可能值预分配。

2、构造函数中调用resize方法初始化所有位为false，确保索引安全访问。

立即学习“C++免费学习笔记（深入）”；

3、set方法通过下标操作将指定整数对应位置设为true，无需额外位运算封装。

4、test方法直接返回vector对应索引的布尔值，实现O(1)查找。

5、遍历所有索引，收集值为true的索引，构成去重后的有序结果集。

二、手动管理uint64_t数组的高性能位图

规避std::vector的代理对象开销与迭代器限制，采用原生无符号整数数组，通过位运算直接控制每一位，提升设置与查询吞吐量。

1、计算所需uint64_t元素个数：(max_value + 63) / 64。

2、使用new uint64_t[size]动态分配连续内存块，并用memset初始化为0。

3、set操作中，先计算目标值所在字的索引：index / 64；再计算位偏移：index % 64；最后执行bits[word] |= (1ULL

4、test操作中，同样计算word与bit，返回(bits[word] >> bit) & 1ULL。

5、提供bulk_set接口，支持一次设置连续整数区间，减少循环分支开销。

三、分段Bitmap支持超大范围稀疏数据

当数据最大值极大但实际分布稀疏时，全量分配位图将造成严重内存浪费。分段Bitmap将值域划分为固定大小桶（如64K），仅对非空桶分配子位图。

1、定义桶大小BUCKET_SIZE，通常取65536或131072。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

2、使用std::unordered_map>存储活跃桶，键为桶序号（value / BUCKET_SIZE）。

3、set操作中，先计算桶号bucket_id = value / BUCKET_SIZE，若桶不存在则分配并清零新数组；再在桶内执行标准位设置。

4、test操作中，先查map是否存在对应bucket_id，不存在则直接返回false；存在则按桶内偏移查询。

5、遍历时枚举map中每个桶，对每个桶内位图扫描并还原原始值：bucket_id * BUCKET_SIZE + bit_pos。

四、内存映射文件支持百亿级静态位图

针对只读、超大规模位图（如标记百亿URL是否已爬取），将位图持久化至磁盘并使用mmap加载，避免启动时全部载入内存。

1、预计算总位数N，确定所需字节数：(N + 7) / 8。

2、创建指定大小的空文件，使用posix_fallocate确保空间分配。

3、以PROT_READ | PROT_WRITE和MAP_SHARED标志调用mmap，获取可读写内存指针。

4、所有set/test操作均作用于mmap返回的指针，操作系统自动处理页调度与脏页回写。

5、程序退出前调用msync确保修改落盘，munmap释放映射。

五、并发安全的原子位图封装

在多线程插入场景下，需保证位操作的原子性，防止多个线程同时修改同一字内的不同位引发竞态。

1、底层仍使用uint64_t数组，但每个字对应一个std::atomic，而非原始类型。

2、set操作中，循环执行fetch_or：desired = 1ULL

3、test操作可直接load原子变量后执行位与，因读操作本身不改变状态，无需循环。

4、为降低争用，采用哈希分片策略：将值映射到多个独立原子数组之一，分片数通常为CPU核心数的2倍。

5、每个分片维护独立的atomic*数组及长度，set前先hash(value) % shard_count选择目标分片。