在处理用户行为日志、爬虫URL记录或传感器采集流水时，工程师往往要对数亿甚至数十亿条整数或字符串标识做去重。若直接采用STL的unordered_set，每个元素附带指针与哈希开销，内存很快就会成为瓶颈。位图算法把存在性压缩到单个比特，用极小的空间代价换取稳定且可预测的查询速度，是海量数据去重里非常实用的基础方案。
一、位图去重的基本理论与空间模型
位图（Bitmap）的核心思想是为每一个可能的取值分配一个比特位。当数值出现时，把对应比特置为1；查询时只需读取该比特就能判断是否存在。假设我们需要对0到N-1范围内的无符号整数去重，传统集合容器每个节点往往要几十字节，而位图只需要N个比特，也就是N/8字节。当N为十亿时，位图占用约119MB，而哈希表轻松超过4GB。
这种映射方式不仅节省空间，还让查找操作变成简单的移位与位与运算，时间复杂度恒定在O(1)。不过位图要求数据值域相对紧凑，如果数据稀疏且最大值很大，直接开全局位图反而会浪费空间，这时就需要后续提到的分块或布隆过滤器思路来补位。
1.1 比特映射的数学表达
对于一个输入值x，我们把它映射到字节下标 byte_index = x / 8 和位偏移 bit_offset = x % 8。置位操作等价于 buffer[byte_index] |= (1 << bit_offset)，查询操作等价于 (buffer[byte_index] & (1 << bit_offset)) != 0。这套公式在任何支持位运算的语言里都通用，在C++里还能借助std::vector<uint8_t>获得连续内存与自动释放。
理解这个公式后，你会发现在多核环境下，不同x写入不同字节时几乎没有缓存争用，因此位图天然适合并行标记。只要保证单个字节内的位操作使用原子指令或线程分片，就能轻松把吞吐堆上去。
二、基础C++位图实现与源码
下面给出一个最小可用、线程不安全但极易嵌入项目的位图类。它支持构造时指定最大数值、添加元素、查询元素和清除元素。代码以文本形式展示，所有尖括号均已转义，可直接复制到.cpp文件编译。
#include <vector>
#include <cstdint>
#include <stdexcept>
class BitMap {
public:
explicit BitMap(uint64_t max_value) : size_((max_value + 7) / 8) {
if (max_value == 0) throw std::invalid_argument("max_value must be > 0");
buffer_.assign(size_, 0);
}
void set(uint64_t x) {
uint64_t byte_idx = x / 8;
uint8_t bit_idx = x % 8;
buffer_[byte_idx] |= static_cast<uint8_t>(1 << bit_idx);
}
bool test(uint64_t x) const {
uint64_t byte_idx = x / 8;
uint8_t bit_idx = x % 8;
return (buffer_[byte_idx] & static_cast<uint8_t>(1 << bit_idx)) != 0;
}
void reset(uint64_t x) {
uint64_t byte_idx = x / 8;
uint8_t bit_idx = x % 8;
buffer_[byte_idx] &= static_cast<uint8_t>(~(1 << bit_idx));
}
uint64_t memory_bytes() const {
return size_;
}
private:
uint64_t size_;
std::vector<uint8_t> buffer_;
};
// 使用示例
#include <iostream>
int main() {
BitMap bm(1000000000ULL);
bm.set(12345);
std::cout << bm.test(12345) << std::endl;
std::cout << bm.memory_bytes() << std::endl;
return 0;
}
2.1 代码要点解析
构造函数里用 (max_value + 7) / 8 而不是 max_value / 8，是为了向上取整，保证最大合法值也有对应比特。buffer_使用std::vector而不是原生数组，既避免手动delete，也能在拷贝时获得合理行为。set、test、reset三个函数都没有循环，仅做除法、取模和位运算，生成的汇编通常只有几条指令。
示例main函数里构造了可容纳十亿值的位图，实测memory_bytes返回125000000，约119MB。如果在同样数据规模下用unordered_set<uint32_t>，在GCC默认设置下内存往往超过3GB，差距超过二十倍。这就是位图在去重场景里最直观的优势。
三、空间开销的进一步优化策略
基础位图要求值域连续。如果数据来自分布式系统，ID从零到四十亿但只有其中两亿个出现过，直接开四十亿比特就要500MB，仍显浪费。此时可以引入分块位图：把值域切成多个区间，每个区间仅在被触碰时才分配对应的小数组。
3.1 分块位图设计
例如以每65536个值为一块，全局维护一个指针数组，初始为空。当set(x)被调用，先算出块号 block = x / 65536，若块未分配则new一个小位图；再在块内算局部偏移。这样内存只和实际出现的块数成正比。下面给出简化结构：
#include <vector>
#include <cstdint>
#include <memory>
class BlockBitMap {
public:
BlockBitMap(uint64_t max_value, uint32_t block_size = 65536)
: block_size_(block_size),
blocks_((max_value + block_size - 1) / block_size, nullptr) {}
void set(uint64_t x) {
uint64_t block = x / block_size_;
uint32_t offset = x % block_size_;
if (!blocks_[block]) {
blocks_[block].reset(new std::vector<uint8_t>((block_size_ + 7) / 8, 0));
}
(*blocks_[block])[offset / 8] |= static_cast<uint8_t>(1 << (offset % 8));
}
bool test(uint64_t x) const {
uint64_t block = x / block_size_;
if (!blocks_[block]) return false;
uint32_t offset = x % block_size_;
return ((*blocks_[block])[offset / 8] & static_cast<uint8_t>(1 << (offset % 8))) != 0;
}
private:
uint32_t block_size_;
std::vector<std::unique_ptr<std::vector<uint8_t>>> blocks_;
};
分块位图在稀疏数据下能省掉九成以上内存，代价是多一次指针寻址和可能的动态分配。如果块大小选得过细，指针数组本身会膨胀；选得过粗，又退化成普通位图。经验上取2的次幂且匹配CPU缓存行倍数，能让局部性更好。
除了分块，还可以用布隆过滤器做前置去重：它用多个哈希函数把元素映射到更短的比特数组，允许极低误判但空间极小。在日志初筛阶段先用布隆过滤器挡掉明显重复的，再把疑似新元素进精确位图，整体空间与IO都能再降一截。
四、查找效率与工程化注意点
位图查询是O(1)且缓存友好，但在频繁随机test的场景，如果buffer_超过L3缓存，访存延迟会显现。一种办法是按线程分片，让每个核只写自己值域段，减少伪共享；另一种是对齐到64字节，避免一个比特跨越缓存行造成额外加载。
4.1 编译器优化与原子化
在单线程下，开启 -O2 后位运算会被内联并向量化，吞吐极高。如果必须多线程并发set，不要对整个字节加锁，可以用 __atomic_or_fetch 等内置函数做原子位或，既保证安全又比互斥锁轻量。下面展示原子置位的写法：
#include <atomic>
#include <vector>
#include <cstdint>
class AtomicBitMap {
public:
explicit AtomicBitMap(uint64_t max_value)
: buf_((max_value + 7) / 8) {}
void set(uint64_t x) {
uint64_t idx = x / 8;
uint8_t mask = static_cast<uint8_t>(1 << (x % 8));
std::atomic<uint8_t>* p = reinterpret_cast<std::atomic<uint8_t>*>(&buf_[idx]);
p->fetch_or(mask, std::memory_order_relaxed);
}
bool test(uint64_t x) const {
uint8_t v = buf_[x / 8];
return (v & static_cast<uint8_t>(1 << (x % 8))) != 0;
}
private:
std::vector<uint8_t> buf_;
};
上面的AtomicBitMap把每个字节视作原子变量，fetch_or保证并发置位不丢失。test不需要原子，因为一旦置位就不会被清掉。实际压测中，这种粒度比std::mutex包裹整个set快五倍以上，且内存布局和普通位图一致。
最后提醒，如果数据带有字符串KEY而非整数，需要先通过哈希函数（如MurmurHash）转成固定长度整数再进位图，或者改用布隆过滤器。直接把字符串塞进位图在C++里没有意义，也会破坏空间模型。
五、总结与实践建议
位图算法用比特级压缩解决了海量整数去重的空间难题，基础实现仅需几十行C++。当数据稠密时优先用全局位图，稀疏时切分块位图，超高并发下用原子字节操作避免锁竞争。结合布隆过滤器还能在前端再削一波流量。
建议你在做去重模块前先统计数据的最大值、分布和并发度，再决定用哪一层优化。把本文给出的源码作为基线，逐步替换块大小与原子策略，通常能在百毫秒内完成十亿级标记，且常驻内存控制在百兆级别，对大多数服务端任务是完全可接受的。