摘要：需求其實(shí)很清晰，只是要判斷一個(gè)數(shù)據(jù)是否存在即可。實(shí)際情況也是如此既然要判斷一個(gè)數(shù)據(jù)是否存在于集合中，考慮的算法的效率以及準(zhǔn)確性肯定是要把數(shù)據(jù)全部到內(nèi)存中的。所以布隆過(guò)濾有以下幾個(gè)特點(diǎn)只要返回?cái)?shù)據(jù)不存在，則肯定不存在。

最近有朋友問(wèn)我這么一個(gè)面試題目：

現(xiàn)在有一個(gè)非常龐大的數(shù)據(jù)，假設(shè)全是 int 類型?，F(xiàn)在我給你一個(gè)數(shù)，你需要告訴我它是否存在其中(盡量高效)。

需求其實(shí)很清晰，只是要判斷一個(gè)數(shù)據(jù)是否存在即可。

但這里有一個(gè)比較重要的前提：非常龐大的數(shù)據(jù)。

先不考慮這個(gè)條件，我們腦海中出現(xiàn)的第一種方案是什么？

我想大多數(shù)想到的都是用 HashMap 來(lái)存放數(shù)據(jù)，因?yàn)樗膶?xiě)入查詢的效率都比較高。

寫(xiě)入和判斷元素是否存在都有對(duì)應(yīng)的 API，所以實(shí)現(xiàn)起來(lái)也比較簡(jiǎn)單。

為此我寫(xiě)了一個(gè)單測(cè)，利用 HashSet 來(lái)存數(shù)據(jù)（底層也是 HashMap ）；同時(shí)為了后面的對(duì)比將堆內(nèi)存寫(xiě)死：

-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError 

為了方便調(diào)試加入了 GC 日志的打印，以及內(nèi)存溢出后 Dump 內(nèi)存。

    @Test
    public void hashMapTest(){
        long star = System.currentTimeMillis();

        Set hashset = new HashSet<>(100) ;
        for (int i = 0; i < 100; i++) {
            hashset.add(i) ;
        }
        Assert.assertTrue(hashset.contains(1));
        Assert.assertTrue(hashset.contains(2));
        Assert.assertTrue(hashset.contains(3));

        long end = System.currentTimeMillis();
        System.out.println("執(zhí)行時(shí)間：" + (end - star));
    }

當(dāng)我只寫(xiě)入 100 條數(shù)據(jù)時(shí)自然是沒(méi)有問(wèn)題的。

還是在這個(gè)基礎(chǔ)上，寫(xiě)入 1000W 數(shù)據(jù)試試：

執(zhí)行后馬上就內(nèi)存溢出。

可見(jiàn)在內(nèi)存有限的情況下我們不能使用這種方式。

實(shí)際情況也是如此；既然要判斷一個(gè)數(shù)據(jù)是否存在于集合中，考慮的算法的效率以及準(zhǔn)確性肯定是要把數(shù)據(jù)全部 load 到內(nèi)存中的。

基于上面分析的條件，要實(shí)現(xiàn)這個(gè)需求最需要解決的是如何將龐大的數(shù)據(jù) load 到內(nèi)存中。

而我們是否可以換種思路，因?yàn)橹皇切枰袛鄶?shù)據(jù)是否存在，也不是需要把數(shù)據(jù)查詢出來(lái)，所以完全沒(méi)有必要將真正的數(shù)據(jù)存放進(jìn)去。

偉大的科學(xué)家們已經(jīng)幫我們想到了這樣的需求。

Burton Howard Bloom 在 1970 年提出了一個(gè)叫做 Bloom Filter（中文翻譯：布隆過(guò)濾）的算法。

它主要就是用于解決判斷一個(gè)元素是否在一個(gè)集合中，但它的優(yōu)勢(shì)是只需要占用很小的內(nèi)存空間以及有著高效的查詢效率。

所以在這個(gè)場(chǎng)景下在合適不過(guò)了。

