Bloom Filter

Definition 定义

Bloom filter（布隆过滤器）：一种概率型数据结构，用于快速判断某个元素是否可能在集合中。特点是：

• 若返回“不在”，则一定不在；
• 若返回“在”，则可能在（存在假阳性 false positive），但通常不会出现假阴性。
  常用于大规模系统中做快速去重、缓存穿透防护、黑名单/已访问判断等。

Pronunciation 发音

/bluːm ˈfɪltər/

Examples 例句

A Bloom filter can tell you quickly whether an item is definitely not in the set.
布隆过滤器可以快速告诉你某个元素是否一定不在集合中。

Before querying the database, the service checks a Bloom filter to reduce unnecessary reads, accepting a small probability of false positives.
在查询数据库之前，服务会先检查布隆过滤器以减少不必要的读取，并接受小概率的假阳性。

Etymology 词源

“Bloom filter”得名于提出该结构的计算机科学家 Burton Howard Bloom。其中 filter 表示“过滤/筛选”，指它用于筛掉“肯定不存在”的元素；该方法最早系统性发表于 1970 年的论文中。

Related Words 相关词

• Hash
• Bitset
• Probabilistic
• Membership
• False Positive
• Cuckoo Filter
• Count-Min Sketch
• HyperLogLog

Notable Works 作品例证

• “Space/Time Trade-offs in Hash Coding with Allowable Errors”（1970，B. H. Bloom）：提出布隆过滤器的经典论文。
• Introduction to Algorithms（CLRS）：在散列/概率数据结构相关内容中常提及布隆过滤器作为工程常用工具。
• Designing Data-Intensive Applications（Martin Kleppmann）：讨论大规模系统中的索引、去重与概率结构时涉及布隆过滤器。