不了解布隆過濾器联四？一文給你整的明明白白撑碴！

海量數(shù)據(jù)處理以及緩存穿透這兩個場景讓我認(rèn)識了布隆過濾器懦鼠，我查閱了一些資料來了解它钻哩，但是很多現(xiàn)成資料并不滿足我的需求屹堰，所以就決定自己總結(jié)一篇關(guān)于布隆過濾器的文章。希望通過這篇文章讓更多人了解布隆過濾器街氢，并且會實際去使用它扯键！

下面我們將分為幾個方面來介紹布隆過濾器：

什么是布隆過濾器？
布隆過濾器的原理介紹珊肃。
布隆過濾器使用場景荣刑。
通過 Java 編程手動實現(xiàn)布隆過濾器。
利用Google開源的Guava中自帶的布隆過濾器伦乔。
Redis 中的布隆過濾器厉亏。

1.什么是布隆過濾器？

首先烈和，我們需要了解布隆過濾器的概念叶堆。

布隆過濾器（Bloom Filter）是一個叫做 Bloom 的老哥于1970年提出的。我們可以把它看作由二進(jìn)制向量（或者說位數(shù)組）和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結(jié)構(gòu)斥杜。相比于我們平時常用的的 List、Map 沥匈、Set 等數(shù)據(jù)結(jié)構(gòu)蔗喂，它占用空間更少并且效率更高，但是缺點是其返回的結(jié)果是概率性的高帖，而不是非常準(zhǔn)確的缰儿。理論情況下添加到集合中的元素越多，誤報的可能性就越大散址。并且乖阵，存放在布隆過濾器的數(shù)據(jù)不容易刪除。

位數(shù)組中的每個元素都只占用 1 bit 预麸，并且每個元素只能是 0 或者 1瞪浸。這樣申請一個 100w 個元素的位數(shù)組只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。

總結(jié)：一個名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結(jié)構(gòu)吏祸，這種數(shù)據(jù)結(jié)構(gòu)是高效且性能很好的对蒲，但缺點是具有一定的錯誤識別率和刪除難度。并且贡翘，理論情況下蹈矮，添加到集合中的元素越多，誤報的可能性就越大鸣驱。

2.布隆過濾器的原理介紹

當(dāng)一個元素加入布隆過濾器中的時候泛鸟，會進(jìn)行如下操作：

使用布隆過濾器中的哈希函數(shù)對元素值進(jìn)行計算，得到哈希值（有幾個哈希函數(shù)得到幾個哈希值）踊东。
根據(jù)得到的哈希值北滥，在位數(shù)組中把對應(yīng)下標(biāo)的值置為 1刚操。

當(dāng)我們需要判斷一個元素是否存在于布隆過濾器的時候，會進(jìn)行如下操作：

對給定元素再次進(jìn)行相同的哈希計算碑韵；
得到值之后判斷位數(shù)組中的每個元素是否都為 1赡茸，如果值都為 1，那么說明這個值在布隆過濾器中祝闻，如果存在一個值不為 1占卧，說明該元素不在布隆過濾器中。

舉個簡單的例子：

布隆過濾器hash計算

如圖所示联喘，當(dāng)字符串存儲要加入到布隆過濾器中時华蜒，該字符串首先由多個哈希函數(shù)生成不同的哈希值，然后在對應(yīng)的位數(shù)組的下表的元素設(shè)置為 1（當(dāng)位數(shù)組初始化時豁遭，所有位置均為0）叭喜。當(dāng)?shù)诙未鎯ο嗤址畷r，因為先前的對應(yīng)位置已設(shè)置為 1蓖谢，所以很容易知道此值已經(jīng)存在（去重非常方便）捂蕴。

如果我們需要判斷某個字符串是否在布隆過濾器中時，只需要對給定字符串再次進(jìn)行相同的哈希計算闪幽，得到值之后判斷位數(shù)組中的每個元素是否都為 1啥辨，如果值都為 1，那么說明這個值在布隆過濾器中盯腌，如果存在一個值不為 1溉知，說明該元素不在布隆過濾器中。

不同的字符串可能哈希出來的位置相同腕够，這種情況我們可以適當(dāng)增加位數(shù)組大小或者調(diào)整我們的哈希函數(shù)级乍。

