实现布隆过滤器

墨蓝 2023-10-10 17:47 64阅读 0赞

### 什么是布隆过滤器 ###

它实际上是由一个很长的二进制数组+一系列hash算法映射函数，用于判断一个元素是否存在于集合中。  
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

### 布隆过滤器原理 ###

布隆过滤器其实就是是一个BIT数组，通过一系列hash算法映射出对应的hash,然后将hash对应的数组下标位置改为1。查询时就是对数据在进行一系列hash算法得到下标，从BIT数组里取数据，**如果是1 则说明数据有可能存在，如果是0 说明一定不存在**。

### java实现布隆过滤器 ###

package com.fandf.test.redis;
    
    import java.util.BitSet;
    
    /**
     * java布隆过滤器
     *
     * @author fandongfeng
     */
    public class MyBloomFilter {
        
    
        /**
         * 位数组大小
         */
        private static final int DEFAULT_SIZE = 2 << 24;
    
        /**
         * 通过这个数组创建多个Hash函数
         */
        private static final int[] SEEDS = new int[]{
        4, 8, 16, 32, 64, 128, 256};
    
        /**
         * 初始化位数组，数组中的元素只能是 0 或者 1
         */
        private final BitSet bits = new BitSet(DEFAULT_SIZE);
    
        /**
         * Hash函数数组
         */
        private final MyHash[] myHashes = new MyHash[SEEDS.length];
    
        /**
         * 初始化多个包含 Hash 函数的类数组，每个类中的 Hash 函数都不一样
         */
        public MyBloomFilter() {
        
            // 初始化多个不同的 Hash 函数
            for (int i = 0; i < SEEDS.length; i++) {
        
                myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
            }
        }
    
        /**
         * 添加元素到位数组
         */
        public void add(Object value) {
        
            for (MyHash myHash : myHashes) {
        
                bits.set(myHash.hash(value), true);
            }
        }
    
        /**
         * 判断指定元素是否存在于位数组
         */
        public boolean contains(Object value) {
        
            boolean result = true;
            for (MyHash myHash : myHashes) {
        
                result = result && bits.get(myHash.hash(value));
            }
            return result;
        }
    
        /**
         * 自定义 Hash 函数
         */
        private class MyHash {
        
            private int cap;
            private int seed;
    
            MyHash(int cap, int seed) {
        
                this.cap = cap;
                this.seed = seed;
            }
    
            /**
             * 计算 Hash 值
             */
            int hash(Object obj) {
        
                return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));
            }
        }
    
        public static void main(String[] args) {
        
            String str = "好好学技术";
            MyBloomFilter myBloomFilter = new MyBloomFilter();
            System.out.println("str是否存在：" + myBloomFilter.contains(str));
            myBloomFilter.add(str);
            System.out.println("str是否存在：" + myBloomFilter.contains(str));
        }
    }

### Guava实现布隆过滤器 ###

引入依赖

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

package com.fandf.test.redis;
    
    import com.google.common.base.Charsets;
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    /**
     * @author fandongfeng
     */
    public class GuavaBloomFilter {
        
    
        public static void main(String[] args) {
        
            BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
            bloomFilter.put("好好学技术");
            System.out.println(bloomFilter.mightContain("不好好学技术"));
            System.out.println(bloomFilter.mightContain("好好学技术"));
        }
    }

### hutool实现布隆过滤器 ###

引入依赖

<dependency>
        <groupId>cn.hutool</groupId>
        <artifactId>hutool-all</artifactId>
        <version>5.8.3</version>
    </dependency>

package com.fandf.test.redis;
    
    import cn.hutool.bloomfilter.BitMapBloomFilter;
    import cn.hutool.bloomfilter.BloomFilterUtil;
    
    /**
     * @author fandongfeng
     */
    public class HutoolBloomFilter {
        
        public static void main(String[] args) {
        
            BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000);
            bloomFilter.add("好好学技术");
            System.out.println(bloomFilter.contains("不好好学技术"));
            System.out.println(bloomFilter.contains("好好学技术"));
        }
    }