布隆过滤器

一个很长的二进制向量和一个映射函数

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

它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

先来看这张图：

步骤一：对参数 A经过映射函数得到一个二进制向量，进行标记。再对参数B进行映射，这时他们两个存在相同的向量位置（类似于哈希冲突）。

步骤二：检查参数C是否在过滤器中，经过映射函数得到 C 的向量，去过滤器中查看，得到结果 C 不在过滤器中，并且是肯定不在。

步骤三：检查参数 D是否在过滤器中，经过映射函数得到 D 的向量，发现 D 的向量已经存在于过滤器中，但之前并没有插入 D 这个参数，所以从这里可以看出布隆过滤器在判断参数在过滤器中有一定的误识别率，但是在判断参数不在过滤器中没有问题。

步骤四：删除参数B，从图中也可以很明显的看出，A,B 存在交集，那么删除 B 的时候怎么删除。这就是删除困难。