| slug | id | title | date | comments | tags | description | references | ||
|---|---|---|---|---|---|---|---|---|---|
68-bloom-filter |
68-bloom-filter |
布隆过滤器 |
2018-10-09 12:39 |
true |
|
布隆过滤器是一种数据结构，用于以时间和空间高效的方式检测一个元素是否在一个集合中。查询返回“可能在集合中”或“绝对不在集合中”。 |
布隆过滤器是一种数据结构，用于以时间和空间高效的方式检测一个元素是否在一个集合中。
可能会出现假阳性匹配，但不会出现假阴性——换句话说，查询返回“可能在集合中”或“绝对不在集合中”。元素可以添加到集合中，但不能移除（尽管可以通过“计数”布隆过滤器来解决这个问题）；添加到集合中的元素越多，假阳性的概率就越大。
使用案例
- Cassandra 使用布隆过滤器来确定 SSTable 是否包含特定行的数据。
- HBase 布隆过滤器是一种有效的机制，用于测试 StoreFile 是否包含特定行或行-列单元格。
- 网站的反欺诈系统可以有效地使用布隆过滤器来拒绝被禁止的用户。
- 谷歌 Chrome 浏览器曾经使用布隆过滤器来识别恶意 URL。