布隆过滤器BloomFilter Java实现

喜欢ヅ旅行 2022-11-04 14:29 214阅读 0赞

关于**布隆过滤器**BloomFilter的概念原理请参考下列文章  
[https://www.jasondavies.com/bloomfilter][https_www.jasondavies.com_bloomfilter]  
[http://llimllib.github.io/bloomfilter-tutorial][http_llimllib.github.io_bloomfilter-tutorial]

Java领域可以使用Google 的Guava框架里的实现**布隆过滤器**。

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>30.1-jre</version>
    </dependency>

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    import java.math.BigDecimal;
    
    public class BloomFilterDemo {
        /**
         * 预期数据量(实际数据如果超过预期数据将会导致误判率升高)
         */
        private static int dataSize = 1000000;
    
        /**
         * 能容忍的误判率(误判率不能为0,BloomFilter理论上存在误判的情况)
         */
        private static double falseRate = 0.0001;
    
        private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), dataSize, falseRate);
    
    
        public static void main(String[] args) {
            //存储100万条数据到bloomFilter中
            int inputSize = 1000000;
            for (int i = 0; i < inputSize; i++) {
                bloomFilter.put(i);
            }
    
            int errorCount = 0;
            //测试误判率，即构造没有存储的数据去bloomFilter中判断
            int testSize = inputSize * 2;
            for (int i = inputSize; i < testSize; i++) {
                if (bloomFilter.mightContain(i)) {
                    errorCount++;
                }
            }
            System.out.println("误判总次数：" + errorCount);
            System.out.println("误判比例：" + (new BigDecimal(errorCount).divide(new BigDecimal(inputSize), 6, BigDecimal.ROUND_HALF_UP)));
        }
    }

实际使用时，自行构造放到**布隆过滤器** **BloomFilter** 中的对象。

**布隆过滤器** **BloomFilter** 的使用场景参考：  
[https://blog.csdn.net/lovingprince/article/details/6632328][https_blog.csdn.net_lovingprince_article_details_6632328]  
[https://www.cnblogs.com/sunsky303/p/11834102.html][https_www.cnblogs.com_sunsky303_p_11834102.html]

[https_www.jasondavies.com_bloomfilter]: https://www.jasondavies.com/bloomfilter
[http_llimllib.github.io_bloomfilter-tutorial]: http://llimllib.github.io/bloomfilter-tutorial
[https_blog.csdn.net_lovingprince_article_details_6632328]: https://blog.csdn.net/lovingprince/article/details/6632328
[https_www.cnblogs.com_sunsky303_p_11834102.html]: https://www.cnblogs.com/sunsky303/p/11834102.html