布隆过滤器通过位数组和多个哈希函数判断元素是否存在，插入时将哈希位置设为1，查询时若所有位置均为1则可能存在，否则一定不存在；C++实现使用std::bitset管理位数组，结合字符串哈希或std::hash加盐生成多个哈希值，支持高效插入与查询，但存在误判可能且不支持删除。
布隆过滤器是一种高效的空间节省型数据结构，用于判断一个元素是否可能在集合中。它通过多个哈希函数将元素映射到位数组中，并支持快速查询。C++ 实现布隆过滤器主要包括位数组管理和多个哈希函数的设计。
1. 基本原理与设计思路
布隆过滤器的核心是一个长度为 m 的位数组和 k 个独立的哈希函数。当插入一个元素时，使用 k 个哈希函数计算出 k 个位置，并将这些位置设为 1。查询时检查这 k 个位置是否都为 1，如果有一个是 0，则该元素一定不存在；若全为 1，则元素可能存在（存在误判可能）。
注意：布隆过滤器不支持删除操作（除非使用计数变种），且有一定的误判率。
2. 使用 bitset 和哈希函数实现
下面是一个简单的 C++ 实现示例，使用 std::bitset 存储位数组，并采用字符串哈希方法模拟多个哈希函数：
立即学习“C++免费学习笔记（深入）”；
#include#include #include #include #include class BloomFilter { private: std::bitset<1000000> bits; // 位数组，大小可根据需要调整 int numHashes; // 哈希函数个数 int size; // 位数组大小 // 简单哈希函数：基于字符串和种子生成不同哈希值 size_t hash(const std::string& str, size_t seed) const { size_t hash = seed; for (char c : str) { hash = hash * 31 + c; } return hash % size; } public: BloomFilter(int n_hashes = 5, int bit_size = 1000000) : numHashes(n_hashes), size(bit_size) {} // 插入元素 void insert(const std::string& key) { for (int i = 0; i < numHashes; ++i) { size_t pos = hash(key, i); bits.set(pos); } } // 查询元素是否存在（可能误判） bool mightContain(const std::string& key) const { for (int i = 0; i < numHashes; ++i) { size_t pos = hash(key, i); if (!bits.test(pos)) { return false; // 一定不存在 } } return true; // 可能存在 } };
3. 使用示例
测试代码如下：
int main() {
BloomFilter bf(7, 1000000);
bf.insert("apple");
bf.insert("banana");
bf.insert("cherry");
std::cout << "apple: " << (bf.mightContain("apple") ? "可能在" : "不在") << "\n";
std::cout << "grape: " << (bf.mightContain("grape") ? "可能在" : "不在") << "\n";
return 0;
}输出结果：
apple: 可能在 grape: 不在
注意：即使没有插入 grape，也可能因哈希冲突显示“可能存在”，这就是误判情况。
4. 提升哈希质量的方法
上述实现使用简单乘法哈希，实际应用中可改用更高质量的哈希算法，如 MurmurHash、FNV 或使用标准库中的 std::hash 进行多次扰动：
// 利用 std::hash 并加盐生成多个哈希 templatesize_t combinedHash(const T& key, size_t seed) { std::hash hasher; return hasher(key) ^ (seed + 0x9e3779b9 + (hasher(key) << 6) + (hasher(key) >> 2)); }
这样可以在不依赖第三方库的情况下获得更好的分布效果。
基本上就这些。实现布隆过滤器的关键在于合理选择位数组大小和哈希函数数量，以平衡空间、速度和误判率。
