[布隆過濾器BloomFilter] 舉例說明+證明推導

寫在前面

網上有很多寫布隆過濾器的部落格，但是大部分都是隻關注一個點，不能非常好的從原理到應用了解，是以這裡對布隆過濾器進行了整理。很多思想和例子都來自網上的的一些部落格，非常感謝這些可愛哒人兒的付出，這裡會盡量整理的比較詳細，規整，有頭有尾。

一、引例

在提到實作去重功能時，大部分人都會直接選擇HashSet，HashSet可以起到去重的效果，并且其時間複雜度為 O ( 1 ) O(1) O(1)，但是其存在的最大問題是記憶體占用比較大。是以我們可以選擇使用布隆過濾器。

1、引例1

我們在爬取網頁資訊時，如果不進行任何設定進行網頁資訊的爬取，則可能爬取到相同url的内容，是以我們需要去重，可以使用HashSet，但是如果url數量太多，使用HashSet需要占據大量的記憶體，是以我們可以使用布隆過濾器。

2、引例2

我們在使用新聞網頁看新聞時，它會給我們不停的推薦新的内容，但是在每次推薦時都需要進行去重處理，去掉那些使用者已經看過的内容，否則就失去了推薦的意義。那麼新聞網頁是如何完成去重操作的呢？

一種方法是直接進行篩選，也就是記錄下使用者已經通路過的新聞，每次推薦保證推薦的新聞沒有被通路過，但是這種操作下，我們需要記錄已經通路的新聞，而且在推薦時也要判斷是否新聞已被看過，很多使用者的情況下，這需要強大的記憶體消耗及性能要求。（若将已看過的新聞存儲在記憶體中，則需要消耗大量的記憶體；若存在的資料庫中，則需要頻繁的資料庫的exist操作；對于前端的一些緩存系統，可能判斷機制是若頁面在本地，則直接傳回本地查詢的結果，否則從後端讀取，這樣就造成了頻繁讀取緩存系統，使後端壓力變大）

在這種情況下，我們可以使用布隆過濾器，判斷目前新聞是否已被通路。

二、布隆過濾器功能

• 用于解決去重問題
• 起到去重的同時，空間上能節省90%以上
• 會有很小的誤判率（False positive），即BloomFilter判斷為不存在的一定不存在，但是其判定為存在也可能不存在（請參見原理部分，更容易了解）

三、Bloom Filter思想

1、基本思想

若想判斷一個元素是不是在一個集合裡，一般想到的是将所有元素儲存起來，然後通過比較确定。連結清單、樹等等資料結構都是這種思路。但是随着集合中元素的增加，我們需要的存儲空間越來越大，檢索速度也越來越慢。我們可以使用一種叫作散清單（又叫哈希表，Hash table）的資料結構。它可以通過一個Hash函數将一個元素映射成一個位陣列（Bit Array）中的一個點。這樣一來，我們隻要看看這個點是不是 1 就知道可以集合中有沒有它了。這就是布隆過濾器的基本思想。

2、舉例說明

布隆過濾器是一個bit向量或者說是bit數組，假設我們的Bloom Filter是一個8位的bit向量，初始元素為0，假設有3個哈希函數，則其結果示意圖如下：

①如上圖所示，第①步是布隆過濾器的初始結果，在這一步中，是以bit位都初始化為0

②現在如果有一個詞“Java”，其hash值為1，3，6，則将其對應的bit位置1，如圖②所示

③現在有另外一個詞“Python”，其hash值為2，6，7，則将其對應的bit位置1，如果③所示，注意：6位置的1被覆寫

④如果現在需要查詢“C++”是否存在，若“C++”對應的hash值是1，4，7，則bit為1和7對應元素是1，但是bit4位置元素是0，是以可以判斷“C++”現在不存在。

判斷方法： 當需要查詢的詞的所有bit位所有都為1時，說明待查詢詞可能已經存在。但是隻要有一個為0，則可以說明，待查詢詞一定不存在。

⑤如果現在需要查詢“C++”是否存在，若“C++”對應的hash值是1，6，7，則hash位置對應的元素都是1，是以可以判斷“C++”可能存在。

