布隆过滤器（Bloom Filter）
定义
布隆过滤器（Bloom Filter）是一种概率型数据结构，用于在超大规模数据集中快速判断一个元素是否存在，仅使用少量内存空间，且具备数据隐私性。
核心原理
布隆过滤器不存储具体数据，而仅仅存储数据指纹（哈希值），通过多个哈希函数将数据映射到位图（bitmap） 中的多个位置，通过比对指纹来判断数据是否存在。
基本操作：
- 添加元素：用 k 个哈希函数计算哈希值，将位图中对应的 k 个位置设为 1
- 查询元素：用同样的 k 个哈希函数计算哈希值，检查位图中对应的 k 个位置：
- 如果任意一位为 0 → 元素一定不存在（无假阴性）
- 如果所有位都为 1 → 元素可能存在（有假阳性）
特性
| 特性 | 说明 |
|---|---|
| 空间效率 | 极高，仅存储哈希值，不存储实际数据 |
| 查询时间 | $O(k)$，k 为哈希函数个数，通常为常数 |
| 假阴性（False Negative） | 不存在（如果查询说不存在，就一定不存在） |
| 假阳性（False Positive） | 可能存在（如果查询说存在，可能实际上不存在） |
| 数据隐私性 | 高（不存储实际数据） |
| 删除元素 | 不支持（位图中的位置可能被多个元素共享） |
与哈希集合的对比
| 维度 | 哈希集合 | 布隆过滤器 |
|---|---|---|
| 空间复杂度 | $O(N)$ | $O(m)$，m << N |
| 数据存储 | 存储实际数据 | 仅存储哈希指纹 |
| 数据隐私 | 无 | 有 |
| 假阳性 | 无 | 有（可调整误差率） |
| 假阴性 | 无 | 无 |
| 删除支持 | 支持 | 不支持 |
| 适用规模 | 小规模到中规模 | 超大规模（亿级+） |
应用场景
- 恶意 URL 检测：判断 HTTP 请求 URL 是否在恶意 URL 列表中（亿级数据），仅消耗少量内存
- 大数据存储系统：为每个数据文件维护布隆过滤器，快速判断目标数据是否存在，避免无效磁盘 IO
- 缓存穿透防护：判断请求的数据是否存在于数据库中
- 爬虫 URL 去重：判断 URL 是否已被爬取
- 垃圾邮件过滤：判断邮件地址是否在黑名单中
误差率与参数选择
布隆过滤器的假阳性率取决于：
- 位数组大小（m）：越大，误差率越低
- 哈希函数个数（k）：需要权衡（太少会增加冲突，太多会占用更多空间并降低性能）
- 已插入元素数量（n）
公式：假阳性率 $p \approx (1 - e^{-kn/m})^k$
位图的基础作用
布隆过滤器使用位图（bitmap） 作为底层存储结构：
- 位图用 1 bit 表示状态（0/1），相比布尔数组节省 7/8 内存
- 布隆过滤器将元素的多个哈希值映射到这个位图中
局限性与补充方案
-
无法删除元素：因为多个元素可能共享某些位，删除一个元素可能会误删其他元素
- 解决方案：使用 Counting Bloom Filter（用计数器替代位）
-
假阳性问题：可能误判元素存在
- 解决方案：结合白名单、二次确认等方法
-
无法获取实际数据：只能判断存在性，不能获取原始数据
- 解决方案：需要时使用布隆过滤器 + 哈希表组合