一、前言

講個使用場景，比如我們在使用新聞客戶端看新聞時，它會給我們不停地推薦新的內(nèi)容，它每次推薦時要去重，去掉那些已經(jīng)看過的內(nèi)容。問題來了，新聞客戶端推薦系統(tǒng)如何實現(xiàn)推送去重的？

1. 你會想到服務器記錄了用戶看過的所有歷史記錄，當推薦系統(tǒng)推薦新聞時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經(jīng)存在的記錄。問題是當用戶量很大，每個用戶看過的新聞又很多的情況下，這種方式，推薦系統(tǒng)的去重工作在性能上跟的上么？

1. 實際上，如果歷史記錄存儲在關系數(shù)據(jù)庫里，去重就需要頻繁地對數(shù)據(jù)庫進行 exists 查詢，當系統(tǒng)并發(fā)量很高時，數(shù)據(jù)庫是很難扛住壓力的

2. 你可能又想到了緩存，但是如此多的歷史記錄全部緩存起來，那得浪費多大存儲空間??？而且這個存儲空間是隨著時間線性增長，你撐得住一個月，你能撐得住幾年么？但是不緩存的話，性能又跟不上，這該怎么辦？

這時，布隆過濾器 (Bloom Filter) 閃亮登場了，它就是專門用來解決這種去重問題的。它在起到去重的同時，在空間上還能節(jié)省 90% 以上，只是稍微有那么點不精確，也就是有一定的誤判概率。

二、什么是布隆過濾器？

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

三、布隆過濾器原理

講述布隆過濾器的原理之前，我們先思考一下，通常你判斷某個元素是否存在用的是什么?應該蠻多人回答 HashMap 吧，確實可以將值映射到HashMap 的 Key，然后可以在 0(1)的時間復雜度內(nèi)返回結果,效率奇高。但是 HashMap的實現(xiàn)也有缺點，例如存儲容量占比高，考慮到負載因子的存在，通常空間是不能被用滿的，而一旦你的值很多例如上億的時候,那HashMap占據(jù)的內(nèi)存大小就變得很可觀了。

當一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

注：圖中是三個散列函數(shù)，實際當中不一定是三個，所以上面用的k。

如下圖所示，兩個不同的值，經(jīng)過相同的哈希運算后，可能會得出同樣的值。即下圖中，hello和你好 經(jīng)過哈希運算后，得出的下標都為2，把位2上的值改為1。所以，無法判斷位2上的值為1是誰的值。

同時，如果只存儲了"你好"未存儲"hello"，當查詢hello時，經(jīng)過哈希運算得出值為2，去位2中查看，得知值為1，得出結論"hello"可能存在于過濾器中，即發(fā)生了誤判。

誤判可以通過增多哈希函數(shù)進行降低。哈希函數(shù)越多，誤判率越低。同時，布隆過濾器查找和插入的時間復雜度都為O(k)，k為哈希函數(shù)的個數(shù)。所以，哈希函數(shù)越多，時間復雜度越高。具體如何選擇，需要根據(jù)數(shù)據(jù)量的多少進行。

優(yōu)點：

• 占用空間小，因為他是不存儲實際數(shù)據(jù)的。
• 保密性非常好，不存儲原始數(shù)據(jù)，別人也不知道0和1是什么。
• 他底層是基于位數(shù)組的，基于數(shù)組的特性查詢和插入是非常快的。

缺點：

• 由于上文中提到的數(shù)據(jù)經(jīng)過哈希計算后值相同的原因，一般情況下不能從布隆過濾器中刪除元素。
• 存在誤判，本身不在里面可能經(jīng)過hash計算會認為存在。

四、布隆過濾器使用場景

綜上，我們可以得出：布隆過濾器可以判斷指定的元素一定不存在或者可能存在！ 打個比方，當它說不認識你時，肯定就不認識；當它說見過你時，可能根本就沒見過面，不過因為你的臉跟它認識的人中某臉比較相似 (某些熟臉的系數(shù)組合)，所以誤判以前見過你。

套在上面的新聞推薦使用場景中，布隆過濾器能準確過濾掉那些已經(jīng)看過的內(nèi)容，那些沒有看過的新內(nèi)容，它也會過濾掉極小一部分 (誤判)，但是絕大多數(shù)新內(nèi)容它都能準確識別。這樣就可以完全保證推薦給用戶的內(nèi)容都是無重復的。

一般有如下幾種使用場景：

