1.介紹

BloomFilter（布隆過濾器）是一種可以高效地判斷元素是否在某個集合中的算法。

在很多日常場景中，都大量存在著布隆過濾器的應用。例如：檢查單詞是否拼寫正確、網絡爬蟲的URL去重、黑名單檢驗，微博中昵稱不能重復的檢測。在工業界中，google著名的分布式數據庫BigTable也用

了布隆過濾器來查找不存在的行或列，以減少磁盤查找的IO次數；Google Chrome瀏覽器使用BloomFilter來判斷一個網站是否為惡意網站。

對于以上場景，可能很多人會說，用HashSet甚至簡單的鏈表、數組做存儲，然后判斷是否存在不就可以了嗎？

當然，對于少量數據來說，HashSet是很好的選擇。但是對于海量數據來說，BloomFilter相比于其他數據結構在空間效率和時間效率方面都有著明顯的優勢。

但是，布隆過濾器具有一定的誤判率，有可能會將本不存在的元素判定為存在。因此，對于那些需要“零錯誤”的應用場景，布隆過濾器將不太適用。具體的原因將會在第二部分中介紹。

在本文的第二部分，本文將會介紹BloomFilter的基本算法思想；第三部分將會基于Google開源庫Guava來講解BloomFilter的具體實現；在第四部分中，將會介紹一些開源的BloomFilter的擴展，以解決目前BloomFilter的不足。

2.算法講述

布隆過濾器是基于Hash來實現的，在學習BloomFilter之前，也需要對Hash的原理有基本的了解。個人認為，BloomFilter的總體思想實際上和bitmap很像，但是比bitmap更節省空間，誤判率也更低。

BloomFilter的整體思想并不復雜，主要是使用k個Hash函數將元素映射到位向量的k個位置上面，并將這k個位置全部置為1。當查找某元素是否存在時，查找該元素所對應的k位是否全部為1即可說明該元素是否存在。

2.1算法流程

BloomFilter的整體算法流程可總結為如下步驟：

如上圖所示，元素x分別被三個Hash函數映射到了三個位置8、1、14，并將這三個位置從0變為1。
若檢查一個元素y是否存在，首先第一步使用k個Hash函數將元素y映射到k位。分別檢測每一位是否為0。若某一位為0，則元素y一定不存在，若全部為1，則有可能存在。

2.2空間復雜度

BloomFilter 使用位向量來表示元素，而不存儲本身，這樣極大壓縮了元素的存儲空間。其空間復雜度為O(m)，m是位向量的長度。而m與插入總數量n的關系如公式

我們可以利用這個公式來算一下需要抓取100萬個URL時BloomFilter所占據的空間。

假設要求誤判率為1%，因此該公式可轉化為m=9.6∗n

。故此時BloomFilter位向量的大小為100w∗9.6=960wbit

，約1.1M內存空間。

只需要1.1M的內存空間，就可滿足100萬個url的去重需求，這個空間復雜度之低不可謂不驚人。

實際上，哪怕是1億個URL，也僅需100M左右的內存空間即可滿足BloomFilter的空間需求，這對于絕大部分爬蟲的體量來說，是完全可行的。

1MB ≈ 10^3KB ≈ 10^6Byte ≈ 8 * 10^6b = 800Wbit

2.3時間復雜度

時間復雜度方面 BloomFilter的時間復雜度僅與Hash函數的個數k有關，即O(k)

2.4缺點

刪除元素

BloomFilter 由于并不存儲元素，而是用位的01來表示元素是否存在，并且很有可能一個位時被多個元素同時使用。所以無法通過將某元素對應的位置為0來刪除元素。

幸運的是，目前學術界和工業界都有很多方法擴展已解決以上問題。

強烈建議讀取下面兩篇文章，并且把其中的公式推導一遍：

轉載大部分來自：http://cyhone.com/2017/02/07/Introduce-to-BloomFilter/

同時推薦：http://llimllib.github.io/bloomfilter-tutorial/zh_CN/

原文：https://www.cnblogs.com/wenbochang/p/11414687.html