引言

實際項目中經常存在這樣的場景，即檢查某個元素是否存在於特定的集合

• 集合通過線性結構進行存儲，通過遍歷線性結構在O(n)時間複雜度內獲取結果
• 集合通過K-V結構進行存儲，在O(1)時間複雜度內獲取結果
• .......

沒有完全適合所有場景的解決方案，當把問題升級到海量數據集合規模，上述的簡單依賴內存的處理方式可能就不太適用了，因為我們沒有足夠大的內存容納這些數據。布隆過濾器（Bloom Filter）正是這樣一種精巧的設計，能夠在空間複雜度和時間複雜度方面進行平衡。

布隆過濾器原理剖析

布隆過濾器由布隆（Burton Howard Bloom）在1970年提出，本質上是一個很長的二進制向量和一系列隨機映射函數，核心應用場景是 “檢測一個元素是否在一個集合中”，布隆過濾器具有良好的空間效率和查詢性能。

一個空的布隆過濾器有長度為M比特數組構成，且所有位都初始化0。一個元素Key通過K個不同的hash函數隨機散列到bit數組的K個位置上，K必須遠小於M。K和M的大小由錯誤率（False Positiverate）決定。

• 將特定的Key寫入布隆過濾器

基於選定的K個Hash函數計算出相應的K個哈希值C1~CK，分別對m取模運算獲得哈希值對應的比特數組下標位置，然後將這K個位置的值設為 “1”。

• 在布隆過濾器中檢索特定Key

當我們搜索一個值的時候，若該值經過 K 個哈希函數運算後的任何一個索引位為 ”0“，那麼該值肯定不在集合中。但如果所有哈希索引值均為 ”1“，則只能說該搜索的值可能存在集合中。

特點

從布隆過濾器的特點可以看出，不同的Key經過多個哈希函數計算的哈希值存在完全相同的概率，因此，使用布隆過濾器存在一定的誤判概率：

• 某個Key經過多個Hash運算在bit數組的所有位置都為1，並不能保證該元素一定存在於布隆過濾器
• 某個Key經過多個Hash函數在bit數組的所有位置不全為1，則能保證該元素一定不存在與布隆過濾器

與布隆過濾器相關的幾個參數包括:Bit數組長度、Hash函數個數、存儲的元素個數、誤判率

布隆過濾器的誤判率計算公式如下：

從公式可以看出，誤判率P由m/n/k決定，如果位數組容量m增大，則誤判率p降低，如果存儲的元素n增大，則誤判率p增大。在m和n給定情況下，在最優p的情況下，

經典實用場景

布隆過濾器主要解決“檢查給定元素是否存在”的問題，其應用場景粉刺航道，大家比較熟悉的典型應用場景例如：

1. 爬蟲對海量URL進行去重處理

2. 反垃圾郵件過濾

3. 緩存中用於解決緩存穿透問題

4. Google BigTable、Apache HBbase 和 Apache Cassandra 使用布隆過濾器減少對不存在的行和列的查找

由於布隆過濾器存在一定的誤判率，因此，在使用布隆過濾器時要結合實際的業務場景，對可接受的誤判和布隆過濾器容量有一定的預估，以此設計滿足實際業務需求的布隆過濾器。

布隆過濾器實現

Guava中對BloomFilter的實現源碼如下：

<code>package com.google.common.hash;
public final class BloomFilter implements Predicate, Serializable {
     // 比特數組
    private final BitArray bits;
    // 哈希函數的個數 
    private final int numHashFunctions;
    // The funnel to translate Ts to bytes  

    private final Funnel super T> funnel;
    // 將元素轉化成位數組索引位置的策略接口
    private final Strategy strategy;
    ......

  @VisibleForTesting
  static  BloomFilter create(
      Funnel super T> funnel, int expectedInsertions /* n */, double fpp, Strategy strategy) {
    // ......
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }
}/<code>

<code>// Guava定義的BitArray類
static final class BitArray {
    final long[] data;
    long bitCount;
    ......
}
// Guava中的策略枚舉，支持兩種：MURMUR128_MITZ_32和MURMUR128_MITZ_64
enum BloomFilterStrategies implements BloomFilter.Strategy {
    MURMUR128_MITZ_32() { // 省略
    }
    MURMUR128_MITZ_64(){ // 省略
    }
}/<code>

總結

對於 “元素是否存在於特定集合” 這類問題，布隆過濾器採用了典型的 “空間換時間” 的基本思路，由於其自身設計的特性，在保證了優秀的時間複雜度同時，也覺有非常好的空間複雜度。同時，布隆過濾器存在一定的誤判率，因此，在實際項目中要結合具體的業務場景，對誤判率、元素容量、Hash函數個數、布隆過濾器長度等參數進行平衡，以滿足實際需求。

閱讀更多 瘋狂架構 的文章

關鍵字: 布隆 設計 計算複雜性理論