下面來(lái)分析下它的實(shí)現(xiàn)原理。

官方的說(shuō)法是：它是一個(gè)保存了很長(zhǎng)的二級(jí)制向量，同時(shí)結(jié)合 Hash 函數(shù)實(shí)現(xiàn)的。

聽(tīng)起來(lái)比較繞，但是通過(guò)一個(gè)圖就比較容易理解了。

如圖所示：

首先需要初始化一個(gè)二進(jìn)制的數(shù)組，長(zhǎng)度設(shè)為 L（圖中為 8），同時(shí)初始值全為 0 。

當(dāng)寫(xiě)入一個(gè) A1=1000 的數(shù)據(jù)時(shí)，需要進(jìn)行 H 次 hash 函數(shù)的運(yùn)算（這里為 2 次）；與 HashMap 有點(diǎn)類似，通過(guò)算出的 HashCode 與 L 取模后定位到 0、2 處，將該處的值設(shè)為 1。

A2=2000 也是同理計(jì)算后將 4、7 位置設(shè)為 1。

當(dāng)有一個(gè) B1=1000 需要判斷是否存在時(shí)，也是做兩次 Hash 運(yùn)算，定位到 0、2 處，此時(shí)他們的值都為 1 ，所以認(rèn)為 B1=1000 存在于集合中。

當(dāng)有一個(gè) B2=3000 時(shí)，也是同理。第一次 Hash 定位到 index=4 時(shí)，數(shù)組中的值為 1，所以再進(jìn)行第二次 Hash 運(yùn)算，結(jié)果定位到 index=5 的值為 0，所以認(rèn)為 B2=3000 不存在于集合中。

整個(gè)的寫(xiě)入、查詢的流程就是這樣，匯總起來(lái)就是：

對(duì)寫(xiě)入的數(shù)據(jù)做 H 次 hash 運(yùn)算定位到數(shù)組中的位置，同時(shí)將數(shù)據(jù)改為 1 。當(dāng)有數(shù)據(jù)查詢時(shí)也是同樣的方式定位到數(shù)組中。
一旦其中的有一位為 0 則認(rèn)為數(shù)據(jù)肯定不存在于集合，否則數(shù)據(jù)可能存在于集合中。

所以布隆過(guò)濾有以下幾個(gè)特點(diǎn)：

只要返回?cái)?shù)據(jù)不存在，則肯定不存在。

返回?cái)?shù)據(jù)存在，但只能是大概率存在。

同時(shí)不能清除其中的數(shù)據(jù)。

第一點(diǎn)應(yīng)該都能理解，重點(diǎn)解釋下 2、3 點(diǎn)。

為什么返回存在的數(shù)據(jù)卻是可能存在呢，這其實(shí)也和 HashMap 類似。

在有限的數(shù)組長(zhǎng)度中存放大量的數(shù)據(jù)，即便是再完美的 Hash 算法也會(huì)有沖突，所以有可能兩個(gè)完全不同的 A、B 兩個(gè)數(shù)據(jù)最后定位到的位置是一模一樣的。

這時(shí)拿 B 進(jìn)行查詢時(shí)那自然就是誤報(bào)了。

刪除數(shù)據(jù)也是同理，當(dāng)我把 B 的數(shù)據(jù)刪除時(shí)，其實(shí)也相當(dāng)于是把 A 的數(shù)據(jù)刪掉了，這樣也會(huì)造成后續(xù)的誤報(bào)。

基于以上的 Hash 沖突的前提，所以 Bloom Filter 有一定的誤報(bào)率，這個(gè)誤報(bào)率和 Hash 算法的次數(shù) H，以及數(shù)組長(zhǎng)度 L 都是有關(guān)的。

算法其實(shí)很簡(jiǎn)單不難理解，于是利用 Java 實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的雛形。

public class BloomFilters {

    /**
     * 數(shù)組長(zhǎng)度
     */
    private int arraySize;

    /**
     * 數(shù)組
     */
    private int[] array;

