布隆过滤器（Bloom Filter）实现

布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）



现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

以下是实现方式：

import java.util.BitSet;

public class bloomFilter {

	private int defaultSize = 5000 << 10000;
	private int basic = defaultSize -1;
	private String key = null;
	private BitSet bits = new BitSet(defaultSize);
	
	public bloomFilter(String key){
		this.key = key;
	}
	
	private int[] lrandom(){
		int[] randomsum = new int[8];
		int random1 = hashCode(key,1);
		int random2 = hashCode(key,2);
		int random3 = hashCode(key,3);
		int random4 = hashCode(key,4);
		int random5 = hashCode(key,5);
		int random6 = hashCode(key,6);
		int random7 = hashCode(key,7);
		int random8 = hashCode(key,8);
		randomsum[0] = random1;
		randomsum[1] = random2;
		randomsum[2] = random3;
		randomsum[3] = random4;
		randomsum[4] = random5;
		randomsum[5] = random6;
		randomsum[6] = random7;
		randomsum[7] = random8;
		return randomsum;
	}
	
	private int[] sameLrandom(){
		int[] randomsum = new int[8];
		int random1 = hashCode(key,1);
		int random2 = hashCode(key,1);
		int random3 = hashCode(key,1);
		int random4 = hashCode(key,1);
		int random5 = hashCode(key,1);
		int random6 = hashCode(key,1);
		int random7 = hashCode(key,1);
		int random8 = hashCode(key,1);
		randomsum[0] = random1;
		randomsum[1] = random2;
		randomsum[2] = random3;
		randomsum[3] = random4;
		randomsum[4] = random5;
		randomsum[5] = random6;
		randomsum[6] = random7;
		randomsum[7] = random8;
		return randomsum;
	}
	
	private void add(){
		if(exist()){
			System.out.println("已经包含("+key+")");
			return;
		}
		int keyCode[] = lrandom();
		bits.set(keyCode[0]);
		bits.set(keyCode[1]);
		bits.set(keyCode[2]); 
		bits.set(keyCode[3]); 
		bits.set(keyCode[4]); 
		bits.set(keyCode[5]); 
		bits.set(keyCode[6]); 
		bits.set(keyCode[7]);
	}
	
	private boolean exist(){
		int keyCode[] = lrandom();
		if(bits.get(keyCode[0])&&
				bits.get(keyCode[1])
				&&bits.get(keyCode[2])
				&&bits.get(keyCode[3])
				&&bits.get(keyCode[4])
				&&bits.get(keyCode[5])
				&&bits.get(keyCode[6])
				&&bits.get(keyCode[7])){
			return true; 
		}
		return false;
	}
	
	private boolean set0(){
		if(exist()){
			int keyCode[] = lrandom();
			bits.clear(keyCode[0]);
			bits.clear(keyCode[1]);
			bits.clear(keyCode[2]);
			bits.clear(keyCode[3]);
			bits.clear(keyCode[4]);
			bits.clear(keyCode[5]);
			bits.clear(keyCode[6]);
			bits.clear(keyCode[7]);
			return true;
		}
		return false;
	}
	
	private int hashCode(String key,int Q){
		int h = 0;
		int off = 0;
	    char val[] = key.toCharArray();
	    int len = key.length();
		for (int i = 0; i < len; i++) {
            h = (30 + Q) * h + val[off++];
        }
		return changeInteger(h);
	}
	
	private int changeInteger(int h) {
		return basic & h;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		bloomFilter f = new bloomFilter("http://www.agrilink.cn/");
		f.add();
		System.out.println(f.exist());
		f.set0();
		System.out.println(f.exist());
	}

}

评论

1 楼 crackajackk 2010-09-07  

谢谢。。。。。。