Bloom Filter - Guave

昨天前同僚，來請教一個問題，如何對千萬級的資料進行 重複資料判斷；之前資料量不大的時候，一直使用hashset，現在資料量上來了，顯然需要重構；我說“啥？還hashset，計算用Redis set也不能用hashset啊…”

大概場景是，每天需要監控司機的位置資訊，位置資訊可經基站資料轉化成Long整數，資料量會達到千萬級别，但其中不乏基站發送的重複資料，是以想去重，并且對精度要求也不是很高，偶爾的偏離位置也可以接受；

我一聽，這不是标準的布隆過濾器的case麼，不能再标準了…

什麼是布隆過濾器

布隆過濾器，說簡單也很簡單，底層就是一個很長的 0/1 bit數組，再加上幾個 hash 函數；

• 資料插入：當新添加一個元素的時候，會對元素依次應用hash函數，并計算出在數組中對應的index位置，标記1；是以一個元素，會對應幾個index位置為1
• 資料查找：當超找一個元素的時候，也對其應用hash函數，如果對應位置的value有一個為0，那就說明這個元素肯定不存在；但是如果對應的位置都為1，隻能說明，這個元素可能存在，畢竟是hash函數取模，還是會遇到hash碰撞問題的… 也就是會造成一定誤判

介紹了算法，還需要提供實作思路，不然蹭不到飯的…

萬能的Guave中就有布隆過濾器的實作，并且可以通過設定 誤判百分比，來控制精準度：

讀源碼快樂

源碼就不一行行過了，但必須來看一下 Google 程式員的快樂！代碼中的comments，哈哈！這隻有讀源碼才能體會到的快樂！

1. homie 呦呦check now

public double expectedFpp() {
    // You down with FPP? (Yeah you know me!) Who's down with FPP? (Every last homie!)
    return Math.pow((double) bits.bitCount() / bitSize(), numHashFunctions);
  }
           

1. who cares! 好像這老哥有點暴脾氣，不知道現在是不是已經離職了

/*
 * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
 */
long numBits = optimalNumOfBits(expectedInsertions, fpp);
           

簡單使用

代碼很簡單，隻需簡單的設定下 FPP，即允許誤判率即可，下面設定的是 0.01 基本可以了，沒必要再低了，不然會影響性能；

Long clientSize = 1000_0000L;
    double fpp = 0.01; // false positive probability

    //thread safe
    BloomFilter<Long> bloomFilter = BloomFilter.create(Funnels.longFunnel(), clientSize, fpp);

    for(long i=0; i<clientSize; i++){
        bloomFilter.put(i);
    }

    int bad = 0;
    for(long i=clientSize; i<clientSize + 1000; i++){
        if(bloomFilter.mightContain(i)) bad++;
    }
    System.out.println(bad);