在日常生活和工作中，我們經(jīng)常需要處理海量的數(shù)據(jù)，篩選出有用的信息。
這個時候，布隆過濾器（Bloom Filter）就派上了用場。作為一種空間高效的概率型數(shù)據(jù)結(jié)構(gòu)，布隆過濾器能夠快速有效地檢測一個元素是否屬于一個集合。其應(yīng)用廣泛，從網(wǎng)絡(luò)爬蟲的網(wǎng)頁去重，到數(shù)據(jù)庫查詢優(yōu)化，乃至比特幣網(wǎng)絡(luò)的交易匹配，都離不開它的身影。
本文將深入解析布隆過濾器的原理以及如何在實際情況中進行使用，希望能幫助你更好地理解和運用這種強大的工具。
布隆過濾器簡介
在開發(fā)過程中，經(jīng)常要判斷一個元素是否在一個集合中。假設(shè)你現(xiàn)在要給項目添加IP黑名單功能，此時你手上有大約 1億個惡意IP的數(shù)據(jù)集，有一個IP發(fā)起請求，你如何判斷這個IP在不在你的黑名單中？
類似這種問題用JAVA自己的Collection和Map很難處理，因為它們存儲元素本身，會造成內(nèi)存不足，而我們只關(guān)心元素存不存在，對于元素的值我們并不關(guān)心，具體值是什么并不重要。
「布隆過濾器」可以用來解決類似的問題，具有運行快速，內(nèi)存占用小的特點，它是一個保存了很長的二級制向量，同時結(jié)合 Hash 函數(shù)實現(xiàn)的。
而高效插入和查詢的代價就是，它是一個基于概率的數(shù)據(jù)結(jié)構(gòu)，只能告訴我們一個元素絕對不在集合內(nèi)，對于存在集合內(nèi)的元素有一定的誤判率。
fpp
布隆過濾器中總是會存在誤判率，因為哈希碰撞是不可能百分百避免的。布隆過濾器對這種誤判率稱之為「假陽性概率」，即：False Positive Probability，簡稱為 fpp。
在實踐中使用布隆過濾器時可以自己定義一個 fpp，然后就可以根據(jù)布隆過濾器的理論計算出需要多少個哈希函數(shù)和多大的位數(shù)組空間。需要注意的是這個 fpp 不能定義為 100%，因為無法百分保證不發(fā)生哈希碰撞。
布隆過濾器原理
下圖表示向布隆過濾器中添加元素 www.123.com 和 www.456.com 的過程，它使用了 func1 和 func2 兩個簡單的哈希函數(shù)。
其基本原理如下：
-
初始化：當(dāng)我們創(chuàng)建一個布隆過濾器時，我們首先創(chuàng)建一個全由0組成的位數(shù)組（bit array)。同時，我們還需選擇幾個獨立的哈希函數(shù)，每個函數(shù)都可以將集合中的元素映射到這個位數(shù)組的某個位置。 -
添加元素：在布隆過濾器中添加一個元素時，我們會將此元素通過所有的哈希函數(shù)進行映射，得到在位數(shù)組中的幾個位置，然后將這些位置標(biāo)記為1。 -
查詢元素：如果我們要檢查一個元素是否在集合中，我們同樣使用這些哈希函數(shù)將元素映射到位數(shù)組中的幾個位置，如果所有的位置都被標(biāo)記為1，那么我們就可以說該元素可能在集合中。如果有任何一個位置不為1，那么該元素肯定不在集合中。
通過其原理可以知道，我們可以提高數(shù)組長度以及 hash 計算次數(shù)來降低誤報率，但是相應(yīng)的 CPU、內(nèi)存的消耗也會相應(yīng)地提高，會增加存儲和計算的開銷。因此，布隆過濾器的使用需要在誤判率和性能之間進行權(quán)衡。
布隆過濾器的特點
布隆過濾器有以下兩個特點：
-
只要返回數(shù)據(jù)不存在，則肯定不存在。 -
返回數(shù)據(jù)存在，不一定存在。
布隆過濾器的誤判率主要來源于「哈希碰撞」。因為位數(shù)組的大小有限，不同的元素可能會被哈希到相同的位置，導(dǎo)致即使某個元素并未真正被加入過濾器，也可能因為其他已經(jīng)存在的元素而讓所有哈希函數(shù)映射的位都變?yōu)榱?，從而誤判為存在。這就是布隆過濾器的“假陽性”錯誤。
在有限的數(shù)組長度中存放大量的數(shù)據(jù)，即便是再完美的 Hash 算法也會有沖突，所以有可能兩個完全不同的 A、B 兩個數(shù)據(jù)最后定位到的位置是一模一樣的。這時拿 B 進行查詢時那自然就是誤報了。
布隆過濾器使用
布隆過濾器中的數(shù)據(jù)可不可以刪除
布隆過濾器判斷一個元素存在就是判斷對應(yīng)位置是否為 1 來確定的，但是如果要刪除掉一個元素是不能直接把 1 改成 0 的，因為這個位置可能存在其他元素。
所以如果要支持刪除，最簡單的做法就是加一個計數(shù)器，就是說位數(shù)組的每個位如果不存在就是 0，存在幾個元素就存具體的數(shù)字，而不僅僅只是存 1，但是這樣會帶來其他問題，本來存 1 就是一位就可以滿足了，但是如果要存具體的數(shù)字比如說 2，那就需要 2 位了，所以帶有計數(shù)器的布隆過濾器會占用更大的空間。
以下是帶有計數(shù)器的布隆過濾器的實現(xiàn)：
<dependency>
<groupId>com.baqend</groupId>
<artifactId>bloom-filter</artifactId>
<version>1.0.7</version>
</dependency>
新建一個帶有計數(shù)器的布隆過濾器 CountingBloomFilter：
import orestes.bloomfilter.FilterBuilder;
public class CountingBloomFilter {
public static void mAIn(String[] args) {
orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
0.01).countingBits(8).buildCountingBloomFilter();
cbf.add("zhangsan");
cbf.add("lisi");
cbf.add("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
cbf.remove("wangwu");
System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
}
}
構(gòu)建布隆過濾器前面 兩個參數(shù)一個就是期望的元素數(shù)，一第二個就是 fpp 值，后面的 countingBits 參數(shù)就是計數(shù)器占用的大小，這里傳了一個 8 位，即最多允許 255 次重復(fù)，如果不傳的話這里默認(rèn)是 16 位大小，即允許 65535次重復(fù)。
布隆過濾器應(yīng)該設(shè)計為多大
假設(shè)在布隆過濾器里面有 k 個哈希函數(shù)，m 個比特位（也就是位數(shù)組長度），以及 n 個已插入元素，錯誤率會近似于 (1-ekn/m)k，所以你只需要先確定可能插入的數(shù)據(jù)集的容量大小 n，然后再調(diào)整 k 和 m 來為你的應(yīng)用配置過濾器。
布隆過濾器應(yīng)該使用多少個哈希函數(shù)
對于給定的 m（比特位個數(shù)）和 n（集合元素個數(shù)），最優(yōu)的 k（哈希函數(shù)個數(shù)）值為: (m/n)ln(2)。
布隆過濾器的時間復(fù)雜度和空間復(fù)雜度
對于一個 m（比特位個數(shù)）和 k（哈希函數(shù)個數(shù)）值確定的布隆過濾器，添加和判斷操作的時間復(fù)雜度都是 O(k)，這意味著每次你想要插入一個元素或者查詢一個元素是否在集合中，只需要使用 k 個哈希函數(shù)對該元素求值，然后將對應(yīng)的比特位標(biāo)記或者檢查對應(yīng)的比特位即可。
布隆過濾器實現(xiàn)
Guava的布隆過濾器的實現(xiàn)
Guava有自帶的布隆過濾器的實現(xiàn)：
public class BloomFilterTest {
public static void main(String[] args) {
long star = System.currentTimeMillis();
BloomFilter<Integer> filter = BloomFilter.create(
Funnels.integerFunnel(),
//預(yù)計存放多少數(shù)據(jù)
10000000,
//可以接受的誤報率
0.01);
for (int i = 0; i < 10000000; i++) {
filter.put(i);
}
Assert.isTrue(filter.mightContain(1),"不存在");
Assert.isTrue(filter.mightContain(2),"不存在");
Assert.isTrue(filter.mightContain(3),"不存在");
Assert.isTrue(filter.mightContain(10000000),"不存在");
long end = System.currentTimeMillis();
System.out.println("執(zhí)行時間：" + (end - star));
}
}
Guava自帶的布隆過濾器，只需直接傳入預(yù)期的數(shù)據(jù)量以及fpp，它會自動幫我們計算數(shù)組長度和哈希次數(shù)。
這段代碼創(chuàng)建了一個預(yù)期存儲10000000個整數(shù)的布隆過濾器，誤報率為1%。
然后，代碼將0到9999999的所有整數(shù)添加到過濾器中。然后，對數(shù)字1、2、3和10000000進行測試。對于前三個數(shù)字，因為他們已經(jīng)被添加到過濾器中，所以mightContain返回true；對于最后一個數(shù)字（10000000），由于它并未加入過濾器，mightContain方法可能返回false，但也有1%的概率返回true（誤報）。
BitMap（位圖）
BitMap不會存在誤判的情況，位圖也是布隆過濾器的實現(xiàn)，但是占用內(nèi)存空間隨集合內(nèi)最大元素的增大而增大。而布隆過濾器，因為其可能一個bit為多個元素作標(biāo)識，這就保證了它的空間利用率。這兩種方式根據(jù)業(yè)務(wù)進行選擇。
以32位整型為例，它可以表示數(shù)字的個數(shù)為2^32，可以申請一個位圖，讓每個整數(shù)對應(yīng)的位圖中的一個bit，這樣2^32個數(shù)需要的位圖的大小為512MB。
具體實現(xiàn)的思路為：申請一個512MB的位圖，并把所有的位都初始化為0，接著遍歷所有的整數(shù)，對遍歷到的數(shù)字，把相應(yīng)的位置上的bit設(shè)置為1。
最后判斷待查找的數(shù)對應(yīng)的位圖上的值是多少，如果是0，那么表示這個數(shù)字不存在，如果是1，那么表示這個數(shù)字存在。
Java中有BitMap的實現(xiàn)類：BitSet，Java中的BitSet類創(chuàng)建一種特殊類型的數(shù)組來保存位值。該類實現(xiàn)了一個可動態(tài)擴展的位向量。位集的大小會隨著需要而增長。這使得它成為了實現(xiàn)位圖的理想選擇。
public class BitMapTest {
public static void main(String[] args) {
int[] array = {3, 8, 5, 7, 1};
BitSet bitSet = new BitSet(5);
for (int i = 0; i < array.length; i++) {
bitSet.set(array[i], true);
}
bitSet.stream().forEach(e -> System.out.println(e));
}
}
這段代碼首先創(chuàng)建了一個BitSet實例，然后遍歷數(shù)組，把數(shù)組中每個元素值設(shè)為位集中對應(yīng)索引的位。例如，數(shù)組中的第一個元素是3，那么就把位集的第三位設(shè)為true。最后，使用stream()方法和lambda表達式打印出所有被設(shè)置為true的位的索引。
這就是本篇文章的全部內(nèi)容。在總結(jié)我們對布隆過濾器的探討時，我們可以看到其獨特和強大之處。這種數(shù)據(jù)結(jié)構(gòu)經(jīng)常被應(yīng)用于各種場景，包括緩存系統(tǒng)、網(wǎng)絡(luò)路由器，甚至是大規(guī)模分布式數(shù)據(jù)庫中。盡管它存在一定的誤報率，但是通過精心選擇哈希函數(shù)的數(shù)量和位數(shù)組的大小，我們可以降低這個概率。
布隆過濾器的高效性、節(jié)省空間的特性以及靈活的設(shè)計使得它成為解決各種問題的有力工具。但需要注意的是，作為工程師和開發(fā)者，我們必須理解并接受其限制和妥協(xié)，如假陽性的可能性和無法從過濾器中刪除元素的事實。然而，正是這些限制，為我們提供了改進和創(chuàng)新的機會，推動我們尋找更多高效、靈活的數(shù)據(jù)處理方法。
總的來說，布隆過濾器是一個強大而高效的工具，值得我們深入理解和廣泛應(yīng)用。同時，它也是計算機科學(xué)中眾多神奇的示例之一，展示了如何通過聰明的設(shè)計和妥協(xié)，解決現(xiàn)實世界中的挑戰(zhàn)問題。
