C++简单实现布隆过滤器

布隆过滤器是一种空间效率高、适用于大规模数据集的概率性数据结构。它可以帮助快速判断一个元素是否可能存在于一个集合中，以及可能不存在于集合中（有一定的误判率）。

原理解释

1. 位数组（Bit Array）：布隆过滤器内部使用一个比特数组（通常初始化为全0），该数组通常较大。在C++代码示例中，我们使用了 std::bitset<1000000> 来表示比特数组，但实际应用中可根据需求调整大小。
2. 哈希函数（Hash Functions）：布隆过滤器使用多个不同的哈希函数。在代码示例中，我们使用了三个哈希函数（hash1、hash2、hash3）。这些哈希函数会将输入的元素映射到比特数组上的位置。通过多个哈希函数，可以减少冲突的可能性。
3. 插入元素：当要向布隆过滤器中插入一个元素时，首先对该元素进行多次哈希映射（使用多个哈希函数），然后将对应的比特数组位置标记为1。
4. 检查元素：当要检查某个元素是否存在于布隆过滗器时，同样使用多个哈希函数对目标元素进行哈希映射，并检查对应的比特数组位置是否均为1。如果其中有任何一个位置为0，则该元素肯定不存在于布隆过滤器中；如果所有位置均为1，则该元素可能存在于布隆过滤器中。

性能与误判率

• 性能：布隆过滤器的查询和插入操作效率很高，因为它们只涉及一组位运算和哈希计算。
• 误判率：由于多个元素可能映射到同一位，以及哈希冲突的存在，布隆过滤器在确定元素“可能存在”时，可能会产生一定的误判率。这意味着，当布隆过滤器认为元素存在时，实际上可能并不存在；但当认为元素不存在时，那么元素一定不存在。

布隆过滤器通常用于缓存、大规模数据处理和网络路由等领域，以快速定位哪些数据值得进一步详细检查。

下面是一个用 C++ 实现的简单布隆过滤器示例。请注意，这只是一个简单的演示，并不适用于生产环境。在实际情况下，您可能需要更多的错误检测和容错处理。

#include <bitset>
#include <functional>

class BloomFilter {
private:
    std::bitset<1000000> bit_array; // 位数组大小为 1000000
    std::hash<std::string> hash1;
    std::hash<std::string> hash2;
    std::hash<std::string> hash3;

public:
    void add(const std::string& item) {
        size_t hashVal1 = hash1(item) % 1000000;
        size_t hashVal2 = hash2(item) % 1000000;
        size_t hashVal3 = hash3(item) % 1000000;

        bit_array[hashVal1] = 1;
        bit_array[hashVal2] = 1;
        bit_array[hashVal3] = 1;
    }

    bool possiblyContains(const std::string& item) {
        size_t hashVal1 = hash1(item) % 1000000;
        size_t hashVal2 = hash2(item) % 1000000;
        size_t hashVal3 = hash3(item) % 1000000;

        return bit_array[hashVal1] && bit_array[hashVal2] && bit_array[hashVal3];
    }
};

int main() {
    BloomFilter filter;
    filter.add("apple");
    filter.add("banana");

    std::cout << filter.possiblyContains("apple") << std::endl;  // 输出 1 (true)
    std::cout << filter.possiblyContains("grape") << std::endl;  // 输出 0 (false)

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

该示例中使用了位集来表示布隆过滤器的位数组。您可以根据需求进行调整，比如更改位数组的大小、哈希函数等。