记忆碎片

最近看到网上的一些算法总提到Bloom Filter，很多说明都是搬了一大堆的公式或者是一堆的英文，感觉看起来甚是费解。
Bloom Filter其实就是位图的一个扩展而已，位图会产生重复的冲突，Bloom Filter使用了多个hash函数，共同置位，这样就减少了冲突的误判率。布隆过滤器是由巴顿.布隆于一九七零年提出的。

详细讲一下 这个 思想：
假如我们有一亿个URL需要存储，我们先建立一个八亿的二进制位图，然后将这八亿个二进制全部清零。对于每个URL，我们用不同的K个(我们选择4个)随机函数产生器(不同的hash函数)，产生4个值(h1,h2,h3,h4)。然后再把这四个值通过一个函数映射到0-八亿个数之间的某四个数，这样就可以，直接设置四个位图为1，如下图：

插入成功了的话，那么查找就很简单了。直接用插入过程的运算，判断h1,h2,h3,h4，对应的位是否为1，如果全部为1即是命中！但是，我们可以想到，Bloom Filter有一定的误判率，即该数据不存在，但是，如果hash后的函数数据对应值全部为1的话，那么既是伪命中！这个概率比较小，解决办法既是再重新做一个类似白名单的缓存。

通过上面的理解，很简单可以明白，该算法对数据的插入和查找是比较简单，但是，如果动态数据怎么办呢？也就是说，假如我想删除怎么办呢？很遗憾，Bloom Filter不支持删除操作。不过Bloom Filter改进以后是可以删除的。比如：Counting Bloom Filter，既是把位图中的位，更新为一个技术器，每次映射以后，不是简单的置1，而是+1，然后对应的删除时-1。
具体的应用就是 过滤了，比如过滤IP、URL、Email等。