前言
在上一篇文章中，我们见识了位图（Bitset）在处理海量整型数据时的恐怖统治力：仅需 500MB 内存就能处理 40 亿个整数的查找与去重。
但是，现实工程中我们遇到的往往不是纯数字。比如：
爬虫系统需要对 10 亿个 URL 进行去重。垃圾邮件过滤系统需要判断一个邮箱地址是否在千万级的黑名单中。数据库防止'缓存穿透'，需要快速判断一个查询条件（通常是字符串）是否存在。
URL 和邮箱都是字符串，位图只能存整型，如果用哈希把字符串转成整型存入位图，会遇到极其严重的哈希冲突（不同的字符串算出了同一个整型，导致误判）。
为了在极致压缩空间的同时，尽可能降低字符串映射带来的哈希冲突，1970 年，Burton Howard Bloom 提出了一个绝妙的数据结构——布隆过滤器（Bloom Filter）。
一、布隆过滤器的核心原理
1.1 基本概念
布隆过滤器的本质是：一个极长的位图（Bitset） + 多个相互独立的哈希函数。
空间效率极高：不存储元素本身，只存储映射标记查询结果概率性：判断不存在一定正确，判断存在可能误判
1.2 核心特性
| 特性 | 说明 |
|---|---|
| 假阳性（False Positive） | 可能误判存在的元素为不存在（有概率） |
| 假阴性（False Negative） | 绝不误判不存在的元素为存在（100%准确） |
| 删除操作 | 标准实现不支持删除 |
1.3 工作原理图解
1.3.1 插入元素过程
初始状态：位图全 0 [0][0][0][0][0][0][0][0][0][0]
插入"find"：
哈希函数 1 → 位置 2
哈希函数 2 → 位置 5
哈希函数 3 → 位置 7
结果： [0][1][0][0][1][0][1][0][0][0]
↑ ↑ ↑
h1=2 h2=5 h3=7
1.3.2 查询元素过程
查询"find"：
h1=2(1)、h2=5(1)、h3=7(1) → 全部为 1 → **可能存在**
查询"hello"：
h1=2(1)、h2=5(1)、h3=8(0) → 有一个为 0 → **一定不存在**
核心结论：只要有一个 bit 位为 0，元素一定不存在；全部为 1 时，元素可能存在（可能被其他元素冲突导致）
二、误判率分析与参数选择
2.1 误判率公式
布隆过滤器的误判率与三个参数相关：
m：位图长度（bit 数） n：插入元素个数 k：哈希函数个数
最优哈希函数个数：
k = (m/n) * ln2
最小误判率：
p = (1 - e^(-kn/m))^k ≈ 0.6185^(m/n)
2.2 参数选择指南
| 期望误判率 | m/n 比率 | k 值（哈希函数个数） |
|---|---|---|
| 10% | 4.8 | 3 |
| 1% | 9.6 | 4 |
| 0.1% | 14.4 | 5 |
| 0.01% | 19.2 | 6 |
经验公式：当使用 3 个哈希函数时，位图长度应为元素个数的 4 倍左右（m ≈ 4.2n）。
三、C++ 完整实现
3.1 哈希函数设计
布隆过滤器要求哈希函数彼此独立且均匀分布。这里选用三种经典字符串哈希算法：
#pragma once
#include <bitset>
#include <string>
#include <vector>
namespace bloom_filter {
// 1. BKDRHash - 综合评分最高的字符串哈希算法
struct BKDRHash {
size_t operator()(const std::string& key) {
size_t hash = 0;
for (auto ch : key) {
hash = hash * 131 + ch; // 131 是经验值，有效降低冲突
}
return hash;
}
};
// 2. APHash - 另一种优秀哈希算法
struct APHash {
size_t operator()(const std::string& key) {
size_t hash = 0;
int i = 0;
for (auto ch : key) {
if ((i & 1) == 0) {
hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
} else {
hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
}
++i;
}
return hash;
}
};
// 3. DJBHash - 简洁高效的哈希算法
struct DJBHash {
size_t operator()(const std::string& key) {
size_t hash = 5381; // 5381 是经验初始值
for (auto ch : key) {
hash += (hash << 5) + ch; // hash * 33 + ch
}
return hash;
}
};
}
3.2 布隆过滤器模板类
// BloomFilter 模板参数说明：
// N - 插入元素的预估个数
// X - 每个元素占用位数（m/n 比率），默认 4 表示每个元素占 4 个 bit
// K - 元素类型，默认为 string
// HashFunc1/2/3 - 三个哈希函数
template<size_t N, // 预期插入元素个数
size_t X = 4, // 每个元素占用 bit 数（m/n 比率）
class K = std::string,
class HashFunc1 = bloom_filter::BKDRHash,
class HashFunc2 = bloom_filter::APHash,
class HashFunc3 = bloom_filter::DJBHash>
class BloomFilter {
public:
// 构造函数：初始化位图大小 = N * X
BloomFilter() : _bits(N * X) {}
// 插入元素
void set(const K& key) {
size_t len = N * X;
size_t hash1 = HashFunc1()(key) % len;
size_t hash2 = HashFunc2()(key) % len;
size_t hash3 = HashFunc3()(key) % len;
_bits.set(hash1);
_bits.set(hash2);
_bits.set(hash3); // 如果需要更多哈希函数，可以继续添加
}
// 判断元素是否存在
bool test(const K& key) const {
size_t len = N * X;
size_t hash1 = HashFunc1()(key) % len;
// 只要有一个位为 0，一定不存在
if (!_bits.test(hash1)) {
return false;
}
size_t hash2 = HashFunc2()(key) % len;
if (!_bits.test(hash2)) {
return false;
}
size_t hash3 = HashFunc3()(key) % len;
if (!_bits.test(hash3)) {
return false;
}
// 所有位都为 1，可能存在（有误判概率）
return true;
}
// 重置过滤器
void clear() {
_bits.reset();
}
// 获取位图大小（bit 数）
size_t bit_size() const {
return N * X;
}
// 获取已占用 bit 数
size_t count() const {
return _bits.count();
}
private:
std::bitset<N * X> _bits; // 底层位图
};
}
四、布隆过滤器的进阶讨论
4.1 为什么不支持删除？
布隆过滤器无法直接支持删除操作，原因如下：
假设有两个元素 A 和 B：
A 映射到位置{1, 4, 7}
B 映射到位置{4, 8, 9}
删除 A 时，如果将位置 1、4、7 置 0，会导致：
- 位置 4 被清 0，影响 B 的存在判断
- B 本来存在，现在查询 B 时位置 4 为 0，错误判断 B 不存在
解决方案：使用计数布隆过滤器，每个位置扩展为计数器，插入时+1，删除时-1。但代价是占用更多空间。
4.2 应用场景
| 场景 | 说明 | 示例 |
|---|---|---|
| 缓存穿透防护 | 过滤不存在数据的请求，保护数据库 | Redis + 布隆过滤器 |
| 恶意 URL 检测 | 快速判断 URL 是否在黑名单中 | 浏览器安全功能 |
| 爬虫 URL 去重 | 避免重复爬取相同网页 | 搜索引擎爬虫 |
| 垃圾邮件过滤 | 快速判断发件人是否在黑名单 | 邮件系统 |
| 基因序列分析 | DNA 序列快速匹配 | 生物信息学 |
4.3 性能分析
| 指标 | 值 |
|---|---|
| 插入时间复杂度 | O(k) k 为哈希函数个数 |
| 查询时间复杂度 | O(k) k 为哈希函数个数 |
| 空间复杂度 | m bits m 为位图长度 |
| 误判率 | 可控制在 1% 以下 |
五、总结与思考
5.1 核心思想回顾
哈希 + 位图：用多个哈希函数将元素映射到位图 概率性存在：用空间换时间，容忍可控误判 不可删除：bit 位被多个元素共享
5.2 设计要点
哈希函数选择：BKDRHash、APHash、DJBHash 等独立均匀的哈希函数 参数平衡：根据 n（元素个数）和 p（期望误判率）计算 m（位图大小）和 k（哈希函数个数） 空间计算：m ≈ 4.2n（k=3 时），每个元素约占用 4bit
5.3 优缺点对比
| 优点 | 缺点 |
|---|---|
| 空间效率极高 | 存在误判率 |
| 插入查询 O(k) 快速 | 不支持删除 |
| 不存储元素本身（安全） | 不能遍历元素 |
| 适合海量数据 | 需要预先估计数据量 |
布隆过滤器是哈希与位图思想的完美结合，它用一个精妙的概率模型解决了海量数据判重的难题。从理论到实践，从单机到分布式，布隆过滤器在大数据领域扮演着不可或缺的角色。
