布隆过滤器通过位数组和多个哈希函数判断元素是否存在，C++中可用vector<bool>和std::hash实现，插入时将哈希位置设为1，查询时若所有位均为1则可能存在，允许误判但不漏判。
布隆过滤器（Bloom Filter）是一种空间效率高、查询速度快的概率型数据结构，用于判断一个元素是否可能在集合中。它允许一定的误判率（即把不在集合中的元素误判为存在），但不会将存在的元素漏判。C++ 中可以通过位数组和多个哈希函数来实现布隆过滤器。
基本原理与设计思路
布隆过滤器的核心是一个长度为 m 的位数组 bitset，初始时所有位都为 0。同时定义 k 个独立的哈希函数，每个函数可以将输入元素映射到位数组的一个位置。
当插入一个元素时：
- 用 k 个哈希函数计算出 k 个位置
- 将位数组中这 k 个位置都设为 1
当查询一个元素是否存在时：
立即学习“C++免费学习笔记（深入）”；
- 同样计算出 k 个位置
- 如果这些位置中有任意一位是 0，则该元素一定不存在
- 如果所有位都是 1，则该元素可能存在（可能是误判）
核心组件实现
在 C++ 中，我们可以使用 std::vector<bool> 或 std::bitset 来表示位数组。考虑到动态大小，vector<bool> 更灵活。
对于哈希函数，可以使用 STL 提供的 std::hash 模板，并通过加盐或扰动方式生成多个不同的哈希值。
// 示例：使用 std::hash 和扰动生成多个哈希
size_t hash1 = std::hash<T>{}(value);
size_t hash2 = hash1 * 0x9e3779b9 + 0xabcdef12;
for (int i = 0; i < k; ++i) {
size_t combined_hash = hash1 + i * hash2;
size_t index = combined_hash % bitset_size;
bit_array[index] = true;
}
C++ 实现代码示例
以下是一个通用的布隆过滤器模板类实现：
#include <iostream>
#include <vector>
#include <functional>
#include <cmath>
template <typename T>
class BloomFilter {
private:
std::vector<bool> bit_array;
size_t size;
size_t hash_count;
public:
explicit BloomFilter(size_t n, double fpp) {
// n: 预期元素数量，fpp: 可接受误判率
size = static_cast<size_t>(-n * log(fpp) / (log(2)*log(2)));
hash_count = static_cast<size_t>(size * log(2) / n);
bit_array.resize(size, false);
}
void insert(const T& value) {
size_t h1 = std::hash<T>{}(value);
size_t h2 = h1 * 0x9e3779b9 + 0xabcdef12;
for (size_t i = 0; i < hash_count; ++i) {
size_t combined_hash = h1 + i * h2;
size_t index = combined_hash % size;
bit_array[index] = true;
}
}
bool mightContain(const T& value) const {
size_t h1 = std::hash<T>{}(value);
size_t h2 = h1 * 0x9e3779b9 + 0xabcdef12;
for (size_t i = 0; i < hash_count; ++i) {
size_t combined_hash = h1 + i * h2;
size_t index = combined_hash % size;
if (!bit_array[index]) {
return false;
}
}
return true;
}
};
使用示例与注意事项
下面是一个简单使用示例：
int main() {
BloomFilter<std::string> bf(1000, 0.01); // 支持1000个元素，误判率1%
bf.insert("hello");
bf.insert("world");
std::cout << std::boolalpha;
std::cout << bf.mightContain("hello") << "\n"; // true
std::cout << bf.mightContain("test") << "\n"; // 可能为 false 或 true（误判）
return 0;
}
注意点：
- 布隆过滤器不支持删除操作（除非使用计数版本 Counting Bloom Filter）
- 哈希函数的数量和位数组大小需根据预期元素数量和误判率计算
- std::hash 对某些类型可能不够均匀，可考虑自定义更强哈希
- vector<bool> 是特化版本，行为类似位集，适合节省空间
基本上就这些。实现一个高效可靠的布隆过滤器关键在于合理选择参数和哈希策略，C++ 提供了足够灵活的工具来完成这一任务。