注意： 為什麼強調可能存在，是因為，當已存在的單詞較多的時候，很多hash位置都為1，這時候待查詢詞對應的hash位置可能都為1，但是其并不存在。比如“C++”對應的hash位置是1，6，7，且對應值全部為1，是以我們判斷“C++”存在，但其實在此之前我們并沒有加入“C++”這個單詞到BloomFilter。

3、BloomFilter可以支援的操作

• 支援插入操作

  從上述例子可以知道，如果想要插入一個元素到布隆過濾器，隻需要将其對應hash對應元素置1

• 支援查詢操作

  上述例子中已經提到，可以支援查詢操作，也就是判斷其是否已經存在。當需要查詢的詞的所有bit位所有都為1時，說明待查詢詞可能已經存在。但是隻要有一個為0，則可以說明，待查詢詞一定不存在。

• 支援删除操作麼？

  原則上BloomFilter不支援删除操作，因為其置1操作是覆寫式的，如果現在需要删除“Python”這個詞，則需要将其對應的hash值位置恢複為0，即将2，6，7位置恢複為0，這種方法會使得“Java”中的6位置處的1失蹤。

  當然可以采用一種方法就是計數法，比如現在BloomFilter中6位置處已經為1，再次插入時，不是覆寫1，而是進行+1操作。當進行删除操作時，不進行置0操作，而是執行減1操作。但是這種方法需要對每個bit位增加一個存儲操作，會增加記憶體占用。

四、Bloom Filter公式推導

1、誤判率推導

假設 m m m是該bit數組的大小， k k k是哈希函數的個數， n n n是插入的元素的個數。

假設hash函數以等機率條件選擇并設定bit位為“1”，則其機率為 1 m \frac{1}{m} m1​，是以bit數組中某一特定的位在進行元素插入時的hash操作中沒有被置為1的機率是 1 − 1 m 1- \frac{1}{m} 1−m1​

在經過 k k k個哈希函數之後，該位仍然沒有被置“1”的機率是： ( 1 − 1 m ) k (1- \frac{1}{m})^k (1−m1​)k.

若插入了 n n n個元素，該位仍然沒有被置“1”的機率是： ( 1 − 1 m ) k n (1- \frac{1}{m})^{kn} (1−m1​)kn.

因為該位被置“1”的機率是： 1 − ( 1 − 1 m ) k n 1-(1- \frac{1}{m})^{kn} 1−(1−m1​)kn.

現在檢測某一進制素是否在該集合中，則表明需要判斷是否所有hash值對應的位都置1，但是該方法可能會錯誤的認為原本不在集合中的元素是在BloomFilter中的，即導緻誤判率的發生，其機率為：

[ 1 − ( 1 − 1 m ) k n ] k ≈ ( 1 − e − k n m ) k [1-(1- \frac{1}{m})^{kn}]^k \approx ( 1- e^{-\frac{kn}{m}})^k [1−(1−m1​)kn]k≈(1−e−mkn​)k

≈ \approx ≈是因為使用了近似公式: lim ⁡ x − > ∞ ( 1 − 1 x ) − x = e \lim_{x->\infty }(1-\frac{1}{x})^{-x}=e limx−>∞​(1−x1​)−x=e

從上式可以看出，當 m m m增大時，誤判率減小；當 n n n增大時，誤判率增大。

2、最佳哈希函數個數推導

k k k為何值時，誤判率可以最小呢？

誤判率函數:

f ( k ) = ( 1 − e − k n m ) k f(k) = ( 1- e^{-\frac{kn}{m}})^k f(k)=(1−e−mkn​)k

令 b = e n m b = e^{\frac{n}{m}} b=emn​ ，則簡化為 f ( k ) = [ ( 1 − b − k ) ] k f(k)=[(1-b^{-k})]^k f(k)=[(1−b−k)]k

兩邊取對數得：

l n f ( k ) = k l n ( 1 − b − k ) lnf(k) = kln(1-b^{-k}) lnf(k)=kln(1−b−k)

兩邊對 k k k求導得：

