免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP，暢享免費電子書等14項超值服

開通VIP

首頁

好書

留言交流

下載APP

聯(lián)系客服
布隆過濾器java實現(xiàn)

網(wǎng)上有很多的原理解釋說明，此處不再對bloom filter做過多的說明，直接上代碼（注：代碼參考了網(wǎng)上其他博客的實現(xiàn)，比如布隆過濾器（Bloom Filter）Java實現(xiàn)）

  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.  * 描述： 布隆過濾器，傳統(tǒng)的布隆過濾器不支持從集合中刪除成員 
  24.  */  
  25. public class BloomFilterTest {  
  26.     //DEFAULT_SIZE為2的29次方，即此處的左移28位  
  27.     private static final int DEFAULT_SIZE = 2<<28;  
  28.     /* 
  29.      * 不同哈希函數(shù)的種子，一般取質(zhì)數(shù) 
  30.      * seeds數(shù)組共有8個值，則代表采用8種不同的哈希函數(shù) 
  31.      */  
  32.     private int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};  
  33.     /* 
  34.      * 初始化一個給定大小的位集 
  35.      * BitSet實際是由“二進制位”構(gòu)成的一個Vector。 
  36.      * 假如希望高效率地保存大量“開－關(guān)”信息，就應(yīng)使用BitSet. 
  37.      */  
  38.     private BitSet bitSets = new BitSet(DEFAULT_SIZE);  
  39.     //構(gòu)建hash函數(shù)對象  
  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.          *  通過調(diào)用SimpleHash.hash(),可以得到根據(jù)8種hash函數(shù)計算得出hash值。   
  48.          *  傳入DEFAULT_SIZE(最終字符串的長度），seeds[i](一個指定的質(zhì)數(shù))即可得到需要的那個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.      * 創(chuàng)建時間：2014-8-30 下午02:07:35 
  61.      * 描述：將給定的字符串標記到bitSets中，即設(shè)置字符串的8個函數(shù)值的位置為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.      * 創(chuàng)建時間：2014-8-30 下午02:12:30 
  74.      * 描述：判斷給定的字符串是否已經(jīng)存在在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函數(shù)值中有一個位置不存在即可判斷為不存在Bloofilter中  
  87.                 return false;  
  88.             }  
  89.         }  
  90.           
  91.         return true;  
  92.     }  
  93.       
  94.     /** 
  95.      *  
  96.      * 方法名：init 
  97.      * 作者：zhouyh 
  98.      * 創(chuàng)建時間：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.      * 創(chuàng)建時間：2014-8-30 下午02:26:59 
  130.      * 描述：根據(jù)傳入的流，初始化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.             //創(chuàng)建輸入流  
  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.             //關(guān)閉流  
  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.      * 創(chuàng)建時間：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.plating.org/news_info.asp?pid=28&id=2857"));  
  193.     }  
  194.       
  195.     public static class SimpleHash {  
  196.         /* 
  197.          * cap為DEFAULT_SIZE，即用于結(jié)果的最大字符串的值 
  198.          * seed為計算hash值的一個key值，具體對應(yīng)上文中的seeds數(shù)組 
  199.          */  
  200.         private int cap;  
  201.         private int seed;  
  202.         /** 
  203.          *  
  204.          * 構(gòu)造函數(shù) 
  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.          * 創(chuàng)建時間：2014-8-30 下午01:47:10 
  218.          * 描述：計算hash的函數(shù)，用戶可以選擇其他更好的hash函數(shù) 
  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）對網(wǎng)址的判重上

本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊舉報。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
BloomFilter——大規(guī)模數(shù)據(jù)處理利器
深入解析String#intern 及其可能帶來的問題
基于list_head實現(xiàn)的通用內(nèi)核Hash表
PHP擴展編寫第二步：參數(shù)，數(shù)組，以及ZVAL
Java的Hashtable實現(xiàn)
BloomFilter算法的C#簡化版,主要應(yīng)用于URL消重 - King's blog ...
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)！
如果VIP功能使用有故障，
可點擊這里聯(lián)系客服！

聯(lián)系客服