不能直接用std::set或unordered_set替代布隆过滤器，因其内存开销大、查询延迟高；布隆过滤器用bit数组+多哈希，空间仅为unordered_set的1/10，操作均为O(k)，但存在误判且不支持删除。
为什么不能直接用 std::set 或 unordered_set 替代布隆过滤器
因为内存开销和查询延迟不满足场景需求——布隆过滤器用固定大小的 bit 数组 + 多个哈希函数，空间占用通常只有 unordered_set 的 1/10 甚至更低，且所有操作都是 O(k)（k 是哈希函数个数），没有动态内存分配和指针跳转。但代价是存在误判率（false positive），且不支持删除（标准版本）。如果你要判断“某 URL 是否大概率已爬过”，或“某用户 ID 是否可能在黑名单中”，它比容器类更轻量、更适合嵌入式或高吞吐服务。
手写核心：bit 数组 + k 个独立哈希函数怎么实现
关键不是“写多复杂的哈希”，而是保证 k 个哈希结果在 [0, m) 范围内尽量均匀分布且相互独立。C++11 后推荐复用 std::hash 模板，通过种子扰动生成不同哈希流：
struct BloomFilter {
std::vector<bool> bits;
size_t m; // bit 数组长度
size_t k; // 哈希函数个数
std::vector<size_t> seeds;
<pre class='brush:php;toolbar:false;'>BloomFilter(size_t capacity, double false_positive_rate)
: m(static_cast<size_t>(ceil(-capacity * log(false_positive_rate) / (log(2) * log(2))))),
k(static_cast<size_t>(round((double)m / capacity * log(2)))) {
bits.resize(m, false);
seeds.resize(k);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<size_t> dis;
for (auto& s : seeds) s = dis(gen);
}
template <typename T>
void add(const T& item) {
for (size_t i = 0; i < k; ++i) {
size_t hash = std::hash<T>{}(item) ^ seeds[i];
bits[hash % m] = true;
}
}
template <typename T>
bool may_contain(const T& item) const {
for (size_t i = 0; i < k; ++i) {
size_t hash = std::hash<T>{}(item) ^ seeds[i];
if (!bits[hash % m]) return false;
}
return true;
}};
注意：std::vector<bool></bool> 是特化类型，底层按位存储，但访问 bits[i] 可能有额外封装开销；生产环境可换为 std::vector<uint8_t></uint8_t> + 位运算手动管理，避免迭代器代理对象带来的性能抖动。
立即学习“C++免费学习笔记（深入）”；
常见误判来源：哈希碰撞 + 模运算放大偏斜
即使哈希本身均匀，hash % m 在 m 不是 2 的幂时会引入分布偏差（尤其当哈希值集中在某段时）。解决方式有两个：
- 把
m设为质数（如用筛法预生成附近质数），比 2 的幂更能缓解模偏斜 - 改用双重哈希（
(h1(x) + i * h2(x)) % m）替代多个独立哈希——但这会增加计算成本，且对布隆过滤器收益有限，一般不推荐 - 更实际的做法：用
std::hash对不同类型做适配，比如对std::string直接调用没问题，但对自定义结构体必须提供std::hash<mystruct></mystruct>特化，否则编译失败
插入后查不到？检查这三点
这是最常卡住人的地方，不是逻辑错，而是细节漏：
-
seeds必须在构造时初始化，不能在add()里懒生成——否则每次调用哈希种子不同，插入和查询用的哈希流不一致 - 模板函数
may_contain和add的T类型必须完全一致，比如add("abc")传的是const char[4]，而may_contain("abc")可能推导成const char*，导致哈希值不同 → 查不到 - bit 数组索引用了
hash % m，但hash是size_t，若seeds[i]很大导致溢出（虽然少见），建议用std::hash<size_t>{}(hash) % m</size_t>二次哈希兜底
布隆过滤器最难调的从来不是算法，而是哈希一致性——只要插入和查询走的是同一套哈希路径，它就可靠；一旦类型、种子、模数三者有一处不匹配，误判率就从理论值飙升到接近 100%。
