布隆过滤器

概念

布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，因为它只存储0和1，不存储具体数据

核心

如果布隆过滤器认为某个键不存在，那么这个键就一定不存在

如果布隆过滤器认为某个键存在，那么这个键只是可能存在（还可能不存在）

特点

• 高效的插入和查询

• 不支持删除操作

• 查询结果有误差（针对键值存在的情况）

实现原理

布隆过滤器由位图和n个hash函数构成。布隆过滤器的操作是一个key经过多个hash函数，然后对位图大小进行取余得到多个槽位并对应置为1。 请求流程：

1. 将要查询的元素给k个哈希函数

2. 得到对应于位数组上的k个位置

3. 如果k个位置有一个为0，则一定不在集合中

4. 如果k个位置全部为1，则可能在集合中

Q1

为什么bit全部为1时，元素只是可能存在呢？

假设我们现在要查询Z元素，假设Z元素并不存在。但是巧了经过hash计算出来的位置为1,2。我们很清楚，这里的1是属于X元素的，2是属于Y元素的。并不存在Z。但是经过hash计算的结果返回值都是1。所以程序认为Z是存在的，但实际上Z并不存在，此现象称为假阳率false positive。

Q2

为什么布隆过滤器不支持删除操作呢？

因为在位图中每个槽位只有两种状态（0或者1），一个槽位被置为1，但不确定它被设置了多少次；也不知道被多少个key hash映射而来；以及具体被哪个hash函数映射而来。所以你把它删除了，可能导致对其他key进行查询时返回错误的结果。