Guava BloomFilter

布隆過濾器是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。

基本概念

當需要判斷某個元素是否在某個數據集中時，一般會怎么做？

1. 將數據集封裝成集合，比如List、Set等
2. 通過集合提供的API判斷該元素是否存在于集合

這樣的實現比較簡單，同時通過現有的JDK都能很快達到目的，但是設想一下，如果上面說到的集合數據量非常的大，這樣不僅會耗費較大的存儲空間，同時 在集合中檢索元素的時間復雜度也會隨之增加。那么有沒比較好的方法去實現判斷元素是否存在這樣的情形呢？

也就是 布隆過濾器 。

通過一系列的Hash函數將元素映射到一個位陣列（Bit Array）中的多個點位上，判斷元素是否存在，則是判斷所有點位是不是都為1。然而，位陣列上都為1并不一定能夠保證該元素一定存在，也有可能是其他元素Hash后落在了該點位上，這就是布隆過濾器的誤判。

因此通過布隆過濾器我們可以確定：

1. 元素可能在集合中
2. 元素一定不在集合中

應用場景

• 網頁爬蟲時忽略已經判定的URL路徑
• 郵箱通過設置過濾垃圾郵件
• 集合重復元素的判別，有效判斷元素不在集合中
• 防止數據緩存時的緩存穿透問題

優缺點

• 優點
  • 相比于其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。
  • 布隆過濾器存儲空間和插入/查詢時間都是常數。
  • Hash函數相互之間沒有關系，方便由硬件并行實現。
  • 布隆過濾器不需要存儲元素本身，對保密要求非常嚴格的場合有優勢。
  • 布隆過濾器可以表示全集，其它任何數據結構都不能。
• 缺點
  • 元素存在的誤判
  • 一般情況下不支持元素（位陣列）的刪除

實現原理

核心其實是元素如何存儲？如何判斷元素是否存在？核心方法就兩個，一個“存”一個檢查，里面涉及到了算法相關知識，感興趣可以深入研究下其實現原理與思想。

• put 將元素放入過濾器中，但不是存儲

public < T > boolean put(@ParametricNullness T object, Funnel< ? super T > funnel, int numHashFunctions, LockFreeBitArray bits) {
            long bitSize = bits.bitSize(); // 位數組，可以通過redis來實現分布式的布隆過濾器
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong(); //通過funnel將對象轉換成基本類型并計算64位hash
            int hash1 = (int)hash64; // 取低32位
            int hash2 = (int)(hash64 > >> 32); // 取高32位
            boolean bitsChanged = false;
            // 
            for(int i = 1; i <= numHashFunctions; ++i) {
                int combinedHash = hash1 + i * hash2;
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }

                bitsChanged |= bits.set((long)combinedHash % bitSize);
            }

            return bitsChanged;
        }

• mightContain 與put相似，計算的過程相同，不同的是值的判斷

public < T > boolean mightContain(@ParametricNullness T object, Funnel< ? super T > funnel, int numHashFunctions, LockFreeBitArray bits) {
            long bitSize = bits.bitSize();
            long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
            int hash1 = (int)hash64;
            int hash2 = (int)(hash64 > >> 32);

            for(int i = 1; i <= numHashFunctions; ++i) {
                int combinedHash = hash1 + i * hash2;
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }

                if (!bits.get((long)combinedHash % bitSize)) {
                    return false;
                }
            }

            return true;
        }

我們可以簡單第理解其實現原理？比如現在有一個容器，我們定義為String[] bitArray = new String[26]作為 位陣列 ， 現在有一堆由小寫英文組成的元素，我們假定Hash算法為a-z到1~26的映射。

1. 現在有一個元素abc，hash后為1110000000...，保存到bitArray ：1110000000...
2. 現在有一個元素cde, hash后為0011100000...，保存到bitArray ：1111100000...
3. 現在又有一個新的元素ade，hash后同樣為100110000...，很明顯會認為該元素存在，這就是FFP

為什么判斷元素一定不在集合中呢？很顯然，如果一個元素存在，則該元素hash后的bit數組必須全部都是1，反之則不存在

示例

@Test
    public void match(){
        BloomFilter filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),10000,0.2);
        List< String > ids = new ArrayList<  >();

        IntStream.rangeClosed(1,10000).forEach(index- >{
            String id = UUID.randomUUID().toString();
            ids.add(id);
            filter.put( id );
        });

        ids.forEach(id- >{
            // 正常情況下全部失敗，但是會有 20%的返回true
            System.out.println( id + ":" + filter.mightContain( id+1 ));
        });
    }

流程很簡單：

1. 根據配置構建BloomFilter對象
2. 通過put方法，初始化數據到filter
3. 通過方法mightContain判斷元素是否存在

結束語

BloomFilter雖然看起來簡單，但是其內部的實現包含了很多的數學與算法知識，我們只是通過其簡單的API就能各種復雜的功能。關于如何將目前說到的這些在具體的項目中進行實踐與集成 后面會來介紹，首先我們能夠先了解一些技術一起能解決上面問題，理解了原理與目的，使用也就不是難事。