布隆過濾器，這一篇給你講的明明白白

什麼是 BloomFilter

布隆過濾器（英語：Bloom Filter）是 1970 年由布隆提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。主要用于判斷一個元素是否在一個集合中。

通常我們會遇到很多要判斷一個元素是否在某個集合中的業務場景，一般想到的是将集合中所有元素儲存起來，然後通過比較确定。連結清單、樹、散清單（又叫哈希表，Hash table）等等資料結構都是這種思路。但是随着集合中元素的增加，我們需要的存儲空間也會呈現線性增長，最終達到瓶頸。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分别為$O(n)$，$O(logn)$，$O(1)$。

這個時候，布隆過濾器（Bloom Filter）就應運而生。

布隆過濾器原理

了解布隆過濾器原理之前，先回顧下 Hash 函數原理。

哈希函數

哈希函數的概念是：将任意大小的輸入資料轉換成特定大小的輸出資料的函數，轉換後的資料稱為哈希值或哈希編碼，也叫散列值。下面是一幅示意圖：

所有散列函數都有如下基本特性：

如果兩個散列值是不相同的（根據同一函數），那麼這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有确定性的結果，具有這種性質的散列函數稱為單向散列函數。
散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同，這種情況稱為“散列碰撞（collision）”。

但是用 hash表存儲大資料量時，空間效率還是很低，當隻有一個 hash 函數時，還很容易發生哈希碰撞。

布隆過濾器資料結構

BloomFilter 是由一個固定大小的二進制向量或者位圖（bitmap）和一系列映射函數組成的。

在初始狀态時，對于長度為 m 的位數組，它的所有位都被置為0，如下圖所示：

當有變量被加入集合時，通過 K 個映射函數将這個變量映射成位圖中的 K 個點，把它們置為 1（假定有兩個變量都通過 3 個映射函數）。

查詢某個變量的時候我們隻要看看這些點是不是都是 1 就可以大機率知道集合中有沒有它了

如果這些點有任何一個 0，則被查詢變量一定不在；
如果都是 1，則被查詢變量很可能存在

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的。

誤判率

布隆過濾器的誤判是指多個輸入經過哈希之後在相同的bit位置1了，這樣就無法判斷究竟是哪個輸入産生的，是以誤判的根源在于相同的 bit 位被多次映射且置 1。

這種情況也造成了布隆過濾器的删除問題，因為布隆過濾器的每一個 bit 并不是獨占的，很有可能多個元素共享了某一位。如果我們直接删除這一位的話，會影響其他的元素。(比如上圖中的第 3 位)

特性

一個元素如果判斷結果為存在的時候元素不一定存在，但是判斷結果為不存在的時候則一定不存在。
布隆過濾器可以添加元素，但是不能删除元素。因為删掉元素會導緻誤判率增加。

添加與查詢元素步驟

添加元素

将要添加的元素給 k 個哈希函數
得到對應于位數組上的 k 個位置
将這k個位置設為 1

查詢元素

将要查詢的元素給k個哈希函數
得到對應于位數組上的k個位置
如果k個位置有一個為 0，則肯定不在集合中
如果k個位置全部為 1，則可能在集合中

優點

相比于其它的資料結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數 $O(K)$，另外，散列函數互相之間沒有關系，友善由硬體并行實作。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集，其它任何資料結構都不能；

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。随着存入的元素數量增加，誤算率随之增加。但是如果元素數量太少，則使用散清單足矣。

另外，一般情況下不能從布隆過濾器中删除元素。我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加 1, 這樣删除元素時将計數器減掉就可以了。然而要保證安全地删除元素并非如此簡單。首先我們必須保證删除的元素的确在布隆過濾器裡面。這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

在降低誤算率方面，有不少工作，使得出現了很多布隆過濾器的變種。

布隆過濾器使用場景和執行個體

在程式的世界中，布隆過濾器是程式員的一把利器，利用它可以快速地解決項目中一些比較棘手的問題。

