C++ 实现高性能的布隆过滤器(Bloom Filter) _ 结合多哈希函数与位图优化逻辑【源码】-C++-PHP中文网

std::bitset不能用于生产级布隆过滤器，因其大小需编译期确定，不支持运行时动态计算位图尺寸，且缺乏线程安全、内存对齐和原子操作支持；应改用对齐的std::vector配合std::atomic实现。

c++ 实现高性能的布隆过滤器(bloom filter) _ 结合多哈希函数与位图优化逻辑【源码】

因为 std::bitset 大小必须在编译期确定，而实际场景中布隆过滤器的位图大小（m）取决于预期元素数 n 和误判率 p，只能运行时计算。硬编码尺寸会导致内存浪费或容量不足。

更关键的是，std::bitset::test() 和 std::bitset::set() 虽然快，但缺乏对多线程并发写入的安全控制，也没有对齐优化——现代 CPU 对未对齐的 64 位原子操作会降级为锁总线，严重拖慢吞吐。

用 std::vector<uint64_t></uint64_t> 手动管理位图，按 64 位对齐分配，配合 std::atomic<uint64_t></uint64_t> 实现无锁 set（仅限单 writer 多 reader 场景）
若需多 writer 安全，改用 std::atomic<uint64_t>::fetch_or()</uint64_t>，但要注意：它不保证位图操作的幂等性，重复插入同一元素可能触发多次原子操作，性能略降
避免用 std::vector<bool></bool> —— 它是特化代理类，operator[] 返回临时 proxy 对象，无法用于原子操作，且迭代器行为不符合直觉

布隆过滤器质量不取决于“哈希函数个数”，而取决于 k 个哈希值在 [0, m) 区间内是否均匀、独立分布。直接调用 std::hash<t></t> 一次再线性扰动（如 h1 + i * h2）容易产生相关性，尤其当 h2 % m == 0 时退化为单点命中。

推荐用 “Double Hashing + MurmurHash3 派生” 方案：先用 MurmurHash3_x64_128 计算 128 位哈希，拆成两个 64 位整数 h1、h2，然后生成 k 个位置：

for (size_t i = 0; i

布隆过滤器天然允许 false positive，但绝不允许 false negative。这意味着：contains(x) 必须看到 insert(x) 写入的所有位，哪怕写入尚未完成。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

典型错误是把 insert 实现成 “读-改-写” 循环（如先 load 一个 uint64_t，修改对应 bit，再 store 回去），这在多线程下会丢失其他线程的并发写入。

正确做法：每个 insert 对每个目标位使用 std::atomic<uint64_t>::fetch_or(bit_mask)</uint64_t>，确保位设置是原子的
contains 可以用普通 load（非原子），但必须用 memory_order_acquire 保证看到之前所有 fetch_or 的结果；或者干脆全用 memory_order_relaxed —— 因为即使短暂看到旧值，也只是延迟返回 true，不破坏语义
注意：fetch_or 对 uint64_t 的原子性依赖 CPU 支持（x86-64 原生支持），ARM64 需确认编译器生成 LDAXR/STLXR 序列；GCC/Clang 在 -march=native 下通常能正确处理

布隆过滤器不是动态容器 —— 它没有存储原始元素，无法 rehash 迁移。一旦初始化 m_ 和 k_，就不可更改。试图“扩容”只会让旧位图失效，新插入元素查不到、老元素也查不准。

真实系统中应对数据规模增长的方案只有两个：

预估上限，一次性分配足够大的位图（例如按 10 倍峰值预估，用 mmap + MAP_POPULATE 提前分配物理页，避免 runtime 缺页中断）
用分层结构：底层多个固定大小布隆过滤器（如每个 1MB），外层用一致性哈希路由 key 到某个 filter；过期时整体淘汰某一层，而非单个 filter resize
绝对不要在构造后调用 resize() 并 memcpy 位图 —— 位偏移映射关系已变，所有查询结果不可信

最常被忽略的一点：布隆过滤器的误判率是理论值，实际受哈希质量、内存对齐、CPU cache line 争用影响很大；压测时一定要用真实数据分布跑 long-run benchmark，而不是只看公式推导。