布隆过滤器原理（有眼睛就能看懂）

作用嘛就是用来过滤非法key，避免缓存穿透（请求直接打到数据库），布隆过滤器底层用的是位数组，不仅节省空间，性能也嘎嘎猛，而且占用内存不会随着使用变大

先贴demo后BB

public class MyBloomFilter {
    //后面hash函数会用到，用来生成不同的hash值，可以随便给，但别给奇数
    private final int[] ints = {6, 8, 16, 38, 58, 68};
    private Integer currentBeanCount = 0;
    //你的布隆过滤器容量
    private int DEFAULT_SIZE = Integer.MAX_VALUE;
    //bit数组，用来存放结果
    private final BitSet bitSet = new BitSet(DEFAULT_SIZE);

    public MyBloomFilter() {
    }

    public MyBloomFilter(int size) {
        if (size > Integer.MAX_VALUE) throw new RuntimeException("size is too large");
        if (size <= (2 << 8)) throw new RuntimeException("size is too small");
        DEFAULT_SIZE = size;
    }
	
	//获取当前过滤器的对象数量
    public Integer getCurrentBeanCount() {
        return currentBeanCount;
    }

    //计算出key的hash值，并将对应下标置为true
    public void push(Object key) {
        Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
        currentBeanCount++;
    }

    //判断key是否存在，true不一定说明key存在，但是false一定说明不存在
    public boolean contain(Object key) {
        boolean result = true;
        for (int i : ints) {
            result = result && bitSet.get(hash(key, i));
        }
        return result;
    }

    //hash算法，借鉴了hashmap的算法
    private int hash(Object key, int i) {
        int h;
        int index = key == null ? 0 : (DEFAULT_SIZE - 1 - i) & ((h = key.hashCode()) ^ (h >>> 16));
        return index > 0 ? index : -index;
    }
}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

测试

    public static void main(String[] args) {
        MyNewBloomFilter myNewBloomFilter = new MyNewBloomFilter();
        myNewBloomFilter.add("张学友");
        myNewBloomFilter.add("郭德纲");
        myNewBloomFilter.add("蔡徐鸡");
        myNewBloomFilter.add(666);
        System.out.println(myNewBloomFilter.isContain("张学友"));//true
        System.out.println(myNewBloomFilter.isContain("张学友 "));//false
        System.out.println(myNewBloomFilter.isContain("张学友1"));//false
        System.out.println(myNewBloomFilter.isContain("郭德纲"));//true
        System.out.println(myNewBloomFilter.isContain("蔡徐老母鸡"));//false
        System.out.println(myNewBloomFilter.isContain(666));//true
        System.out.println(myNewBloomFilter.isContain(888));//false
    }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

原理

通过对比hash算法计算出来的下标，注意，我们是对比一组，而不是只看一次，一次hash结果对应一个下标

把同一个key进行多次hash运算，将hash出来的下标放入数组，数组默认全为0，放入元素后该下标就为1，后面判断是否存在元素的时候也是进行同样次数的hash运算，看下结果对应的所有下标是否全为1，若全为1，则代表该key可能存在，若存在不为1的，则说明该key一定不存在；

默认位数组：[0，0，0，0，0，0]
比方说有个已知key的下标是0，2，5
对应位数组：[1，0，1，0，0，1]
判断某个未知key存不存在的时候，假设我们计算出来的下标是0，2，4
对应位数组：[1，0，1，0，1，0]
此时位数组内5对应下标值为0，而已知key位数组的5对应下标位1，说明这两个一定不是同一个key

相反，如果某个key计算出来的下标为[1，0，1，0，0，1]，只能说这个key可能存在，因为这个位置可能是其它key计算出来的

如果对上面的hash算法有疑惑，请移步帮你真正理解hashCode和hash算法

demo复制可用，家里有条件的都在编译器上跑一跑，测一测

ok我话讲完

嘤嘤嘤~

文章来源: huangjie.blog.csdn.net，作者：负债程序猿，版权归原作者所有，如需转载，请联系作者。

原文链接：huangjie.blog.csdn.net/article/details/108407706