布隆过滤器是一种概率型集合，用很小空间回答“某元素是否可能存在”。它由长度为 m 的位图和 k 个哈希位置组成。插入时把对应位设为 1；查询时检查这些位，只要有一位为 0，就能确定元素不存在；全部为 1，只能说可能存在。

误判来自不同元素共享位：从未插入的元素也可能碰巧命中所有 1。标准布隆过滤器不会假阴性，前提是位图未被错误清除、哈希规则一致。随着元素增加，1 的比例升高，误判率随之上升；容量规划要结合预计元素数 n 与可接受误判率选择 m 和 k，而不是任意开一块位图。

1
2
3
4
5
6
add(x):
  for each hash h: bits[h(x) mod m] = 1
contains(x):
  for each hash h:
    if bits[h(x) mod m] == 0: return false
  return true

单次插入和查询为 O(k)，位图空间 O(m)，通常把 k 视为小常数。普通版本不能安全删除，因为清掉共享位会让其他元素产生假阴性；需要删除时可使用计数布隆过滤器，但每个位置存计数会增加空间并需处理溢出。

它适合缓存穿透防护、爬虫 URL 粗去重和存储系统读前过滤；命中后仍须访问权威数据源确认。误区是把“可能存在”当作存在、上线后无限加入元素、不做版本与哈希兼容，以及把它当安全鉴权。小结：布隆过滤器用可控误判换空间，职责是快速排除，不是保存事实。