@ TOC
布隆過濾器(BloomFilter)是一種大家在學校沒怎麼學過，但在計算機很多領域非常常用的資料結構，它可以用來高效判斷某個key是否屬于一個集合，有極高的插入和查詢效率(O(1))，也非常省存儲空間。當然它也不是完美無缺，它也有自己的缺點，接下來跟随我一起詳細了解下BloomFilter的實作原理，以及它優缺點、應用場景，最後再看下Google guava包中BloomFilter的實作，并對比下它和HashSet在不同資料量下記憶體空間的使用情況。
學過資料結構的人都知道，在計算機領域我們經常通過犧牲空間換時間，或者犧牲時間換空間，BloomFilter給了我們一種新的思路——犧牲準确率換空間。是的，BloomFilter不是100%準确的，它是有可能有誤判，但絕對不會有漏判斷，說通俗點就是，BloomFilter有可能錯殺好人，但不會放過任何一個壞人。BloomFilter最大的優點就是省空間，缺點就是不是100%準确，這點當然和它的實作原理有關。
BloomFilter的原理
在講解BloomFilter的實作前，我們先來了解下什麼叫Bitmap(位圖)，先給你一道《程式設計珠玑》上的題目。
給你一個有100w個數的集合S，每個數的資料大小都是0-100w，有些資料重複出現，這就意味着有些資料可能都沒出現過，讓你以O(n)的時間複雜度找出0-100w之間沒有出現在S中的數，盡可能減少記憶體的使用。
既然時間複雜度都限制是O(N)了，意味着我們不能使用排序了，我們可以開一個長為100w的int數組來标記下哪些數字出現過，在就标1，不在标0。但對于每個數來說我們隻需要知道它在不在，隻是0和1的差別，用int(32位)有點太浪費空間了，我們可以按二進制位來用每個int，這樣一個int就可以标記32個數，空間占用率一下子減少到原來的1/32，于是我們就有了位圖，Bitmap就是用n個二進制位來記錄0-m之間的某個數有沒有出現過。
Bitmap的局限在于它的存儲資料類型有限，隻能存0-m之間的數，其他的資料就存不了了。如果我們想存字元串或者其他資料怎麼辦？其實也簡單，隻需要實作一個hash函數，将你要存的資料映射到0-m之間就行了。這裡假設你的hash函數産生的映射值是均勻的，我們來計算下一個m位的Bitmap到底能存多少資料?
當你在Bitmap中插入了一個數後，通過hash函數計算它在Bitmap中的位置并将其置為1，這時任意一個位置沒有被标為1的機率是：
$$
1 - \frac{1}{m}
當插入n個數後，這個機率會變成：
(1 - \frac{1}{m})^n
是以任意一個位置被标記成1的機率就是：
P_1 = 1 - (1 - \frac{1}{m})^n
這時候你判斷某個key是否在這個集合S中時，隻需要看下這個key在hash在Bitmap上對應的位置是否為1就行了，因為兩個key對應的hash值可能是一樣的，是以有可能會誤判，你之前插入了a，但是hash(b)==hash(a)，這時候你判斷b是否在集合S中時，看到的是a的結果，實際上b沒有插入過。
從上面公式中可以看出有 $P_1$ 的機率可能會誤判，尤其當n比較大時這個誤判機率還是挺大的。 如何減少這個誤判率？我們最開始是隻取了一個hash函數，如果說取k個不同的hash函數呢！我們每插入一個資料，計算k個hash值，并對k位置為1。在查找時，也是求k個hash值，然後看其是否都為1，如果都為1肯定就可以認為這個數是在集合S中的。
問題來了，用k個hash函數，每次插入都可能會寫k位，更耗空間，那在同樣的m下，誤判率是否會更高呢？我們來推導下。
在k個hash函數的情況下，插入一個數後任意一個位置依舊是0的機率是：
(1 - \frac{1}{m})^k
插入n個數後任意一個位置依舊是0的機率是：
(1 - \frac{1}{m})^{kn}
是以可知，插入n個數後任意一個位置是1的機率是
1 -
因為我們用是用k個hash共同來判斷是否是在集合中的，可知當用k個hash函數時其誤判率如下。它一定是比上面1個hash函數時誤判率要小（雖然我不會證明）
\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} < (1 - \left[1 - \frac{1}{m}\right]^n)
維基百科也給出了這個誤判率的近似公式（雖然我不知道是怎麼來的，是以這裡就直接引用了）
\left(1-\left[1-\frac{1}{m}\right]^{k n}\right)^{k} \approx\left(1-e^{-k n / m}\right)^{k}
到這裡，我們重新發明了Bloomfilter，就是這麼簡單，說白了Bloomfilter就是在Bitmap之上的擴充而已。對于一個key，用k個hash函數映射到Bitmap上，查找時隻需要對要查找的内容同樣做k次hash映射，通過檢視Bitmap上這k個位置是否都被标記了來判斷是否之前被插入過，如下圖。
通過公式推導和了解原理後，我們已經知道Bloomfilter有個很大的缺點就是不是100%準确，有誤判的可能性。但是通過選取合适的bitmap大小和hash函數個數後，我們可以把誤判率降到很低，在大資料盛行的時代，适當犧牲準确率來減少存儲消耗還是很值得的。
除了誤判之外，BloomFilter還有另外一個很大的缺點 __隻支援插入，無法做删除__。如果你想在Bloomfilter中删除某個key，你不能直接将其對應的k個位全部置為0，因為這些位置有可能是被其他key共享的。基于這個缺點也有一些支援删除的BloomFilter的變種，适當犧牲了空間效率，感興趣可以自行搜尋下。
如何确定最優的m和k？
知道原理後再來了解下怎麼去實作，我們在決定使用Bloomfilter之前，需要知道兩個資料，一個是要存儲的數量n和預期的誤判率p。bitmap的大小m決定了存儲空間的大小，hash函數個數k決定了計算量的大小，我們當然都希望m和k都越小越好，如何計算二者的最優值，我們大概來推導下。（備注：推導過程來自Wikipedia）
由上文可知，誤判率p為
p \approx \left(1-e^{-k n / m}\right)^{k} \ (1)
對于給定的m和n我們想讓誤判率p最小，就得讓
k=\frac{m}{n} \ln2 \ (2)
把(2)式代入(1)中可得
p=\left(1-e^{-\left(\frac{m}{n} \ln 2\right) \frac{n}{m}}\right)^{\frac{m}{n} \ln 2} \ (3)
對(3)兩邊同時取ln并簡化後，得到
\ln p=-\frac{m}{n}(\ln 2)^{2}
最後可以計算出m的最優值為
m=-\frac{n \ln p}{(\ln 2)^{2}}
因為誤判率p和要插入的資料量n是已知的，是以我們可以直接根據上式計算出m的值，然後把m和n的值代回到(2)式中就可以得到k的值。至此我們就知道了實作一個bloomfilter所需要的所有參數了，接下來讓我們看下Google guava包中是如何實作BloomFilter的。
guava中的BloomFilter
BloomFilter無法通過new去建立新對象，而它提供了create靜态方法來生成對象，其核心方法如下。
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
checkNotNull(funnel);
checkArgument(
expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
long numBits = optimalNumOfBits(expectedInsertions, fpp);
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
} 從代碼可以看出，需要4個參數，分别是
- funnel 用來對參數做轉化,友善生成hash值
- expectedInsertions 預期插入的資料量大小，也就是上文公式中的n
- fpp 誤判率，也就是上文公式中的誤判率p
- strategy 生成hash值的政策，guava中也提供了預設政策，一般不需要你自己重新實作
從上面代碼可知，BloomFilter建立過程中先檢查參數的合法性，之後使用n和p來計算bitmap的大小m（optimalNumOfBits(expectedInsertions, fpp)），通過n和m計算hash函數的個數k（optimalNumOfHashFunctions(expectedInsertions, numBits)）,這倆方法的具體實作如下。
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
} 其實就是上文中列出的計算公式。
後面插入和查找的邏輯就比較簡單了，這裡不再贅述，有興趣可以看下源碼，我們這裡通過BloomFilter提供的方法清單了解下它的功能就行。
從上圖可以看出，BloomFilter除了提供建立和幾個核心的功能外，還支援寫入Stream或從Stream中重新生成BloomFilter，友善資料的共享和傳輸。
使用案例
- HBase、BigTable、Cassandra、PostgreSQ等著名開源項目都用BloomFilter來減少對磁盤的通路次數，提升性能。
- Chrome浏覽器用BloomFilter來判别惡意網站。
- 爬蟲用BloomFilter來判斷某個url是否爬取過。
-
比特币也用到了BloomFilter來加速錢包資訊的同步。
……
和HashSet對比
我們一直在說BloomFilter有巨大的存儲優勢，做個優勢到底有多明顯，我們拿jdk自帶的HashSet和guava中實作的BloomFilter做下對比，資料僅供參考。
測試環境
測試平台 Mac
guava(28.1)BloomFilter，JDK11(64位) HashSet
使用om.carrotsearch.java-sizeof計算實際占用的記憶體空間
測試方式
BloomFilter vs HashSet
分别往BloomFilter和HashSet中插入UUID，總計插入100w個UUID，BloomFilter誤判率為預設值0.03。每插入5w個統計下各自的占用空間。結果如下，橫軸是資料量大小，縱軸是存儲空間，機關kb。
可以看到BloomFilter存儲空間一直都沒有變，這裡和它的實作有關，事實上你在告訴它總共要插入多少條資料時BloomFilter就計算并申請好了記憶體空間，是以BloomFilter占用記憶體不會随插入資料的多少而變化。相反，HashSet在插入資料越來越多時，其占用的記憶體空間也會越來越多，最終在插入完100w條資料後，其記憶體占用為BloomFilter的100多倍。
在不同fpp下的存儲表現
在不同的誤判率下，插入100w個UUID，計算其記憶體空間占用。結果如下，橫軸是誤判率大小，縱軸是存儲空間，機關kb。
fpp,size
0.1,585.453125
0.01,1170.4765625
1.0E-3,1755.5
1.0E-4,2340.53125
1.0E-5,2925.5546875
1.0E-6,3510.578125
1.0E-7,4095.6015625
1.0E-8,4680.6328125
1.0E-9,5265.65625
1.0E-10,5850.6796875 可以看出，在同等資料量的情況下，BloomFilter的存儲空間和ln(fpp)呈反比，是以增長速率其實不算快，即便誤判率減少9個量級，其存儲空間也隻是增加了10倍。