如網頁 URL 去重、垃圾郵件識别、大集合中重複元素的判斷和緩存穿透等問題。

布隆過濾器的典型應用有：

資料庫防止穿庫。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter來減少不存在的行或列的磁盤查找。避免代價高昂的磁盤查找會大大提高資料庫查詢操作的性能。
業務場景中判斷使用者是否閱讀過某視訊或文章，比如抖音或頭條，當然會導緻一定的誤判，但不會讓使用者看到重複的内容。
緩存當機、緩存擊穿場景，一般判斷使用者是否在緩存中，如果在則直接傳回結果，不在則查詢db，如果來一波冷資料，會導緻緩存大量擊穿，造成雪崩效應，這時候可以用布隆過濾器當緩存的索引，隻有在布隆過濾器中，才去查詢緩存，如果沒查詢到，則穿透到db。如果不在布隆器中，則直接傳回。
WEB攔截器，如果相同請求則攔截，防止重複被攻擊。使用者第一次請求，将請求參數放入布隆過濾器中，當第二次請求時，先判斷請求參數是否被布隆過濾器命中。可以提高緩存命中率。Squid 網頁代理緩存伺服器在 cache digests 中就使用了布隆過濾器。Google Chrome浏覽器使用了布隆過濾器加速安全浏覽服務
Venti 文檔存儲系統也采用布隆過濾器來檢測先前存儲的資料。
SPIN 模型檢測器也使用布隆過濾器在大規模驗證問題時跟蹤可達狀态空間。

Coding~

知道了布隆過濾去的原理和使用場景，我們可以自己實作一個簡單的布隆過濾器

自定義的 BloomFilter

public class MyBloomFilter {

    /**
     * 一個長度為10 億的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;

    /**
     * 為了降低錯誤率，使用加法hash算法，是以定義一個8個元素的質數數組
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    /**
     * 相當于建構 8 個不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**
     * 初始化布隆過濾器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);

    /**
     * 添加資料
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //計算 hash 值并修改 bitmap 中相應位置為 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判斷相應元素是否存在
     * @param value 需要判斷的元素
     * @return 結果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一個 hash 函數傳回 false 則跳出循環
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    /**
     * 模拟使用者是不是會員，或使用者在不線上。。。
     */
    public static void main(String[] args) {

        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }

        // 添加1億資料
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);

        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}

class HashFunction {

    private int size;
    private int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

What？我們寫的這些早有大牛幫我們實作，還造輪子，真是浪費時間，No，No，No，我們學習過程中是可以造輪子的，造輪子本身就是我們自己對設計和實作的具體落地過程，不僅能提高我們的程式設計能力，在造輪子的過程中肯定會遇到很多我們沒有思考過的問題，成長看的見~~

實際項目使用的時候，上司和我說項目一定要穩定運作，沒自信的我放棄了自己的輪子。

Guava 中的 BloomFilter

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

public class GuavaBloomFilterDemo {

    public static void main(String[] args) {
        //後邊兩個參數：預計包含的資料量，和允許的誤內插補點
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
        for (int i = 0; i < 100000; i++) {
            bloomFilter.put(i);
        }
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(100001));

        //bloomFilter.writeTo();
    }
}

分布式環境中，布隆過濾器肯定還需要考慮是可以共享的資源，這時候我們會想到 Redis，是的，Redis 也實作了布隆過濾器。

當然我們也可以把布隆過濾器通過

bloomFilter.writeTo()

寫入一個檔案，放入OSS、S3這類對象存儲中。

Redis 中的 BloomFilter

Redis 提供的 bitMap 可以實作布隆過濾器，但是需要自己設計映射函數和一些細節，這和我們自定義沒啥差別。

Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之後才正式登場。布隆過濾器作為一個插件加載到 Redis Server 中，給 Redis 提供了強大的布隆去重功能。

在已安裝 Redis 的前提下，安裝 RedisBloom，有兩種方式

