布隆过滤器
特点
- 精确判断不存在，但是可能会误判一个不在集合中的元素为存在（即：假阳）
- 不支持删除元素（几个hash函数计算出来的下标可能别的key也用到了）
总结来说就是：判断不存在的时候一定不存在，判断存在的时候大概率存在。
误判率可以通过调整参数来降低，但是无法完全消除。
数据结构的组成
布隆过滤器由一个 bitSet 和一组 hash 函数组成，是一种空间效率非常高的概率算法和数据结构。在初始化的时候，bitSet 的每一位被初始化为 0，同时会定义一组 hash函数，例如有 3 组 hash 函数，hash1，hash2，hash3.
写入流程
当我们要写入一个值时，过程如下，以“jionghui”为例：
- 首先将“jionghui”跟3组 Hash 函数分别计算，得到 bitSet 的下标为：1、7、10。
- 将 bitSet 的这3个下标标记为1。
假设我们还有另外两个值：java 和 diaosi，按上面的流程跟 3组 Hash 函数分别计算，结果如下：
- java：Hash 函数计算 bitSet 下标为：1、7、11
- diaosi：Hash 函数计算 bitSet 下标为：4、10、11
查询流程
当我们要查询一个值时，过程如下，同样以“jionghui”为例：
- 首先将“jionghui”跟3组 Hash 函数分别计算，得到 bitSet 的下标为：1、7、10
- 查看 bitSet 的这 3 个下标是否都为 1，如果这 3 个下标不都为 1，则说明该值必然不存在，如果这 3 个下标都为 1，只能说明可能存在，并不能说明一定存在
其实上图的例子已经说明了这个问题了，当我们只有值“jionghui”和“diaosi”时，bitSet 下标为1的有：1、4、7、10、11。当我们又加入值“java”时，bitSet 下标为1的还是这5个，所以当 bitSet 下标为1的为：1、4、7、10、11 时，我们无法判断值“java”存不存在。
其根本原因是，不同的值在跟 Hash 函数计算后，可能会得到相同的下标，所以某个值的标记位，可能会被其他值给标上了。这也是为啥布隆过滤器只能判断某个值可能存在，无法判断必然存在的原因。但是反过来，如果该值根据Hash函数计算的标记位没有全部都为1，那么则说明必然不存在。
降低这种误判率的思路也比较简单：
- 加大 bitSet 的长度，这样不同的值出现“冲突”的概率就降低了，从而误判率也降低。
- 提升 Hash 函数的个数，Hash 函数越多，每个值对应的 bit 越多，从而误判率也降低。
HashMap 和布隆过滤器
数据量小的时候使用 hashmap 一点问题也没有，而且没有误判，非常完美。但是当数据量上去之后布隆过滤器的空间优势非常明显，key 占用的空间越大，布隆过滤器的优势就越明显。
guava 中的布隆过滤器在默认情况下，误判率接近 3%，使用 5 个 hash 函数。
空间和时间方面具有巨大优势，同时因为hash函数之间相互没有关系，方便由硬件来并行实现。布隆过滤器本身不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
实际应用
- google的分布式数据库bigtable使用了布隆过滤器来查找不存在的行或列，以减少磁盘IO的查找次数
- squid网页代理缓存服务器也使用了布隆过滤器
- chrome浏览器使用布隆过滤器加速安全浏览服务