    public BloomFilters(int arraySize) {
        this.arraySize = arraySize;
        array = new int[arraySize];
    }

    /**
     * 寫(xiě)入數(shù)據(jù)
     * @param key
     */
    public void add(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        array[first % arraySize] = 1;
        array[second % arraySize] = 1;
        array[third % arraySize] = 1;

    }

    /**
     * 判斷數(shù)據(jù)是否存在
     * @param key
     * @return
     */
    public boolean check(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        int firstIndex = array[first % arraySize];
        if (firstIndex == 0) {
            return false;
        }

        int secondIndex = array[second % arraySize];
        if (secondIndex == 0) {
            return false;
        }

        int thirdIndex = array[third % arraySize];
        if (thirdIndex == 0) {
            return false;
        }

        return true;

    }


    /**
     * hash 算法1
     * @param key
     * @return
     */
    private int hashcode_1(String key) {
        int hash = 0;
        int i;
        for (i = 0; i < key.length(); ++i) {
            hash = 33 * hash + key.charAt(i);
        }
        return Math.abs(hash);
    }

    /**
     * hash 算法2
     * @param data
     * @return
     */
    private int hashcode_2(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++) {
            hash = (hash ^ data.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }

    /**
     *  hash 算法3
     * @param key
     * @return
     */
    private int hashcode_3(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(hash);
    }
}

首先初始化了一個(gè) int 數(shù)組。

寫(xiě)入數(shù)據(jù)的時(shí)候進(jìn)行三次 hash 運(yùn)算，同時(shí)把對(duì)應(yīng)的位置置為 1。

查詢時(shí)同樣的三次 hash 運(yùn)算，取到對(duì)應(yīng)的值，一旦值為 0 ，則認(rèn)為數(shù)據(jù)不存在。

實(shí)現(xiàn)邏輯其實(shí)就和上文描述的一樣。

下面來(lái)測(cè)試一下，同樣的參數(shù)：

-Xms64m -Xmx64m -XX:+PrintHeapAtGC

    @Test
    public void bloomFilterTest(){
        long star = System.currentTimeMillis();
        BloomFilters bloomFilters = new BloomFilters(10000000) ;
        for (int i = 0; i < 10000000; i++) {
            bloomFilters.add(i + "") ;
        }
        Assert.assertTrue(bloomFilters.check(1+""));
        Assert.assertTrue(bloomFilters.check(2+""));
        Assert.assertTrue(bloomFilters.check(3+""));
        Assert.assertTrue(bloomFilters.check(999999+""));
        Assert.assertFalse(bloomFilters.check(400230340+""));
        long end = System.currentTimeMillis();
        System.out.println("執(zhí)行時(shí)間：" + (end - star));
    }

執(zhí)行結(jié)果如下：

只花了 3 秒鐘就寫(xiě)入了 1000W 的數(shù)據(jù)同時(shí)做出來(lái)準(zhǔn)確的判斷。

當(dāng)讓我把數(shù)組長(zhǎng)度縮小到了 100W 時(shí)就出現(xiàn)了一個(gè)誤報(bào)，400230340 這個(gè)數(shù)明明沒(méi)在集合里，卻返回了存在。

這也體現(xiàn)了 Bloom Filter 的誤報(bào)率。

我們提高數(shù)組長(zhǎng)度以及 hash 計(jì)算次數(shù)可以降低誤報(bào)率，但相應(yīng)的 CPU、內(nèi)存的消耗就會(huì)提高；這就需要根據(jù)業(yè)務(wù)需要自行權(quán)衡。

剛才的方式雖然實(shí)現(xiàn)了功能，也滿足了大量數(shù)據(jù)。但其實(shí)觀察 GC 日志非常頻繁，同時(shí)老年代也使用了 90%，接近崩潰的邊緣。

總的來(lái)說(shuō)就是內(nèi)存利用率做的不好。

其實(shí) Google Guava 庫(kù)中也實(shí)現(xiàn)了該算法，下面來(lái)看看業(yè)界權(quán)威的實(shí)現(xiàn)。

-Xms64m -Xmx64m -XX:+PrintHeapAtGC 

