BloomFilter（布隆过滤器）

BloomFilter（布隆过滤器）

　　布隆过滤器（英语：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 。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPqGhoaHXotLio7rX1rf7tK6808jruvO+zbG7srvE3Mm+s/3By6Os0vLOqsm+s/274dOwz+y1vcbky/vX1rf7tK6hozxiciAvPg0KoaGhocj00OjSqsm+s/3X1rf7tK6jrL/J0tTKudPDY291bnRpbmcgYmxvb20gZmlsdGVyKENCRimjrNXiysfSu9bWu/mxvmJsb29tIGZpbHRlcrXEseTM5aOsQ0JGvau7+bG+Ymxvb20gZmlsdGVyw7/Su7j2Yml0uMTOqtK7uPa8xsr9xvejrNXi0fm+zb/J0tTKtc/Wyb6z/dfWt/u0rrXEuabE3MHLoaM8YnIgLz4NCqGhoaE8YnIgLz4NCqGhoaG008nPw+bO0sPHv8nS1L+0tb1ibG9vbSBmaWx0ZXLW99Kq09DI/bj2ss7K/aO6PGJyIC8+DQqhoaGho7GjqbTmtKLX1rf7tK61xLj2yv1uPGJyIC8+DQqhoaGho7KjqSC5/s+juq/K/bj2yv1rPGJyIC8+DQqhoaGho7Ojqc67yv3X6bTz0KFtPC9wPg0KPHA+oaGhoc7Sw8fAtLfWzvbPwqO6PGJyIC8+DQqhoaGhyPSy5cjr0ru49tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqigxLTEvbSleazxiciAvPg0KoaGhocTHw7TO0sPHsuXI62649tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqjxiciAvPg0KKDEtMS9tKV5rbiZhc3ltcDtlXigta24vbSk8YnIgLz4NCqGhoaG8tMSz0rvOu86qMbXEuMXCynDOqqO6MS0gZV4oLWtuL20po6zEx8O0ttTT2sv509BruPa5/s+juq/K/aGhoaG21NOma867trzOqjGjqLPlzbujqbXEuMXCymbOqqO6KDEtIGVeKC1rbi9tKSApXms8YnIgLz4NCqGhoaG21MnPyr3H87W8x/O8q9a1o6y1w2s9bG4yICZ0aW1lczsgbSAvbsqxyKG1w9fu0KHWtaOstMvKsXDUvM6qMS8yKG0vMiBiaXRzIDEsIG0vMiBiaXRzIDApPGJyIC8+DQqhoaGhZiA9ICgxLXApo95rICZhc3ltcDsgKD8po95rID0oPymj3ihsbiAyKW0vbiAmYXN5bXA7ICgwLjYxODUpo95tL248L3A+DQo8cD6hoaGhyOe5+20gPSA4biwgdGhlbjxiciAvPg0KoaGhoSBrID0gOChsbiAyKSA9IDUuNTQ1ICh1c2UgNiBoYXNoIGZ1bmN0aW9ucyk8YnIgLz4NCqGhoaEgZiAmYXN5bXA7ICgwLjYxODUpbS9uID0gKDAuNjE4NSk4ICZhc3ltcDsgMC4wMiAoMiUgZmFsc2UgcG9zaXRpdmVzKTxiciAvPg0KoaGhoSBDb21wYXJlIHRvIGEgaGFzaCB0YWJsZTogZiAmYXN5bXA7IDEgJm5kYXNoOyBlLW4vbSA9IDEtZS0xLzggJmFzeW1wOyAwLjExPC9wPg0KPHByZSBjbGFzcz0="brush:sql;"> add(T item) { for(int i = 0; i < k; i++) array[hi(item)] = 1; } contains(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 item)
{
　　for(int i = 0; i < k; i++)
　　　array[hi(item)]++;
}

contains(T item)
{
　　for(int i = 0; i < k; i++)
　　if(!array[hi(item)])
　　　return false;
　　return true;
}

remove(T item)
{
　　for(int i = 0; i < k; i++)
　　array[hi(item)]--;
}

应用举例：
　　1）HTTP缓存服务器、Web爬虫等
　　主要工作是判断一条URL是否在现有的URL集合之中（可以认为这里的数据量级上亿）。
　　对于HTTP缓存服务器，当本地局域网中的PC发起一条HTTP请求时，缓存服务器会先查看一下这个URL是否已经存在于缓存之中，如果存在的话就没有必要去原始的服务器拉取数据了（为了简单起见，我们假设数据没有发生变化），这样既能节省流量，还能加快访问速度，以提高用户体验。
　　对于Web爬虫，要判断当前正在处理的网页是否已经处理过了，同样需要当前URL是否存在于已经处理过的URL列表之中。

　　2）垃圾邮件过滤
　　假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤，那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通信邮件数量非常大（也可以认为数据量级上亿），那么也可以使用Bloom Filter算法。