BloomFilter 与 Cuckoo Filter

BloomFilter 与 CuckooFilter

Bloom Filter 原理

Bloom Filter是一种空间效率很高的随机数据结构，它的原理是，当一个元素被加入集合时，通过K个相互独立的Hash函数将这个元素映射成一个位阵列（Bit array）中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了；如果这些点有任何一个0，则被检索元素一定不在；如果都是1，则被检索元素很可能在。

Bloom Filter的这种高效是有一定代价的，在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，并不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

假设要你写一个网络爬虫程序（web crawler）。由于网络间的链接错综复杂，爬虫在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道爬虫程序已经访问过那些URL。给一个URL，怎样知道爬虫程序是否已经访问过呢？稍微想想，就会有如下几种方案：

将访问过的URL保存到数据库。
用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。

其中，方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了：

方法1：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？

方法2：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。

方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。

方法4：消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。Bloom Filter 与单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第 i 个哈希函数对字符串str哈希的结果记为H_i(str)，并且满足：

0 <= H_i(str) < m 　　　　（1<=i<=k）

(1) 将字符串 str 映射到BitSet中的过程：分别计算H₁(str)，H₂(str)，…，H_k(str)，然后在BitSet中将对应的位置1。

(2) 检查字符串str是否被BitSet记录过的过程：分别计算H₁(str)，H₂(str)，…，H_k(str)，然后在BitSet中对应的位检查是否为1。若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1，则认为字符串str存在。注意：这里也可能存在误判，因为有可能该字符串的所有位都刚好是被其他字符串所对应，这种将该字符串划分错的情况称为false positive 。

(3) 删除字符串过程，字符串加入了就被不能删除了，因为删除会影响到其他字符串。

实在需要删除字符串的可以使用Counting Bloom Filter (CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。