分享

布隆过滤器java实现

 Tornador 2015-02-02

网上有很多的原理解释说明,此处不再对bloom filter做过多的说明,直接上代码(注:代码参考了网上其他博客的实现,比如布隆过滤器(Bloom Filter)Java实现

  1. /** 
  2.   * 项目名:SpiderCrawler 
  3.   * 文件名:BloomFilterTest.java 
  4.   * 作者:zhouyh 
  5.   * 时间:2014-8-29 下午02:54:56 
  6.   * 描述:TODO(用一句话描述该文件做什么)  
  7.   */  
  8. package com.utilTest;  
  9.   
  10. import java.io.BufferedReader;  
  11. import java.io.File;  
  12. import java.io.FileInputStream;  
  13. import java.io.IOException;  
  14. import java.io.InputStream;  
  15. import java.io.InputStreamReader;  
  16. import java.util.BitSet;  
  17.   
  18. /** 
  19.  * 类名: BloomFilterTest 
  20.  * 包名: com.utilTest 
  21.  * 作者: zhouyh 
  22.  * 时间: 2014-8-29 下午02:54:56 
  23.  * 描述: 布隆过滤器,传统的布隆过滤器不支持从集合中删除成员 
  24.  */  
  25. public class BloomFilterTest {  
  26.     //DEFAULT_SIZE为2的29次方,即此处的左移28位  
  27.     private static final int DEFAULT_SIZE = 2<<28;  
  28.     /* 
  29.      * 不同哈希函数的种子,一般取质数 
  30.      * seeds数组共有8个值,则代表采用8种不同的哈希函数 
  31.      */  
  32.     private int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};  
  33.     /* 
  34.      * 初始化一个给定大小的位集 
  35.      * BitSet实际是由“二进制位”构成的一个Vector。 
  36.      * 假如希望高效率地保存大量“开-关”信息,就应使用BitSet. 
  37.      */  
  38.     private BitSet bitSets = new BitSet(DEFAULT_SIZE);  
  39.     //构建hash函数对象  
  40.     private SimpleHash[] hashFuns = new SimpleHash[seeds.length];  
  41.     //布隆过滤器配置文件存放路径  
  42.     private String path = "";  
  43.       
  44.     public BloomFilterTest(String path){  
  45.         /** 
  46.          *  给出所有的hash值,共计seeds.length个hash值。共8位。 
  47.          *  通过调用SimpleHash.hash(),可以得到根据8种hash函数计算得出hash值。   
  48.          *  传入DEFAULT_SIZE(最终字符串的长度),seeds[i](一个指定的质数)即可得到需要的那个hash值的位置。         
  49.          */  
  50.         for(int i=0; i<seeds.length; i++){  
  51.             hashFuns[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);  
  52.         }  
  53.         //配置文件路径地址  
  54.         this.path = path;  
  55.     }  
  56.     /** 
  57.      *  
  58.      * 方法名:add 
  59.      * 作者:zhouyh 
  60.      * 创建时间:2014-8-30 下午02:07:35 
  61.      * 描述:将给定的字符串标记到bitSets中,即设置字符串的8个函数值的位置为1 
  62.      * @param value 
  63.      */  
  64.     public synchronized void add(String value){  
  65.         for(SimpleHash hashFun : hashFuns){  
  66.             bitSets.set(hashFun.hash(value), true);  
  67.         }  
  68.     }  
  69.     /** 
  70.      *  
  71.      * 方法名:isExit 
  72.      * 作者:zhouyh 
  73.      * 创建时间:2014-8-30 下午02:12:30 
  74.      * 描述:判断给定的字符串是否已经存在在bloofilter中,如果存在返回true,不存在返回false 
  75.      * @param value 
  76.      * @return 
  77.      */  
  78.     public synchronized boolean isExit(String value){  
  79.         //判断传入的值是否为null  
  80.         if(null == value){  
  81.             return false;  
  82.         }  
  83.           
  84.         for(SimpleHash hashFun : hashFuns){  
  85.             if(!bitSets.get(hashFun.hash(value))){  
  86.                 //如果判断8个hash函数值中有一个位置不存在即可判断为不存在Bloofilter中  
  87.                 return false;  
  88.             }  
  89.         }  
  90.           
  91.         return true;  
  92.     }  
  93.       
  94.     /** 
  95.      *  
  96.      * 方法名:init 
  97.      * 作者:zhouyh 
  98.      * 创建时间:2014-8-30 下午02:28:49 
  99.      * 描述:读取配置文件 
  100.      */  
  101.     public void init(){  
  102.         File file = new File(path);  
  103.         FileInputStream in = null;  
  104.         try {  
  105.             in = new FileInputStream(file);  
  106.             long lt = System.currentTimeMillis();  
  107.             read(in);  
  108.             System.out.println(System.currentTimeMillis()-lt);  
  109.             System.out.println(Runtime.getRuntime().totalMemory());  
  110.         }catch(Exception e){  
  111.             e.printStackTrace();  
  112.         }finally{  
  113.             try {  
  114.                 if(in!=null){  
  115.                     in.close();  
  116.                     in = null;  
  117.                 }             
  118.             } catch (IOException e) {  
  119.                 // TODO Auto-generated catch block  
  120.                 e.printStackTrace();  
  121.             }  
  122.         }  
  123.     }  
  124.       
  125.     /** 
  126.      *  
  127.      * 方法名:read 
  128.      * 作者:zhouyh 
  129.      * 创建时间:2014-8-30 下午02:26:59 
  130.      * 描述:根据传入的流,初始化bloomfilter 
  131.      * @param in 
  132.      */  
  133.     private void read(InputStream in){  
  134.         if(null == in){ //如果in为null,则返回  
  135.             return;  
  136.         }  
  137.           
  138.         int i = 0;  
  139.         InputStreamReader reader = null;  
  140.           
  141.         try {  
  142.             //创建输入流  
  143.             reader = new InputStreamReader(in, "UTF-8");  
  144.             BufferedReader buffReader = new BufferedReader(reader, 512);  
  145.             String theWord = null;            
  146.             do {  
  147.                 i++;              
  148.                 theWord = buffReader.readLine();  
  149.                 //如果theWord不为null和空,则加入Bloomfilter中  
  150.                 if(theWord!=null && !theWord.trim().equals("")){  
  151.                     add(theWord);  
  152.                 }  
  153.                 if(i%10000 == 0){  
  154.                     System.out.println(i);  
  155.                 }  
  156.                   
  157.             } while (theWord != null);  
  158.               
  159.         } catch (IOException e){  
  160.             e.printStackTrace();  
  161.         } finally{  
  162.             //关闭流  
  163.             try {  
  164.                 if(reader != null){  
  165.                     reader.close();  
  166.                     reader = null;  
  167.                 }                 
  168.                 if(in != null){  
  169.                     in.close();  
  170.                     in = null;  
  171.                 }  
  172.             } catch (IOException e) {  
  173.                 // TODO: handle exception  
  174.                 e.printStackTrace();  
  175.             }  
  176.               
  177.         }  
  178.     }  
  179.       
  180.     /** 
  181.      * 方法名:main 
  182.      * 作者:zhouyh 
  183.      * 创建时间:2014-8-29 下午02:54:56 
  184.      * 描述:TODO(这里用一句话描述这个方法的作用) 
  185.      * @param args 
  186.      */  
  187.     public static void main(String[] args) {  
  188.         // TODO Auto-generated method stub  
  189.         BloomFilterTest bloomFilterTest = new BloomFilterTest("f:/fetchedurls.txt");  
  190.         bloomFilterTest.init();  
  191.           
  192.         System.out.println(bloomFilterTest.isExit("http://www./news_info.asp?pid=28&id=2857"));  
  193.     }  
  194.       
  195.     public static class SimpleHash {  
  196.         /* 
  197.          * cap为DEFAULT_SIZE,即用于结果的最大字符串的值 
  198.          * seed为计算hash值的一个key值,具体对应上文中的seeds数组 
  199.          */  
  200.         private int cap;  
  201.         private int seed;  
  202.         /** 
  203.          *  
  204.          * 构造函数 
  205.          * 作者:zhouyh 
  206.          * @param cap 
  207.          * @param seed 
  208.          */  
  209.         public SimpleHash(int cap, int seed){  
  210.             this.cap = cap;  
  211.             this.seed = seed;  
  212.         }  
  213.         /** 
  214.          *  
  215.          * 方法名:hash 
  216.          * 作者:zhouyh 
  217.          * 创建时间:2014-8-30 下午01:47:10 
  218.          * 描述:计算hash的函数,用户可以选择其他更好的hash函数 
  219.          * @param value 
  220.          * @return 
  221.          */  
  222.         public int hash(String value){  
  223.             int result = 0;  
  224.             int length = value.length();  
  225.             for(int i=0; i<length; i++){  
  226.                 result = seed*result + value.charAt(i);  
  227.             }  
  228.               
  229.             return (cap-1) & result;  
  230.         }  
  231.     }  
  232.   
  233. }  
实际使用中,效果还不错,主要用在了爬虫(crawler)对网址的判重上

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多