摘要：介紹布隆過濾器在上的介紹布隆過濾器是年由布隆提出的。通過介紹已經知曉布隆過濾器的作用是檢索一個元素是否在集合中。控制布隆過濾器的誤判率如果集合的大小相比于輸入對象的個數過小，失誤率就會變高。

布隆過濾器在wiki上的介紹:

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難

事實上，布隆過濾器被廣泛用于網頁黑名單系統、垃圾郵件過濾系統、爬蟲的網址判重系統以及解決緩存穿透問題。通過介紹已經知曉布隆過濾器的作用是檢索一個元素是否在集合中。可能有人認為這個功能非常簡單，直接放在redis中或者數據庫中查詢就好了。又或者當數據量較小，內存又足夠大時，使用hashMap或者hashSet等結構就好了。但是如果當這些數據量很大，數十億甚至更多，內存裝不下且數據庫檢索又極慢的情況，我們應該如何去處理？這個時候我們不妨考慮下布隆過濾器，因為它是一個空間效率占用極少和查詢時間極快的算法，但是需要業務可以忍受一個判斷失誤率。

布隆過濾器離不開哈希函數，所以在這里有必要介紹下哈希函數的概念，如果你已經掌握了，可以直接跳到下一小節。
哈希函數的性質:

經典的哈希函數都有無限大的輸入值域(無窮大)。

經典的哈希函數的輸出域都是固定的范圍(有窮大，假設輸出域為S)

當給哈希函數傳入相同的值時，返回值必一樣

當給哈希函數傳入不同的輸入值時，返回值可能一樣，也可能不一樣。

輸入值會盡可能均勻的分布在S上

前三點都是哈希函數的基礎，第四點描述了哈希函數存在哈希碰撞的現象，因為輸入域無限大，輸出域有窮大，這是必然的，輸入域中會有不同的值對應到輸入域S中。第五點事評價一個哈希函數優劣的關鍵，哈希函數越優秀，分布就越均勻且與輸入值出現的規律無關。比如存在"hash1","hash2","hash3"三個輸入值比較類似，經過哈希函數計算后的結果應該相差非常大，可以通過常見的MD5和SHA1算法來驗證這些特性。如果一個優秀的函數能夠做到不同的輸入值所得到的返回值可以均勻的分布在S中，將其返回值對m取余(%m),得到的返回值可以認為也會均勻的分布在0~m-1位置上。

在大多應用中，當業務系統中發送一個請求時，會先從緩存中查詢；若緩存中存在，則直接返回；若返回中不存在，則查詢數據庫。其流程如下圖所示:

緩存穿透：當請求數據庫中不存在的數據，這時候所有的請求都會打到數據庫上，這種情況就是緩存穿透。如果當請求較多的話，這將會嚴重浪費數據庫資源甚至導致數據庫假死。

接下來開始介紹布隆過濾器。有一個長度為m的bit型數組，如我們所知，每個位置只占一個bit，每個位置只有0和1兩種狀態。假設一共有k個哈希函數相互獨立，輸入域都為s且都大于等于m，那么對同一個輸入對象（可以想象為緩存中的一個key），經過k個哈希函數計算出來的結果也都是獨立的。對算出來的每一個結果都對m取余，然后在bit數組上把相應的位置設置為1(描黑)，如下圖所示：

至此一個輸入對象對bit array集合的影響過程就結束了，我們可以看到會有多個位置被描黑，也就是設置為1.接下來所有的輸入對象都按照這種方式去描黑數組，最終一個布隆過濾器就生成了，它代表了所有輸入對象組成的集合。
那么如何判斷一個對象是否在過濾器中呢？假設一個輸入對象為hash1,我們需要通過看k個哈希函數算出k個值，然后把k個值取余（%m），就得到了k個[0,m-1]的值。然后我們判斷bit array上這k個值是否都為黑，如果有一個不為黑，那么肯定hash1肯定不在這個集合里。如果都為黑，則說明hash1在集合里，但有可能誤判。因為當輸入對象過多，而集合過小，會導致集合中大多位置都會被描黑，那么在檢查hash1時，有可能hash1對應的k個位置正好被描黑了，然后錯誤的認為hash1存在集合里。

如果bit array集合的大小m相比于輸入對象的個數過小，失誤率就會變高。這里直接引入一個已經得到證明的公式，根據輸入對象數量n和我們想要達到的誤判率為p計算出布隆過濾器的大小m和哈希函數的個數k.
布隆過濾器的大小m公式:

哈希函數的個數k公式:

布隆過濾器真實失誤率p公式：

假設我們的緩存系統，key為userId，value為user。如果我們有10億個用戶，規定失誤率不能超過0.01%，通過計算器計算可得m=19.17n，向上取整為20n，也就是需要200億個bit，換算之后所需內存大小就是2.3G。通過第二個公式可計算出所需哈希函數k=14.因為在計算m的時候用了向上取整，所以真是的誤判率絕對小于等于0.01%。

關于布隆過濾器，我們不需要自己實現，谷歌已經幫我們實現好了。

pom引入依賴

    com.google.guava
    guava
    25.1-jre

核心api

/**
   * Creates a {@link BloomFilter BloomFilter} with the expected number of
   * insertions and expected false positive probability.
   *
   * 
Note that overflowing a {@code BloomFilter} with significantly more elements
   * than specified, will result in its saturation, and a sharp deterioration of its
   * false positive probability.
   *
   * 
The constructed {@code BloomFilter} will be serializable if the provided
   * {@code Funnel} is.
   *
   * 
It is recommended that the funnel be implemented as a Java enum. This has the
   * benefit of ensuring proper serialization and deserialization, which is important
   * since {@link #equals} also relies on object identity of funnels.
   *
   * @param funnel the funnel of T"s that the constructed {@code BloomFilter} will use
   * @param expectedInsertions the number of expected insertions to the constructed
   *     {@code BloomFilter}; must be positive
   * @param fpp the desired false positive probability (must be positive and less than 1.0)
   * @return a {@code BloomFilter}
   */
  public static  BloomFilter create(
      Funnel funnel, int expectedInsertions /* n */, double fpp) {
    checkNotNull(funnel);
    checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0",
        expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    /*
     * TODO(user): Put a warning in the javadoc about tiny fpp values,
     * since the resulting size is proportional to -log(p), but there is not
     * much of a point after all, e.g. optimalM(1000, 0.0000000000000001) = 76680
     * which is less than 10kb. Who cares!
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel,
          BloomFilterStrategies.MURMUR128_MITZ_32);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

/**
   * Returns {@code true} if the element might have been put in this Bloom filter,
   * {@code false} if this is definitely not the case.
   */
  public boolean mightContain(T object) {
    return strategy.mightContain(object, funnel, numHashFunctions, bits);
  }

一個小例子

public static void main(String... args){
        /**
         * 創建一個插入對象為一億，誤報率為0.01%的布隆過濾器
         */
        BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);
        bloomFilter.put("121");
        bloomFilter.put("122");
        bloomFilter.put("123");
        System.out.println(bloomFilter.mightContain("121"));
    }