布隆筛选详解

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否存在于集合中。其核心特点是：可能误判元素存在，但绝不会误判元素不存在。

一、基本原理

1. 数据结构

位数组（Bit Array）：初始全部为0的数组，用于存储元素的哈希值。
多个哈希函数：将元素映射到数组的不同位置。

2. 操作流程

插入元素：
- 用多个哈希函数计算元素的哈希值，将对应位数组位置置为1。
查询元素：
- 用相同哈希函数计算元素的哈希值，检查对应位是否全为1：
  - 若全为1，元素可能存在（有一定误判率）。
  - 若有任何一位为0，元素必定不存在。

3. 误判率（False Positive Rate）

当位数组被频繁插入元素后，可能出现“所有查询位都被其他元素置为1”的情况，导致误判。
误判率与位数组大小、哈希函数数量和插入元素数量相关。

二、核心公式

最优哈希函数数量：
$\frac{m}{n} \ln 2$
其中， $m$ 为位数组大小， $n$ 为预期插入元素数量。
误判率：
$\approx \left(1 - e^{-\frac{kn}{m}}\right)^k$
当 $k$ 取最优值时，误判率可简化为：
$\approx \left(\frac{1}{2}\right)^k \approx 0.6185^{m/n}$
位数组大小计算：
若期望误判率为 $P$ ，则：
$-\frac{n \ln P}{(\ln 2)^2}$

三、代码实现示例

以下是一个简化的布隆过滤器实现：

#include <vector>
#include <string>
#include <functional>class BloomFilter {
private:std::vector<bool> bitArray;  // 位数组int m;                       // 位数组大小int k;                       // 哈希函数数量std::hash<std::string> hasher;  // 简化示例，实际需多个不同哈希函数public:BloomFilter(int expectedElements, double falsePositiveRate) {// 计算位数组大小和哈希函数数量m = - (expectedElements * std::log(falsePositiveRate)) / (std::log(2) * std::log(2));k = (m / expectedElements) * std::log(2);bitArray.resize(m, false);}// 插入元素void insert(const std::string& element) {for (int i = 0; i < k; ++i) {// 生成k个不同哈希值（简化示例）size_t hash = hasher(element + std::to_string(i)) % m;bitArray[hash] = true;}}// 查询元素是否可能存在bool mayContain(const std::string& element) {for (int i = 0; i < k; ++i) {size_t hash = hasher(element + std::to_string(i)) % m;if (!bitArray[hash]) return false;}return true;}
};

四、应用场景

缓存穿透防护：
- 在访问数据库前，用布隆过滤器判断数据是否存在。若不存在，直接拦截请求，避免数据库压力。
海量数据去重：
- 如爬虫URL去重、垃圾邮件过滤，用极小空间快速判断元素是否已存在。
分布式系统：
- 如Hadoop、Redis等系统中，用于快速判断数据是否存在于本地，减少网络IO。
区块链：
- 比特币等系统用布隆过滤器实现轻量级客户端（SPV），验证交易是否存在于区块中。

五、优缺点

优点	缺点
空间效率极高（仅需位数组）	存在误判率（无法100%准确）
插入和查询时间复杂度O(k)	无法删除元素（因哈希冲突）
不存储原始数据，保护隐私	参数（m、k）需预先设置