【布隆过滤器】过滤器中的战斗机

背景

SET

说到去重，很容易想到STL中的SET容器，它本身自带去重功能，而且还能查询。
那么最简单的方式，直接用SET。每次操作的时候，先查询该事物是否存在？

• 如果存在直接返回“存在”结果。
• 如果不存在就插入其中，然后再返回“不存在”结果。

具体如下图所示：

这种方式准确率是绝对准确的，但是这种方式耗费的内存也是巨大的。
假设每个事物需要 K 字节，那么如果有 M 个事物，一共需要 K * M 字节。那么我们能不能缩小这里的内存呢？
稍微损失一点准确率换取内存？具体见下面HashMap的方式

HashMap

在上一种方式中，它存储了具体的事物信息，其实在我们这个场景中是不需要的。我们需要的只是这个事物是否存在就行了，所以HashMap的方式诞生了。
这种算法在每次操作的时候，先查询该事物是否存在，

• 如果存在返回“存在”结果。
• 如果不存在就在特定位置置1，然后再返回“不存在”结果。

众所周知，hash都是有一定概率冲突的，而且当哈希桶快满的时候，冲突率更高。
接下来我们来看看这里的冲突率有多少？假设哈希桶长度为M，那么每次插入到特定一个桶的概率是：$$(1-\frac{1}{M})$$
而没有插入特定桶的概率是：$$1-(1-\frac{1}{M})$$
然后假设目前已经插入N个事物，那么特定桶中为0的概率是：$$(1-\frac{1}{M})^N$$
特定桶中为1的概率是：$$1-(1-\frac{1}{M})^N$$

假设现在要新插入一个事物，这次插入的冲突率就是：

\[1-(1-\frac{1}{M})^N = 1- ((1+\frac{1}{-M})^{-M})^{-\frac{N}{M}} \approx 1 - e^{-\frac{N}{M}}\]

所以这里在N接近M的时候，冲突率是很高的，这种算法就完全失效了。
有没有办法解决这种情况呢？布隆过滤器能降低这里冲突率。

布隆过滤器

布隆过滤器是用了多hash的方式降低了冲突率的。
这种算法在每次操作的时候，先查询该事物在K个hash桶中是否都存在，

• 如果存在返回“存在”结果。
• 如果有一个桶不存在，就在K个hash桶中全部置1，然后再返回“不存在”结果。

接下来我们来看看这种有K个Hash加持的算法，冲突率有多少？假设哈希桶长度为M，那么每次插入到特定一个桶的概率是：$$K (1-\frac{1}{M})$$
而没有插入特定桶的概率是：$$(1-(1-\frac{1}{M}))^K$$
然后假设目前已经插入N个事物，那么特定桶中为0的概率是：$$(1-\frac{1}{M})^{NK}$$
特定桶中为1的概率是：$$1-(1-\frac{1}{M})^{NK}$$
假设现在要新插入一个事物，这次插入的冲突率就是:

\[(1-(1-\frac{1}{M})^{NK})^K= (1- ((1+\frac{1}{-M})^{-M})^{-\frac{NK}{M}} )\approx (1 - e^{-\frac{NK}{M}})^K\]

由于这里有K次方的加持，它的冲突率小很多的。
一般来说，在使用布隆过滤器的时候，N是由场景已经决定了的，怎么选择M跟K呢？
P为冲突率

\[M=-\frac{NlnP}{(ln2)^2}\]

\[K=\frac{M}{N}ln2\]

由于布隆过滤器都是直接置1，所以它根本无法删除一个事物的。有没有办法支持它删除+统计个数呢？

布隆过滤器升级版

想要删除特定事物，那其实也很简单。
直接把布隆过滤器的位存储改成数字存储就行了。
那么在每次操作的时候，跟布隆过滤器差别的点在于：

• 无论是否存在都在K个hash桶中加1，
• 然后在需要删除的时候，就在K个hash桶中减1。
  具体如下图所示：
  

这种算法是已经支持删除+统计了，相应的它的内存占用可不是翻倍这么简单的。
不同的场景用不同的算法吧，最合适的才是效果最好滴。