最后更新时间 2021-10-05.
布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的。它可以检索一个元素是否存在于集合中。它的优点是空间效率高，查询时间极快，缺点是有一定的误判率，而且删除困难。
1. 背景
编程中，经常会有判断一个元素是否存在一个集合中:
- 网络爬虫程序：判断一个地址是否被访问过；
- 文字处理软件：检查单词的拼写 (也就是判断它是否存在词典里)；
- 电子邮件黑名单。
其中，最直接的办法是，将集合所有元素存储起来，判断时与集合中的元素比较即可。
一般来说会使用哈希表来存储集合，速度快效率高，可以在 O(1) 的时间复杂度返回结果。但是哈希表本身由于负载因子的存在，不可能用满，也就是会有空间浪费的问题，对于网络爬虫来说，可能会处理几十亿的 URL 链接集合，哈希表占据的内存大小是非常可观的。
