布隆过滤器 Bloom Filter

⼀个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在⼀个集合中。

它的优点是空间效率和查询时间都远超（基于二进制位处理）过⼀般的算法，缺点是有一定的误识别率和删除困难。

重点：当查询不存在时是一定不存在（100%不存在），当查询时存在不一定存在（存在误判），所以根据这点，可以用做第一道墙。

使用二进制位进行标识：

图中的 B 元素是不错在的，但是判断上是存在的（误判例子）。

案例

1. ⽐特币网络
   Redis VS BloomFilter
2. 分布式系统(Map-Reduce)

比特币网络示例图：关注 SPV 节点

SPV 节点：可以很快的判断一个交易是否存在，就是使用的 BloomFilter，因为不存在则一定不存在，存在的话再去查（区块查起来是比较慢的，加上这一层可以加速查找）

分布式系统：比如 Map-Reduce