一、應用場景

通常用于構建布隆過濾器

業務場景需要頻繁的查詢數據庫里的數據，但是這些數據又不一定都存在，一些大量無效的數據庫請求，占用了數據庫的鏈接。

本質上保護數據庫，減少無用的請求。

解決：

1、把查詢的數據key放入redis Set中，只有存在才會去查詢，問題就是set過于大，檢查是否存在也會變慢

2、當庫中不存在該值時，依然創建一個value設置為空值，等過期時間后，自行刪除。有可能上一秒庫中不存在，下一秒有了，拿走依然是空值，也不行。

3、布隆過濾器

布隆過濾器（Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。主要用于判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢。上述三種結構的檢索時間復雜度分別為：

• O(n)：鏈表
• O(logn)：樹
• O(1)：哈希表

這個時候，布隆過濾器（Bloom Filter）就應運而生。

1.1. 原理

當一個元素被加入集合時，通過N個Hash函數將這個元素進行Hash，算出一個整數索引值，然后對數組長度進行取模運算，從而得到一個位置，每個Hash函數都會得到一個不同的位置，然后再把位數組中的幾個位置點都置為1。

檢索時，也會把哈希的幾個位置算出來，然后看看位數組中對應的幾個位置是否都為1，只要有一個位為0，那么就說明布隆過濾器里不存在這個元素。

但是，這幾個位置都為1，并不能完全說明這個元素就一定存在其中。因為散列函數是會有碰撞的，不同的輸入，可能在哈希后為同一個位置。即有可能這些位置為1是因為其他元素的存在，這就是布隆過濾器會出現誤判的原因。

因此查詢某個變量的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了

• 如果這些點有任何一個 0
• 如果都是 1，則被查詢變量很可能存在。

1.2 特性與優缺點

1. 不存在時一定不存在

一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在。

原因：布隆過濾器的誤判是指多個輸入經過哈希之后，在相同的bit位的值置1了，這樣就無法判斷究竟是哪個輸入產生的，因此誤判的根源在于相同的 bit 位被多次映射且置 1。

2. 只增不刪

布隆過濾器可以添加元素，但是不能刪除元素。因為刪掉元素會導致誤判率增加。

原因：上述原因中的情況，多個輸入經過哈希之后，在相同的bit位的值置1了，也造成了布隆過濾器的刪除問題。因為布隆過濾器的每一個 bit 并不是獨占的，很有可能多個元素共享了某一位。如果我們直接刪除這一位的話，會影響其他的元素。

如果需要刪除一批元素，可以考慮重新初始化一個布隆過濾器，替換原來的。

3. 優點

• 占用空間極小，插入和查詢速度極快；
• 布隆過濾器可以表示全集，其它任何數據結構都不能；

3. 缺點

• 誤算率隨著元素的增加而增加；
• 一般情況下無法刪除元素；

1.3 應用場景

基于上述的功能，我們大致可以把布隆過濾器用于以下的場景之中：

1. 大數據判斷是否存在來實現去重

這就可以實現出上述的去重功能，如果你的服務器內存足夠大的話，那么使用 HashMap 可能是一個不錯的解決方案，理論上時間復雜度可以達到 O(1) 的級別，但是當數據量起來之后，還是只能考慮布隆過濾器。

2. 判斷用戶是否訪問過

判斷用戶是否閱讀過某視頻或文章，比如抖音或頭條，當然會導致一定的誤判，但不會讓用戶看到重復的內容。

3. 爬蟲/郵箱等系統的過濾

平時不知道你有沒有注意到有一些正常的郵件也會被放進垃圾郵件目錄中，這就是使用布隆過濾器誤判導致的。

4. 天然適合緩存穿透場景

布隆過濾器天然就能應對緩存穿透的場景。

首先，布隆過濾器的應用策略正好和緩存是相反的：

• 緩存策略：緩存中不存在的，再去查db。
• 布隆過濾器策略：過濾器中存在的，再去查緩存（db）。

然后，由于它的特性：一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在。

這表明它的誤判率并不影響它的策略：

• 當判斷結果為存在時：不一定存在。帶來的不好的結果，頂多就是多查一次緩存。
• 當判斷結果為不存在時：一定不存在。策略中判斷不存在時，當前請求就會被攔截，這方面是沒有誤判的。

所以說，布隆過濾器天然適合緩存穿透的場景，它的誤判率對與該場景沒有絲毫影響。

1.4 實現

有很多布隆過濾器的實現，就如同之前將限流器的實現有 guava 和 redisson，布隆過濾器的實現也一樣。

下面兩種實現方式十分相似，都會初始化兩個參數：

• 初始容量：當實際元素的數量超過這個初始化容量時，誤判率上升。設置的過大，會浪費存儲空間，設置的過小，就會影響準確率，所以在使用之前一定要盡可能地精確估計好元素數量，還需要加上一定的冗余空間以避免實際元素可能會意外高出設置值很多。
• 期望錯誤率：期望錯誤率越低，需要的空間就越大。錯誤率越小，需要的存儲空間就越大，對于不需要過于精確的場景，錯誤率設置稍大一點也可以。

參考文獻：https://segmentfault.com/a/1190000043505315