位图算法不适合直接处理海量字符串数据，因其本质是基于整数索引的布尔数组，要求键为有限范围整数；字符串需哈希转换且无法解决冲突，稀疏或大范围数据会导致内存爆炸或严重浪费。
位图算法为什么不适合直接处理“海量”字符串数据
位图（Bitmap）本质是用 bit 作为索引的布尔数组，只适用于**整数键且值域有限**的场景。比如你有 10 亿个 int，范围在 [0, 2^32)，但实际只出现其中 1000 万个不同值——这时位图才真正省空间。一旦数据是 string、long long 超出 size_t 范围，或分布极度稀疏（如 ID 是时间戳 + 随机后缀），std::vector<bool></bool> 或手动 uint64_t* 分配出来的内存要么溢出，要么 99.99% 是零。
常见误用现象：new uint8_t[1ULL 直接崩溃；或用 <code>std::bitset 编译失败——模板参数必须是编译期常量，且太大时栈溢出。
实操建议：
- 先统计原始数据的最小值
min_val和最大值max_val，若max_val - min_val > 10^8，别硬上位图，改用std::unordered_set或外部排序 + 归并去重 - 对字符串去重，必须先哈希（如
std::hash<:string>{}(s) % N</:string>），但要注意哈希冲突——位图本身不解决冲突，它只是“标记某哈希值是否见过”，不能替代布隆过滤器的误判容忍设计 - 若确定是密集小整数（如日志中的 HTTP 状态码、枚举 ID），用
std::vector<bool></bool>最省：它按位压缩，v[i] = true底层只占 1 bit
手写紧凑位图：避免 std::vector<bool></bool> 的代理对象陷阱
std::vector<bool></bool> 返回的是 std::vector<bool>::reference</bool>（代理类），不是 bool&，导致无法取地址、不能用于某些泛型算法。更严重的是，它的迭代器行为不符合随机访问要求，std::sort 或 std::lower_bound 可能静默失效。
立即学习“C++免费学习笔记（深入）”；
实操建议：自己封装一个轻量 BitMap 类，底层用 std::vector<uint64_t></uint64_t>，每次操作按 64 位对齐：
class BitMap {
std::vector<uint64_t> data;
size_t size_;
public:
BitMap(size_t n) : size_(n), data((n + 63) / 64, 0) {}
void set(size_t i) {
if (i >= size_) return;
data[i / 64] |= (1ULL << (i % 64));
}
bool test(size_t i) const {
return i < size_ && (data[i / 64] & (1ULL << (i % 64)));
}
};
注意点：
-
i % 64必须用&和，不要用 <code>pow(2, i%64)——后者是浮点运算，极慢且不准 - 构造时
(n + 63) / 64是向上取整，比(n >> 6) + !!(n & 63)更易读且无分支 - 如果需频繁遍历“哪些位为 1”，别用
for(i=0;i<size_ if>——复杂度 O(N)，应改用 <code>__builtin_popcountll扫描每个uint64_t再定位低位
内存映射文件（mmap）加载超大位图时的分页陷阱
当位图大小超过物理内存（如 512GB 位图跑在 64GB 机器上），用 mmap 映射文件看似可行，但 Linux 默认按需调页（demand paging）。首次 set() 某个远端 offset 会触发缺页中断，内核要分配物理页+清零，延迟不可控；更糟的是，若程序崩溃，未 msync 的修改会丢失，而 MAP_PRIVATE 下修改根本不会写回文件。
实操建议：
- 用
MAP_SHARED | MAP_POPULATE标志，让mmap时就预分配并锁定所有页（需 root 权限或vm.locked_memory限制放宽） - 写入前先用
memset对映射区域做一次“触碰”（touch），强制内核分配页框，避免运行时抖动 - 关键逻辑完成后立刻
msync(addr, len, MS_SYNC)，否则断电即丢数据 - 别用
std::vector管理 mmap 内存——它的析构会delete[]，而 mmap 内存必须用munmap
位图去重结果导出：如何避免 std::vector 二次内存爆炸
很多人用位图标记完后，再遍历整个位图，把所有 test(i)==true 的 i push 到 std::vector<int></int>——这等于把稀疏数据又转成稠密数组，若原始去重后只有 10 万个数，却要扫描 10 亿位，效率极低，且 vector 分配可能失败。
正确做法是边标记边收集，或用游程编码（RLE）压缩存储“连续 1 段”：
std::vector<std::pair<size_t, size_t>> ranges; // [start, end]
for (size_t i = 0; i < bm.size(); ) {
if (bm.test(i)) {
size_t start = i;
while (i < bm.size() && bm.test(i)) ++i;
ranges.emplace_back(start, i-1);
} else ++i;
}
这样导出的 ranges 只占几 KB，而非几 GB。后续需要具体数值时，再按需展开——比如只取前 1000 个，就无需解压全部。
容易被忽略的一点：位图本身不保存原始数据语义。如果你去重的是用户手机号哈希值，导出的 i 是哈希后的整数，不是原手机号。必须额外维护哈希 → 原值的反查表，而这部分无法用位图优化，得用 std::unordered_map 或 LevelDB。