• 解決Redis緩存穿透
• 在爬蟲系統(tǒng)中，我們需要對 URL 進行去重，已經(jīng)爬過的網(wǎng)頁就可以不用爬了。但是URL 太多了，幾千萬幾個億，如果用一個集合裝下這些 URL 地址那是非常浪費空間的。這時候就可以考慮使用布隆過濾器。它可以大幅降低去重存儲消耗，只不過也會使得爬蟲系統(tǒng)錯過少量的頁面。
• 郵箱系統(tǒng)的垃圾郵件過濾功能也普遍用到了布隆過濾器，因為用了這個過濾器，所以平時也會遇到某些正常的郵件被放進了垃圾郵件目錄中
• 新聞推薦、文章推薦等等。

五、空間占用估計

布隆過濾器有兩個參數(shù)，第一個是預計元素的數(shù)量 n，第二個是錯誤率 f。公式根據(jù)這兩個輸入得到兩個輸出，第一個輸出是位數(shù)組的長度 l，也就是需要的存儲空間大小 (bit)，第二個輸出是 hash 函數(shù)的最佳數(shù)量 k。hash 函數(shù)的數(shù)量也會直接影響到錯誤率，最佳的數(shù)量會有最低的錯誤率。

• k=0.7*(l/n) # 約等于
• f=0.6185^(l/n) # ^ 表示次方計算，也就是 math.pow

從公式中可以看出

1. 位數(shù)組相對越長 (l/n)，錯誤率 f 越低，這個和直觀上理解是一致的
2. 位數(shù)組相對越長 (l/n)，hash 函數(shù)需要的最佳數(shù)量也越多，影響計算效率
3. 當一個元素平均需要 1 個字節(jié) (8bit) 的指紋空間時 (l/n=8)，錯誤率大約為 2%
4. 錯誤率為 10%，一個元素需要的平均指紋空間為 4.792 個 bit，大約為 5bit
5. 錯誤率為 1%，一個元素需要的平均指紋空間為 9.585 個 bit，大約為 10bit
6. 錯誤率為 0.1%，一個元素需要的平均指紋空間為 14.377 個 bit，大約為 15bit

你也許會想，如果一個元素需要占據(jù) 15 個 bit，那相對 set 集合的空間優(yōu)勢是不是就沒有那么明顯了？這里需要明確的是，set 中會存儲每個元素的內(nèi)容，而布隆過濾器僅僅存儲元素的指紋。元素的內(nèi)容大小就是字符串的長度，它一般會有多個字節(jié)，甚至是幾十個上百個字節(jié)，每個元素本身還需要一個指針被 set 集合來引用，這個指針又會占去 4 個字節(jié)或 8 個字節(jié)，取決于系統(tǒng)是 32bit 還是 64bit。而指紋空間只有接近 2 個字節(jié)，所以布隆過濾器的空間優(yōu)勢還是非常明顯的。

如果讀者覺得公式計算起來太麻煩，也沒有關系，有很多現(xiàn)成的網(wǎng)站已經(jīng)支持計算空間占用的功能了，我們只要把參數(shù)輸進去，就可以直接看到結果，比如 布隆計算器。(Bloom Filter Calculator (krisives.github.io))

六、實際元素超出時，誤判率會怎樣變化

當實際元素超出預計元素時，錯誤率會有多大變化，它會急劇上升么，還是平緩地上升，這就需要另外一個公式，引入?yún)?shù) t 表示實際元素和預計元素的倍數(shù) t

• f=(1-0.5^t)k # 極限近似，k 是 hash 函數(shù)的最佳數(shù)量

當 t 增大時，錯誤率，f 也會跟著增大，分別選擇錯誤率為 10%,1%,0.1% 的 k 值，畫出它的曲線進行直觀觀察。

從這個圖中可以看出曲線還是比較陡峭的

1. 錯誤率為 10% 時，倍數(shù)比為 2 時，錯誤率就會升至接近 40%，這個就比較危險了
2. 錯誤率為 1% 時，倍數(shù)比為 2 時，錯誤率升至 15%，也挺可怕的
3. 錯誤率為 0.1%，倍數(shù)比為 2 時，錯誤率升至 5%，也比較懸了

得出結論：使用時不要讓實際元素遠大于初始化大小，當實際元素開始超出初始化大小時，應該對布隆過濾器進行重建，重新分配一個 size 更大的過濾器，再將所有的歷史元素批量 add 進去 (這就要求我們在其它的存儲器中記錄所有的歷史元素)。因為 error_rate 不會因為數(shù)量超出就急劇增加，這就給我們重建過濾器提供了較為寬松的時間。

七、布隆過濾器實現(xiàn)方式

1、手動硬編碼實現(xiàn)

