Bitmap不能直接用于任意字符串去重，因其本质仅支持非负整数ID的判重；字符串需先经稳定哈希映射为稠密整数，否则会引发哈希碰撞、编码歧义等bug。
Bitmap 位图为什么不能直接用于任意字符串去重
Bitmap 本质是用 1 位表示一个整数是否存在，它只适合处理**非负整数集合**。如果你手头是手机号、UUID、URL 或中文文本这类字符串，直接套用 std::vector<bool></bool> 或 std::bitset 会编译失败或逻辑错乱——因为没有从字符串到比特下标的映射关系。
常见错误现象：error: no match for 'operator[]' (operand types are 'std::bitset' and 'std::string')
- 必须先做哈希转换：把原始数据映射成
size_t范围内的整数（如用std::hash<:string>{}(s)</:string>） - 哈希后需取模压缩到 Bitmap 容量内（
index = hash_value % bitmap_size），但要注意哈希冲突导致误判 - 若要求**零误判**（如金融类去重），Bitmap 单独不够，得升级为布隆过滤器（Bloom Filter）或配合哈希表回查
如何用 std::vector<uint8_t></uint8_t> 手动实现可扩容 Bitmap
std::bitset 大小编译期固定，std::vector<bool></bool> 虽可变长但标准未保证内存连续且部分编译器对其特化不友好；生产环境更推荐用 std::vector<uint8_t></uint8_t> + 位运算手动管理。
示例关键操作：
立即学习“C++免费学习笔记（深入）”；
class Bitmap {
std::vector<uint8_t> data;
size_t capacity; // 总 bit 数
public:
Bitmap(size_t bits) : capacity(bits), data((bits + 7) / 8, 0) {}
void set(size_t i) {
if (i >= capacity) return;
data[i / 8] |= (1U << (i % 8));
}
bool test(size_t i) const {
if (i >= capacity) return false;
return data[i / 8] & (1U << (i % 8));
}
};
- 用
uint8_t避免vector<bool></bool>的代理迭代器陷阱，确保&data[0]可直接传给 SIMD 或 mmap 内存映射 - 容量单位统一用 bit 数（不是字节数），构造时自动向上对齐到字节边界
- 注意
i % 8和1U 中的 <code>U后缀，防止左移超过int位宽引发未定义行为
查找效率瓶颈真正在哪：Cache Line 与访存模式
很多人以为“位图快是因为 O(1)”，但实测发现吞吐卡在每秒几百万次 test() 就上不去——问题不在算法，而在 CPU 缓存行（Cache Line）争用和随机访存。
- 单次
test(i)只读 1 字节中的 1 bit，但 CPU 每次加载整个 64 字节 Cache Line；若热点数据分散在不同 Line，缓存命中率骤降 - 解决思路不是换算法，而是批量处理：把一批待查 key 哈希后排序，按字节地址分组（
i/8相同的归一组），再用_mm256_loadu_si256一次加载 32 字节做向量化测试 - 如果 key 流具有局部性（如日志中连续 IP 段），可预取相邻字节：
__builtin_prefetch(&data[(i+64)/8], 0, 3)
海量数据落地时绕不开的 mmap + 文件分片
内存中放不下 100 亿级 Bitmap（约 1.25 GB）？别急着上 Redis 或数据库——直接用 mmap 把文件当内存用，配合分片规避单文件过大问题。
- 每个分片控制在 128 MB 以内（即 10^9 bit），对应文件名如
bitmap_001.dat，用index % shard_count定位分片 - 打开文件后调用
mmap(nullptr, len, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0)，返回指针可直接当uint8_t*用 - 务必检查
mmap返回值是否为MAP_FAILED，且在进程退出前调用msync()确保落盘，否则断电=丢数据
真正难的是哈希分布偏斜——某个分片被写满而其他空闲，这需要运行时监控各分片 popcount 并动态调整分片策略，不是加个锁就能解决的事。
