C++怎么实现一个布隆过滤器_C++中用位数组实现的高效概率性数据结构-C++-PHP中文网

C++怎么实现一个布隆过滤器_C++中用位数组实现的高效概率性数据结构

裘德小鎮的故事

发布： 2025-11-22 18:47:17

原创

707人浏览过

布隆过滤器通过位数组和多哈希函数判断元素是否存在，允许误判但不漏判。使用std::vector<bool>实现位存储，插入时将哈希位置设为1，查询时全1则可能存在，否则一定不存在。参数由预期元素数和误判率计算得出，适用于去重、缓存防护等场景。

c++怎么实现一个布隆过滤器_c++中用位数组实现的高效概率性数据结构

布隆过滤器是一种高效的空间节省型概率数据结构，用于判断一个元素是否存在于集合中。它允许一定的误判率（即可能把不存在的元素误判为存在），但不会将存在的元素漏判。C++ 中可以通过位数组和多个哈希函数来实现。

基本原理与设计思路

布隆过滤器的核心是一个长度为 m 的位数组，初始时所有位都为 0。同时定义 k 个独立的哈希函数，每个函数可以将输入元素映射到位数组的一个位置。

当插入一个元素时，用 k 个哈希函数计算出 k 个位置，并将位数组中这些位置设为 1。查询时同样计算 k 个位置，如果所有位置都为 1，则认为元素“可能存在”；只要有一个位置为 0，则元素“一定不存在”。

关键点：

立即学习“C++免费学习笔记（深入）”；

Fliki

高效帮用户创建视频，具有文本转语音功能

151

查看详情

位数组节省内存
k 个哈希函数尽量独立均匀分布
不支持删除操作（标准版本）
存在误判率，但可通过参数调节

使用 std::vector<bool> 实现位数组

C++ 中 std::vector<bool> 是特化模板，底层以位为单位存储，非常适合实现布隆过滤器。

#include <vector>
#include <string>
#include <functional>
#include <cmath>

class BloomFilter {
private:
    std::vector<bool> bits;
    size_t size;
    size_t hashCount;

    // 简单哈希函数：使用 STL 的 hash 并结合乘法扰动
    size_t hash(const std::string& data, size_t seed) const {
        std::hash<std::string> hasher;
        return (hasher(data) ^ seed) % size;
    }

public:
    BloomFilter(size_t expectedElements, double falsePositiveRate) {
        // 根据期望元素数和误判率计算最优参数
        size = static_cast<size_t>(-expectedElements * log(falsePositiveRate) / (log(2) * log(2)));
        hashCount = static_cast<size_t>(size * log(2) / expectedElements);
        size = std::max(size, static_cast<size_t>(1));
        hashCount = std::max(hashCount, static_cast<size_t>(1));

        bits.resize(size, false);
    }

    void insert(const std::string& data) {
        for (size_t i = 0; i < hashCount; ++i) {
            size_t pos = hash(data, i);
            bits[pos] = true;
        }
    }

    bool contains(const std::string& data) const {
        for (size_t i = 0; i < hashCount; ++i) {
            size_t pos = hash(data, i);
            if (!bits[pos]) {
                return false;  // 一定不存在
            }
        }
        return true;  // 可能存在
    }
};

登录后复制

使用示例与注意事项

下面是一个简单的使用例子：

#include <iostream>

int main() {
    BloomFilter bf(1000, 0.01);  // 支持约1000个元素，误判率1%

    bf.insert("apple");
    bf.insert("banana");

    std::cout << bf.contains("apple") << std::endl;     // 输出 1（可能存在）
    std::cout << bf.contains("grape") << std::endl;     // 很可能输出 0
    std::cout << bf.contains("orange") << std::endl;    // 可能误判为1

    return 0;
}

登录后复制

优化建议：