到底是存在還是不存在之 BloomFilter

01、什麼是 BloomFilter（布隆過濾器）

1.1、BloomFilter 原理

BloomFilter 是由一個固定大小的二進制向量或者位圖（bitmap）和一系列（通常好幾個）映射函數組成的。布隆過濾器的原理是，當一個變量被加入集合時，通過 K 個映射函數將這個變量映射成位圖中的 K 個點，把它們置為 1。查詢某個變量的時候我們只要看看這些點是不是都是 1 就可以大概率知道集合中有沒有它了，如果這些點有任何一個 0，則被查詢變量一定不在；如果都是 1，則被查詢變量很可能在。注意，這裡是可能存在，不一定一定存在！這就是布隆過濾器的基本思想。

如下圖所示，字符串 “ziyou” 在經過四個映射函數操作後在位圖上有四個點被設置成了 1。當我們需要判斷 “ziyou” 字符串是否存在的時候只要在一次對字符串進行映射函數的操作，得到四個 1 就說明 “ziyou” 是可能存在的。

為什麼說是可能存在，而不是一定存在呢？那是因為映射函數本身就是散列函數，散列函數是會有碰撞的，意思也就是說會存在一個字符串可能是 “ziyou01” 經過相同的四個映射函數運算得到的四個點跟 “ziyou” 是一樣的，這種情況下我們就說出現了誤算。另外還有可能這四個點位上的 1 是四個不同的變量經過運算後得到的，這也不能證明字符串 “ziyou” 是一定存在的，如下圖框出來的 1 也可能是字符串“張三”計算得到，同理其他幾個位置的 1 也可以是其他字符串計算得到。

1.2 特性

所以通過上面的例子我們就可以明確

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

02、使用場景

2.1、網頁 URL 去重

我們在使用網頁爬蟲的時候（爬蟲需謹慎），往往需要記錄哪些 URL 是已經爬取過的，哪些還是沒有爬取過，這個時候我們就可以採用 BloomFilter 來對已經爬取過的 URL 進行存儲，這樣在進行下一次爬取的時候就可以判斷出這個 URL 是否爬取過。

2.2、黑白名單存儲

工作中經常會有一個特性針對不同的設備或者用戶有不同的處理方式，這個時候可能會有白名單或者黑名單存在，所以根據 BloomFilter 過濾器的特性，我們也可以用它來存在這些數據，雖然有一定的誤算率，但是在一定程度上還是可以很好的解決這個問題的。

2.3、小結

除了上面說的兩種場景，其實還有很多場景，比如熱點數據訪問，垃圾郵件過濾等等，其實這些場景的統一特性就是要判斷某個元素是否在某個集合中，原理都是一樣的。

03、代碼實踐

3.1、自己實現

package com.test.pkg;import java.util.BitSet;/** * 
 * Function：
 * Author：@author ziyou
 * Date：2019-10-23 23:21
 * Desc：無
 */public class BloomFilterTest {    /**     * 初始化布隆過濾器的 bitmap 大小     */    private static final int DEFAULT_SIZE = 2 << 24;    /**     * 為了降低錯誤率，這裡選取一些數字作為基準數     */    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};    /**     * 設置 bitmap     */    private static BitSet bitset = new BitSet(DEFAULT_SIZE);    /**     * 設置 hash 函數數量     */    private static HashFunction[] functions = new HashFunction[seeds.length];    /**     * 添加數據     *     * @param value 需求加入的值     */    public static void put(String value) {        if (value != null) {            for (HashFunction f : functions) {                //計算 hash 值並修改 bitmap 中相應位置為 true                bitset.set(f.hash(value), true);            }        }    }    /**     * 判斷相應元素是否存在     *     * @param value 需要判斷的元素     * @return 結果     */    public static boolean check(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) {        String value = "test";        for (int i = 0; i < seeds.length; i++) {            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);        }        put(value);        System.out.println(check("value"));    }}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;    }}

上面我們自己寫了一個簡單的 BloomFilter ，通過 put 方法錄入數據，通過 check 方法判斷元素是否存在，基本能實現功能，代碼中註釋也寫的很清楚，但是自己實現必定效率不高，所以下面我們看下業內大佬幫我們已經實現好的 BloomFilter。

2.4、Guava 中的 BloomFilter

package com.test.pkg;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;/** * 
 * Function：
 * Author：@author ziyou
 * Date：2019-10-24 00:17
 * Desc：無
 */public class BloomFilterTest02 {    public static void main(String[] args) {        BloomFilter 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));    }}

Guava 中已經幫我們實現好了 BloomFilter 的代碼，我們只需要在使用的地方調用就好。

這裡我們簡單解釋一下構造方法中的後面兩個參數，一個是預計包含的數據量，一個是允許的誤差值。代碼中會根據我們填入的這兩個值，自動幫我們計算出數組的大小，以及需要的散列函數個數，如下圖。更多詳細的內容，讀者可以自行去查看源碼，我們這裡就不介紹了。

04、總結

這篇文章給大家介紹了 BloomFilter，一個用來判斷元素是否存在與某個集合的高效方法，可以在我們日常的工作中運用起來，結合日常工作的場景，可以進行選擇。

閱讀更多 科技伍小黑 的文章

關鍵字: 存在 網絡爬蟲 到底