Bloom Filter(布隆过滤器)

Bloom Filter

是一个空间效率极高的概率型算法和数据结构，用于判断一个数据是否在集合中（类似 Hashset），核心是二进制向量和 hash 函数

优缺点

优点

• 全量存储但是不存储数据本身，适合有保密要求的场景
• 空间效率高
• 插入和查询 时间复杂度都是 O(k),远超一般算法。

缺点

• 存在误算率，数据越多，误算率越高
• 一般情况下无法从过滤器中删除数据
• 二进制数组长度和 hash 函数个数确定过程复杂

应用场景

• google 的分布式数据库 bigTable,hbase 就是用布隆过滤器来查找不存在的行或列，来减少磁盘 IO
• 文档存储检索系统也是用他来检索之前存储的数据
• google chrome,360 浏览器等 也是用她来过滤黑名单网站
• 垃圾邮件地址过滤
• 爬虫 URL 去重
• 解决缓存穿透

用 google guava 框架实战