为什么需要布隆过滤器(Bloom Filter)及其产生背景?

在日常工作中,有一个比较常见的需求,就是需要判断一个元素是否在集合中。

例如以下场景:

给定一个IP黑名单库,检查指定IP是否在黑名单中? 在接收邮件的时候,判断一个邮箱地址是否为垃圾邮件? 在文字处理软件中,检查一个英文单词是否拼写正确?

遇到这种问题,通常直觉会告诉我们,应该使用集合这种数据结构来实现。例如,先将IP黑名单库的所有IP全部存储到一个集合中,然后再拿指定的IP到该集合中检查是否存在,如果存在则说明该IP命中黑名单。 … [阅读文章]

布隆过滤器(Bloom Filter)入门介绍

布隆过滤器(Bloom Filter)是一个数据结构,由布隆(Burton Howard Bloom)于1970年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法,缺点是有一定的误识别率,而且难以删除(一般不支持,需要额外的实现)。 … [阅读文章]