布隆过滤器是一种概率数据结构, 用来便捷地提供一种验证某个元素确认地不存在集合中.
这使得它在访问成本高(通过网络或者磁盘)的搜索项目时特别理想: 如果我有一个特别磁盘数据库,并且想知道是否存在某个 key, 我可以先使用布隆过滤器, 它会明确告诉我 key 可能存在(如果存在的话磁盘查询可以继续), 如果不存在的话,这个时候可以抛弃昂贵的磁盘查找,返回否定的响应给上游.
尽管可以使用其他的数据结构(例如哈希表)来执行同样的查询, 布隆过滤器在每个元素的空间占用方面同样特别有用,通常都是以位数来统计.
布隆过滤器存在一定概率的误报(这是可控的), 但在验证 key 是否存在的初始测试中, 布隆过滤器提供了极为优秀的速度与同样优秀的空间效率.
过滤器被广泛使用在多个场景中:
- 广告服务 确保同个用户不会多次看到同一个广告
- 推荐系统 确认推荐内容不会高频率出现
- 数据库 在访问磁盘前快速检查是否存在
等等