【C++】27. 哈希扩展2 —— 布隆过滤器和海量数据处理
【C++】27. 哈希扩展2 —— 布隆过滤器和海量数据处理
Ronin305
发布于 2025-12-22 13:00:07
发布于 2025-12-22 13:00:07
1. 什么是布隆过滤器
在某些特定场景下，当我们需要处理海量数据（如URL、邮件地址、用户名等非整数数据）并快速判断其是否存在时，传统的位图（BitMap）因其只能处理整数类型而无法适用；而红黑树或哈希表等数据结构虽然可以处理各种数据类型，但当数据量达到亿级时，内存消耗将变得不可接受。这时，布隆过滤器（Bloom Filter）便成为了一个理想的解决方案。
布隆过滤器是由计算机科学家Burton Howard Bloom在1970年发表的一篇名为《Space/Time Trade-offs in Hash Coding with Allowable Errors》的论文中首次提出的。它是一种空间效率极高的概率型数据结构，具有以下显著特点：
- 极高的插入和查询效率（时间复杂度均为O(k)，k为哈希函数数量）
- 占用内存空间极小
- 能够确定性地判断某个元素"绝对不存在"
- 对于"可能存在"的判断有一定的误判率
工作原理
布隆过滤器的核心实现包含三个关键组件：
- 一个长度为m的位数组（Bit Array），初始所有位都置为0
- k个不同的哈希函数，每个函数都能将输入元素映射到位数组的某个位置
其工作流程如下：
- 添加元素：
- 将元素通过k个哈希函数计算出k个哈希值
- 将位数组中这k个位置的值都置为1
- 例如：添加元素"hello"，通过3个哈希函数得到位置3、5、10，则将这些位置置1
- 查询元素：
- 同样用k个哈希函数计算出k个位置
- 检查这些位置是否都为1：
- 如果有任一位置为0，则确定该元素不存在（100%准确）
- 如果所有位置都为1，则该元素可能存在（有误判概率）
设计特点
布隆过滤器的精妙之处在于：
- 多哈希函数设计：通过多个独立的哈希函数将元素映射到位数组的不同位置，可以显著降低冲突概率。例如使用3个不同的哈希函数（如MurmurHash、FNV、Jenkins等），每个元素会占据3个位。
- 空间与准确率的权衡：
- 位数组越大，误判率越低
- 哈希函数数量需要合理选择（不是越多越好）
- 计算公式：对于n个元素，位数组大小m≈-nlnp/(ln2)^2，最优哈希函数数量k≈(m/n)ln2
- 不可删除性：标准布隆过滤器不支持删除操作，因为多个元素可能共享某些位。若需删除功能，可以使用变种如计数布隆过滤器（Counting Bloom Filter）。
实际应用场景
- 网络爬虫URL去重：
- 存储已爬取的URL，避免重复爬取
- 即使有少量误判（将未爬取的URL误判为已爬取），也只是损失少量页面，不影响整体
- 邮件系统垃圾邮件过滤：
- 存储已知垃圾邮件特征
- 误判表现为将正常邮件误判为垃圾邮件，可通过白名单机制弥补
- 分布式系统缓存穿透防护：
- 在Redis等缓存前设置布隆过滤器
- 先快速判断请求数据是否可能存在，避免大量无效查询穿透到数据库
- 区块链领域：
- 比特币轻客户端使用SPV布隆过滤器来查询相关交易
- 以太坊使用改良的布隆过滤器来高效检索日志
布隆过滤器以其独特的空间效率和概率性特征，在大数据处理领域占据着不可替代的地位，是典型的以准确率换取空间效率的算法设计典范。
2. 布隆过滤器误判率推导
推导过程
说明：本推导涉及概率论、极限、对数运算和求导等数学知识。数学基础较好的读者可以深入理解，其他读者记住结论即可。
基本假设
- m：布隆过滤器的二进制位长度
- n：插入过滤器的元素个数
- k：哈希函数的个数
推导步骤
单个哈希函数将某位设置为1的概率：1/m
单个哈希函数不将某位置为1的概率：1 - 1/m
经过k次哈希后，某位仍不为1的概率：(1 - 1/m)^k
根据极限公式：
lim(m→∞) (1 - 1/m)^m = e^-1
(1 - 1/m)^k ≈ e^(-k/m)插入n个元素后，某位不置为1的概率： (1 - 1/m)^(kn) ≈ e^(-kn/m)
插入n个元素后，某位置为1的概率： 1 - (1 - 1/m)^(kn) ≈ 1 - e^(-kn/m)
查询误判概率（所有k次哈希都命中1的概率）： [1 - (1 - 1/m)^(kn)]^k ≈ (1 - e^(-kn/m))^k
结论公式
布隆过滤器的误判率为：
f(k) = (1 - e^(-kn/m))^k
= (1 - (1/e)^(kn/m))^k参数分析
当k固定时：
- n增加 → 误判率增加
- m增加 → 误判率减小
优化哈希函数数量k： 当m和n固定时，取k = (m/n)ln2可使误判率最低
计算位数组长度m： 给定期望误判率p和插入元素数n：
m = -(n*ln p)/(ln 2)^2以上两个公式的推导过程尤其复杂，这里放两篇博客链接布隆过滤器(Bloom Filter)- 原理、实现和推导_ 布隆过滤器原理-CSDN博客 和[布隆过滤器BloomFilter] 举例说明+证明推导_bloom filter 最佳hash函 数数量 推导-CSDN博客
3. 布隆过滤器代码实现
3.1 哈希函数实现
BKDR哈希 (HashFuncBKDR)
size_t operator()(const std::string& s) {
size_t hash = 0;
for (auto ch : s) {
hash *= 31; // 乘法因子
hash += ch; // 累加字符值
}
return hash;
}- 特点：简单高效，Java字符串默认哈希算法
- 优势：计算速度快，冲突率低
- 因子31：奇质数，减少冲突
AP哈希 (HashFuncAP)
size_t operator()(const std::string& s) {
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++) {
if ((i & 1) == 0) { // 偶数位字符
hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
} else { // 奇数位字符
hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
}
}
return hash;
}- 特点：位运算密集，位置敏感
- 优势：对相似字符串区分度高
- 设计：奇偶位置使用不同位操作增加随机性
DJB哈希 (HashFuncDJB)
size_t operator()(const std::string& s) {
size_t hash = 5381; // 魔术初始值
for (auto ch : s) {
hash = hash * 33 ^ ch; // 乘33后异或
}
return hash;
}- 特点：初始值5381，乘数33
- 优势：快速计算，良好分布性
- 设计：^操作增加比特位变化
3.2 布隆过滤器类模板
模板参数
template<size_t N, // 预期元素数量
size_t X = 5, // 每个元素比特数
class K = string, // 元素类型
class Hash1 = HashFuncBKDR, // 哈希函数1
class Hash2 = HashFuncAP, // 哈希函数2
class Hash3 = HashFuncDJB> // 哈希函数3- 高度可配置：允许用户自定义所有关键参数
- 合理默认值：为常见场景提供优化默认配置
位图计算
private:
static const size_t M = N * X; // 位图大小
RO::bitset<M> _bt; // 底层位图- 空间分配：
M = N × X比特 - 示例：N=100万, X=5 → M=500万比特≈625KB
3.3 核心操作
Set操作 - 添加元素
void Set(const K& key) {
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
_bt.set(hash1);
_bt.set(hash2);
_bt.set(hash3);
}- 使用3个不同哈希函数计算哈希值
- 对位图大小取模得到位位置
- 将对应位设为1
Test操作 - 检查元素
bool Test(const K& key) {
size_t hash1 = Hash1()(key) % M;
if (!_bt.test(hash1)) return false; // 肯定不存在
size_t hash2 = Hash2()(key) % M;
if (!_bt.test(hash2)) return false; // 肯定不存在
size_t hash3 = Hash3()(key) % M;
if (!_bt.test(hash3)) return false; // 肯定不存在
return true; // 可能存在（可能有误判）
}- 检查第一个哈希位：为0则肯定不存在
- 检查第二个哈希位：为0则肯定不存在
- 检查第三个哈希位：为0则肯定不存在
- 所有位均为1 → 可能存在
X 值的影响分析
不同 X 值下的性能对比
X 值 | 位图大小 | 误判率 (n=N) | 100万元素内存占用 | 特点 |
|---|---|---|---|---|
3 | 3N | ≈ 5% | 375 KB | 内存最小，误判率高 |
5（默认） | 5N | ≈ 2% | 625 KB | 良好平衡 |
8 | 8N | ≈ 0.5% | 1 MB | 低误判率 |
10 | 10N | ≈ 0.1% | 1.25 MB | 极低误判率 |
16 | 16N | ≈ 0.01% | 2 MB | 接近完美但内存大 |
为什么默认 X=5？
经验平衡点：
- 在大多数应用中，2%的误判率是可接受的
- 内存占用与准确率的良好折衷
哈希函数数量匹配：
当使用 k 个哈希函数时，最优 X ≈ k/ln(2)×(-ln(p))
对于 p=0.02（2%误判率）和 k=3：
X ≈ 3 / (0.693) × (-ln(0.02)) ≈ 5.14因此 X=5 接近理论最优值
如何选择合适的 X 值？
考虑因素：
- 应用场景容忍度：
- 爬虫URL去重：可接受较高误判率（X=3-5）
- 安全敏感场景：需要低误判率（X=8-10）
- 内存限制：
- 嵌入式系统：优先小内存（X=3-4）
- 服务器应用：可接受更大内存（X=5-10）
- 元素数量波动：
- 若实际元素可能超过 N，应增加 X
- 保守设计：X = 1.5 × 理论最优值
使用建议：
// 高精度场景（如金融）
BloomFilter<100000, 10> highPrecisionFilter;
// 内存敏感场景（如IoT设备）
BloomFilter<5000, 3> lowMemoryFilter;
// 通用场景（默认）
BloomFilter<1000000> defaultFilter; // 使用X=5X 与其他参数的关系
1. 与哈希函数数量(k)的协同优化
最优 k = (M/n) * ln(2) ≈ 0.7 * (M/n)- 当 X 固定时：
- 增加 k 可降低误判率，但增加计算开销
- 减少 k 降低计算开销，但增加误判率
2. 与实际元素数量(n)的关系
- 当实际元素数 n > N 时：
- 误判率会高于预期
- 解决方案：增加 X 或使用动态布隆过滤器
总结
X 参数是布隆过滤器设计的关键权衡因子：
- 空间效率：X 越小，内存占用越小
- 误判率：X 越大，误判率越低
- 默认值 X=5：在大多数场景提供最佳平衡
- 灵活调整：根据具体需求调整 X 值优化性能
通过合理选择 X 值，可以在可接受的内存消耗下，获得满足业务需求的误判率水平，这正是布隆过滤器在大数据处理中如此强大的原因。
3.4 测试
先来简单测试一下函数功能：
void TestBloomFilter1()
{
BloomFilter<10> bf;
bf.Set("猪八戒");
bf.Set("孙悟空");
bf.Set("唐僧");
cout << bf.Test("猪八戒") << endl;
cout << bf.Test("孙悟空") << endl;
cout << bf.Test("唐僧") << endl;
cout << bf.Test("沙僧") << endl;
cout << bf.Test("猪八戒1") << endl;
cout << bf.Test("猪戒八") << endl;
}运行结果：
测试计算误判率：
这里我们再设计一个公式计算误判率的函数来作比较：
// 获取公式计算出的误判率
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
return p;
}void TestBloomFilter2()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
//BloomFilter<N, 3> bf;
//BloomFilter<N, 10> bf;
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
//std::string url = "https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f&rsv_t=ceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDo&rqlang=en&rsv_enter=1&rsv_dl=ib&rsv_sug3=3&rsv_sug1=2&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=330&rsv_sug4=2535";
//std::string url = "猪八戒";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.Set(str);
}
// v2跟v1是相似字符串集（前缀一样），但是后缀不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v1.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Test(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集 前缀后缀都不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += std::to_string(i + rand());
v1.push_back(url);
}
size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}运行结果：
4. 布隆过滤器删除问题详解
标准布隆过滤器的删除限制
布隆过滤器(Bloom Filter)作为一种高效的空间概率型数据结构，其默认实现不支持删除操作。这是由于布隆过滤器的核心机制决定的：
- 冲突机制：每个元素通过多个哈希函数映射到位数组的不同位置。例如"猪八戒"可能映射到位1、3、5，"孙悟空"可能映射到位3、7、9
- 删除后果：如果删除"孙悟空"并重置位3、7、9为0，那么：
- 位3是"猪八戒"和"孙悟空"的共同映射位
- 后续查询"猪八戒"时，由于位3变为0，会导致误判为不存在
- 这种现象称为"间接删除"或"连带删除"
计数布隆过滤器方案
为解决删除问题，研究者提出了计数布隆过滤器(Counting Bloom Filter)：
- 实现原理：
- 将原来的单一位数组改为计数器数组
- 每个位置使用多位(通常4-8位)存储计数值
- 插入元素时：对应位置计数器+1
- 删除元素时：对应位置计数器-1
- 示例场景：
- 初始状态：所有计数器为0
- 插入"猪八戒"：位1、3、5的计数器变为1
- 插入"孙悟空"：位3、7、9的计数器变为1，其中位3变为2
- 删除"孙悟空"：位3、7、9的计数器-1，位3从2变为1
- 优势：
- 允许安全的删除操作
- 保持空间效率，仅比标准布隆过滤器多占用几倍空间
计数方案的缺陷
计数布隆过滤器并非完美解决方案，存在以下问题：
- 误删风险：
- 删除一个未存储的元素(如"唐僧")时：
- 计算其哈希位置
- 对应计数器减1(可能从1变为0)
- 导致实际存储的元素查询时可能误判为不存在
- 删除一个未存储的元素(如"唐僧")时：
- 空间限制：
- 计数器溢出：若使用4位计数器，最大值为15，频繁插入可能导致溢出
- 解决方案：使用更大位数(如8位)，但会增加空间开销
- 性能影响：
- 计数器操作比位操作更耗时
- 内存访问模式不如位数组紧凑
改进方案
- 定期重建：
- 维护一个操作日志记录所有插入/删除
- 定期(如每天)根据日志重建布隆过滤器
- 优点：保证数据一致性
- 缺点：重建期间服务可能不可用
- 分层布隆过滤器：
- 主过滤器：标准布隆过滤器，只记录存在状态
- 删除列表：记录已删除元素
- 查询时：主过滤器存在且不在删除列表才算存在
- 可删除布隆过滤器(Dynamic Bloom Filter)：
- 使用多个标准布隆过滤器轮换
- 删除时标记到删除列表
- 空间利用率较低但实现简单
5. 海量数据处理问题
5.1 从10亿个整数中找出前100个最大值
这是一个典型的Top K问题，可以通过堆结构高效解决。具体实现方法在我们数据结构"堆"章节中已有详细讲解。TOP-K
5.2 位图相关题目
这些题目在我们讲解位图数据结构的章节中均有涉及。位图
5.3 海量数据查询交集问题解决方案详解：100亿query文件在1GB内存限制下
问题规模与挑战分析
- 数据规模：两个文件各包含100亿条query记录
- 存储需求：每条query平均50字节 → 单个文件500GB，总数据量1TB
- 内存限制：仅1GB可用内存（相当于总数据量的0.1%）
- 核心挑战：传统数据结构（哈希表、红黑树）无法直接处理如此大规模数据
解决方案一：布隆过滤器法（近似算法）
实现原理
- 布隆过滤器构建：
- 创建一个大型布隆过滤器（位数组）
- 将文件A的所有query通过k个哈希函数映射到位数组中
- 将对应位设置为1
- 查询过程：
- 遍历文件B的每个query
- 通过相同的k个哈希函数计算位位置
- 如果所有位均为1 → 判定为"可能存在"（加入结果集）
- 如果有任一位置为0 → 确定不存在（排除）
- 结果特性：
- 零假阴性：确保不会遗漏真实交集
- 存在假阳性：可能包含非交集元素
- 假阳性率可通过位数组大小和哈希函数数量控制
内存优化策略
- 分块处理：
- 将500GB文件划分为50个10GB块
- 每次只处理一个文件块：
- 构建当前块的布隆过滤器
- 扫描整个文件B进行查询
- 合并各块结果
- 参数优化：
- 每个query分配5-8位存储空间
- 使用3-5个独立哈希函数
- 100亿元素总内存需求：6.25-10GB（分块后每块0.125-0.2GB）
适用场景
- 可接受一定误判率的应用（如初步筛选）
- 网络爬虫URL去重
- 垃圾邮件初步过滤
- 缓存穿透防护
优缺点
优势：
- 空间效率高
- 查询速度快（O(k)时间复杂度）
- 不会遗漏真实交集
局限：
- 结果存在假阳性
- 需要后期去重处理
- 分块增加磁盘I/O开销
解决方案二：哈希切分法（精确算法，推荐）
核心思想
使用哈希函数将大文件划分为小文件对，确保：
- 相同query必然落入同编号的小文件
- 不同query可能落入不同小文件
- 只需比较同编号文件对（Ai vs Bi）
实施步骤
第一阶段：文件切分
选择哈希函数：
- 使用高质量哈希函数（如MurmurHash3）
- 确保均匀分布，减少冲突
确定切分份数：
- 计算公式：
切分份数 = 总文件大小 / 目标小文件大小 - 目标小文件大小：≤500MB（考虑哈希表开销）
- 500GB文件 → 约1000份（每份平均500MB）
切分过程：
文件A切分：
query → 哈希函数 → hash_value % 1000 → 写入A_i文件 (i=0..999)
文件B切分：
query → 相同哈希函数 → hash_value % 1000 → 写入B_i文件第二阶段：小文件对处理
处理流程：
for i in range(0, 999):
加载小文件A_i到内存哈希表
遍历小文件B_i的每个query：
if query in 哈希表：
输出到结果文件内存控制：
- 单个小文件≤500MB
- 加载到哈希表后内存占用≤1.5GB
- 实际内存监控：超过阈值则触发异常处理
第三阶段：异常处理（大文件处理）
当小文件过大时（内存不足）：
原因分析： a) 大量重复query → 使用哈希表自动去重 b) 大量不同query（哈希冲突）→ 需要二次切分
二次切分策略：
- 使用不同哈希函数（避免相同冲突）
- 增加切分份数（如100-500份）
- 递归处理子文件对
处理流程：
try:
加载小文件A_i到内存
catch 内存不足异常:
选择新哈希函数H2
将A_i切分为A_i0, A_i1... A_i99 (100份)
将B_i切分为B_i0, B_i1... B_i99
for j in range(0,99):
递归处理(A_ij, B_ij)文件对关键优化技术
- 动态切分策略：
- 根据实际内存调整切分份数
- 公式：
切分份数 = max(文件大小/(内存×0.6), 100)
- 高效哈希函数：
- 一级哈希：64位FNV-1a算法
- 二级哈希：MurmurHash3变种
- 三级哈希：带种子的CityHash
- 内存监控机制：
- 实时跟踪进程内存使用
- 设置安全阈值（如900MB）
- 主动触发异常避免系统崩溃
- 并行处理：
- 不同文件对独立处理 → 天然并行
- 多线程/分布式处理加速
- 线程安全结果写入
适用场景
- 需要精确结果的场景
- 用户行为分析
- 基因组数据比对
- 安全审计日志分析
方案优势
- 100%准确率：无假阳性/假阴性
- 内存高效：通过切分适配任意内存限制
- 可扩展性：
- 支持递归切分处理极端情况
- 易于并行化加速
- 通用性强：适用于各种数据类型
方案对比与选择指南
特性 | 布隆过滤器法 | 哈希切分法 |
|---|---|---|
准确性 | 近似（有假阳性） | 精确 |
内存需求 | 中等（需分块） | 低（自适应） |
磁盘I/O | 中高（多次扫描） | 中等（两次主要I/O） |
实现复杂度 | 简单 | 中等 |
处理时间 | 较短 | 较长 |
最佳适用场景 | 初步筛选/去重 | 精确分析/审计 |
选择建议：
- 优先哈希切分：当需要精确结果时
- 布隆过滤起器：当可接受误判且追求速度时
- 混合策略：先用布隆过滤器快速筛选，再用哈希切分精确处理
性能优化进阶
- 外排序归并：
- 对超大文件对使用外部排序
- 双指针归并查找交集
- 流式处理：
- 较小文件加载到内存
- 流式扫描较大文件
- 内存映射文件：
- 避免数据拷贝开销
- 零拷贝访问磁盘数据
总结
在1GB内存限制下处理100亿query文件的交集问题：
- 哈希切分法是首选解决方案：
- 通过分治策略将问题分解
- 自适应处理不同数据分布
- 保证结果100%准确
- 关键成功因素：
- 高质量哈希函数（确保均匀分布）
- 动态切分策略（适应内存限制）
- 递归异常处理（解决冲突问题）
- 实施要点：
- 初始切分份数：500-2000份
- 小文件大小阈值：≤500MB
- 内存监控阈值：≤900MB
- 二次切分份数：100-500份
该方案不仅适用于query交集问题，还可扩展至海量数据去重、相似度计算、关联分析等多种场景，是大数据处理的核心技术之一。
5.4 处理超过100G的日志文件，其中包含IP地址，如何设计算法找出出现频率最高的IP？以及出现频率前10的IP地址？
解题思路与上题类似：
- 读取日志文件中的每个IP地址
- 使用哈希函数计算：i = HashFunc(IP)%500，将IP分配到对应的Ai小文件中
- 对每个小文件使用map<string, int>统计IP出现次数
- 在统计过程中记录出现次数最多的IP或top10 IP
核心原理：
- 相同IP通过哈希处理后必定进入同一个小文件
- 不会出现同一个IP分散在多个小文件的情况
- 因此对小文件统计的IP频率是准确的
完整代码：
#pragma once
#include <string>
#include <iostream>
#include "bitset.h"
namespace RO
{
struct HashFuncBKDR
{
// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
// 一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子为31。
size_t operator()(const std::string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash *= 31;
hash += ch;
}
return hash;
}
};
struct HashFuncAP
{
// 由Arash Partow发明的一种hash算法。
size_t operator()(const std::string& s)
{
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++)
{
if ((i & 1) == 0) // 偶数位字符
{
hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
}
else // 奇数位字符
{
hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashFuncDJB
{
// 由Daniel J. Bernstein教授发明的一种hash算法。
size_t operator()(const std::string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash = hash * 33 ^ ch;
}
return hash;
}
};
template<size_t N,
size_t X = 5,
class K = string,
class Hash1 = HashFuncBKDR,
class Hash2 = HashFuncAP,
class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % M;
size_t hash2 = Hash2()(key) % M;
size_t hash3 = Hash3()(key) % M;
_bt.set(hash1);
_bt.set(hash2);
_bt.set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % M;
if (!_bt.test(hash1)) return false;
size_t hash2 = Hash2()(key) % M;
if (!_bt.test(hash2)) return false;
size_t hash3 = Hash3()(key) % M;
if (!_bt.test(hash3)) return false;
return true; // 可能存在误判
}
// 获取公式计算出的误判率
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
return p;
}
private:
static const size_t M = N * X;
RO::bitset<M> _bt;
};
void TestBloomFilter1()
{
BloomFilter<10> bf;
bf.Set("猪八戒");
bf.Set("孙悟空");
bf.Set("唐僧");
cout << bf.Test("猪八戒") << endl;
cout << bf.Test("孙悟空") << endl;
cout << bf.Test("唐僧") << endl;
cout << bf.Test("沙僧") << endl;
cout << bf.Test("猪八戒1") << endl;
cout << bf.Test("猪戒八") << endl;
}
void TestBloomFilter2()
{
srand(time(0));
const size_t N = 1000000;
BloomFilter<N> bf;
//BloomFilter<N, 3> bf;
//BloomFilter<N, 10> bf;
std::vector<std::string> v1;
//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
//std::string url = "https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f&rsv_t=ceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDo&rqlang=en&rsv_enter=1&rsv_dl=ib&rsv_sug3=3&rsv_sug1=2&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=330&rsv_sug4=2535";
std::string url = "猪八戒";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.Set(str);
}
// v2跟v1是相似字符串集（前缀一样），但是后缀不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v1.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Test(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集 前缀后缀都不一样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += std::to_string(i + rand());
v1.push_back(url);
}
size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号