Bloom Filter学习

Bloom Filter学习
概述
    当对一个元素x进行判断是否属于集合S时，我们常利用的是hash算法。hash查询虽然非常有价值，但是hash算法对空间的利用率基本为50%，因此当对海量数据进行处理、或者keys自身非常大时，这种利用hash算法的查询方式便变得不实用。Bloom Filter 是对hash函数的一种改进，是空间效率极高的基于随机数的一种数据结构。利用Bloom Filter 可以让你在有限的空间里完成对成员的测试，这个特性将对与海量数据的处理具有极大的吸引力，但是Bloom Filter的这种空间的节省也是有一定代价的，那就是存在着一定的假命中，即误判的风险，并且这种风险根据集合元素的数量，hash函数的选择以及bloom filter空间的大小有密切的关系。因此，此数据结构不适用于“零错误”的场景。由于bloom filter利用了极小的错误率带来了极大的空间利用率，所以bloom filter被被广泛应用于分布式数据库，网络缓存，对等网络，信息检索等领域。

Bloom Filter 原理
    Bloom FIlter 基本思想是利用了多个相互独立的hash函数来对元素的存在与否进行查询，该结构主要包含两部分：k个相互独立的hash函数和一个包含m位的位向量。假设初始集合为具有n个元素的集合S={x1, x2,...,xn}，并且Bloom Filter初始是一个包含m位的位向量，每一位均置为0。Bloom Filter使用k个相互独立的hash函数{h1,h2,...,hk}，这些hash函数将集合S中的元素映射到{0,1,...,m-1}范围中。对于每一个元素x属于S，则将位向量中对应的h1(x),h2(x),...,hk(x)相应位置为1。之后，当判断元素w的归属性时，就可以通过位向量中h1(w),h2(w),...,hk(w)对应的位全为1来表示元素w属于集合S,如果某一位或则多位存储单元为0，则表示元素w不属于集合S。

错误估计
    正如你想的那样，如果元素w不属于集合S，然而恰好在集合中存在某些元素将w对应的位向量中h1(w),h2(w),...,hk(w)对应位全只为了1，这就产生了“假命中”。假命中率依赖与位向量的长度m，集合元素n的数量。而且如果hash函数选择不好，hash函数产生的热点(即hash值频繁的分布在某些位上)也会增加假命中率。
    在估计之前为了简化模型，我们假设kn
总结
    Bloom Filter在元素的查找过程中利用了多个hash函数进行判定，带有一定的时间换空间性质，但是其在解决问题的同时又引入了误判的问题。但是，在合理选定高质量hash函数以及设计合理的位向量大小后，假命中率会非常的低。由于Bloom filters 非常的简洁，因而其倍受重视。同时，由于Bloom Filter使用hash来存储数据，因此不可能在不做穷举搜索的情况下重建集合S中的元素，所以，Bloom Filter能在不向全世界广播列表的情况下共享已有的资料信息，因此，它们在p2p应用中将非常有用。伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现，Bloom Filter必将获得更大的发展。


reference:
    [1] http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
    [2] 使用 Bloom Filters   原作者:Maciej Ceglowski  译者:兰花仙子
    [3] Bloom Filters的研究和应用 池净，方启泉