简介
Bloom Filter(又叫布隆过滤器)是由B.H.Bloom在1970年提出的一种多哈希函数映射的快速查找算法。该算法的原名叫：“Space/time trade-offs in hash coding with allowable errors”，即一种允许一定容错率的哈希算法，因为在实际应用中经常有这样的情况：普通hash算法相对高额的空间消耗承受不住过大的数据，而实际上对询问的正确性要求又不大。在这种情况下Bloom Filter的时空优越性就体现出来了。
为了说明Bloom Filter存在的重要意义，举一个实例：
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。比较靠谱的方法是建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。这个方法显然很合理，但是当数据量变得非常庞大的时候单一哈希函数发生冲突的概率太高。若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍！显然不符合实际。而事实上在这种应用中，少抓了几个网页的代价是很小的，所以其实并没有特别的必要来保证询问的完美正确性。
Bloom Filter算法相对朴素算法的区别就是使用了多个哈希函数，而不是一个。
初始化
- 创建一个$m$位$BitSet$，下标为$[0,m-1]$，将所有位初始化为0。
- 选择$k$个独立的均匀分布的的哈希函数$H =\{h_0\ h_1\ … h_{k-1}\}$，每一个$h_i$函数映射的值域在$[0,m-1]$中均匀分布。
- 我们将一个Bloom Filter 用一个$(m,n,k,H)$四元数表示，将需要查询的集合用$S$表示，将对于集合$S$的Bloom Filter 用$BF_s$表示，将那个$BitSet$中的第$i$位用$BF_s[i]$表示。
加值
为了将$x\in S$加入到$BF_s$中，我们需要计算$x$对于$k$个hash函数的值，并将其对应的$BF_s[i]$位置为１，即：
$$BF_s[i]=1,(0\leq i\leq k-1)$$
查询
对于待查询的元素$y$，我们同样需要将他用这$k$个hash函数进行映射，对于所得到的$k$个值，如果存在某一个值对应的$BF_s[i]$为０，则认为$y$存在集合$S$中，返回$true$，否则认为不存在，返回$false$。
删除
该数据结构不支持删除。
正确性
由于对于每一个加进集合中的元素$y$，其$k$个哈希值对应的那些比特位一定为１，所以如果$y$对$BF_s$的询问结果如果是$false$，那么可以断定$y$不在集合$S$中；但是如果$y$对$BF_s$的询问结果如果是$true$，那么我们并不能确实的断定$y$在集合$S$中。那么，由于每一个$BF_s[i]$被置为１的概率$p=1-(1-\frac1m)^{kn}$，我们可以从理论上证明判断失误的概率ｃ满足：$$c=p^k\times(1+O(\frac{k}{p}\sqrt{\frac{ln\ m-kln\ p}{m}}))$$即c是关于ｋ的可忽略函数，即我们总是可以通过调节参数来是我们的$BF_s$达到我们所要求的准确性。
参数选择
假设我们能容忍的出错几率为$\epsilon$，那么整个系统的效率应当取决与$m$和$k$值的选择。
数组大小m值的确定
由理论可以推得m值应当满足$$m\geq n log_2e\cdot log_2\frac1\epsilon.$$其中ｅ为自然对数。
哈希函数数目k值的确定
由于每一个$BF_s[i]$被置为１的概率为$$1-(1-\frac1m)^{kn}$$那么对于每一个返回值为$true$的询问，其判断失误的概率为$$(1-(1-\frac1m)^{kn})^k\approx(1-e^{\frac{kn}{m}})^k$$.当右边取最小值时，应满足关系式$$k=ln\ 2\times \frac{m}{n}$$如果m取上面的最优值，那么ｋ应当满足:$$k=log_2{\frac1\epsilon}.$$
其他操作
对于两个由唯一$(m,n,k,H)$构成的，用来处理两个不同集合$S_1$和$S_2$的Bloom Filter 来说，我们可以通过将$BF_{s_1}$和$BF_{s_2}$这两个$BitSet$进行位与运算得到一个新的Bloom Filter $BF_{s_1\cap_2}$