引文

思考一個問題：從大量數(shù)據(jù)里面如何高效率地去重沪编？
有過一點編程經(jīng)驗的人都知道，可以通過Set這種數(shù)據(jù)結(jié)構(gòu)來做到年扩。比如HashSet蚁廓，采用了Hash算法，可以在O(1)的復(fù)雜度完成數(shù)據(jù)的添加和查詢操作厨幻。確實相嵌，大多數(shù)情況，這也是我們會采取的方案况脆。但是因為Set需要保存源數(shù)據(jù)信息饭宾，且有Hash沖突，當樣本數(shù)據(jù)量特別龐大的情況下格了，比如有千萬甚至上億的數(shù)據(jù)量時捏雌，這種方式顯得有些不切實際。

布隆過濾器

布隆過濾器(Bloom Filter)的思想跟Hashmap有部分類似笆搓，也是通過hash函數(shù)映射的方式保存樣本信息，不一樣的是它依賴的數(shù)據(jù)結(jié)構(gòu)是一個位數(shù)組纬傲，數(shù)組每一位上要么是0满败，要么是1，初始狀態(tài)全是0叹括。

位數(shù)組

當要往過濾器添加一個元素的時候算墨，我們需要n(n是正整數(shù))個獨立的hash函數(shù)給目標元素做哈希運算，然后我們將得到的n個結(jié)果分別映射到位數(shù)組上汁雷。
舉個簡單的例子净嘀，假設(shè)我們要添加元素的元素是數(shù)字，我們?nèi)為3侠讯，選取的3個hash函數(shù)分別是

$hash_{1}(x) = (x ^ 2)$ %20

$hash_{2}(x) = (x ^ 3)$ %20

$hash_{3}(x) = (x ^ 4)$ %20

當添加7這個元素的時候挖藏，通過三個hash函數(shù)計算的結(jié)果分別是9，3和1厢漩，我們把位數(shù)組對應(yīng)下標的元素記為1膜眠。

元素7的指紋信息

這樣元素7就在位數(shù)組上以9，3和1三個位置信息的形式，存儲了起來宵膨。后續(xù)所有的元素都經(jīng)過三個hash函數(shù)架谎，映射到位數(shù)組上。于是當我們要判斷某個元素是否存在的時候辟躏，我們?nèi)?shù)組上此元素應(yīng)該在的位置處查看谷扣，對應(yīng)的數(shù)字是否都為1。如果有數(shù)字為0捎琐，那么元素肯定不存在会涎。如果數(shù)字都為1，那么元素大概率存在野哭。

算法研究

布隆過濾器是一種概率數(shù)據(jù)結(jié)構(gòu)(probabilistic data structure)在塔，可能會出現(xiàn)誤判，但不會漏判拨黔。因為不同元素的hash結(jié)果可能會相同蛔溃，而且被映射位置的數(shù)字可能已經(jīng)被其他元素置為1，所以我們不能判斷某個元素一定重復(fù)篱蝇。

Hash函數(shù)

過濾器需要一系列獨立的hash函數(shù)贺待，函數(shù)的目標是將輸出均勻地打散在目標域上。也就是說零截，元素通過hash函數(shù)映射到位數(shù)組上任何位置的概率應(yīng)該是相同的麸塞。另外還有重要的一點，就是算法速度要快涧衙，過濾器的性能很大程度上取決于hash函數(shù)的性能哪工。好的hash函數(shù)能在保持良好時間效率的情況下，降低過濾器的誤判率弧哎。其中比較知名的是MurmurHash, FNV Hash, MD5

參數(shù)選擇

一個合格的布隆過濾器雁比，需要有很高的空間時間效率，較低并且可控的誤判率撤嫩。從而我們很容易發(fā)現(xiàn)幾個問題偎捎。

如何選取位數(shù)組長度m。m越大序攘，占用的空間越大茴她；m越小，誤判的幾率越高程奠。
如何選取hash函數(shù)個數(shù)k丈牢。k越大，數(shù)組越快被占滿從而誤判率越高梦染；k越小赡麦，產(chǎn)生hash沖突的概率越大朴皆，導(dǎo)致誤判率也越高。

對于上述的問題泛粹，切入點是最小化誤差率遂铡。怎樣是誤差？不就是當查詢一個未重復(fù)元素的時候晶姊，對應(yīng)映射的位置已經(jīng)都為1了嗎扒接。對于長度為m的位數(shù)組，某個位置被設(shè)為1的概率是 $\frac{1}{m}$ 们衙，所以這個位置仍然為0的概率是

$1-\frac{1}{m}$

每個元素都會有k個hash映射钾怔，假設(shè)所有的hash結(jié)果相互獨立，當數(shù)組已經(jīng)添加了n個元素的時候蒙挑，該位置依然為0的概率是

$(1-\frac{1}{m})^{kn}$

于是這個位置已經(jīng)是1了的概率是

$1-(1-\frac{1}{m})^{kn}$

所以對于某個元素做k次hash映射宗侦，對應(yīng)位置都已為1的概率，即誤判率 $P_f$ 為

$P_f=(1-(1-\frac{1}{m})^{kn})^k$

因為

$\lim\limits_{x \to \infty} (1-\frac{1}{x})^x=\frac{1}{e}$

