java-guava 布隆筛选器用法及比较

ゞ浴缸里的玫瑰 2024-01-15 00:57 32阅读 0赞

布隆筛选器使用场景：  
一般用于一个字符串是否存的预测，如爬虫是否抓取过这个URL等。  
优点：  
对于特大的集合来说，检索快、占用内存少等。  
缺点：  
存在漏报率。

分别使用 set、boolmfilter 检索一千万个数字，通过调整 fpp 值可以观察漏报率

public static void main (String[] args){
        double fpp = 0.00001f; //精度，漏报率
        //最大可存储 800w+ key,漏报率万分之1
        BloomFilter<String> bloomFilter
                = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),1024*1024*16,fpp);
    
        long begin = System.currentTimeMillis();
        int count=10000000;
        int wrong = 0;
        String key ="";
        for(int i=0;i<count;i++){
            key = String.valueOf(i);
            if(bloomFilter.mightContain(key)){
                wrong++;
                System.out.println("key="+key);
            }
            bloomFilter.put(key);
        }
        long timeCost = System.currentTimeMillis() - begin;
    
        System.out.println(MessageFormat.format(
                "boolm,漏报：{0},count={1},耗时：{2}"
                ,wrong,count,timeCost));
    
    
        System.out.println("xxx");
    
    
        Set<String> bs = new HashSet<>();
    
        wrong=0;
        begin = System.currentTimeMillis();
        for(int i=0;i<count;i++){
            key = String.valueOf(i);
            if(bs.contains(key)){
                wrong++;
                System.out.println("key="+key);
            }
            bloomFilter.put(key);
        }
        timeCost = System.currentTimeMillis() - begin;
        System.out.println(MessageFormat.format(
                "set,漏报：{0},count={1},耗时：{2}"
                ,wrong,count,timeCost));
    
        System.out.println("xxx");
    }