布隆过滤器 Bloom Filter

空间高效的概率性数据结构 — 有时候说"可能"，但从来不会说"没有"时其实"有"

---

概念

关键特性

特性	说明
无假阴性	contains() 返回 false 时，元素一定不在集合中
可能有假阳性	contains() 可能对未添加的元素返回 true
不能删除	位一旦设置无法清除
空间高效	只占哈希表的一小部分内存

---

复杂度

操作	时间	空间
add	O(k)	O(m)
contains	O(k)	O(m)

k = 哈希函数数量, m = 位数组大小

---

决策指南

场景	推荐
需要精确答案	用 HashSet
内存受限，可容忍假阳性	布隆过滤器
需要删除元素	用计数布隆过滤器变体