海量数据处理专题（二）——Bloom Filter

海量数据向来都是百度，淘宝，腾讯面试的热点，虽然微软不看重这个，但是了解一下还是很有必要的。

最近在写倒排索引，希望继续关注本博。

===========================================================

【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，采用Bloom Filter的数据结构，可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍，不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典，进行数据的判重，或者集合求交集

【基本原理及要点】

对于原理来说很简单，位数组外加k个独立hash函数。Bloom filter提供两种基本的操作，将元素加入集合和判断某一元素是否属于该集合，一下说明如何操作：

将一个元素加入集合：首先将要加入集合的元素用k个hash函数进行hash，得到k个hash index，然后在集合的位数组中将这k个hash index的位置置1，下面用两幅图来描述这个过程。

 

bloom filter位数组（集合）的初始状态

插入两个个元素，X1，X2：

bloom-filter-插入元素

查找元素是否属于该集合：首先同样用定义的hash函数对该元素进行hash得到hash index，然后查位数组中对应的hash index是否都是1，如果是，则表明该元素属于该集合，反之不属于【当然不全是了，请继续看后面】，如图，判断元素Y1，Y2是否属于该集合。

 

bloom-filter-判断元素是否属于集合

如上图，由于y1的三个hash index有一个不为1，因此不属于该集合，而y2所有的hash index的位置上都为1，因此属于该集合。

【Bloom Filter的不足】

很明显上面这个查找过程并不保证....继续阅读：http://blog.redfox66.com/post/2010/09/24/mass-data-topic-2-bloom-filter.aspx