位图算法通过比特位标记整数存在性，适用于内存受限下的海量整数去重与查询；分段位图、roaring bitmap、内存映射、多线程封装、simd加速及布隆过滤器前置等策略分别应对超大值域、稀疏分布、持久化、并发、批量操作和高重复率场景。
一、位图算法基本原理与适用场景
当需要在内存受限条件下对大量整型数据（如32位无符号整数）进行去重或存在性判断时，Bitmap通过将每个整数映射为一个比特位来实现空间高效存储。该模型不存储原始数值，仅标记“出现与否”，因此适用于值域范围明确且相对集中的海量整数集合。
1、确定待处理数据的最大可能取值上限N，申请长度为⌈N/8⌉字节的连续内存块。
2、对任意整数x，其对应比特位置由行号x/8与列偏移x%8共同决定，使用位运算定位并设置标志位。
3、插入操作执行按位或运算，查询操作执行按位与运算，两者时间复杂度均为O(1)。
二、分段位图设计应对超大值域
当数据值域远超单机内存可分配位图容量（例如0~2^40），需将值域划分为多个连续子区间，每个区间独立构建位图，并采用哈希表或数组索引管理各段实例。此结构保留O(1)查询特性，同时规避单一位图内存溢出风险。
1、设定每段覆盖宽度W（如2^20），计算总段数S = ⌈max_value / W⌉。
2、初始化大小为S的指针数组segments，每个元素指向new uint8_t[W/8]分配的位图内存。
3、对输入值x，先计算段索引seg_idx = x / W，再在segments[seg_idx]中执行标准位图操作。
4、释放资源时逐段调用delete[]，避免内存泄漏。
三、Roaring Bitmap替代方案集成
针对稀疏分布或存在大量空洞区间的实际数据，传统位图空间利用率急剧下降。Roaring Bitmap将值域分块为65536大小的容器，对每块依据密度自动选择array、bitmap或run编码，兼顾查询速度与压缩率。
1、引入roaring/roaring.hh头文件，确保编译时链接libroaring库。
2、声明roaring_bitmap_t* rb = roaring_bitmap_create()，用于承载去重后数据。
3、遍历原始数据流，对每个整数x调用roaring_bitmap_add(rb, x)完成插入。
4、使用roaring_bitmap_contains(rb, x)执行O(log n)存在性检查，其中n为当前容器内实际元素个数。
四、内存映射文件支持超大规模持久化位图
当去重结果需跨进程复用或超出物理内存容量时，可将位图数据直接映射至磁盘文件，利用操作系统页缓存机制平衡I/O与访问延迟，避免全量加载。
1、创建指定大小的空文件，使用open()获取fd，再通过ftruncate()扩展至所需字节数。
2、调用mmap()将文件映射为可读写内存区域，返回指针作为位图基地址。
3、所有位操作（如set_bit、test_bit）均作用于该映射地址，修改实时同步至文件。
4、操作完成后调用munmap()解除映射，close()关闭文件描述符。
五、多线程安全位图封装策略
在并发插入场景下，多个线程对同一比特位执行set操作可能引发竞态。需在不显著降低性能前提下保障原子性，推荐采用细粒度锁分区或无锁CAS机制。
1、将整个位图划分为若干固定大小的桶（如每桶4096位），为每个桶分配独立std::mutex实例。
2、对整数x，计算桶索引bucket_id = (x / 8) / BUCKET_SIZE，锁定对应mutex后再执行位操作。
3、或使用std::atomic
4、确保所有线程共享同一base_ptr及长度信息，禁止局部拷贝位图元数据。
六、SIMD指令加速批量位操作
利用AVX2指令集一次处理256位数据，可大幅提升连续区间置位、清零或扫描性能。适用于预知数据具有局部聚集特征的场景，如日志时间戳去重。
1、确认CPU支持AVX2指令集，编译时添加-mavx2 -O3参数启用优化。
2、将位图起始地址按32字节对齐，使用_mm256_load_si256加载256位数据到ymm寄存器。
3、调用_mm256_or_si256执行并行按位或运算，再用_mm256_store_si256写回内存。
4、对未对齐首尾部分改用标量指令补充处理，保证逻辑完整性。
七、布隆过滤器前置过滤降低位图压力
当原始数据中存在极高比例重复项时，可在位图前部署轻量级布隆过滤器，仅将布隆器判定为“可能存在”的新元素送入位图处理，显著减少位图写入次数和冲突概率。
1、构造k=3个独立哈希函数，初始化m位布隆过滤器数组，初始值全为0。
2、对每个输入x，计算h1(x), h2(x), h3(x)，检查对应位是否全为1；若否，则进入位图插入流程并更新布隆器。
3、布隆器本身使用uint64_t数组实现，哈希结果对m取模后转换为bit_index = hash % (m*8)进行位操作。
4、布隆器误判率控制在0.1%以内，通过增大m或k值进一步调节精度。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
