布隆過濾器：原理與應用-魔扣目錄

在日常生活和工作中，我們經常需要處理海量的數據，篩選出有用的信息。

這個時候，布隆過濾器（Bloom Filter）就派上了用場。作為一種空間高效的概率型數據結構，布隆過濾器能夠快速有效地檢測一個元素是否屬于一個集合。其應用廣泛，從網絡爬蟲的網頁去重，到數據庫查詢優化，乃至比特幣網絡的交易匹配，都離不開它的身影。

本文將深入解析布隆過濾器的原理以及如何在實際情況中進行使用，希望能幫助你更好地理解和運用這種強大的工具。

布隆過濾器簡介

在開發過程中，經常要判斷一個元素是否在一個集合中。假設你現在要給項目添加IP黑名單功能，此時你手上有大約 1億個惡意IP的數據集，有一個IP發起請求，你如何判斷這個IP在不在你的黑名單中？

類似這種問題用JAVA自己的Collection和Map很難處理，因為它們存儲元素本身，會造成內存不足，而我們只關心元素存不存在，對于元素的值我們并不關心，具體值是什么并不重要。

「布隆過濾器」可以用來解決類似的問題，具有運行快速，內存占用小的特點，它是一個保存了很長的二級制向量，同時結合 Hash 函數實現的。

而高效插入和查詢的代價就是，它是一個基于概率的數據結構，只能告訴我們一個元素絕對不在集合內，對于存在集合內的元素有一定的誤判率。

fpp

布隆過濾器中總是會存在誤判率，因為哈希碰撞是不可能百分百避免的。布隆過濾器對這種誤判率稱之為「假陽性概率」，即：False Positive Probability，簡稱為 fpp。

在實踐中使用布隆過濾器時可以自己定義一個 fpp，然后就可以根據布隆過濾器的理論計算出需要多少個哈希函數和多大的位數組空間。需要注意的是這個 fpp 不能定義為 100%，因為無法百分保證不發生哈希碰撞。

布隆過濾器原理

下圖表示向布隆過濾器中添加元素 www.123.com 和 www.456.com 的過程，它使用了 func1 和 func2 兩個簡單的哈希函數。

其基本原理如下：

初始化：當我們創建一個布隆過濾器時，我們首先創建一個全由0組成的位數組（bit array)。同時，我們還需選擇幾個獨立的哈希函數，每個函數都可以將集合中的元素映射到這個位數組的某個位置。
添加元素：在布隆過濾器中添加一個元素時，我們會將此元素通過所有的哈希函數進行映射，得到在位數組中的幾個位置，然后將這些位置標記為1。
查詢元素：如果我們要檢查一個元素是否在集合中，我們同樣使用這些哈希函數將元素映射到位數組中的幾個位置，如果所有的位置都被標記為1，那么我們就可以說該元素可能在集合中。如果有任何一個位置不為1，那么該元素肯定不在集合中。

通過其原理可以知道，我們可以提高數組長度以及 hash 計算次數來降低誤報率，但是相應的 CPU、內存的消耗也會相應地提高，會增加存儲和計算的開銷。因此，布隆過濾器的使用需要在誤判率和性能之間進行權衡。

布隆過濾器的特點

布隆過濾器有以下兩個特點：

只要返回數據不存在，則肯定不存在。
返回數據存在，不一定存在。

布隆過濾器的誤判率主要來源于「哈希碰撞」。因為位數組的大小有限，不同的元素可能會被哈希到相同的位置，導致即使某個元素并未真正被加入過濾器，也可能因為其他已經存在的元素而讓所有哈希函數映射的位都變為了1，從而誤判為存在。這就是布隆過濾器的“假陽性”錯誤。

在有限的數組長度中存放大量的數據，即便是再完美的 Hash 算法也會有沖突，所以有可能兩個完全不同的 A、B 兩個數據最后定位到的位置是一模一樣的。這時拿 B 進行查詢時那自然就是誤報了。

布隆過濾器使用

布隆過濾器中的數據可不可以刪除

布隆過濾器判斷一個元素存在就是判斷對應位置是否為 1 來確定的，但是如果要刪除掉一個元素是不能直接把 1 改成 0 的，因為這個位置可能存在其他元素。

所以如果要支持刪除，最簡單的做法就是加一個計數器，就是說位數組的每個位如果不存在就是 0，存在幾個元素就存具體的數字，而不僅僅只是存 1，但是這樣會帶來其他問題，本來存 1 就是一位就可以滿足了，但是如果要存具體的數字比如說 2，那就需要 2 位了，所以帶有計數器的布隆過濾器會占用更大的空間。

以下是帶有計數器的布隆過濾器的實現：

