1.引言

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

2.什么是布隆過濾器

布隆過濾器（Bloom Filter）其實是基于bitmap的一種應用，?1970 年由布隆提出。它由一個很長的二進制比特數(shù)組和一系列哈希函數(shù)構成，用于高效地檢索數(shù)據(jù)是否存在。通俗的說可以把布隆過濾器理解為一個集合，我們可以往里面添加值，并且能判斷某個值是否在里面。當布隆過濾器告訴我們某個值存在時，其實這個值只是有可能存在；可是它說某個值不存在時，那這個值就真的不存在。

3.工作機制

如圖1 所示，初始化比特數(shù)組的值全為0，長度m=23，并假設有k=3個能把數(shù)據(jù)均勻映射到值域為 [0,m) 的哈希函數(shù)，經(jīng)過一系列添值操作后，數(shù)組的值會散亂地被賦為1。我們先將數(shù)據(jù)a、b、c放入布隆過濾器，對a、b、c各自分別使用三個哈希函數(shù)得到映射值（即比特數(shù)組索引下標）。再根據(jù)下標將比特數(shù)組對應的值置為1，從而表示這三個數(shù)據(jù)已經(jīng)存在。

然后我們用兩個不曾被布隆過濾器標記的數(shù)據(jù)d、e模擬布隆過濾器的篩選過程。同樣要使用前文設定的3個哈希函數(shù)，經(jīng)散列得到比特數(shù)組索引下標，然后按下標查詢得到對應的數(shù)組值。如果說3個索引值里出現(xiàn)了至少一個值為0，那么可以肯定的說這個數(shù)據(jù)肯定不存在，比如d。但是也會出現(xiàn)e這種情況，查得的值均為1，但是e明明不存在。其實出現(xiàn)這種情況的原因很好理解：那些被置為 1 的位置也可能是由于其他元素的操作而改變的。所以布隆過濾器存在假正率（False Positive）。

4.時間復雜度 空間復雜度

時間復雜度：在查找過程里，取值過程是直接查找，但是取值的次數(shù)等于哈希函數(shù)的個數(shù)成，所以時間復雜度為O(k),k為哈希函數(shù)的個數(shù)。另外哈希計算可以使用硬件加速，故查找效率很高。

空間復雜度：存儲上，假設比特數(shù)組長度為m=10000000，則申請的內存大小為10000000bit=1250000B=1220.703125KB≈1.20MB≈0.001164GB。這在動輒內存8G起步的設備上，其實占用很小。

?5.正確率和容錯

首先對False positive概率進行推導：

假設 Hash 函數(shù)以等概率條件選擇并設置比特數(shù)組中的某一位，m 是該位數(shù)組的大小，k 是 Hash 函數(shù)的個數(shù)，那么位數(shù)組中某一特定的位在進行元素插入時的 Hash 操作中沒有被置位的概率是：

?那么在所有 k 次 Hash 操作后該位都沒有被置 "1" 的概率是：

如果我們插入了 n 個元素，那么某一位仍然為 "0" 的概率是：

因而該位為 "1"的概率是：

現(xiàn)在檢測某一元素是否在該集合中。標明某個元素是否在集合中所需的 k 個位置都按照如上的方法設置為 "1"，但是該方法可能會使算法錯誤的認為某一原本不在集合中的元素卻被檢測為在該集合中（False Positive），該概率由以下公式確定：

其實上述結果是在假定由每個 Hash 計算出需要設置的位（bit） 的位置是相互獨立為前提計算出來的，不難看出，隨著 m （比特數(shù)組大?。┑脑黾?，F(xiàn)alse Positive的概率會下降，同時隨著插入元素個數(shù) n 的增加，F(xiàn)alse Positive的概率又會上升，對于給定的m，n，如何選擇Hash函數(shù)個數(shù) k 由以下公式確定：

此時False Positive的概率為：

而對于給定的False Positive概率 p，如何選擇最優(yōu)的位數(shù)組大小 m 呢，

上式表明，比特數(shù)組的大小最好與插入元素的個數(shù)成線性關系。

對于布隆過濾器不會漏報，但可能誤報這個情況，我們當然希望準確度越高越好。

