布隆过滤器（Bloom Filter）是由 Burton Howard Bloom 于 1970 年提出，它是一种空间利用率很高的概率型数据结构，用于判断一个元素是否在集合中。在垃圾邮件过滤的黑白名单方法、爬虫（Crawler）的网址判重模块中经常被用到。虽然哈希表也能用于判断元素是否在集合中，但是完成同样的问题，布隆过滤器需要的内存比哈希表小得多。布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，false positive rate（误报率）越大，但是 false negative （漏报）是不可能的。
参考资料：