1 f ( k ) ⋅ f ′ ( k ) = l n ( 1 − b − k ) + k b − k l n b 1 − b − k \frac{1}{f(k)} \cdot f'(k) = ln(1-b^{-k}) + \frac{kb^{-k}lnb}{1-b^{-k}} f(k)1​⋅f′(k)=ln(1−b−k)+1−b−kkb−klnb​

若 f ( k ) f(k) f(k)取最值，則 f ′ ( k ) = 0 f'(k) = 0 f′(k)=0，則：

l n ( 1 − b − k ) + k b − k l n b 1 − b − k = 0 = > ( 1 − b − k ) ⋅ l n ( 1 − b − k ) = − k b − k l n b = > ( 1 − b − k ) ⋅ l n ( 1 − b − k ) = b − k l n ( b − k ) = > 1 − b − k = b − k = > b − k = 1 2 = > e − k n m = 1 2 = > k n m = l n 2 = > k = l n 2 ⋅ m n = 0.7 ⋅ m n \begin{array}{lcl} &&ln(1-b^{-k}) + \frac{kb^{-k}lnb}{1-b^{-k}} = 0 \\ &&=>(1-b^{-k}) \cdot ln(1-b^{-k}) = -kb^{-k}lnb \\ &&=>(1-b^{-k}) \cdot ln(1-b^{-k}) = b^{-k}ln(b^{-k}) \\ &&=>1-b^{-k} = b^{-k} \\ &&=> b^{-k} = \frac{1}{2} \\ &&=> e^{\frac{-kn}{m}} = \frac{1}{2} \\ &&=>\frac{kn}{m} = ln2 \\ &&=>k=ln2 \cdot \frac{m}{n} = 0.7 \cdot \frac{m}{n} \end{array} ​​ln(1−b−k)+1−b−kkb−klnb​=0=>(1−b−k)⋅ln(1−b−k)=−kb−klnb=>(1−b−k)⋅ln(1−b−k)=b−kln(b−k)=>1−b−k=b−k=>b−k=21​=>em−kn​=21​=>mkn​=ln2=>k=ln2⋅nm​=0.7⋅nm​​

也就是當 k = 0.7 ⋅ m n k=0.7 \cdot \frac{m}{n} k=0.7⋅nm​時，誤判率最低， k k k為最佳哈希函數的個數。此時誤判率為：

P ( e r r o r ) = f ( k ) = ( 1 − e − k n m ) k = 2 − l n 2 ⋅ m n ≈ 0.6158 ⋅ m n \begin{array}{lcl} P(error) = f(k) &=& ( 1- e^{-\frac{kn}{m}})^k \\ &=& 2^{-ln2 \cdot \frac{m}{n}} \\ &\approx& 0.6158 \cdot \frac{m}{n} \end{array} P(error)=f(k)​==≈​(1−e−mkn​)k2−ln2⋅nm​0.6158⋅nm​​

3、Bloom Filter記憶體占用

在實際應用時，使用者需要決定需要插入的元素數 n n n和期望的誤差率 P P P，也就是 n n n和 P P P這兩個值是已知的，則：

（1）首先需要計算需要占用的記憶體大小 m m m

P = 2 − l n 2 ⋅ m n l n P = l n 2 ⋅ ( − l n 2 ) m n m = − n ⋅ l n P ( l n 2 ) 2 \begin{array}{lcl} && P = 2^{-ln2 \cdot \frac{m}{n}} \\ && lnP = ln2 \cdot (-ln2)\frac{m}{n} \\ && m = - \frac{n \cdot ln P}{ (ln2)^2 } \end{array} ​​P=2−ln2⋅nm​lnP=ln2⋅(−ln2)nm​m=−(ln2)2n⋅lnP​​

于是，我們知道記憶體占用為 m = − n ⋅ l n P ( l n 2 ) 2 m = - \frac{n \cdot ln P}{ (ln2)^2 } m=−(ln2)2n⋅lnP​bit，現在已知變量為 n n n, m m m和 P P P