?從上圖可以看出，數(shù)據(jù)冗余量越大，哈希函數(shù)越多，錯誤率越低。但是總體來看，錯誤率控制在1%以內。

確定了正確率的問題后，接下來就是關鍵的容錯了，怎么容錯才算完美，既能解決問題，又能照顧容錯成本呢？一方面由于布隆過濾器使用多個哈希函數(shù)進行處理，所以生成的值正常會均勻分布，數(shù)據(jù)不均衡從而造成數(shù)據(jù)稀疏時成本較高的問題就不存在了；另一方面，雖然說數(shù)據(jù)量增大超過預先設計的最大值也會對布隆過濾器造成影響，但是影響并不是很嚴重，除非差別過于巨大。因為實際數(shù)據(jù)量增大后，只會影響到上圖m/n的值，帶來的影響只是略微影響到布隆過濾器的正確率。

6.優(yōu)點

• 增加和查詢元素的時間復雜度為：O(K), (K為哈希函數(shù)的個數(shù)，一般比較小)，與數(shù)據(jù)量大小無關
• 哈希函數(shù)相互之間沒有關系，方便硬件并行運算
• 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴格的場合有很大優(yōu)勢
• 在能夠承受一定的誤判時，布隆過濾器比其他數(shù)據(jù)結構有這很大的空間優(yōu)勢
• 數(shù)據(jù)量很大時，布隆過濾器可以表示全集，其他數(shù)據(jù)結構不能
• 使用同一組散列函數(shù)的布隆過濾器可以進行交、并、差運算

7.使用場景

布隆過濾器被廣泛用于數(shù)據(jù)量龐大的情況下的查詢、去重等業(yè)務，比如：

• 黑名單過濾
• 垃圾郵件過濾
• 爬蟲判重系統(tǒng)
• 推薦系統(tǒng)去重
• 緩存穿透
• 區(qū)塊鏈的SPV支付
• Web攔截器
• ……

8.缺點

• 有誤判率，即存在假正率，即不能準確判斷元素是否在集合中
• 不能獲取元素本身
• 一般情況下不能從布隆過濾器中刪除元素
• 隨著使用的時間越來越長，因為不能刪除，存進里面的元素越來越多，占用內存越來越多，誤判率越來越高，最后不得不重置。
• 如果采用計數(shù)方式刪除，可能會存在計數(shù)回繞問題
• 數(shù)據(jù)量過于龐大時，計算機內存也會進行頻繁的頁面置換（這個其實不獨屬于布隆過濾器的缺點）?

9.總結

總體來說，布隆過濾器是一個很有意思的數(shù)據(jù)結構，空間效率和查詢時間都遠遠超過一般的算法。目前已經(jīng)在業(yè)務中廣泛使用，比如常用的redis里已經(jīng)集成了布隆過濾器。本篇只是就最基本的布隆過濾器做了介紹，在具體應用中，布隆過濾器還有更多的有趣的功能和進一步改進的數(shù)據(jù)結構。朋友們可以親自coding一下，比如嘗試一下redis的布隆過濾器，或者嘗試給布隆過濾器實現(xiàn)刪除數(shù)據(jù)的功能等等。

9.Reference

布隆過濾器 - 維基百科，自由的百科全書 (wikipedia.org)

hash 算法原理及應用漫談 (qq.com)

詳解布隆過濾器的原理、優(yōu)缺點_一只快樂的野指針吼的博客-CSDN博客_布隆過濾器原理

布隆過濾器，這一篇給你講的明明白白-阿里云開發(fā)者社區(qū) (aliyun.com)

布隆過濾器及其使用場景 - Master HaKu - 博客園 (cnblogs.com)

Redis布隆過濾器（原理+圖解） (biancheng.net)

布隆過濾器(Bloom Filter)詳解 - 李玉龍 - 博客園 (cnblogs.com)

Merkle Tree、Merkle Proof、SPV安全性分析、Bloom過濾器_真·skysys的博客-CSDN博客

簡化的支付驗證（SPV）和布隆過濾器（bloom fliter）

"不靠譜"的布隆過濾器是怎么成為大數(shù)據(jù)世界中的韋小寶的？

布隆過濾器踩坑日記文章來源地址http://www.zghlxwxcb.cn/news/detail-482961.html

到了這里，關于布隆過濾器（Bloom Filter）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！