布隆过滤器

布隆过滤器(Bloom filter)是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。

使用布隆过滤器获得的结果，可能为假阳性匹配，但是不可能为假阴性匹配。换句话说，查询返回的结果是“==要么在可能不在，要么不在肯定不在==”。元素可以添加到集合中，但不能删除（尽管这可以通过额外的“计数”布隆过滤器来解决）；添加到集合中的元素越多，误报的可能性越大。

用例

• Cassandra使用布隆过滤器来确定SSTable是否有特定行的数据。
• HBase布隆过滤器是一种测试StoreFile是否包含特定行或者行列单元格的有效机制。
• 使用布隆过滤器，网站的反作弊系统可以有效地拒绝被禁止使用的用户。
• 谷歌的Chrome浏览器曾使用布隆过滤器来识别恶意链接。