在學習redis過程中提到一個緩存擊穿的問題， 書中參考的解決方案之一是使用布隆過濾器， 那么就有必要來了解一下什么是布隆過濾器。在參考了許多博客之后， 寫個總結記錄一下。

一、布隆過濾器簡介

什么是布隆過濾器？

本質上布隆過濾器( BloomFilter )是一種數據結構，比較巧妙的概率型數據結構（probabilistic data structure），特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”。

相比于傳統的 Set、Map 等數據結構，它更高效、占用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。

布隆過濾器原理

布隆過濾器內部維護一個bitArray(位數組)， 開始所有數據全部置 0 。當一個元素過來時，能過多個哈希函數（hash1,hash2,hash3....）計算不同的在哈希值，并通過哈希值找到對應的bitArray下標處，將里面的值 0 置為 1 。 需要說明的是，布隆過濾器有一個誤判率的概念，誤判率越低，則數組越長，所占空間越大。誤判率越高則數組越小，所占的空間越小。

下面以網址為例來進行說明, 例如布隆過濾器的初始情況如下圖所示：

現在我們需要往布隆過濾里中插入baidu這個url，經過3個哈希函數的計算，hash值分別為1，4，7，那么我們就需要對布隆過濾器的對應的bit位置1， 就如圖下所示：

接下來，需要繼續往布隆過濾器中添加tencent這個url，然后它計算出來的hash值分別3，4，8，繼續往對應的bit位置1。這里就需要注意一個點， 上面兩個url最后計算出來的hash值都有4，這個現象也是布隆不能確認某個元素一定存在的原因，最后如下圖所示：

布隆過濾器的查詢也很簡單，例如我們需要查找python，只需要計算出它的hash值， 如果該值為2，4，7，那么因為對應bit位上的數據有一個不為1， 那么一定可以斷言python不存在，但是如果它計算的hash值是1，3，7，那么就只能判斷出python可能存在，這個例子就可以看出來， 我們沒有存入python，但是由于其他key存儲的時候返回的hash值正好將python計算出來的hash值對應的bit位占用了，這樣就不能準確地判斷出python是否存在。

因此， 隨著添加的值越來越多， 被占的bit位越來越多， 這時候誤判的可能性就開始變高，如果布隆過濾器所有bit位都被置為1的話，那么所有key都有可能存在， 這時候布隆過濾器也就失去了過濾的功能。至此，選擇一個合適的過濾器長度就顯得非常重要。

從上面布隆過濾器的實現原理可以看出，它不支持刪除， 一旦將某個key對應的bit位置0，可能會導致同樣bit位的其他key的存在性判斷錯誤。

布隆過濾器的準確性

布隆過濾器的核心思想有兩點：

多個hash，增大隨機性，減少hash碰撞的概率擴大數組范圍，使hash值均勻分布，進一步減少hash碰撞的概率。

雖然布隆過濾器已經盡可能的減小hash碰撞的概率了，但是，并不能徹底消除，因此正如上面的小例子所舉的小例子的結果來看， 布隆過濾器只能告訴我們某樣東西一定不存在以及它可能存在。

關于布隆過濾器的數組大小以及相應的hash函數個數的選擇， 可以參考網上的其他博客或者是這個維基百科上對應詞條上的結果: Probability of false positives .