布隆過濾器原理（有眼睛就能看懂）

作用嘛就是用來過濾非法key，避免緩存穿透（請求直接打到資料庫）， 布隆過濾器

底層用的是位數組，不僅節省空間，性能也嘎嘎猛，而且占用記憶體不會随着使用變大

先貼demo後BB

public class MyBloomFilter {
    //你的布隆過濾器容量
    private static final int DEFAULT_SIZE = 2 << 28;
    //bit數組，用來存放key
    private static BitSet bitSet = new BitSet(DEFAULT_SIZE);
    //後面hash函數會用到，用來生成不同的hash值，可随意設定，别問我為什麼這麼多8，圖個吉利
    private static final int[] ints = {1, 6, 16, 38, 58, 68};

    //add方法，計算出key的hash值，并将對應下标置為true
    public void add(Object key) {
        Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
    }

    //判斷key是否存在，true不一定說明key存在，但是false一定說明不存在
    public boolean isContain(Object key) {
         boolean result = true;
        for (int i : ints) {
            //短路與，隻要有一個bit位為false，則傳回false
            result = result && bitSet.get(hash(key, i));
        }
        return result;
    }

    //hash函數，借鑒了hashmap的擾動算法，強烈建議大家把這個hash算法看懂，這個設計真的牛皮加閃電
    private int hash(Object key, int i) {
        int h;
        return key == null ? 0 : (i * (DEFAULT_SIZE - 1) & ((h = key.hashCode()) ^ (h >>> 16)));
    }
}      

測試

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
    }      

原理

通過對比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我話講完

嘤嘤嘤~