布隆过滤器是一种空间高效、概率型的数据结构，通过多个哈希函数将元素映射到位数组的多个位置并置1，查询时仅当所有对应位均为1才判定“可能存在”，否则“肯定不存在”，其核心是接受哈希冲突、利用多哈希降低误判率，而非解决冲突。
布隆过滤器不是“解决”哈希冲突，而是**接受冲突、利用多个哈希函数降低误判概率**。它不追求 100% 准确，只保证：查不到 = 绝对不存在；查到了 = 可能存在。这点必须先厘清，否则所有实现都会跑偏。
为什么 std::bitset 不能直接用于字符串去重
因为 std::bitset 只支持编译期确定大小的整型索引，比如 bitset 只能存 0~999 的整数。字符串没有天然整型 ID，强行用 hash(str) % N 映射，单个哈希函数一撞就误判——比如 "user123" 和 "admin456" 算出同一个余数，置位后 test("admin456") 就会返回 true，哪怕它根本没插入过。
常见错误现象：
- 插入 10 万个用户名，
test("fake")却返回true - 误判率随数据量增长陡升，100 万后接近 50%
所以必须用多个独立哈希函数，让每个字符串至少有 k 个“指纹位”。只有这 k 个位全为 1，才认为“可能在”。
立即学习“C++免费学习笔记（深入）”；
三个哈希函数怎么选才靠谱
不能随便写 std::hash<string>()</string> 调三次——C++ 标准库的 std::hash 在不同编译器/版本下结果不一致，部署到线上可能全乱。得用确定性哈希算法，比如 BKDRHash、DJBHash、APHash。
实操建议：
- 模板参数显式传入三个哈希类：
BloomFilter - 每个哈希类必须重载
operator()，返回size_t，且对同一输入永远返回相同值 - 避免用
time()或随机盐值，布隆过滤器要求可序列化、跨进程一致
示例片段（非完整）：
struct BKDRHash {
size_t operator()(const string& s) const {
size_t hash = 0;
for (char c : s) hash = hash * 131 + c;
return hash;
}
};布隆过滤器长度 N 和哈希个数 k 怎么定
N 不是拍脑袋定的。开太小，位图很快全被置 1，所有 test() 都返回 true；开太大，内存浪费，且 k 个哈希位分散导致漏判增多。k 也不是越多越好——k=1 时误判率高；k=10 时计算开销翻倍，但误判率下降边际效益极低。
工程上直接套公式：
若预计插入 n 个元素，容忍误判率 p，则最优 k ≈ ln(2) × N/n，最优 N ≈ −n × ln(p) / (ln(2))²
但更简单的是用经验值：
- n = 100 万，p = 1% → N ≈ 9.6M bit（约 1.2MB），k = 7
- n = 1 亿，p = 0.1% → N ≈ 1.4G bit（约 175MB），k = 10
- 实际常把 N 定为 2 的幂（如
1 ），方便取模用位运算 <code>& (N-1)
注意：std::bitset 不支持运行时大小，必须用 vector<char></char> 或 vector<uint64_t></uint64_t> 手动管理位数组。
为什么布隆过滤器不能安全 reset
因为多个字符串可能共用同一个比特位。比如 "alice" 和 "bob" 都让第 1024 位为 1，此时调用 reset("alice") 把第 1024 位置 0，test("bob") 就会错报 false —— 它明明存在，却被“删掉”了。
想支持删除？只能升级为计数布隆过滤器（Counting Bloom Filter）：
- 每个位换成 4-bit 计数器（0~15），
set()时对应位置 +1，reset()时 -1 - 代价是内存翻 4 倍，且计数器会溢出（15→0），导致误判
- 绝大多数场景（如 URL 去重、用户注册检测）根本不需要 delete，硬加只会拖慢吞吐、引入 bug
真正容易被忽略的一点：布隆过滤器一旦构建完成，**所有哈希函数和位图大小就锁死了**。扩容 = 重建，无法增量 resize。线上服务做热更新时，必须预留双 buffer 或灰度切换机制。