（2）求得哈希函數的個數 k = l n 2 ⋅ m n = 0.7 ⋅ m n k = ln2 \cdot \frac{m}{n} = 0.7 \cdot \frac{m}{n} k=ln2⋅nm​=0.7⋅nm​

至此 n n n, m m m， P P P和 k k k都已經知道。

（3）求記憶體占用

當 k k k最優時： P ( e r r o r ) = 2 − l n 2 ⋅ m n P(error) = 2^{-ln2 \cdot \frac{m}{n}} P(error)=2−ln2⋅nm​ = 2 − k =2^{-k} =2−k.

P ( e r r o r ) = 2 − k = > l o g 2 P = − k = > k = l o g 2 1 P = > l n 2 ⋅ m n = l o g 2 1 P = > m n = 1 l n 2 ⋅ l o g 2 1 P = > m n = 1.44 ⋅ l o g 2 1 P \begin{array}{lcl} &&P(error) = 2^{-k} \\ && => log_2P = -k \\ &&=> k = log_2 \frac{1}{P} \\ && =>ln2 \cdot \frac{m}{n} = log_2 \frac{1}{P} \\ && => \frac{m}{n}=\frac{1}{ln2} \cdot log_2 \frac{1}{P} \\ && => \frac{m}{n} = 1.44 \cdot log_2 \frac{1}{P} \end{array} ​​P(error)=2−k=>log2​P=−k=>k=log2​P1​=>ln2⋅nm​=log2​P1​=>nm​=ln21​⋅log2​P1​=>nm​=1.44⋅log2​P1​​

是以，若我們設定 P = 1 % P=1\% P=1%，則存儲每個元素需要 m n = 1.44 ⋅ l o g 2 1 0.01 = 9.57 \frac{m}{n}= 1.44 \cdot log_2 \frac{1}{0.01}=9.57 nm​=1.44⋅log2​0.011​=9.57bits的空間（9.57是bit位置為0和置為1的總bit位數），此時 k = 0.7 ⋅ m n = 0.7 ⋅ 9.57 = 6.7 k=0.7 \cdot \frac{m}{n} =0.7 \cdot 9.57=6.7 k=0.7⋅nm​=0.7⋅9.57=6.7bits(6.7是bit位置為1的bit位數)；若我們想将誤判率降低為原來的 1 10 \frac{1}{10} 101​，則存儲每個元素需要增加 1.44 ⋅ ( l o g 2 10 a − l o g 2 a ) = 1.44 ⋅ l o g 2 10 = 4.78 1.44 \cdot (log_2 {10a}-log_2 a)=1.44 \cdot log_2 10 = 4.78 1.44⋅(log2​10a−log2​a)=1.44⋅log2​10=4.78bits的空間。

當 k = 0.7 ⋅ m n k=0.7 \cdot \frac{m}{n} k=0.7⋅nm​時，誤判率 P P P最低，此時 P ( e r r o r ) = ( 1 − e − k n m ) k P(error) = ( 1- e^{-\frac{kn}{m}})^k P(error)=(1−e−mkn​)k, e − k n m = 1 2 e^{\frac{-kn}{m}} = \frac{1}{2} em−kn​=21​，也就是 ( 1 − 1 m ) k n = 1 2 (1- \frac{1}{m})^{kn}=\frac{1}{2} (1−m1​)kn=21​，此公式意義為：若插入了 n n n個元素，該位仍然沒有被置“1”的機率，也就是說想保持錯誤率低，布隆過濾器的空間使用率需為50%。

五、Bloom Filter優缺點

1、優點

• 布隆過濾器本質上是一種資料結構，是一種比較巧妙的機率型資料結構
• 插入和查詢非常高效，占用空間少（隻需要m個bit位）

2、缺點

• 其具有一定機率的誤判性（False Positive），即Bloom Filter認為存在的東西很有可能不存在。
• 若不進行計數操作，BloomFilter無法進行删除操作。

六、參考文章

[1] 詳解布隆過濾器的原理、使用場景和注意事項

[2] 應用 5：層巒疊嶂——redis布隆過濾器

[3] 布隆過濾器(Bloom Filter)詳解

[4] 【原】布隆過濾器 (Bloom Filter) 詳解