一、前言

講個(gè)使用場(chǎng)景，比如我們?cè)谑褂眯侣効蛻舳丝葱侣剷r(shí)，它會(huì)給我們不停地推薦新的內(nèi)容，它每次推薦時(shí)要去重，去掉那些已經(jīng)看過的內(nèi)容。問題來(lái)了，新聞客戶端推薦系統(tǒng)如何實(shí)現(xiàn)推送去重的？

1. 你會(huì)想到服務(wù)器記錄了用戶看過的所有歷史記錄，當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行篩選，過濾掉那些已經(jīng)存在的記錄。問題是當(dāng)用戶量很大，每個(gè)用戶看過的新聞?dòng)趾芏嗟那闆r下，這種方式，推薦系統(tǒng)的去重工作在性能上跟的上么？

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

2. 你可能又想到了緩存，但是如此多的歷史記錄全部緩存起來(lái)，那得浪費(fèi)多大存儲(chǔ)空間?。慷疫@個(gè)存儲(chǔ)空間是隨著時(shí)間線性增長(zhǎng)，你撐得住一個(gè)月，你能撐得住幾年么？但是不緩存的話，性能又跟不上，這該怎么辦？

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

二、什么是布隆過濾器？

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

三、布隆過濾器原理

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

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

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

如下圖所示，兩個(gè)不同的值，經(jīng)過相同的哈希運(yùn)算后，可能會(huì)得出同樣的值。即下圖中，hello和你好 經(jīng)過哈希運(yùn)算后，得出的下標(biāo)都為2，把位2上的值改為1。所以，無(wú)法判斷位2上的值為1是誰(shuí)的值。

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

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

優(yōu)點(diǎn)：

• 占用空間小，因?yàn)樗遣淮鎯?chǔ)實(shí)際數(shù)據(jù)的。
• 保密性非常好，不存儲(chǔ)原始數(shù)據(jù)，別人也不知道0和1是什么。
• 他底層是基于位數(shù)組的，基于數(shù)組的特性查詢和插入是非?？斓摹?/li>

缺點(diǎn)：

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

四、布隆過濾器使用場(chǎng)景

綜上，我們可以得出：布隆過濾器可以判斷指定的元素一定不存在或者可能存在！ 打個(gè)比方，當(dāng)它說(shuō)不認(rèn)識(shí)你時(shí)，肯定就不認(rèn)識(shí)；當(dāng)它說(shuō)見過你時(shí)，可能根本就沒見過面，不過因?yàn)槟愕哪樃J(rèn)識(shí)的人中某臉比較相似 (某些熟臉的系數(shù)組合)，所以誤判以前見過你。

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

一般有如下幾種使用場(chǎng)景：

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

五、空間占用估計(jì)

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

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

從公式中可以看出

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

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

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

六、實(shí)際元素超出時(shí)，誤判率會(huì)怎樣變化

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

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

當(dāng) t 增大時(shí)，錯(cuò)誤率，f 也會(huì)跟著增大，分別選擇錯(cuò)誤率為 10%,1%,0.1% 的 k 值，畫出它的曲線進(jìn)行直觀觀察。

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

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

得出結(jié)論：使用時(shí)不要讓實(shí)際元素遠(yuǎn)大于初始化大小，當(dāng)實(shí)際元素開始超出初始化大小時(shí)，應(yīng)該對(duì)布隆過濾器進(jìn)行重建，重新分配一個(gè) size 更大的過濾器，再將所有的歷史元素批量 add 進(jìn)去 (這就要求我們?cè)谄渌拇鎯?chǔ)器中記錄所有的歷史元素)。因?yàn)?error_rate 不會(huì)因?yàn)閿?shù)量超出就急劇增加，這就給我們重建過濾器提供了較為寬松的時(shí)間。

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

1、手動(dòng)硬編碼實(shí)現(xiàn)

public class MyBloomFilter {
    /**
     * 位數(shù)組大小 33554432
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過這個(gè)數(shù)組創(chuàng)建多個(gè)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];
    /**
     * 初始化多個(gè)包含 Hash 函數(shù)的類數(shù)組，每個(gè)類中的 Hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個(gè)不同的 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;
        }
        /**
         * 計(jì)算 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值進(jìn)去
        for (long i = 0; i < capacity; i++) {
            myBloomFilter.add(i);
        }
        // 統(tǒng)計(jì)誤判次數(shù)
        int count = 0;
        // 我在數(shù)據(jù)范圍之外的數(shù)據(jù)，測(cè)試相同量的數(shù)據(jù)，判斷錯(cuò)誤率是不是符合我們當(dāng)時(shí)設(shè)定的錯(cuò)誤率
        for (long i = capacity; i < capacity * 2; i++) {
            if (myBloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

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

引入Guava的依賴：

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

代碼實(shí)現(xiàn)：

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

輸出結(jié)果：

假如數(shù)據(jù)為10000容錯(cuò)率為0.01，統(tǒng)計(jì)出來(lái)的誤判個(gè)數(shù)是87。

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

引入hutool 的依賴：

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

代碼實(shí)現(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)計(jì)誤判次數(shù)
        int count = 0;
        // 我在數(shù)據(jù)范圍之外的數(shù)據(jù)，測(cè)試相同量的數(shù)據(jù)，判斷錯(cuò)誤率是不是符合我們當(dāng)時(shí)設(shè)定的錯(cuò)誤率
        for (int i = capacity; i < capacity * 2; i++) {
            if (filter.contains(String.valueOf(i))) {
                count++;
            }
        }
        System.out.println("誤判元素為=={" + count + "}");
    }
}

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

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

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

八、使用建議

比起容錯(cuò)率RedisBloom還是夠可以的。 10000的長(zhǎng)度0.01的容錯(cuò)，只有58個(gè)誤判！比Guava 還要強(qiáng)，并且Guava 他并沒有做持久化。

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

最新評(píng)論