C++实现哈希冲突的布隆过滤器算法 _ 海量数据过滤策略【详解】-C++-PHP中文网

布隆过滤器是一种空间高效、概率型的数据结构，通过多个哈希函数将元素映射到位数组的多个位置并置1，查询时仅当所有对应位均为1才判定“可能存在”，否则“肯定不存在”，其核心是接受哈希冲突、利用多哈希降低误判率，而非解决冲突。

c++实现哈希冲突的布隆过滤器算法 _ 海量数据过滤策略【详解】

布隆过滤器不是“解决”哈希冲突，而是**接受冲突、利用多个哈希函数降低误判概率**。它不追求 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，才认为“可能在”。

三个哈希函数怎么选才靠谱

不能随便写 std::hash() 调三次——C++ 标准库的 std::hash 在不同编译器/版本下结果不一致，部署到线上可能全乱。得用确定性哈希算法，比如 BKDRHash、DJBHash、APHash。

实操建议：

模板参数显式传入三个哈希类：BloomFilter
每个哈希类必须重载 operator()，返回 size_t，且对同一输入永远返回相同值
避免用 time() 或随机盐值，布隆过滤器要求可序列化、跨进程一致

示例片段（非完整）：

C++14

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

下载

struct BKDRHash {
    size_t operator()(const string& s) const {
        size_t hash = 0;
        for (char c : s) hash = hash * 131 + c;
        return hash;
    }
};