直接編譯進行安裝

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make     #編譯 會生成一個rebloom.so檔案
redis-server --loadmodule /path/to/rebloom.so   #運作redis時加載布隆過濾器子產品
redis-cli    # 啟動連接配接容器中的 redis 用戶端驗證

使用Docker進行安裝

docker pull redislabs/rebloom:latest # 拉取鏡像
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest #運作容器
docker exec -it redis-redisbloom bash
redis-cli

使用

布隆過濾器基本指令：

bf.add 添加元素到布隆過濾器
bf.exists 判斷元素是否在布隆過濾器
bf.madd 添加多個元素到布隆過濾器，bf.add 隻能添加一個
bf.mexists 判斷多個元素是否在布隆過濾器

127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.add user John
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Linda
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0

我們隻有這幾個參數，肯定不會有誤判，當元素逐漸增多時，就會有一定的誤判了，這裡就不做這個實驗了。

上面使用的布隆過濾器隻是預設參數的布隆過濾器，它在我們第一次 add 的時候自動建立。

Redis 還提供了自定義參數的布隆過濾器，

bf.reserve 過濾器名 error_rate initial_size

error_rate：允許布隆過濾器的錯誤率，這個值越低過濾器的位數組的大小越大，占用空間也就越大
initial_size：布隆過濾器可以儲存的元素個數，當實際存儲的元素個數超過這個值之後，過濾器的準确率會下降

但是這個操作需要在 add 之前顯式建立。如果對應的 key 已經存在，bf.reserve 會報錯

127.0.0.1:6379> bf.reserve user 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve topic 0.01 1000
OK

我是一名 Javaer，肯定還要用 Java 來實作的，Java 的 Redis 用戶端比較多，有些還沒有提供指令擴充機制，筆者已知的 Redisson 和 lettuce 是可以使用布隆過濾器的，我們這裡用

Redisson

public class RedissonBloomFilterDemo {

    public static void main(String[] args) {

        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
        // 初始化布隆過濾器，預計統計元素數量為55000000，期望誤差率為0.03
        bloomFilter.tryInit(55000000L, 0.03);
        bloomFilter.add("Tom");
        bloomFilter.add("Jack");
        System.out.println(bloomFilter.count());   //2
        System.out.println(bloomFilter.contains("Tom"));  //true
        System.out.println(bloomFilter.contains("Linda"));  //false
    }
}

擴充

為了解決布隆過濾器不能删除元素的問題，布谷鳥過濾器橫空出世。論文《Cuckoo Filter：Better Than Bloom》作者将布谷鳥過濾器和布隆過濾器進行了深入的對比。相比布谷鳥過濾器而言布隆過濾器有以下不足：查詢性能弱、空間利用效率低、不支援反向操作（删除）以及不支援計數。

由于使用較少，暫不深入。

文章持續更新，可以微信搜「 JavaKeeper 」第一時間閱讀，無套路領取 500+ 本電子書和 30+ 視訊教學和源碼，本文 GitHub github.com/JavaKeeper 已經收錄，Javaer 開發、面試必備技能兵器譜，有你想要的。

參考與感謝

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf http://www.justdojava.com/2019/10/22/bloomfilter/ https://www.cnblogs.com/cpselvis/p/6265825.html https://juejin.im/post/5cc5aa7ce51d456e431adac5

布隆過濾器，這一篇給你講的明明白白

什麼是 BloomFilter

布隆過濾器原理

哈希函數

布隆過濾器資料結構

誤判率

特性

添加與查詢元素步驟

添加元素

查詢元素

優點

缺點

布隆過濾器使用場景和執行個體

Coding~

自定義的 BloomFilter

Guava 中的 BloomFilter

Redis 中的 BloomFilter

擴充

參考與感謝

繼續閱讀

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

CentOS 7,docker安裝

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

【Docker】端口映射問題操作步驟

登入plsql 報錯 the account is locked --使用者被鎖

Effective Java 8:通用程式設計

SequoiaDB巨杉資料庫C++驅動概述

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希