布隆过滤器

布隆过滤器简介

布隆过滤器是一个位数组和哈希函数实现的一种数据结构，它相对于其他我们平常用的List，Set等更节省内存空间，不过它存在误判概率。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

例如申请100万个元素位数组只用10^6/8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间，特别节省空间。

布隆过滤器使用场景

判断一个元素是否在一个大量元素集中
对元素去重判断

布隆过滤器原理

添加

对添加的元素进行哈希运算，得到哈希值，并根据哈希值把对应数组下标的bit设为1

判断

对添加的元素进行哈希运算，得到哈希值，并根据哈希值去获得对应数组下标bit的值，如果都为1则添加的元素可能在存在，否则该元素不存在。
我的理解：如果在可能是假的，如果不在就是真的不在拉。

基本代码实现

package com.czj.testarray;

import java.util.BitSet;

/**
 * 创建在 2020/5/7 22:14
 */
public class MyBloomFilter<T> {

    //位数组默认大小
    private static final int DEFAULT_SIZE = 2<<24;

    //哈希种子,可以根据这个种子数组创建不同的哈希函数
    private static final int[] SEEDS= {4,7,520,3,143};

    //位数组
    private BitSet bitSet;

    //哈希函数
    private MyHash[] hashes;

    public MyBloomFilter(){
        this(DEFAULT_SIZE);
    }

    public MyBloomFilter(int size){
        bitSet = new BitSet(size);
        hashes = new MyHash[SEEDS.length];
        for (int i=0;i<SEEDS.length;i++){
            hashes[i] = new MyHash(size,SEEDS[i]);
        }
    }

    /**
     * @author czj
     * 添加元素
     * @date 2020/5/7 22:27
     * @param [value]
     * @return void
     */
    public void add(T value){
        for (MyHash hash:hashes){
            bitSet.set(hash.hash(value),true);
        }
    }

    /**
     * @author czj
     * 判断元素是否存在 可能会误判
     * 存在可能假存在，不存在是真不存在拉
     * @date 2020/5/7 22:27
     * @param [value]
     * @return boolean
     */
    public boolean contains(T value){
        boolean flag = true;
        for (MyHash hash:hashes){
            flag = flag && bitSet.get(hash.hash(value));
            if (!flag){
                break;
            }
        }
        return flag;
    }
    private static class MyHash{
        private int cap,seed;

        public MyHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        //这段哈希运算 网上看的。。。
        public int hash(Object value){
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }

    public static void main(String[] args) {
        MyBloomFilter<Integer> myBloomFilter = new MyBloomFilter<>();
        myBloomFilter.add(4);
        myBloomFilter.add(9);
        System.out.println(myBloomFilter.contains(123));
        myBloomFilter.add(123);
        System.out.println(myBloomFilter.contains(123));
        System.out.println(myBloomFilter.contains(4));
    }
}

结果

false
true
true

实际场景

上面只是为了搞明白布隆过滤器的原理，平常我们直接利用Google开源的 Guava中自带的布隆过滤器就ok拉。

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