Bitmap不适合直接处理海量64位整数去重，因其值域达2⁶⁴，无法分配全量位数组；实际方案需分层哈希降维（如高12位定桶、低20位定偏移），配合std::bitset实现可控假阳性的近似去重，兼顾内存（512MB）与吞吐。
Bitmap 为什么不适合直接处理“海量”整数去重
直接用 std::vector<bool></bool> 或 std::bitset 做全量位图，前提是值域已知且紧凑。比如你要去重的是 0~10⁷ 范围内的整数，那 10⁷ bit ≈ 1.25 MB，很省；但若原始数据是 64 位随机 long long（如时间戳、UUID 拆解、日志 ID），值域跨度动辄 2⁶⁴，根本没法分配那么大的位数组。
真正能落地的“海量数据去重 Bitmap”，本质是分层 + 映射 + 截断：先哈希降维，再用小位图存局部存在性。否则不是内存爆炸，就是缓存行失效严重，查找反而比 std::unordered_set 还慢。
常见错误现象：std::bad_alloc 直接崩溃；或看似跑通，但 val >> 20 类硬编码导致高位信息丢失，重复率飙升。
用 std::bitset<1<<20> + 两级哈希实现可调精度去重
核心思路：把原始 uint64_t 值通过哈希映射到固定大小桶中，每个桶配一个 std::bitset 记录低位特征。这不是严格无误去重，而是概率可控的近似去重（Bloom Filter 变种），但空间从 GB 级压到 MB 级，吞吐翻倍。
立即学习“C++免费学习笔记（深入）”；
- 第一级哈希取高 12 位作为桶索引：
bucket = (x >> 52) & 0xfff（共 4096 个桶） - 第二级哈希取低 20 位作为位图偏移：
bit_pos = hash_32(x) & 0xfffff（hash_32推荐用 MurmurHash3 的 32 位截断版） - 每个桶用
std::bitset<1<<20>（128 KB），总内存 ≈ 4096 × 128 KB = 512 MB —— 可根据数据分布缩放桶数和位图大小 - 插入时仅置位，不查重；查询时若对应 bit 为 0 则**一定未见过**，为 1 则**可能见过**（有假阳性）
示例关键片段：
class ScalableBitmap {
static constexpr size_t BUCKET_CNT = 4096;
static constexpr size_t BITSET_SIZE = 1U << 20;
std::array<std::bitset<BITSET_SIZE>, BUCKET_CNT> buckets_;
<pre class='brush:php;toolbar:false;'>uint32_t fast_hash(uint64_t x) const {
x ^= x >> 33; x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33; x *= 0xc4ceb9fe1a85ec53ULL;
x ^= x >> 33; return x & 0xfffff;
}public: bool test_and_set(uint64_t x) { size_t bucket = (x >> 52) & 0xfff; uint32_t pos = fasthash(x); bool existed = buckets[bucket][pos]; buckets_[bucket].set(pos); return existed; } };
std::vector<bool> 和 std::bitset 在位操作性能上的真实差距
别迷信 std::bitset 一定更快。它在编译期确定大小时能内联位操作指令（如 bts），但若你用 std::vector<bool> 存 10M 位，现代 GCC/Clang 对 operator[] 的优化已足够好，实测差异常小于 5%。真正瓶颈在 cache line 命中率 —— 一锅端大位图不如分块访问。
容易踩的坑：
-
std::vector<bool>是特化容器，data()不可用，无法直接 mmap 或 memcpy；std::bitset无此限制但大小必须编译期常量 - 用
std::vector<uint64_t>手写位操作（v[i/64] &= ~(1ULL << (i%64))）反而更易向量化，LLVM 能自动展开成movmskpd+popcnt流水线 - 调试时别依赖
std::bitset::to_string()—— 1M 位会生成 1MB 字符串，卡死终端
假阳性率控制与实际去重率验证方法
理论假阳性率 ≈ (1 − e^(−kn/m))ᵏ，其中 k 是哈希函数个数（这里为 1），m 是总位数（如 512 MB × 8 = 4.2e9 bit），n 是插入元素数。但真实数据往往有偏斜 —— 比如日志 ID 高位集中，会导致某些桶过载，假阳性飙升。
必须做的验证：
- 运行时统计各桶的置位密度：
buckets_[i].count() / double(BITSET_SIZE)，超过 0.8 就该扩容桶或切分哈希 - 拿已知无重复的测试集（如递增
uint64_t序列）喂入，看test_and_set()返回 true 的比例 —— 这才是你的实际 FP rate - 如果业务允许少量漏判（即把新数据当旧数据丢弃），就用布隆过滤器；如果要求零漏判（如金融流水去重），Bitmap 必须配合后置精确校验（例如用
std::unordered_set<uint64_t>存可疑项）
最易被忽略的一点：哈希函数质量比位图大小影响更大。用 x * 2654435761U 这类简单乘法哈希，在 1e9 数据量下 FP rate 可能达 15%；换成 Murmur3 或 AHash，能压到 0.3% 以内 —— 这部分开销远小于多占几 MB 内存。