所以當數(shù)據(jù)量很大的時候忆蚀，誤判率可以近似的表示為

$P_f\approx(1-e^\frac{-kn}{m})^k$

對于給定的m和n矾利，可以解出當 $P_f$ 達到極小值也就是最優(yōu)值時，k的取值為

$k=\frac{m}{n}ln2$

將這個結(jié)果代入到原來的表達式中消去k馋袜，最終可以得到

$lnP_f=-\frac{m}{n}(ln2)^2$

從而得到最優(yōu)位數(shù)組的大小

$m=-\frac{nlnP_f}{(ln2)^2}$

舉個例子男旗，當我們預(yù)估樣本數(shù)量大小n為5,000,000的時候，期望過濾器有低于1%的誤判率欣鳖，依據(jù)以上兩個公式察皇，我們可以算出理想的位數(shù)組長度為

$m=-\frac{nlnP_f}{(ln2)^2}=-\frac{5,000,000*ln0.01}{(ln2)^2}\approx47,925,292$

最優(yōu)hash函數(shù)個數(shù)為

$k=\frac{m}{n}ln2=\frac{47,925,292}{5,000,000}ln2\approx7$

也就是說在這種情況下我們可以將位數(shù)組長度為設(shè)置為47,925,292，并且選擇7個hash函數(shù)來達到目標泽台。

布隆過濾器的優(yōu)勢

時間效率高

因為是通過數(shù)組下標查詢什荣，對每個hash函數(shù)映射結(jié)果查詢的時間復(fù)雜度都是O(1)。而且各個hash函數(shù)都是不相關(guān)的怀酷，查詢?nèi)蝿?wù)可以并行地處理溃睹，充分地發(fā)揮計算機多核多線程的優(yōu)勢，甚至可以利用分布式的計算力來進一步優(yōu)化效率胰坟。

占用內(nèi)存小

對于給定的誤判率1%，每個元素的存儲通常不會超過10字節(jié)泞辐。相較于Hashset之類的要保存源元素的數(shù)據(jù)結(jié)構(gòu)來說笔横，無論元素的原始大小是多少，布隆過濾器的大小都是恒定的咐吼，一般只需要10%-25%的內(nèi)存占用吹缔。

信息安全

布隆過濾器并不保存源信息，而是保存源信息的幾個hash指紋锯茄，所以有非常好的保密性厢塘，非常適合對信息比較敏感的場景茶没。

布隆過濾器的不足

誤判

作為一種概率數(shù)據(jù)結(jié)構(gòu)，誤判應(yīng)該是最大的缺點了晚碾。不過我們還是可以通過選取適當?shù)膮?shù)抓半，將誤判率控制在一定的可接受范圍內(nèi)。

無法刪除數(shù)據(jù)

因為hash沖突的存在格嘁，當考慮要刪除某個元素的時候笛求，我們不能簡單地把相應(yīng)映射位置的數(shù)字記為0，因為很可能有其他元素也映射到了這些位置糕簿。如下圖探入，3和7元素都映射到了1和9兩個位置，當把7對應(yīng)位置的元素置為0的時候懂诗，也影響到了元素3蜂嗽。

hash沖突

一些布隆過濾器的變體，如計數(shù)布隆過濾器(Counting Bloom Filter)殃恒，穩(wěn)定布隆過濾器(Stable Bloom Filter)可以支持元素的刪除植旧，但是是通過犧牲空間效率或準確性來達成的。

應(yīng)用場景

綜合布隆過濾器的優(yōu)劣芋类，我們可以知道過濾器的適用場景大致有幾個特點

對誤判有一定的容忍度

樣本的數(shù)量比較龐大

對時間空間效率要求比較高

避免緩存穿透
將緩存的數(shù)據(jù)放到布隆過濾器里面隆嗅，當請求一個一定不存在的資源的時候，在過濾器層便可把請求返回侯繁，從而防止緩存穿透攻擊導(dǎo)致DB癱瘓胖喳。如：Bigtable, Apache HBase
垃圾郵件/黑名單/危險網(wǎng)站的過濾
將所有被標記為垃圾郵件的郵箱地址存到過濾器里，當收到新郵件時贮竟，如果發(fā)現(xiàn)發(fā)件人在過濾器里則自動拉入垃圾郵箱丽焊。因為誤判的存在，所以有時候我們會發(fā)現(xiàn)正常的郵件會被歸入垃圾郵件咕别。如：瀏覽器技健，郵件系統(tǒng)
URL的去重
對于某些網(wǎng)頁爬蟲程序，把已經(jīng)處理過的URL放到過濾器里面惰拱，可以減少爬蟲的很多重復(fù)工作雌贱。
用戶喜好推送系統(tǒng)
根據(jù)用戶的瀏覽記錄，給用戶發(fā)一些推送偿短。我們可以把所有用戶的瀏覽記錄放到過濾器里面欣孤，保證推送不重復(fù)。如：Medium

總結(jié)

布隆過濾器是一個時間空間效率都很高的過濾器昔逗，但是會有一定的誤判率降传。在海量數(shù)據(jù)的處理場景中有廣泛的應(yīng)用。

參考

Bloom Filter
Bloom Filters by Example

Bloom過濾器