Bloom Filter

先给出学习的几篇博文：

1. 数学之美系列二十一 ——布隆过滤器（Bloom Filter）
2. 布隆过滤器 (Bloom Filter) 详解：http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
3. Bloom Filter概念和原理：http://blog.csdn.net/jiaomeng/article/details/1495500
4. wiki：http://en.wikipedia.org/wiki/Bloom_filter

Bloom Filter（布隆过滤器）要点：

1. 应用范型：判断一个元素是否在一个集合中。包括：单词拼写检查、嫌疑人名单比对、网络爬虫对已爬过的网页过滤、垃圾电子邮件过滤等；
2. 算法组成：m位的位数组（all set to 0）、k个不同的哈希函数（each of which maps or hashes some set element to one of them array positions with a uniform random distribution.）
3. 算法描述：
   1. 增加元素时，用k个哈希函数得到所增加元素在位数组中的k个位置，并把所有k个位置置1；（你可能想到，不同哈希函数可能得到重复的位置，不同关键的哈希结果也可能得到重复的位置）
   2. 查询元素时（查询等于差测试该元素是否在集合中），用k个哈希函数得到所查询元素在位数组中的k个位置：如果这k个位置中任何一位或几位是0，那么这个元素绝对不存在；如果这k个位置全部是1，即可能是该查询元素在插入时设置为1，也可能恰好是其他元素插入时设置为1（这就导致所谓false positive）。在简单的bloom filter中，没有办法区分这两种情况，但其它一些高级技术可以处理这个问题。
   3. 删除元素时，在简单的 Bloom filter 中，删除元素是不允许的（原因是 false negatives不允许）。删除一个元素映射的k个位置（setting any one of thosek bits to zero ），也会删除其他元素恰好映射到的那些位置。因为无法确定是否有其他元素的增加影响到要删除元素所有映射的位置，删除k个位置中的任何位置都会引入false negatives。
   4. 当k很大时，设计k个独立的哈希函数是不现实并且困难的。对于一个良好的宽输出的哈希函数，应该在不同位域有很少或者没有相关性。通过把输出划分到多个位域，这样的哈希函数可以生成多个不同哈希函数。对于较大的k和m，独立的哈希函数之间有可以忽略的false positive rate。
   5. 待续
4. 待续