<dependency>
    <groupId>com.baqend</groupId>
    <artifactId>bloom-filter</artifactId>
    <version>1.0.7</version>
</dependency>

新建一個帶有計數器的布隆過濾器 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
    }
}

構建布隆過濾器前面兩個參數一個就是期望的元素數，一第二個就是 fpp 值，后面的 countingBits 參數就是計數器占用的大小，這里傳了一個 8 位，即最多允許 255 次重復，如果不傳的話這里默認是 16 位大小，即允許 65535次重復。

布隆過濾器應該設計為多大

假設在布隆過濾器里面有 k 個哈希函數，m 個比特位（也就是位數組長度），以及 n 個已插入元素，錯誤率會近似于 (1-ekn/m)k，所以你只需要先確定可能插入的數據集的容量大小 n，然后再調整 k 和 m 來為你的應用配置過濾器。

布隆過濾器應該使用多少個哈希函數

對于給定的 m（比特位個數）和 n（集合元素個數），最優的 k（哈希函數個數）值為: (m/n)ln(2)。

布隆過濾器的時間復雜度和空間復雜度

對于一個 m（比特位個數）和 k（哈希函數個數）值確定的布隆過濾器，添加和判斷操作的時間復雜度都是 O(k)，這意味著每次你想要插入一個元素或者查詢一個元素是否在集合中，只需要使用 k 個哈希函數對該元素求值，然后將對應的比特位標記或者檢查對應的比特位即可。

布隆過濾器實現

Guava的布隆過濾器的實現

Guava有自帶的布隆過濾器的實現：

public class BloomFilterTest {

    public static void main(String[] args) {
        long star = System.currentTimeMillis();
        BloomFilter<Integer> filter = BloomFilter.create(
                Funnels.integerFunnel(),
                //預計存放多少數據
                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("執行時間：" + (end - star));

    }
}

Guava自帶的布隆過濾器，只需直接傳入預期的數據量以及fpp，它會自動幫我們計算數組長度和哈希次數。

這段代碼創建了一個預期存儲10000000個整數的布隆過濾器，誤報率為1%。

然后，代碼將0到9999999的所有整數添加到過濾器中。然后，對數字1、2、3和10000000進行測試。對于前三個數字，因為他們已經被添加到過濾器中，所以mightContain返回true；對于最后一個數字（10000000），由于它并未加入過濾器，mightContain方法可能返回false，但也有1%的概率返回true（誤報）。

BitMap（位圖）

BitMap不會存在誤判的情況，位圖也是布隆過濾器的實現，但是占用內存空間隨集合內最大元素的增大而增大。而布隆過濾器，因為其可能一個bit為多個元素作標識，這就保證了它的空間利用率。這兩種方式根據業務進行選擇。

以32位整型為例，它可以表示數字的個數為2^32，可以申請一個位圖，讓每個整數對應的位圖中的一個bit，這樣2^32個數需要的位圖的大小為512MB。

具體實現的思路為：申請一個512MB的位圖，并把所有的位都初始化為0，接著遍歷所有的整數，對遍歷到的數字，把相應的位置上的bit設置為1。

最后判斷待查找的數對應的位圖上的值是多少，如果是0，那么表示這個數字不存在，如果是1，那么表示這個數字存在。

Java中有BitMap的實現類：BitSet，Java中的BitSet類創建一種特殊類型的數組來保存位值。該類實現了一個可動態擴展的位向量。位集的大小會隨著需要而增長。這使得它成為了實現位圖的理想選擇。

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));
 
        }
}

這段代碼首先創建了一個BitSet實例，然后遍歷數組，把數組中每個元素值設為位集中對應索引的位。例如，數組中的第一個元素是3，那么就把位集的第三位設為true。最后，使用stream()方法和lambda表達式打印出所有被設置為true的位的索引。

這就是本篇文章的全部內容。在總結我們對布隆過濾器的探討時，我們可以看到其獨特和強大之處。這種數據結構經常被應用于各種場景，包括緩存系統、網絡路由器，甚至是大規模分布式數據庫中。盡管它存在一定的誤報率，但是通過精心選擇哈希函數的數量和位數組的大小，我們可以降低這個概率。

布隆過濾器的高效性、節省空間的特性以及靈活的設計使得它成為解決各種問題的有力工具。但需要注意的是，作為工程師和開發者，我們必須理解并接受其限制和妥協，如假陽性的可能性和無法從過濾器中刪除元素的事實。然而，正是這些限制，為我們提供了改進和創新的機會，推動我們尋找更多高效、靈活的數據處理方法。

總的來說，布隆過濾器是一個強大而高效的工具，值得我們深入理解和廣泛應用。同時，它也是計算機科學中眾多神奇的示例之一，展示了如何通過聰明的設計和妥協，解決現實世界中的挑戰問題。