简介

1970年布隆提出了布隆过滤器(Bloom Filter)。

布隆过滤器上是一个很长的二进制向量和一系列随机映射函数。它可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

布隆过滤器（Bloom Filter）本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0，为了将数据项添加到布隆过滤器中，会提供K个不同的哈希函数，并将结果位置上对应位的值置为 “1”。

哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上，会产生误报的情况。布隆过滤器有一个可预测的误判率(FPP):

  • n是已添加的元素数量
  • m是布隆过滤器的长度(如比特数组的大小)
  • k是哈希的此时

当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。

布隆过滤器应用场景

  • 网页爬虫对URL去重，避免爬取相同的URL地址
  • 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱
  • Google Chrome 使用布隆过滤器识别恶意 URL
  • Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找