1. Bloom Filter
【Bloom Filter】
Bloom Filter（BF）是一种空间效率
很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。
Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是
Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。
因此，Bloom Filter不适合那些“零错误”的应用场合。
而在能容忍低错误率的应用场合下，Bloom Filter
比其他常见的算法
（如hash，折半查找）
极大节省了空间。
Bloom Filter的详细介绍：
海量数据处理之Bloom Filter详解
【适用范围】
可以用来实现数据字典，进行数据的判重，或者集合求交集
【基本原理及要点】
原理要点：一是位数组， 而是k个独立hash函数。
1）位数组：
假设Bloom Filter使用一个m比特的数组来保存信息，
初始状态时，
Bloom Filter
是一个包含
m
位的
位数组
，每一位都置为
0，
即BF整个数组的元素都设置为0。
2）k个独立hash函数
为了表达S={x
1
, x
2
,…,x
n
}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。
当我们往
Bloom Filter中增加任意一个元素x时候，
我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。
即第
i
个哈希函数映射的位置
hash
i
(x)
就会被置为
1
（
1
≤
i
≤
k
）。
注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。
