`

布隆过滤器(Bloom Filter)之java实例

阅读更多

 在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。

今天,我们介绍一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

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

假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 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 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。

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

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

package com.huigao.util;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
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 BitSet getBits() {
			return bits;
		}

		public void setBits(BitSet bits) {
			this.bits = bits;
		}

		public BloomFilter(){
	    	
	    }
	       
	    public BloomFilter(String key){   
	        this.key = key;   
	    }   
	       
	    private int[] lrandom(String key){   
	        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(String key){   
	        if(exist( key)){   
	            System.out.println("已经包含("+key+")");   
	            return;   
	        }   
	        int keyCode[] = lrandom(key);   
	        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(String key){   
	        int keyCode[] = lrandom(key);   
	        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 void saveBit(String filename){
	    	
	    	try {
	    		File file=new File(filename);
				ObjectOutputStream oos=new ObjectOutputStream(new FileOutputStream(file,false));
				oos.writeObject(bits);
				oos.flush();
				oos.close();
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			} catch (IOException e) {
				e.printStackTrace();
			}
	    }
	    
	    public BitSet readBit(String filename){
	    	BitSet bits=new BitSet(defaultSize);
	       File file=new File(filename);
	       if(!file.exists()){
	    	   return bits;
	       }
	       try {
			ObjectInputStream ois=new ObjectInputStream(new FileInputStream(file));
			 bits=(BitSet)ois.readObject();
			ois.close();
			
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
		}
		return bits;
	    }
	    public static void main(String[] args) {   
	    	
	    	String fileName="c:\\test\\BloomFilter.txt";
	    	String url="http://www.agrssdddd.com/";
	    	BloomFilter bf=new BloomFilter();
	    	BitSet bitSet=bf.readBit(fileName);
	    	bf.setBits(bitSet);
	    	bf.add(url);
	    System.out.println(bf.exist(url));
	    bf.saveBit(fileName);
	    
	    	
	      /*  BloomFilter f = new BloomFilter("http://www.agrilink.cn/");   
	        f.add();   
	        System.out.println(f.exist());   */
//	        f.set0();   
//	        System.out.println(f.exist());   
	    }   

}   

 

 

分享到:
评论
5 楼 willwen 2014-02-11  
有个疑问,楼主,为何初始化bits 从txt读取已有的网址是直接以下语句就可以完成
  bf.setBits(bitSet); 
为何不需要对txt文件中的网址逐个调用add方法,即为何不需要逐个调用lrandom方法,谢谢!
4 楼 slqprrx 2011-10-20  
for (int j = 1; j < 30; j++) {
    String mk;
    if(j < 10)
    mk = "0" + j;
    else
    mk = String.valueOf(j);
    System.out.println(mk + "->" + (5000 << j));
}


结果:
01->10000
02->20000
03->40000
04->80000
05->160000
06->320000
07->640000
08->1280000
09->2560000
10->5120000
11->10240000
12->20480000
13->40960000
14->81920000
15->163840000
16->327680000
17->655360000
18->1310720000
19->-1673527296
20->947912704
21->1895825408
22->-503316480
23->-1006632960
24->-2013265920
25->268435456
26->536870912
27->1073741824
28->-2147483648
29->0
30->0
31->0
32->5000
33->10000
34->20000
35->40000
36->80000
37->160000
38->320000
39->640000
40->1280000
41->2560000
42->5120000
43->10240000
44->20480000
45->40960000
46->81920000
47->163840000
48->327680000
49->655360000
50->1310720000
51->-1673527296
52->947912704
53->1895825408
54->-503316480
55->-1006632960
56->-2013265920
57->268435456
58->536870912
59->1073741824
3 楼 slqprrx 2011-10-20  
徐风子 写道
private int defaultSize = 5000 << 10000;
这行写得太潇洒了……

这个的确是够潇洒的。。[
2 楼 徐风子 2011-09-26  
private int defaultSize = 5000 << 10000;
这行写得太潇洒了……
1 楼 徐风子 2011-09-26  
private int defaultSize = 5000 << 10000;    

相关推荐

    布隆过滤器BloomFilters的一个简单Java库

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...

    bloom filter布隆过滤器学习资料大全

    布隆过滤器(Bloom Filter)是一种空间效率极高...通过这个“bloom filter布隆过滤器学习资料大全”,你可以深入研究布隆过滤器的理论、算法实现以及在不同场景下的应用实例,提升对这一重要数据结构的理解和应用能力。

    test-bloomfilter.zip

    要使用Redisson实现布隆过滤器,我们需要在SpringBoot应用中引入Redisson的依赖,配置Redis连接,并创建对应的BloomFilter实例。在代码中,我们可以调用`bf.add()`方法向过滤器添加元素,使用`bf.contains()`方法...

    介绍Bloom Filter(布隆过滤器)原理、实现及具体应用

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会误判,但不会漏判,即可能存在假阳性(False Positive),但绝不会有假阴性(False Negative)。...

    reids布隆过滤器压缩包

    在Redis中,`BF`(Bloom Filter)命令集提供了对布隆过滤器的操作。例如,`BF.ADD`用于添加元素,`BF.MADD`可以一次添加多个元素,`BF.EXISTS`用来检查元素是否存在,`BF.SCAND`则允许批量查询元素。这些命令的设计...

    Python-cljcbloom一个用Clojure脚本实现的跨平台布隆过滤器

    要使用Python-cljcbloom,开发者需要安装库,然后导入并创建布隆过滤器实例,添加元素,最后进行查询。示例代码可能如下: ```python from cljc_bloom import BloomFilter bloom = BloomFilter(capacity=...

    redis高可用core

    3. **负载均衡**:为了更有效地分配读请求,可以使用负载均衡器,如Nginx或LVS,根据策略将请求路由到合适的从节点。 4. **一致性问题**:虽然读写分离能提升性能,但可能导致短暂的数据不一致。为了解决这个问题,...

    RedisBloom-2.0.3.tar.gz

    RedisBloom是一个专门为Redis设计的高效、可扩展的布隆过滤器模块,它在数据存储和检索中扮演着重要角色,特别是在需要处理大量潜在重复数据的场景中。2.0.3版本是RedisBloom的一个稳定版本,适用于CentOS 7和9操作...

    bloom

    在IT行业中,"bloom"通常与数据结构和算法中的布隆过滤器(Bloom Filter)有关,这是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。"盛开"可能指的是该过滤器在处理大量数据时的高效性能,...

    go-cuckoof:去实现布谷鸟过滤器

    布谷鸟过滤器(Cuckoo Filter)是一种空间效率极高的数据结构,常用于近似成员关系查询,类似于布隆过滤器(Bloom Filter)。它由Edward O. Fanaee-T和Gang Wang在2014年提出,其设计灵感来源于布谷鸟巢寄生行为,故...

    Node.js-hyperfilter用于过滤分布式数据流

    hyperfilter的工作原理可以简单理解为一种布隆过滤器(Bloom Filter)的变体。布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。尽管可能会有误判,但在处理海量数据时,其...

    Java调用Redis 简单Demo

    此外,Redis还支持事务(Transaction)、发布/订阅(Publish/Subscribe)、布隆过滤器(Bloom Filter)等功能,可以根据实际需求选择使用。 总结起来,Java调用Redis主要涉及以下知识点: 1. 引入Jedis库 2. 创建...

    大数据量,海量数据 处理方法总结.pdf

    布隆过滤器可以视为位图的一个扩展,在其基础上增加了多个哈希函数,提高了处理海量数据的能力。位图数据结构的一个经典应用场景是海量日志数据的处理,比如找出某天访问某网站次数最多的IP地址。 具体应用实例包括...

    百度2012年实习生招聘笔试试题

    由于无法使用哈希表来直接比较URL,可以考虑使用布隆过滤器(Bloom Filter)来减少存储需求。布隆过滤器是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。 1. **算法步骤**: - 使用布隆...

    RoaringBitmap.zip

    它在处理大规模数据集时能够提供显著的性能优势,比传统的布隆过滤器(Bloom Filter)和Java内置的BitSet类更为高效。RoaringBitmap的设计目标是减少内存占用并加快位操作的速度。 RoaringBitmap的核心思想是将一个...

    HBase.The.Definitive.Guide

    书中介绍了Get、Put、Scan等基本操作,以及如何优化查询性能,例如使用过滤器(Filter)和布隆过滤器(Bloom Filter)。此外,还涉及到了HBase的分布式特性,如Region划分和RegionServer的角色,以及数据的分裂和...

    用于电力大数据快速组合查询的动态索引技术.zip

    4. 动态索引技术实例:例如,跳跃式B+树(Skip List)和布隆过滤器(Bloom Filter)等数据结构常被用于动态索引。跳跃式B+树允许快速跳过多个节点,提高查询速度;布隆过滤器则可以快速判断一个元素是否可能存在,...

    JS小游戏源码

    JS可以处理复杂的几何形状碰撞,比如使用布隆过滤器(Bloom Filter)或自定义算法来检测两个球是否接触。同时,游戏的计分系统、球的发射角度计算以及背景动画的实现,都是JS编程的实例。 3. **开心消消乐**:这款...

    基于redis的二级缓存

    2. **缓存穿透**:防止查询不存在的数据导致Redis频繁被查询,可以使用布隆过滤器(Bloom Filter)预先过滤掉不可能存在的key,降低无效请求。 3. **缓存击穿**:当热点数据过期,同时大量请求涌向数据库,造成数据库...

Global site tag (gtag.js) - Google Analytics