前言
- 布隆过滤器BloomFilter应用十分广泛，尤其是在网络领域，高并发、分布式缓存、比特币网络……
- Filter过滤器和Cache缓存，有着异曲同工之妙，是互补的关系。在向文件系统查询数据之前，先看Cache里面有没有缓存，有的话就直接从缓存读取。布隆过滤器的思想类似，只不过其只存放文件在不在(二进制位是不是1)
实现原理
回顾：哈希函数
哈希函数示意图
和哈希函数把元素映射到一个地址类似，布隆过滤器是把元素散射到一个二进制向量里。
- 布隆过滤器的实现依靠的是一个很长的二进制向量和一系列随机映射函数。
- 可用于检索一个元素是否在一个集合中。
- 优点是空间效率和时间性能都远超一般的算法，缺点是有一定的误识别率（主要是将不在集合中误识别为在集合中）和删除困难。3
两个例子
例一：正确识别
如上图所示，假设内存中已经存在若干元素x，y，z，根据特定的算法将散射到的二进制位修改为1，表示元素存在。当需要查询元素w是否存在于内存，借助布隆过滤器获取到其散射到的二进制位，依次检查这些位置，发现有一位为0，则说明该元素不在内存中
例二：误识别
虽然当过滤器返回“不在”，则可断定该元素确实不在。但是当过滤器给出的结果是“在”，那么这个结果就未必正确。如上图所示，散射函数虽能保证同一个key散射结果唯一，但不能保证多个key散射结果不会和另一个key的散射结果部分重合，这就导致了一定的误识别率。
现实案例
- 比特币网络 Redis vs BloomFilter
SPV：simple payment verification，简单支付验证，快速判断节点间是否有交易关系
- 分布式系统（Map-Reduce）