BloomFilte 布隆过滤器原理与实现

梦里梦外; 2024-04-17 18:21 82阅读 0赞

## 布隆过滤器介绍 ##

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难

### 为什么要用布隆过滤器？ ###

遇到判重系统和缓存穿透时，伴随数据量很大，数十亿甚至更多，内存装不下且数据库检索又极慢的情况，考虑下布隆过滤器，因为它是一个空间效率占用极少和查询时间极快的算法，但是需要业务可以忍受一个判断失误率。

## 应用 ##

### 1、Google Guava 中的布隆过滤与布隆持久化 ###

### 布隆过滤器 ###

/**
     * Funnel，这是Guava中定义的一个接口，它和PrimitiveSink配套使用，
     * 主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……），
     * expectedInsertions 期望插入数据数，int或long
     * 默认用java.nio.ByteBuffer实现，最终均转化为byte数组
     * fpp期望误判率，比如1E-7（千万分之一）
     */
    BloomFilter<String> b = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.000001);
    b.put("121");
    b.put("122");
    b.put("123");
    System.out.println(b.mightContain("12321"));
    BloomFilter<String> b1 = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.000001);
    b1.put("aba");
    b1.put("abb");
    b1.put("abc");
    b1.putAll(b);
    System.out.println(b1.mightContain("123"));

## ##

### 布隆持久化 ###

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    import java.io.*;
    import java.nio.charset.Charset;
    import java.util.Properties;
    
    public class BloomFilterUtil {
    
    
        public final static String  bloomPath = "Bloom";
    
        public static BloomFilter<CharSequence> create() {
            /**
             * Funnel，这是Guava中定义的一个接口，它和PrimitiveSink配套使用，
             * 主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……），
             * expectedInsertions 期望插入数据数，int或long
             * 默认用java.nio.ByteBuffer实现，最终均转化为byte数组
             * fpp期望误判率，比如1E-7（千万分之一）
             */
            BloomFilter<CharSequence> filter = BloomFilter.create(
                    Funnels.stringFunnel(Charset.forName("utf-8")),
                    5000000,
                    0.00001);
            return filter;
        }
    
        /**
         * 持久化的数据加载到布隆
         *
         * @param path
         * @return
         */
        public static BloomFilter<CharSequence> readFrom(String path) {
            /**
             * Funnel，这是Guava中定义的一个接口，它和PrimitiveSink配套使用，
             * 主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……），
             * expectedInsertions 期望插入数据数，int或long
             * 默认用java.nio.ByteBuffer实现，最终均转化为byte数组
             * fpp期望误判率，比如1E-7（千万分之一）
             */
            BloomFilter<CharSequence> filter = BloomFilterUtil.create();
    
            if (null == path || path.isEmpty()) {
                return filter;
            }
            try {
                //将之前持久化的数据加载到Filter
                BufferedInputStream in = new BufferedInputStream(new FileInputStream(path));
                filter = BloomFilter.readFrom(in, Funnels.stringFunnel(Charset.forName("utf-8")));
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
                return null;
            }
            return filter;
        }
    
        /**
         * 布隆持久化
         *
         * @param bloomFilter
         * @param bloomPath
         * @throws IOException
         */
        public static void writeTo(BloomFilter bloomFilter, String bloomPath) throws IOException {
            BufferedOutputStream out = new BufferedOutputStream(new FileOutputStream(bloomPath));
            try {
                //数据持久化到本地
                bloomFilter.writeTo(out);
                out.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
    }

## ##

### 2、基于Redis的分布式布隆过滤器 ###

### Redis+Redission ###

Config config = new Config();
    config.useSingleServer().setAddress("redis://192.168.2.129:6379");
    RedissonClient client = Redisson.create(config);
    RBloomFilter<Object> bloomFilter = client.getBloomFilter("bf2");
    bloomFilter.tryInit(10, 0.01);
    bloomFilter.add("4");
    bloomFilter.add("3");
    bloomFilter.add("2");
    bloomFilter.add("1");
    boolean exists = bloomFilter.isExists();
    boolean contains = bloomFilter.contains("3");
    System.out.println("----1------"+exists);
    System.out.println("-----2-----"+contains);
    RAtomicLong aLong = client.getAtomicLong("redisson-aa");
    aLong.set(100L);
    System.out.println("-----3----"+aLong.get());