布隆过滤器是1970年由布隆提出的一种概率型数据结构，核心作用是快速判断一个元素是否属于某个集合。它不存储元素本身，仅通过位数组和多个哈希函数来实现判断逻辑，在C++的高并发、大数据量场景中应用十分广泛，比如缓存穿透防护、爬虫URL去重等场景都能看到它的身影。
布隆过滤器的核心原理
布隆过滤器的底层结构是一个长度为m的位数组，初始时所有位都设为0。当要添加一个元素时，会使用k个不同的哈希函数对该元素进行计算，得到k个哈希值，将位数组中对应下标的位都设为1。当要判断一个元素是否存在时，同样用这k个哈希函数计算哈希值，检查对应位是否都为1：如果有任意一位为0，说明元素一定不存在；如果所有位都为1，说明元素可能存在，因为可能存在哈希冲突导致其他元素把这些位设成了1。
核心特性说明
- 空间效率极高：不需要存储元素本身，仅用位数组存储标记，相比哈希表等结构节省大量空间
- 查询速度极快：仅需k次哈希计算和位数组访问，时间复杂度为O(k)
- 存在误判率：只能保证元素不存在的判断是绝对准确的，存在的判断有一定概率错误
- 不支持删除操作：因为多个元素可能共享同一个位，直接清零会影响其他元素的判断结果
C++实现布隆过滤器示例
下面我们用C++实现一个简单的布隆过滤器，包含添加元素和判断元素是否存在两个核心功能，使用三个常见的哈希函数来模拟多哈希计算逻辑。
#include <iostream>
#include <vector>
#include <string>
#include <functional>
// 简单的布隆过滤器实现
class BloomFilter {
private:
int m; // 位数组长度
int k; // 哈希函数个数
std::vector<bool> bitArray; // 位数组
// 三个不同的哈希函数
int hash1(const std::string& str) {
std::hash<std::string> hasher;
return hasher(str) % m;
}
int hash2(const std::string& str) {
int hash = 0;
for (char c : str) {
hash = (hash * 31 + c) % m;
}
return hash;
}
int hash3(const std::string& str) {
int hash = 0;
for (char c : str) {
hash = (hash * 131 + c) % m;
}
return hash;
}
public:
// 构造函数，初始化位数组长度和哈希函数个数
BloomFilter(int bitSize, int hashCount) : m(bitSize), k(hashCount) {
bitArray.resize(m, false);
}
// 添加元素到布隆过滤器
void add(const std::string& element) {
int idx1 = hash1(element);
int idx2 = hash2(element);
int idx3 = hash3(element);
bitArray[idx1] = true;
bitArray[idx2] = true;
bitArray[idx3] = true;
}
// 判断元素是否可能存在
bool contains(const std::string& element) {
int idx1 = hash1(element);
int idx2 = hash2(element);
int idx3 = hash3(element);
// 只要有一个位为false，就说明元素一定不存在
if (!bitArray[idx1] || !bitArray[idx2] || !bitArray[idx3]) {
return false;
}
return true;
}
};
int main() {
// 创建布隆过滤器，位数组长度1000，3个哈希函数
BloomFilter bf(1000, 3);
// 添加元素
bf.add("apple");
bf.add("banana");
bf.add("orange");
// 判断元素是否存在
std::cout << "判断apple是否存在: " << (bf.contains("apple") ? "可能存在" : "一定不存在") << std::endl;
std::cout << "判断grape是否存在: " << (bf.contains("grape") ? "可能存在" : "一定不存在") << std::endl;
return 0;
}
布隆过滤器的参数选择
布隆过滤器的误判率和两个核心参数密切相关：位数组长度m和哈希函数个数k。当元素数量n固定时，m越大误判率越低，k也有一个最优值，过多的哈希函数会增加位数组的置位速度，反而可能提升误判率。通常可以通过公式计算最优参数：
- 最优哈希函数个数k = (m/n) * ln2
- 误判率p ≈ (1 - e^(-kn/m))^k
实际开发中可以根据可接受的误判率来反推需要的位数组长度，再计算对应的哈希函数个数。
适用场景与注意事项
布隆过滤器适合用在可以接受一定误判、不需要删除元素、需要快速判断存在性的场景，比如：
- 缓存系统防护缓存穿透，先判断请求的数据是否存在，不存在直接返回，避免查询数据库
- 爬虫系统URL去重，避免重复爬取相同的页面
- 分布式系统判断数据是否存在于某个分片，减少跨分片查询
需要注意的是，如果业务场景要求绝对准确的存在性判断，或者需要频繁删除元素，布隆过滤器就不适用了，这类场景可以选择计数布隆过滤器或者Cuckoo过滤器等变种结构。