    @Test
    public void guavaTest() {
        long star = System.currentTimeMillis();
        BloomFilter filter = BloomFilter.create(
                Funnels.integerFunnel(),
                10000000,
                0.01);

        for (int i = 0; i < 10000000; i++) {
            filter.put(i);
        }

        Assert.assertTrue(filter.mightContain(1));
        Assert.assertTrue(filter.mightContain(2));
        Assert.assertTrue(filter.mightContain(3));
        Assert.assertFalse(filter.mightContain(10000000));
        long end = System.currentTimeMillis();
        System.out.println("執(zhí)行時(shí)間：" + (end - star));
    }

也是同樣寫(xiě)入了 1000W 的數(shù)據(jù)，執(zhí)行沒(méi)有問(wèn)題。

觀察 GC 日志會(huì)發(fā)現(xiàn)沒(méi)有一次 fullGC，同時(shí)老年代的使用率很低。和剛才的一對(duì)比這里明顯的要好上很多，也可以寫(xiě)入更多的數(shù)據(jù)。

那就來(lái)看看 Guava 它是如何實(shí)現(xiàn)的。

構(gòu)造方法中有兩個(gè)比較重要的參數(shù)，一個(gè)是預(yù)計(jì)存放多少數(shù)據(jù)，一個(gè)是可以接受的誤報(bào)率。
我這里的測(cè)試 demo 分別是 1000W 以及 0.01。

Guava 會(huì)通過(guò)你預(yù)計(jì)的數(shù)量以及誤報(bào)率幫你計(jì)算出你應(yīng)當(dāng)會(huì)使用的數(shù)組大小 numBits 以及需要計(jì)算幾次 Hash 函數(shù) numHashFunctions 。

這個(gè)算法計(jì)算規(guī)則可以參考維基百科。

真正存放數(shù)據(jù)的 put 函數(shù)如下：

根據(jù) murmur3_128 方法的到一個(gè) 128 位長(zhǎng)度的 byte[]。

分別取高低 8 位的到兩個(gè) hash 值。

再根據(jù)初始化時(shí)的到的執(zhí)行 hash 的次數(shù)進(jìn)行 hash 運(yùn)算。

bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);

其實(shí)也是 hash取模拿到 index 后去賦值 1.

重點(diǎn)是 bits.set() 方法。

其實(shí) set 方法是 BitArray 中的一個(gè)函數(shù)，BitArray 就是真正存放數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)。

利用了一個(gè) long[] data 來(lái)存放數(shù)據(jù)。

所以 set() 時(shí)候也是對(duì)這個(gè) data 做處理。

在 set 之前先通過(guò) get() 判斷這個(gè)數(shù)據(jù)是否存在于集合中，如果已經(jīng)存在則直接返回告知客戶端寫(xiě)入失敗。

接下來(lái)就是通過(guò)位運(yùn)算進(jìn)行位或賦值。

get() 方法的計(jì)算邏輯和 set 類似，只要判斷為 0 就直接返回存在該值。

前面幾步的邏輯都是類似的，只是調(diào)用了剛才的 get() 方法判斷元素是否存在而已。

布隆過(guò)濾的應(yīng)用還是蠻多的，比如數(shù)據(jù)庫(kù)、爬蟲(chóng)、防緩存擊穿等。

特別是需要精確知道某個(gè)數(shù)據(jù)不存在時(shí)做點(diǎn)什么事情就非常適合布隆過(guò)濾。

這段時(shí)間的研究發(fā)現(xiàn)算法也挺有意思的，后續(xù)應(yīng)該會(huì)繼續(xù)分享一些類似的內(nèi)容。

如果對(duì)你有幫助那就分享一下吧。

本問(wèn)的示例代碼參考這里：

https://github.com/crossoverJie/JCSprout

你的點(diǎn)贊與分享是對(duì)我最大的支持