Skip to main content

bloomfilter

布隆过滤器是一种用极少内存，快速判断“某个元素是否 可能 存在”的概率型数据结构。

结论只有两种：

  • 一定不存在
  • 可能存在（有一定误判率）

👉 不会漏判，只会误判(多个元素映射到bit数组产生的位冲突) 类似hash冲突

核心目标：
用空间换时间，避免无意义的查询

典型场景：

防止缓存穿透(请求大量缓存和数据库都不存在的 key)

  • 海量数据去重
  • 黑名单 / 白名单快速判断

核心结构​

布隆过滤器只有两样东西：

1️⃣ 一个很大的 bit 数组​

  • 每一位只有 0 / 1
  • 初始全是 0
index: 0 1 2 3 4 5 6 7 8 9 ...
value: 0 0 0 0 0 0 0 0 0 0

2️⃣ 多个 hash 函数​

  • 同一个元素
  • 通过 k 个不同 hash
  • 映射到 bit 数组的 k 个位置

添加元素的过程（put）​

假设：

  • bit 数组长度 = 16
  • hash 函数 = 3 个
  • 插入元素 "user1001"

1️⃣ 计算 hash​

h1("user1001") → 3
h2("user1001") → 7
h3("user1001") → 11

2️⃣ 把对应 bit 置为 1​

index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
value:  0 0 0 1 0 0 0 1 0 0  0  1  0  0  0  0

查询元素的过程（mightContain）​

查询 "user1001"：

  1. 重新算 同样的 k 个 hash
  2. 检查对应 bit 是否 全部为 1
  • 只要 有一个是 0 → 一定不存在
  • 如果 全部是 1 → 可能存在

误判是怎么来的（重点）​

假设后来又插入了其他元素：

"order500" → 占了 bit 3
"item900"  → 占了 bit 7
"abc"      → 占了 bit 11

现在查询 "user9999"：

h1 → 3
h2 → 7
h3 → 11

虽然 "user9999" 从未插入过，
但它映射的 bit 位 刚好全被别人占了。

👉 这就是误判

七、为什么不会漏判​

如果一个元素被插入过：

  • 插入时：所有 bit 被置为 1
  • 查询时：这些 bit 不可能变回 0

所以：

存在的元素一定能查到

八、为什么不能删除元素​

如果你把某一位 1 → 0：

  • 可能会影响 其他元素
  • 造成漏判

解决思路（但成本高）：

  • 计数布隆过滤器（每个 bit 变成计数器）

九、关键参数（非常重要）​

布隆过滤器由三个参数决定：

参数含义
n预计元素数量
mbit 数组长度
khash 函数个数

关系结论（不用记公式）​

  • n 固定：
    • m 越大 → 误判率越低
  • m 固定：
    • k 太小 → 冲突多
    • k 太大 → bit 被快速填满

👉 存在一个最优 k

十、一句话总结工作流程​

用多个 hash 把元素映射到 bit 位上；
插入就是置 1；
查询就是检查这些位是否都为 1；
有 0 一定不存在，全 1 只是可能存在。

实现​