Bloom Filter（布隆过滤器）
分类：数据结构与算法
布隆过滤器bloom
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。 如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(log n),O(n/k)。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
若一个字符串对应的bit不全为1，则肯定没有； 若一个字符串对应的Bit全为1，不一定有，因为有可能该字符串的所有位都刚好是被其他字符串所对应，这种情况称为false positive 。
注意：字符串加入后就被不能删除了，因为删除会影响到其他字符串。 若需要删除字符串，可以使用counting bloom filter(CBF)，这是一种基本bloom filter的变体，CBF将基本bloom filter每一个bit改为一个计数器，这样就可以实现删除字符串的功能了。 从上面我们可以看到bloom filter主要有三个参数： １）存储字符串的个数n ２） 哈希函数个数k ３）位数组大小m
我们来分析下： 若插入一个字符串，位数组bit位j上还为0的概率显然为(1-1/m)^k 那么我们插入n个字符串，位数组bit位j上还为0的概率显然为 (1-1/m)^kn≈e^(-kn/m) 即某一位为1的概率p为：1- e^(-kn/m)，那么对于所有k个哈希函数 对应k位都为1（冲突）的概率f为：(1- e^(-kn/m) )^k 对上式求导求极值，得k=ln2 × m /n时取得最小值，此时p约为1/2(m/2 bits 1, m/2 bits 0) f = (1-p)＾k ≈ ()＾k =()＾(ln 2)m/n ≈ (0.6185)＾m/n
如果m = 8n, then k = 8(ln 2) = 5.545 (use 6 hash functions) f ≈ (0.6185)m/n = (0.6185)8 ≈ 0.02 (2% false positives) Compare to a hash table: f ≈ 1 – e-n/m = 1-e-1/8 ≈ 0.11
add<T>(T item){for(int i = 0; i < k; i++)array[hi(item)] = 1;}contains<T>(T item){for(int i = 0; i < k; i++)if(!array[hi(item)]) return false;return true;}
Bloom Filter通过允许少量的错误来节省大量的存储空间，但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。 另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
Counting Bloom Filter
Insertion ： increment counter Deletion ： decrement counter Overflow ： keep bit 1 forever
为了避免计数溢出，计数必须要有足够的位数。 我们先计算第i个Counter被增加j次的概率，其中n为集合元素个数，k为哈希函数个数，m为Counter个数（对应着原来位数组的大小）：
上面等式右端的表达式中，前一部分表示从nk次哈希中选择j次，中间部分表示j次哈希都选中了第i个Counter，后一部分表示其它nk – j次哈希都没有选中第i个Counter。因此，第i个Counter的值大于j的概率可以限定为：
add<T>(T item){ for(int i = 0; i < k; i++) array[hi(item)]++;}contains<T>(T item){ for(int i = 0; i < k; i++) if(!array[hi(item)]) return false; return true;}remove<T>(T item){ for(int i = 0; i < k; i++) array[hi(item)]–;}
应用举例： 1）HTTP缓存服务器、Web爬虫等 主要工作是判断一条URL是否在现有的URL集合之中（可以认为这里的数据量级上亿）。 对于HTTP缓存服务器，，当本地局域网中的PC发起一条HTTP请求时，缓存服务器会先查看一下这个URL是否已经存在于缓存之中，如果存在的话就没有必要去原始的服务器拉取数据了（为了简单起见，我们假设数据没有发生变化），这样既能节省流量，还能加快访问速度，以提高用户体验。 对于Web爬虫，要判断当前正在处理的网页是否已经处理过了，同样需要当前URL是否存在于已经处理过的URL列表之中。
你可以这样理解 impossible(不可能)–I'm possible (我是可能的)。
