支持删除的布隆过滤器
一般情况下布隆过滤器只能填入不能删除，有些特别的需求比如支持读写删的系统就会需要支持删除的布隆过滤器
原始布隆过滤器
我们先看看原始的布隆过滤器是个怎么回事
前提假设
原始的布隆过滤器有几个很重要的点，其实是个非常简单的东西
- 一个哈希函数：\(hash(T)\)
- 注意，该哈希函数最好稳定不需要种子，摘要哈希最好。
- 一个可以被位操作的数据类型 \(T\)（也可以叫做向量？毕竟实际上是由一个十分长的位组成的东西）
- 一个统计有多少位相同的算法：\(clac(T,T)\)
原始的布隆过滤器使用多个位来作为其内部数据表示，我们这里使用
u8 作为 \(T\)
的实际类型
1 | |
我们使用上文的 \(hash()\) 函数来对输入 \(input\) 做如下处理
\[ result=hash(input) \]
则我们同样得到了一个类型为u8 的 \(result\) ，其内容为
0000_0001
判断是否存在
在得到哈希结果后，我们利用这个结果来进行判断
1 | |
我们使用的数据类型总共有 8 位，其中相等的位数为
7 位，并不完全相等，那么我们可以认为这个元素肯定不存在
写入数据
我们将这个数组写入到这个我们的过滤器里，这样我们的过滤器里的内容就变成了如下内容
1 | |
- 假如有新的数据，我们就继续按照判断是否存在来判断是否存在于过滤器中
- 如果需要写入数据，我们就按照上文来写入数据
假阳性（False Positive）与误判率
假阳性（误判）
考虑到一种情况，我们的布隆过滤器满了
1 | |
这个时候无论对什么数据进行哈希，得到的结果都会被布隆过滤器判定为存在。那么这里就产生了很重要的问题：误判
误判率
我们做如下假设
- 布隆过滤器的总位数为 \(m\)
- 函数 \(hash\) 产生的结果为 \(result\)
- \(result\) 的位数为 \(k\)
则在插入时布隆过滤器中的某一个特定的位没有被操作的概率是
\[ 1-\frac{1}{m} \] 在完全插入
\(result\) 后某一位仍然为
0 的概率为
\[ (1-\frac{1}{m})^{k} \]
在执行了 \(n\)
次插入后，某一位仍然为 0 的概率就为
\[(1-\frac{1}{m})^{kn}\]
那么很容易得出，某一位为 1 的概率是
\[1-(1-\frac{1}{m})^{kn}\]
我们假设过滤器中所有位均被设置为
1，那么认为某一个原本不应该在集合中的元素却被误判的概率则为
\[P=(1-[1-\frac{1}{m}]^{kn})^k\] 则我们得到的误判率计算公式为 \(P\)。对于该公式，我们假设 \(m\) 趋近于无限，则我们可以进行进一步的处理：令 \(L=(1-\frac{1}{m})^{kn}\)，我们对\(L\) 进行极限，根据极限的定义我们可以得到如下的结果
\[\lim_{m\to\infty}(L)\approx {e^{-1}}^{\frac{kn}{m}}\]
什么？忘了指数函数的极限了？
简单回忆一下一般形式的指数函数的极限：
\[\lim_{m\to\infty}(1-\frac{x}{m})^m=e^{-x} \]
那么我们可以得到其误判率大概为
\[P\approx(1-e^{-x})^k\]