一、布隆過濾器原理

　　 如果想要判斷一個元素是不是在一個集合中存在，一般的想法是將所有元素保存起來，然后再拿著這個元素在集合中一個一個進行比對。但是隨著集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。 針對這種需要在大量數據中去判斷某一個值是事否存在的情況，1970年由布隆提出了布隆過濾器的概念。布隆過濾器本質是一個位數組，位數組就是數組的每個元素都只占用 1 bit 。每個元素只能是 0 或者 1。這樣申請一個 10000 個元素的位數組只占用 10000 / 8 = 1250 字節 的空間。布隆過濾器除了一個位數組，還有 n個哈希函數。

　　 它具體的實現思想是并不將具體的數據存儲在數組中，而是通過hash函數對要存儲的數據進行三次hash運算，并將hash運算的結果做為位數組的下標，將對應的數組元素修改為1。

　　 例如：我們要將"oracle"、"database"、"filter"存儲到布隆過濾器中可以這樣做。如下圖所示

<img src=" 防緩存穿透利器-隆過濾器(BloomFilter).assets/image-20220716172346986.png" 
alt="image-20220716172346986" style="zoom:67%;" />

　　 從上圖中可以看到，我們有三個hash函數(h1()、h2()、h3())和一個位數組，oracle經過三個hash函數，得到第1、4、5位為1，database同理得到2、5、10位1，這樣如果我們需要判斷oracle是否在此位數組中，則通過hash函數判斷位數組的1、4、5位是否均為1，如果均為1，則判斷oracle在此位數組中，database同理。這就是布隆過濾器判斷元素是否在集合中的原理。

　　 但同學們也會發現，如果我們現在要判斷"mysql"是否存在，例如它通過三次hash運算得到的值分別是4,5,10。現在即使你的位數中沒有存儲“mysql”,布隆過濾器也會判斷它存在。這是因為"oracle"、"database"、"filter"算出的hash值已經導致上面的三個位置的值被改為了1，這樣就會導致誤判。但是可以保證的是，如果布隆過濾器判斷一個元素不在一個集合中，那這個元素一定不會再集合中。

　　 產生上面誤判的主要原因是hash碰撞導致的。但如果我們將位數組設置的足夠大，并且讓hash運算執行的次數多一些，這樣就會降低誤判率。

　　 布隆過率器還有另一個問題就是不能刪除。這是因為在位數組上的同一個點有可能有多個輸入值的映射，如果刪除了會影響布隆過濾器里其他元素的判斷結果。

　　 所以我們可以總結出布隆過濾器的優缺點如下：

　　- 優點：

　　- 所占空間小(并不存儲真正的數據)，空間效率高

　　- 查詢時間短

　　- 缺點:

　　- 元素添加到數組中后，不能被刪除

　　- 有一定的誤判率

　　二、布隆過濾器使用場景

　　- 解決緩存穿透問題，緩存穿透是指查詢一個一定不存在的數據，由于緩存是不命中就到數據庫中去查，并且出于容錯考慮，如果從數據庫中查不到數據則不寫入緩存，這將導致這個不存在的數據每次請求都要到數據庫中去查詢，失去了緩存的意義。在流量大時，可能數據庫就掛掉了，要是有人利用不存在的key頻繁攻擊我們的應用，這就是漏洞。這時候可以用布隆過濾器當緩存的索引，只有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則再到數據庫中查。如果不在布隆器中，則直接返回。

　　- 在業務場景中可以用來判斷用戶是否閱讀過某些文章或視頻，比如抖音或頭條，當然會導致一定的誤判，但不會讓用戶看到重復的內容。

　　- 黑名單：比如在郵件系統中可以使用布隆器設置黑名單，判斷郵件地址是否在黑名單中。也可以設IP黑名單防止網格爬蟲等。

　　- 垃圾郵件過濾，從數十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱。

　　三、實踐

　　3.1 通過 Java 編程手動實現布隆過濾器

package com.heima.rbac.controller;

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位數組的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過這個數組可以創建 6 個不同的哈希函數
     */
    private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132};

    /**
     * 位數組。數組中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函數的類的數組
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多個包含 hash 函數的類的數組，每個類中的 hash 函數都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個不同的 Hash 函數
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位數組
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判斷指定元素是否存在于位數組
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 靜態內部類。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

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

        /**
         * 計算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

　　3.2 Redis 中的布隆過濾器

　　redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通過加載 [module](https://github.com/RedisLabsModules/rebloom) 來使用 redis 中的布隆過濾器。但是這不是最簡單的方式，使用 docker 可以直接在 redis 中體驗布隆過濾器。

　　```

　　> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom

　　> docker exec -it bloomfilter redis-cli

　　```

　　redis 布隆過濾器主要就兩個命令：

　　- `bf.add` 添加元素到布隆過濾器中：`bf.add urls http://www.itcast.com`。

　　- `bf.exists` 判斷某個元素是否在過濾器中：`bf.exists urls http://www.itcast.com`。

　　上面說過布隆過濾器存在誤判的情況，在 redis 中有兩個值決定布隆過濾器的準確率：

　　- `error_rate`：允許布隆過濾器的錯誤率，這個值越低過濾器的位數組的大小越大，占用空間也就越大。

　　- `initial_size`：布隆過濾器可以儲存的元素個數，當實際存儲的元素個數超過這個值之后，過濾器的準確率會下降。

　　redis 中有一個命令可以來設置這兩個值：

　　```

　　bf.reserve urls 0.01 100

　　```

　　三個參數的含義：

　　- 第一個值是過濾器的名字。

　　- 第二個值為 `error_rate` 的值。

　　- 第三個值為 `initial_size` 的值。

　　使用這個命令要注意一點：執行這個命令之前過濾器的名字應該不存在，如果執行之前就存在會報錯：`(error) ERR item exists`。