一、布隆过滤器
1. 什么是布隆过滤器？
布隆过滤器是一种空间效率极高的概率型数据结构，核心作用是快速判断「一个元素是否存在于集合中」。它的特点可以总结为：
- 说「元素不在」→ 100%准确（绝对没在集合里）；
- 说「元素在」→ 可能误判（有小概率其实不在）；
- 极致省空间（比传统Set/哈希表省几个数量级）。
2. 解决什么问题？
举两个典型场景：
- 缓存穿透：用户查Redis中不存在的key，请求会直接打到数据库，拖垮数据库。用布隆过滤器先判：如果布隆说“不存在”，直接返回；只有说“存在”，才查Redis/数据库。
- 爬虫去重：爬10亿URL，用Set存需要几十GB空间，布隆过滤器只需要几百MB，就能快速判断URL是否已爬过。
3. 工作原理（类比）
想象一个「空白笔记本」（位数组，每页只有0/1，初始全0），再准备3个「盖章器」（哈希函数）：
- 插入元素（比如URL：
https://test.com）：
用3个盖章器分别盖这个URL，得到3个页码（比如10、25、48），把笔记本的10、25、48页都标为1； - 查询元素：
同样用3个盖章器盖URL，得到3个页码；- 只要有一页是0 → 这个URL肯定没插过；
- 全是1 → 可能插过（其他URL的盖章可能刚好覆盖这3页）。
二、布隆过滤器 原理详解
1. 核心组件
- 位数组（Bit Array）：长度为
m，每个位只有0/1，是布隆过滤器的核心存储； - k个独立哈希函数：每个哈希函数能把任意输入（如字符串）映射到
[0, m-1]的整数下标。
2. 核心流程
| 操作 | 步骤 |
|---|---|
| 插入 | 1. 对元素调用k个哈希函数，得到k个下标； 2. 把位数组对应下标位设为1； |
| 查询 | 1. 对元素调用k个哈希函数，得到k个下标； 2. 检查所有下标位： - 有一个0 → 元素不存在； - 全1 → 元素可能存在； |
3. 关键参数（决定误判率）
n：预期要插入的元素总数；p：期望的误判率（比如0.01=1%）；m（位数组长度）：m = -n * ln(p) / (ln2)²（n越大、p越小，m越大）；k（最优哈希函数数）：k = (m/n) * ln2 ≈ 0.693*m/n（k太大/太小都会升高误判率）。
4. 局限性
- 无法删除元素（位数组的位是共享的，删除会影响其他元素）；
- 存在误判（只能降低，无法消除）；
- 需提前预估
n和p（预估不准会导致误判率升高或空间浪费）。
三、C++实现布隆过滤器（一步一步）
步骤1：头文件与基础准备
先引入必要的头文件，定义辅助函数（计算对数、哈希函数）：
#include<iostream>#include<vector>#include<cmath>#include<string>#include<algorithm>// ceil、round// 哈希函数1：BKDR哈希（经典字符串哈希）staticuint64_tBKDRHash(conststd::string&str){uint64_thash=0;for(charc:str){hash=hash*131+c;// 131是常用质数，可替换为31/13131等}returnhash;}// 哈希函数2：AP哈希staticuint64_tAPHash(conststd::string&str){uint64_thash=0;for(size_t i=0;i<str.size();++i){if(i%2==0){hash^=(hash<<7)^c^(hash>>3);}else{hash^=(~((hash<<11)^c^(hash>>5)));}}returnhash;}步骤2：设计布隆过滤器类
核心成员：位数组、位数组长度m、哈希函数个数k；
核心方法：构造函数（计算m/k）、插入、查询。
classBloomFilter{private:std::vector<bool>bits_;// 位数组（vector<bool>是特化类型，省空间）size_t bit_size_;// 位数组长度msize_t hash_num_;// 哈希函数个数kpublic:// 构造函数：传入预期元素数n、期望误判率pBloomFilter(size_t expected_n,doublefalse_positive_p){// 步骤1：计算最优的m（位数组长度）doubleln2=log(2);bit_size_=static_cast<size_t>(ceil(-expected_n*log(false_positive_p)/(ln2*ln2)));// 步骤2：计算最优的k（哈希函数个数）hash_num_=static_cast<size_t>(round((bit_size_/expected_n)*ln2));// 步骤3：初始化位数组（初始全0）bits_.resize(bit_size_,false);// 打印参数（方便调试）std::cout<<"布隆过滤器初始化完成："<<std::endl;std::cout<<"预期元素数："<<expected_n<<std::endl;std::cout<<"期望误判率："<<false_positive_p<<std::endl;std::cout<<"位数组长度m："<<bit_size_<<std::endl;std::cout<<"哈希函数个数k："<<hash_num_<<std::endl;}// 插入元素（字符串类型）voidinsert(conststd::string&key){// 先计算两个基础哈希值，组合出k个哈希值uint64_th1=BKDRHash(key);uint64_th2=APHash(key);// 循环k次，计算每个哈希下标并置1for(size_t i=0;i<hash_num_;++i){// 组合公式：h = h1 + i*h2（避免哈希函数重复）uint64_tpos=(h1+i*h2)%bit_size_;bits_[pos]=true;}}// 查询元素是否存在（返回true=可能存在，false=绝对不存在）boolcontains(conststd::string&key){uint64_th1=BKDRHash(key);uint64_th2=APHash(key);for(size_t i=0;i<hash_num_;++i){uint64_tpos=(h1+i*h2)%bit_size_;// 只要有一个位是0，说明绝对不存在if(!bits_[pos]){returnfalse;}}// 全1，说明可能存在returntrue;}};步骤3：测试代码
验证插入、查询的效果，观察误判/准确的情况：
intmain(){// 初始化布隆过滤器：预期插入100个元素，期望误判率1%BloomFilterbf(100,0.01);// 插入一批URLstd::vector<std::string>urls={"https://www.baidu.com","https://www.google.com","https://www.github.com","https://www.bilibili.com","https://www.zhihu.com"};for(constauto&url:urls){bf.insert(url);}// 测试1：查询已插入的元素（应该返回true）std::cout<<"\n===== 查询已插入的元素 ====="<<std::endl;for(constauto&url:urls){std::cout<<url<<" → "<<(bf.contains(url)?"可能存在":"绝对不存在")<<std::endl;}// 测试2：查询未插入的元素（应该返回false，或小概率误判为true）std::cout<<"\n===== 查询未插入的元素 ====="<<std::endl;std::vector<std::string>non_urls={"https://www.tiktok.com",// 未插入"https://www.taobao.com",// 未插入"https://www.jd.com"// 未插入};for(constauto&url:non_urls){std::cout<<url<<" → "<<(bf.contains(url)?"可能存在（误判）":"绝对不存在")<<std::endl;}return0;}步骤4：运行结果解释
示例输出（参数和结果可能略有差异）：
布隆过滤器初始化完成： 预期元素数：100 期望误判率：0.01 位数组长度m：959 哈希函数个数k：7 ===== 查询已插入的元素 ===== https://www.baidu.com → 可能存在 https://www.google.com → 可能存在 https://www.github.com → 可能存在 https://www.bilibili.com → 可能存在 https://www.zhihu.com → 可能存在 ===== 查询未插入的元素 ===== https://www.tiktok.com → 绝对不存在 https://www.taobao.com → 绝对不存在 https://www.jd.com → 绝对不存在- 已插入的元素：全部返回「可能存在」（符合预期）；
- 未插入的元素：全部返回「绝对不存在」（无误会，误判率低）；
- 若未插入的元素返回「可能存在」，就是误判（调整m/k可降低概率）。
四、关键说明
- 哈希函数选择：
示例用了BKDR+AP哈希组合出k个哈希值，也可以用其他哈希函数（如DJB、SDBM），核心是哈希函数要「均匀分布」，避免哈希碰撞集中。 - vector的替代：
vector是比特级存储（省空间），但效率略低。如果追求性能，可改用std::bitset（编译期确定大小）或手动管理字节数组（如char[]，按位操作）。 - 误判率优化：
若误判率过高，可增大m（位数组长度）或调整k（哈希函数个数），或降低期望误判率p。 - 通用化扩展：
示例只支持字符串，可模板化类（template <typename T>），并为不同类型（int、double等）实现哈希函数。
总结
布隆过滤器的核心是「用空间换时间+概率妥协」，适合「允许小概率误判、追求极致空间效率」的场景。C++实现的关键是：
- 按公式计算最优的
m和k； - 实现均匀分布的哈希函数；
- 对位数组进行高效的置1/检查操作。
