BloomFilter——大规模数据处理凶器[转]

2014-01-06

BloomFilter——大规模数据处理利器[转]　　图1.Bloom Filter加入字符串过程　　很简单吧？这样就将字符串str映射

BloomFilter——大规模数据处理利器[转]

　　图1.Bloom Filter加入字符串过程

　　很简单吧？这样就将字符串str映射到BitSet中的k个二进制位了。

(2)?检查字符串是否存在的过程?

　　下面是检查字符串str是否被BitSet记录过的过程：

　　对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后检查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否为1，若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1，则“认为”字符串str存在。

　　若一个字符串对应的Bit不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）

　　但是若一个字符串对应的Bit全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为false positive 。

(3)?删除字符串过程?

?? 字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。

　　Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

三. Bloom Filter参数选择?

?? (1)哈希函数选择

?? 　　哈希函数的选择对性能的影响应该是很大的，一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。

???(2)Bit数组大小选择?

?? 　　哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1。该文献证明了对于给定的m、n，当 k = ln(2)* m/n 时出错的概率是最小的。

?? 　　同时该文献还给出特定的k，m，n的出错概率。例如：根据参考文献1，哈希函数个数k取10，位数组大小m设为字符串个数n的20倍时，false positive发生的概率是0.0000889 ，这个概率基本能满足网络爬虫的需求了。 ?

四. Bloom Filter实现代码?

??　?下面给出一个简单的Bloom Filter的Java实现代码：

import?java.util.BitSet;

publicclass?BloomFilter?
{
/*?BitSet初始分配2^24个bit?*/?
privatestaticfinalint?DEFAULT_SIZE?=1<<25;?
/*?不同哈希函数的种子，一般应取质数?*/
privatestaticfinalint[] seeds?=newint[] {?5,?7,?11,?13,?31,?37,?61?};
private?BitSet bits?=new?BitSet(DEFAULT_SIZE);
/*?哈希函数对象?*/?
private?SimpleHash[] func?=new?SimpleHash[seeds.length];

public?BloomFilter()?
{
for?(int?i?=0; i?<?seeds.length; i++)
{
func[i]?=new?SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}

//?将字符串标记到bits中
publicvoid?add(String value)?
{
for?(SimpleHash f : func)?
{
bits.set(f.hash(value),?true);
}
}

//判断字符串是否已经被bits标记
publicboolean?contains(String value)?
{
if?(value?==null)?
{
returnfalse;
}
boolean?ret?=true;
for?(SimpleHash f : func)?
{
ret?=?ret?&&?bits.get(f.hash(value));
}
return?ret;
}

/*?哈希函数类?*/
publicstaticclass?SimpleHash?
{
privateint?cap;
privateint?seed;

public?SimpleHash(int?cap,?int?seed)?
{
this.cap?=?cap;
this.seed?=?seed;
}

//hash函数，采用简单的加权和hash
publicint?hash(String value)?
{
int?result?=0;
int?len?=?value.length();
for?(int?i?=0; i?<?len; i++)?
{
result?=?seed?*?result?+?value.charAt(i);
}
return?(cap?-1)?&?result;
}
}
}

参考文献：

[1]Pei Cao. Bloom Filters - the math.

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

[2]Wikipedia. Bloom filter.

http://en.wikipedia.org/wiki/Bloom_filter

热点排行

编程

BloomFilter——大规模数据处理凶器[转]