Bloom Filter是一种空间高效的概率型数据结构，用于判断元素“可能在集合中”或“绝对不在”，仅用位数组和多个哈希函数实现，支持add()和contains()，但不支持删除，存在可控误判率。
什么是Bloom Filter？为什么用C++实现
Bloom Filter 是一种空间高效的概率型数据结构，用于快速判断一个元素是否“可能在集合中”或“绝对不在集合中”。它不存实际元素，只用少量比特位和多个哈希函数做标记，因此内存占用极小，但存在可控的误判率（false positive），且不支持删除。C++适合实现它，因为能直接控制内存布局、位操作和模板泛型，避免运行时开销。
核心设计：位数组 + 多哈希函数
关键组件只有两个：一个动态位数组（bit array） 和 若干个独立哈希函数。假设位数组长度为 m，插入 n 个元素，用 k 个哈希函数，则最优 k ≈ (m/n) ln2，误判率 ≈ (1 − e−kn/m)k。
- 用
std::vector实现位数组，按 64 位整数分块，用位运算（&,|,>>,）高效读写单个 bit - 哈希函数推荐用
std::hash配合不同种子（如乘以质数再异或），或使用 MurmurHash3 的变体，确保分布均匀 - 对每个元素计算 k 个哈希值，并对 m 取模，得到 k 个位置，全部置为 1
标准接口与关键实现细节
一个实用的 Bloom Filter 类至少应支持 add()、contains() 和 size()。注意以下易错点：
-
位索引计算：哈希值 % m 可能较慢，可用
hash & (m-1)替代——但要求 m 是 2 的幂，此时需向上取最近的 2 的幂 -
线程安全：默认不加锁；若需并发写入，可在
add()中用原子操作（std::atomic_ref或fetch_or）更新对应 word -
模板化支持任意类型：通过
std::hash要求 T 可哈希；对字符串等大对象，可加 move 语义或引用传参减少拷贝 -
不提供
remove()：因为多个元素可能共用同一位，清除会破坏其他元素的存在性
简单可运行示例（无依赖，C++17）
下面是一个轻量级实现的核心骨架（省略异常处理和完整构造逻辑）：
templateclass BloomFilter { std::vector bits; size_t m; // total bits size_t k; // hash functions count std::vector seeds = {13, 37, 61, 109, 181}; // example seeds size_t hash(const T& x, size_t seed) const { auto h = std::hash{}(x); return (h ^ (h >> 32)) * seed; } public: BloomFilter(size_t capacity, double false_positive_rate = 0.01) : m{std::max(static_cast
(1), static_cast (-capacity log(false_positive_rate) / (log(2)log(2))))}, k{std::max(1UL, static_cast (m / capacity * log(2)))} { m = 1ULL void add(const T& x) {for (size_t i = 0; i < k && i < seeds.size(); ++i) { size_t pos = hash(x, seeds[i]) & (m - 1); size_t word_idx = pos / 64; size_t bit_idx = pos % 64; bits[word_idx] |= (1ULL << bit_idx); } } bool contains(const T& x) const { for (size_t i = 0; i < k && i < seeds.size(); ++i) { size_t pos = hash(x, seeds[i]) & (m - 1); size_t word_idx = pos / 64; size_t bit_idx = pos % 64; if (!(bits[word_idx] & (1ULL << bit_idx))) return false; } return true; }
};
用法：
BloomFilter<:string> bf(10000, 0.02); bf.add("hello"); assert(bf.contains("hello"));基本上就这些。它不复杂但容易忽略位对齐、哈希分布和误判率估算——调好这三个，就能在缓存穿透防护、URL 去重、数据库布隆索引等场景里稳稳压低内存开销。
for (size_t i = 0; i < k && i < seeds.size(); ++i) {
size_t pos = hash(x, seeds[i]) & (m - 1);
size_t word_idx = pos / 64;
size_t bit_idx = pos % 64;
bits[word_idx] |= (1ULL << bit_idx);
}
}
bool contains(const T& x) const {
for (size_t i = 0; i < k && i < seeds.size(); ++i) {
size_t pos = hash(x, seeds[i]) & (m - 1);
size_t word_idx = pos / 64;
size_t bit_idx = pos % 64;
if (!(bits[word_idx] & (1ULL << bit_idx)))
return false;
}
return true;
}
