布隆过滤器（Bloom Filter） 布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否在集合中。它的核心特点是通过多个哈希函数和位数组实现，具有 假阳性 （False Positive）可能，但 绝不会出现假阴性 （False Negative）。 1. 布隆过滤器的基本原理 位数组（Bit Array） 初始化一个长度为 \( m \) 的位数组，所有位初始值为 0。 多个哈希函数 选择 \( k \) 个相互独立的哈希函数 \( h_ 1, h_ 2, ..., h_ k \)，每个函数将输入映射到位数组的某个位置（范围在 \([ 0, m-1 ]\)）。 2. 添加元素 假设要添加元素 \( x \)： 分别用 \( k \) 个哈希函数计算 \( x \) 的哈希值： \[ h_ 1(x), h_ 2(x), ..., h_ k(x) \] 将位数组中对应位置设为 1： \[ \text{set bit at } h_ 1(x), h_ 2(x), ..., h_ k(x) \text{ to 1} \] 示例 ： 位数组长度 \( m = 10 \)，哈希函数个数 \( k = 3 \) 添加元素 "apple"： 假设哈希值： \( h_ 1(\text{apple}) = 2, h_ 2(\text{apple}) = 5, h_ 3(\text{apple}) = 8 \) 将位数组下标 2、5、8 设为 1。 3. 查询元素 判断元素 \( y \) 是否在集合中： 计算 \( y \) 的 \( k \) 个哈希值。 检查位数组中这些位置是否 全部为 1 ： 如果有一位为 0，说明 \( y \) 一定不在集合中（ 绝无假阴性 ）。 如果全部为 1，说明 \( y \) 可能 在集合中（ 可能存在假阳性 ）。 假阳性原因 ： 其他元素可能意外设置了相同的位（哈希碰撞），导致误判。 4. 关键参数设计 布隆过滤器的性能由以下参数决定： 位数组长度 \( m \) ： \( m \) 越大，假阳性概率越低，但空间开销越大。 哈希函数个数 \( k \) ： \( k \) 过多会导致位数组迅速填满，增加假阳性；\( k \) 过少则哈希冲突概率高。 预期元素数量 \( n \) ： 假阳性概率公式（近似）： \[ P_ {\text{false positive}} \approx \left(1 - e^{-kn/m}\right)^k \] 最优 \( k \) 值： \[ k = \frac{m}{n} \ln 2 \] 5. 优缺点 优点 ： 空间效率和查询时间远超哈希表。 添加和查询操作都是 \( O(k) \)，与数据量无关。 缺点 ： 无法删除元素（因为可能影响其他元素的位）。 存在假阳性（可通过调整参数控制概率）。 6. 应用场景 缓存系统 ：防止缓存穿透（查询不存在的数据）。 爬虫去重 ：避免重复抓取同一 URL。 分布式系统 ：如 BigTable、Cassandra 用布隆过滤器减少磁盘查找。 7. 改进变种 计数布隆过滤器 ：用计数器代替位，支持删除（但空间开销增大）。 布谷鸟过滤器 ：减少空间开销，支持删除操作。 通过以上步骤，你可以理解布隆过滤器如何以极小空间实现高效集合成员判定，并学会根据需求设计参数平衡假阳性概率和空间成本。