C++ 数据结构之布隆过滤器

简介

布隆过滤器是一种用于快速判断一个元素是否存在于一个集合中的数据结构。它的空间效率和查询效率都比较高，在某些场景下，它可以代替传统的哈希表。

原理

布隆过滤器的基本原理是：将一个元素映射为多个位数组中的位置。在插入元素时，将这些位置上的值设置为1；在查询元素时，如果这些位置上的值都为1，则认为元素存在于集合中；否则认为元素不存在。（由于哈希函数的不可逆性，可能会出现把不同元素映射到同一位置的情况，因此判断元素不存在是有误差的，但判断元素存在则是准确的）。

为了使误判率尽可能小，布隆过滤器需要用到一个较大的位数组，以及多个不同的哈希函数。一般情况下，哈希函数使用 MurmurHash 或 xxHash 等快速哈希函数即可。

实现

下面介绍一个简单的布隆过滤器的实现。

代码如下：

#include <vector>
#include <cstdlib>
#include <ctime>

class BloomFilter {
public:
    BloomFilter(int n, double p): bit_array_(n), k_(std::log(2) * n / p) {
        srand(time(nullptr));
        for (int i = 0; i < k_; i++) {
            int random_seed = rand();
            hash_seeds_.push_back(random_seed);
        }
    }

    void Add(const std::string& str) {
        for (int i = 0; i < k_; i++) {
            int position = Hash(str, hash_seeds_[i]) % bit_array_.size();
            bit_array_[position] = true;
        }
    }

    bool Query(const std::string& str) const {
        for (int i = 0; i < k_; i++) {
            int position = Hash(str, hash_seeds_[i]) % bit_array_.size();
            if (!bit_array_[position]) {
                return false;
            }
        }
        return true;
    }

private:
    std::vector<bool> bit_array_;
    std::vector<int> hash_seeds_;
    int k_;

    int Hash(const std::string& str, int seed) const {
        unsigned int hash = seed;
        for (int i = 0; i < str.size(); i++) {
            hash = hash * 131 + str[i];
        }
        return hash;
    }
};

这段代码中，我们使用了一个 std::vector<bool> 类型的数组作为位数组，以及一个 std::vector<int> 类型的数组作为哈希种子。

在构造函数中，我们需要指定期望布隆过滤器的大小 n 和误判率 p。根据布隆过滤器的原理，一般情况下需要满足 k = ln(2) * n / p，其中 k 为哈希函数的个数。

随机生成 k 个哈希种子，用来生成 k 个哈希函数。

在插入元素时，通过 k 个哈希函数将元素映射到位数组中。将这些位置上的值设置为 1。

在查询元素时，同样使用 k 个哈希函数将元素映射到位数组中。如果所有位置上的值都为 1，则认为元素存在于集合中；否则认为元素不存在。

示例

下面给出两个使用布隆过滤器的示例。

示例1：URL去重

在爬虫程序中，我们需要对爬取到的每个URL进行去重操作。如果使用一个传统的哈希表来进行去重，需要使用大量的内存来存储这些URL，而且查询速度会较慢。布隆过滤器可以帮助我们在较小的空间和较快的查询速度之间取得平衡。

int main() {
    BloomFilter filter(1000000, 0.001);
    std::string url1 = "https://www.baidu.com";
    std::string url2 = "https://www.baidu.com";
    filter.Add(url1);
    if (filter.Query(url2)) {
        std::cout << "URL already exists." << std::endl;
    } else {
        std::cout << "URL does not exist." << std::endl;
    }
    return 0;
}

在上面的示例中，我们创建了一个布隆过滤器，指定了 1000000 的大小，以及 0.001 的误判率。然后向过滤器中插入了一个名字相同的 URL，并且查询了另一个名字相同的 URL。

示例2：IP黑名单过滤

在网络应用中，我们需要对一些IP地址进行黑名单过滤，防止这些IP地址发起攻击。布隆过滤器可以帮助我们在较小的内存和较快的查询速度之间取得平衡。

int main() {
    BloomFilter filter(1000000, 0.001);
    std::string ip1 = "192.168.0.1";
    std::string ip2 = "192.168.0.2";
    filter.Add(ip1);
    if (filter.Query(ip2)) {
        std::cout << "IP is in blacklist." << std::endl;
    } else {
        std::cout << "IP is not in blacklist." << std::endl;
    }
    return 0;
}

在上面的示例中，我们创建了一个布隆过滤器，指定了 1000000 的大小，以及 0.001 的误判率。然后向过滤器中插入了一个 IP 地址，并且查询了另一个 IP 地址，看它是否在黑名单中。

总结

布隆过滤器是一种空间效率和查询效率都比较高的数据结构，常用于集合判重、黑名单过滤等场景中。使用布隆过滤器需要注意一些参数的设置，以及哈希函数的选择。