1. 什么是布隆過濾器

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

• 它并不存儲數(shù)據(jù)本身，因此不能從布隆過濾器中取出原數(shù)據(jù)。
• 它判斷數(shù)據(jù)存在時，有一定誤差：某數(shù)據(jù)不存在其中，但是它可能說數(shù)據(jù)存在。
• 如果它判斷出數(shù)據(jù)不在其中，那么就一定是的。
• 只能往里添加數(shù)據(jù)，不能移除數(shù)據(jù)。

2. 布隆過濾器的原理 (參考文章)

先了解下哈希函數(shù)的概念是：將任意大小的數(shù)據(jù)轉換成特定大小的數(shù)據(jù)的函數(shù)，轉換后的數(shù)據(jù)稱為哈希值或哈希編碼。

布隆過濾器的底層是一個比特數(shù)組，將某個數(shù)據(jù)A放入時，通過若干個哈希函數(shù)計算出若干個值，假設通過3個哈希函數(shù)，算出3個哈希值x，y，z。x，y，z對應到比特數(shù)組的相應位置，將該位置上的比特位設置為1. 那么該數(shù)據(jù)就被放進來了。

在下面的圖中，藍/紅/紫色表示有3個數(shù)據(jù)被放入了比特數(shù)組，各自相應的比特位被設置為1.
此時，數(shù)據(jù)w并沒有被放入比特數(shù)組，但它相應的哈希值對應的比特位都為1，那么布隆過濾器就會認為w存在。這就會造成誤判。

布隆過濾器底層

3. 應用場景

布隆過濾器適用于大數(shù)據(jù)量，但又能允許一定程度的誤差，這樣的場景。例如：

• 爬蟲url判斷重復
  將要爬一個url時，用布隆過濾器判斷是否存在，不存在則放入，存在則不處理。誤判就是此url沒爬過，但布隆過濾器說爬過了，那么爬蟲過程中會缺失一些url，這個不影響。

• 緩存穿透
  通過布隆過濾器將所有數(shù)據(jù)都放入比特數(shù)組。當有請求過來，如果請求的是存在的數(shù)據(jù)，那么肯定會放行；如果是不存在的數(shù)據(jù)，可能會被擋住，小概率可能被放行。那么，大部分的惡意請求就能被擋下來。

4. 布隆過濾器的Java實現(xiàn)

Guava包中提供了BloomFilter的實現(xiàn)。

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterTest {

    public static void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 200000, 1E-7);
                
        bloomFilter.put("test");
        
        boolean contain = bloomFilter.mightContain("test");
        
        if (contain)
            System.out.println("contain test");
    }

}