綜上，我們可以得出：布隆過濾器說某個元素存在帚湘，小概率會誤判玫荣。布隆過濾器說某個元素不在，那么這個元素一定不在客们。

3.布隆過濾器使用場景

判斷給定數(shù)據(jù)是否存在：比如判斷一個數(shù)字是否存在于包含大量數(shù)字的數(shù)字集中（數(shù)字集很大崇决，5億以上！）底挫、防止緩存穿透（判斷請求的數(shù)據(jù)是否有效避免直接繞過緩存請求數(shù)據(jù)庫）等等恒傻、郵箱的垃圾郵件過濾、黑名單功能等等建邓。
去重：比如爬給定網(wǎng)址的時候?qū)σ呀?jīng)爬取過的 URL 去重盈厘。

4.通過 Java 編程手動實現(xiàn)布隆過濾器

我們上面已經(jīng)說了布隆過濾器的原理，知道了布隆過濾器的原理之后就可以自己手動實現(xiàn)一個了官边。

如果你想要手動實現(xiàn)一個的話沸手，你需要：

一個合適大小的位數(shù)組保存數(shù)據(jù)
幾個不同的哈希函數(shù)
添加元素到位數(shù)組（布隆過濾器）的方法實現(xiàn)
判斷給定元素是否存在于位數(shù)組（布隆過濾器）的方法實現(xiàn)外遇。

下面給出一個我覺得寫的還算不錯的代碼（參考網(wǎng)上已有代碼改進(jìn)得到，對于所有類型對象皆適用）：

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位數(shù)組的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通過這個數(shù)組可以創(chuàng)建 6 個不同的哈希函數(shù)
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位數(shù)組契吉。數(shù)組中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函數(shù)的類的數(shù)組
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多個包含 hash 函數(shù)的類的數(shù)組跳仿，每個類中的 hash 函數(shù)都不一樣
     */
    public MyBloomFilter() {
        // 初始化多個不同的 Hash 函數(shù)
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位數(shù)組
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判斷指定元素是否存在于位數(shù)組
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 靜態(tài)內(nèi)部類。用于 hash 操作捐晶！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 計算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

測試：

        String value1 = "https://javaguide.cn/";
        String value2 = "https://github.com/Snailclimb";
        MyBloomFilter filter = new MyBloomFilter();
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
        filter.add(value1);
        filter.add(value2);
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));

Output:

false
false
true
true

測試：

        Integer value1 = 13423;
        Integer value2 = 22131;
        MyBloomFilter filter = new MyBloomFilter();
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));
        filter.add(value1);
        filter.add(value2);
        System.out.println(filter.contains(value1));
        System.out.println(filter.contains(value2));

Output:

false
false
true
true

5.利用Google開源的 Guava中自帶的布隆過濾器

自己實現(xiàn)的目的主要是為了讓自己搞懂布隆過濾器的原理菲语，Guava 中布隆過濾器的實現(xiàn)算是比較權(quán)威的，所以實際項目中我們不需要手動實現(xiàn)一個布隆過濾器惑灵。

首先我們需要在項目中引入 Guava 的依賴：

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

實際使用如下：

我們創(chuàng)建了一個最多存放最多 1500個整數(shù)的布隆過濾器山上，并且我們可以容忍誤判的概率為百分之（0.01）

        // 創(chuàng)建布隆過濾器對象
        BloomFilter<Integer> filter = BloomFilter.create(
                Funnels.integerFunnel(),
                1500,
                0.01);
        // 判斷指定元素是否存在
        System.out.println(filter.mightContain(1));
        System.out.println(filter.mightContain(2));
        // 將元素添加進(jìn)布隆過濾器
        filter.put(1);
        filter.put(2);
        System.out.println(filter.mightContain(1));
        System.out.println(filter.mightContain(2));

在我們的示例中，當(dāng)mightContain（） 方法返回true時英支，我們可以99％確定該元素在過濾器中佩憾，當(dāng)過濾器返回false時，我們可以100％確定該元素不存在于過濾器中干花。

