分类 "数据结构" 下的文章

最后更新时间 2021-10-05.

布隆过滤器 (Bloom Filter) 是 1970 年由布隆提出的。它可以检索一个元素是否存在于集合中。它的优点是空间效率高,查询时间极快,缺点是有一定的误判率,而且删除困难。

1. 背景

编程中,经常会有判断一个元素是否存在一个集合中:

  • 网络爬虫程序:判断一个地址是否被访问过;
  • 文字处理软件:检查单词的拼写 (也就是判断它是否存在词典里);
  • 电子邮件黑名单。

其中,最直接的办法是,将集合所有元素存储起来,判断时与集合中的元素比较即可。

一般来说会使用哈希表来存储集合,速度快效率高,可以在 O(1) 的时间复杂度返回结果。但是哈希表本身由于负载因子的存在,不可能用满,也就是会有空间浪费的问题,对于网络爬虫来说,可能会处理几十亿的 URL 链接集合,哈希表占据的内存大小是非常可观的。

阅读全文