摘要：介紹布隆過濾器在上的介紹布隆過濾器是年由布隆提出的。通過介紹已經(jīng)知曉布隆過濾器的作用是檢索一個元素是否在集合中?？刂撇悸∵^濾器的誤判率如果集合的大小相比于輸入對象的個數(shù)過小，失誤率就會變高。

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

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

事實(shí)上，布隆過濾器被廣泛用于網(wǎng)頁黑名單系統(tǒng)、垃圾郵件過濾系統(tǒng)、爬蟲的網(wǎng)址判重系統(tǒng)以及解決緩存穿透問題。通過介紹已經(jīng)知曉布隆過濾器的作用是檢索一個元素是否在集合中?？赡苡腥苏J(rèn)為這個功能非常簡單，直接放在redis中或者數(shù)據(jù)庫中查詢就好了。又或者當(dāng)數(shù)據(jù)量較小，內(nèi)存又足夠大時，使用hashMap或者h(yuǎn)ashSet等結(jié)構(gòu)就好了。但是如果當(dāng)這些數(shù)據(jù)量很大，數(shù)十億甚至更多，內(nèi)存裝不下且數(shù)據(jù)庫檢索又極慢的情況，我們應(yīng)該如何去處理？這個時候我們不妨考慮下布隆過濾器，因?yàn)樗且粋€空間效率占用極少和查詢時間極快的算法，但是需要業(yè)務(wù)可以忍受一個判斷失誤率。

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

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

經(jīng)典的哈希函數(shù)的輸出域都是固定的范圍(有窮大，假設(shè)輸出域?yàn)镾)

當(dāng)給哈希函數(shù)傳入相同的值時，返回值必一樣

當(dāng)給哈希函數(shù)傳入不同的輸入值時，返回值可能一樣，也可能不一樣。

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

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

在大多應(yīng)用中，當(dāng)業(yè)務(wù)系統(tǒng)中發(fā)送一個請求時，會先從緩存中查詢；若緩存中存在，則直接返回；若返回中不存在，則查詢數(shù)據(jù)庫。其流程如下圖所示:

緩存穿透：當(dāng)請求數(shù)據(jù)庫中不存在的數(shù)據(jù)，這時候所有的請求都會打到數(shù)據(jù)庫上，這種情況就是緩存穿透。如果當(dāng)請求較多的話，這將會嚴(yán)重浪費(fèi)數(shù)據(jù)庫資源甚至導(dǎo)致數(shù)據(jù)庫假死。

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

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

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

哈希函數(shù)的個數(shù)k公式:

布隆過濾器真實(shí)失誤率p公式：

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

關(guān)于布隆過濾器，我們不需要自己實(shí)現(xiàn)，谷歌已經(jīng)幫我們實(shí)現(xiàn)好了。

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){
        /**
         * 創(chuàng)建一個插入對象為一億，誤報(bào)率為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"));
    }