public class MyBloomFilter {
    /**
     * 位數(shù)組大小 33554432
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過這個數(shù)組創(chuàng)建多個Hash函數(shù)
     */
    private static final int[] SEEDS = new int[]{6, 18, 64, 89, 126, 189, 223};
    /**
     * 初始化位數(shù)組，數(shù)組中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    /**
     * Hash函數(shù)數(shù)組
     */
    private MyHash[] myHashes = new MyHash[SEEDS.length];
    /**
     * 初始化多個包含 Hash 函數(shù)的類數(shù)組，每個類中的 Hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個不同的 Hash 函數(shù)
        for (int i = 0; i < SEEDS.length; i++) {
            myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }
    /**
     * 添加元素到位數(shù)組
     */
    public void add(Object value) {
        for (MyHash myHash : myHashes) {
            bits.set(myHash.hash(value), true);
        }
    }
    /**
     * 判斷指定元素是否存在于位數(shù)組
     */
    public boolean contains(Object value) {
        boolean result = true;
        for (MyHash myHash : myHashes) {
            result = result && bits.get(myHash.hash(value));
        }
        return result;
    }
    /**
     * 自定義 Hash 函數(shù)
     */
    private class MyHash {
        private int cap;
        private int seed;
        MyHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }
        /**
         * 計算 Hash 值
         */
        int hash(Object obj) {
            return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16)));
        }
    }
    public static void main(String[] args) {
        long capacity = 10000000L;
        System.out.println(2 << 24);
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        //put值進去
        for (long i = 0; i < capacity; i++) {
            myBloomFilter.add(i);
        }
        // 統(tǒng)計誤判次數(shù)
        int count = 0;
        // 我在數(shù)據(jù)范圍之外的數(shù)據(jù)，測試相同量的數(shù)據(jù)，判斷錯誤率是不是符合我們當時設定的錯誤率
        for (long i = capacity; i < capacity * 2; i++) {
            if (myBloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

2、引入 Guava 實現(xiàn)

引入Guava的依賴：

<dependency>
	<groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>32.0.1-jre</version>
</dependency>

代碼實現(xiàn)：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {
    public static void main(String[] args) {
        // 預期插入數(shù)量
        long capacity = 10000L;
        // 錯誤比率
        double errorRate = 0.01;
        //創(chuàng)建BloomFilter對象，需要傳入Funnel對象，預估的元素個數(shù)，錯誤率
        BloomFilter<Long> filter = BloomFilter.create(Funnels.longFunnel(), capacity, errorRate);
        //        BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 10000, 0.0001);
        //put值進去
        for (long i = 0; i < capacity; i++) {
            filter.put(i);
        }
        // 統(tǒng)計誤判次數(shù)
        int count = 0;
        // 我在數(shù)據(jù)范圍之外的數(shù)據(jù)，測試相同量的數(shù)據(jù)，判斷錯誤率是不是符合我們當時設定的錯誤率
        for (long i = capacity; i < capacity * 2; i++) {
            if (filter.mightContain(i)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

輸出結果：

假如數(shù)據(jù)為10000容錯率為0.01，統(tǒng)計出來的誤判個數(shù)是87。

3、引入 hutool 實現(xiàn)

引入hutool 的依賴：

<dependency>
	<groupId>cn.hutool</groupId>
	<artifactId>hutool-all</artifactId>
	<version>5.8.20</version>
</dependency>

代碼實現(xiàn)：

import cn.hutool.bloomfilter.BitMapBloomFilter;
public class HutoolBloomFilter {
    public static void main(String[] args) {
        // 一旦數(shù)量過大很容易出現(xiàn)內(nèi)存異常：Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        int capacity = 1000;
        // 初始化
        BitMapBloomFilter filter = new BitMapBloomFilter(capacity);
        for (int i = 0; i < capacity; i++) {
            filter.add(String.valueOf(i));
        }
        System.out.println("存入元素為=={" + capacity + "}");
        // 統(tǒng)計誤判次數(shù)
        int count = 0;
        // 我在數(shù)據(jù)范圍之外的數(shù)據(jù)，測試相同量的數(shù)據(jù)，判斷錯誤率是不是符合我們當時設定的錯誤率
        for (int i = capacity; i < capacity * 2; i++) {
            if (filter.contains(String.valueOf(i))) {
                count++;
            }
        }
        System.out.println("誤判元素為=={" + count + "}");
    }
}

hutool 的布隆過濾器不支持 指定 錯誤比率，并且內(nèi)存占用太高了，個人不建議使用。

4、通過redis實現(xiàn)布隆過濾器

Redis實現(xiàn)布隆過濾器的代碼詳解_Redis_腳本之家 (jb51.net)

八、使用建議

比起容錯率RedisBloom還是夠可以的。 10000的長度0.01的容錯，只有58個誤判！比Guava 還要強，并且Guava 他并沒有做持久化。

以上就是Java實現(xiàn)布隆過濾器的幾種方式總結的詳細內(nèi)容，更多關于Java實現(xiàn)布隆過濾器的資料請關注腳本之家其它相關文章！

最新評論