Guava 提供的布隆過濾器的實現(xiàn)還是很不錯的（想要詳細(xì)了解的可以看一下它的源碼實現(xiàn)）妄帘，但是它有一個重大的缺陷就是只能單機(jī)使用（另外，容量擴(kuò)展也不容易）池凄，而現(xiàn)在互聯(lián)網(wǎng)一般都是分布式的場景寄摆。為了解決這個問題，我們就需要用到 Redis 中的布隆過濾器了修赞。

6.Redis 中的布隆過濾器

6.1介紹

Redis v4.0 之后有了 Module（模塊/插件）功能，Redis Modules 讓 Redis 可以使用外部模塊擴(kuò)展其功能桑阶。布隆過濾器就是其中的 Module柏副。詳情可以查看 Redis 官方對 Redis Modules 的介紹：https://redis.io/modules

另外，官網(wǎng)推薦了一個 RedisBloom 作為 Redis 布隆過濾器的 Module,地址：https://github.com/RedisBloom/RedisBloom. 其他還有：

redis-lua-scaling-bloom-filter （lua 腳本實現(xiàn)）：https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
pyreBloom（Python中的快速Redis 布隆過濾器）：https://github.com/seomoz/pyreBloom
《2020最新Java基礎(chǔ)精講視頻教程和學(xué)習(xí)路線蚣录！》
......

RedisBloom 提供了多種語言的客戶端支持割择，包括：Python、Java萎河、JavaScript 和 PHP荔泳。

6.2使用Docker安裝

如果我們需要體驗 Redis 中的布隆過濾器非常簡單，通過 Docker 就可以了虐杯！我們直接在 Google 搜索docker redis bloomfilter 然后在排除廣告的第一條搜素結(jié)果就找到了我們想要的答案（這是我平常解決問題的一種方式玛歌，分享一下），具體地址：https://hub.docker.com/r/redislabs/rebloom/ （介紹的很詳細(xì) ）擎椰。

具體操作如下：

?  ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
?  ~ docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>

6.3常用命令一覽

注意： key:布隆過濾器的名稱支子，item : 添加的元素。

BF.ADD：將元素添加到布隆過濾器中达舒，如果該過濾器尚不存在值朋，則創(chuàng)建該過濾器叹侄。格式：BF.ADD {key} {item}。
BF.MADD: 將一個或多個元素添加到“布隆過濾器”中昨登，并創(chuàng)建一個尚不存在的過濾器趾代。該命令的操作方式BF.ADD與之相同，只不過它允許多個輸入并返回多個值丰辣。格式：BF.MADD {key} {item} [item ...] 撒强。
**BF.EXISTS ** : 確定元素是否在布隆過濾器中存在。格式：BF.EXISTS {key} {item}糯俗。
BF.MEXISTS ：確定一個或者多個元素是否在布隆過濾器中存在格式：BF.MEXISTS {key} {item} [item ...]尿褪。

另外，BF.RESERVE 命令需要單獨介紹一下：

這個命令的格式如下：

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion]得湘。

下面簡單介紹一下每個參數(shù)的具體含義：

key：布隆過濾器的名稱
error_rate :誤報的期望概率杖玲。這應(yīng)該是介于0到1之間的十進(jìn)制值。例如淘正，對于期望的誤報率0.1％（1000中為1）摆马，error_rate應(yīng)該設(shè)置為0.001。該數(shù)字越接近零鸿吆，則每個項目的內(nèi)存消耗越大囤采，并且每個操作的CPU使用率越高。
capacity: 過濾器的容量惩淳。當(dāng)實際存儲的元素個數(shù)超過這個值之后蕉毯，性能將開始下降。實際的降級將取決于超出限制的程度思犁。隨著過濾器元素數(shù)量呈指數(shù)增長代虾，性能將線性下降。

可選參數(shù)：

expansion：如果創(chuàng)建了一個新的子過濾器激蹲，則其大小將是當(dāng)前過濾器的大小乘以expansion棉磨。默認(rèn)擴(kuò)展值為2。這意味著每個后續(xù)子過濾器將是前一個子過濾器的兩倍学辱。

6.4實際使用

127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0

作者：Snailclimb
鏈接：不了解布隆過濾器乘瓤？一文給你整的明明白白！
來源：github

不了解布隆過濾器？一文給你整的明明白白鹿霸！

不了解布隆過濾器排吴？一文給你整的明明白白！