問題
問題描述：一個網站有 20 億 url 存在一個黑名單中，這個黑名單要怎麼存？若此時随便輸入一個 url，你如何快速判斷該 url 是否在這個黑名單中？并且需在給定記憶體空間（比如：500M）内快速判斷出。
分析
可能很多人首先想到的會是使用 HashSet，因為 HashSet基于 HashMap，理論上時間複雜度為：O(1)。達到了快速的目的，但是空間複雜度呢？URL字元串通過Hash得到一個Integer的值，Integer占4個位元組，那20億個URL理論上需要：
20億*4/1024/1024/1024=7.45G
的記憶體，不滿足空間複雜度的要求。
這裡就引出本文要介紹的“布隆過濾器”。
何為布隆過濾器
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識别率和删除困難。
是不是描述的比較抽象？那就直接了解其原理吧！
還是以上面的例子為例：
雜湊演算法得出的Integer的哈希值最大為：
Integer.MAX_VALUE=2147483647
意思就是任何一個URL的哈希都會在0~2147483647之間。
那麼可以定義一個 2147483647 長度的byte數組，用來存儲集合所有可能的值。為了存儲這個byte數組，系統隻需要：
2147483647/8/1024/1024=256M
比如：某個URL（X）的哈希是2，那麼落到這個byte數組在第二位上就是1，這個byte數組将是：
000….00000010
.
下面,我們将這20億個數全部哈希并落到byte數組中:
如果byte數組上的第二位是1，那麼這個URL（X）可能存在。為什麼是可能？因為有可能其它URL因哈希碰撞哈希出來的也是2，這就是誤判。
但是如果這個byte數組上的第二位是0，那麼這個URL（X）就一定不存在集合中。
多次哈希
為了減少因哈希碰撞導緻的誤判機率，可以對這個URL（X）用不同的雜湊演算法進行N次哈希，得出N個哈希值，落到這個byte數組上，如果這N個位置沒有都為1，那麼這個URL（X）就一定不存在集合中。
Guava 的 BloomFilter
Guava架構提供了布隆過濾器的具體實作：BloomFilter，使得開發不用再自己寫一套算法的實作。
建立BloomFilter
BloomFilter提供了幾個重載的靜态 create方法來建立執行個體：
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions);
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions); 複制
調用方法：
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy); 複制
參數含義：
- funnel 指定布隆過濾器中存的是什麼類型的資料，有：IntegerFunnel，LongFunnel，StringCharsetFunnel。
- expectedInsertions 預期需要存儲的資料量
- fpp 誤判率，預設是0.03。
BloomFilter裡byte數組的空間大小由 expectedInsertions， fpp參數決定，見方法：
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
} 複制
真正的byte數組維護在類：BitArray中。最後通過：put和 mightContain方法，添加元素和判斷元素是否存在。
算法特點
1、因使用哈希判斷，時間效率很高。空間效率也是其一大優勢。
2、有誤判的可能，需針對具體場景使用。
3、因為無法分辨哈希碰撞，是以不是很好做删除操作。
使用場景
布隆過濾器的巨大用處就是，能夠迅速判斷一個元素是否在一個集合中。它的常用使用場景如下:
1、黑名單 : 反垃圾郵件，從數十億個垃圾郵件清單中判斷某郵箱是否垃圾郵箱（同理，垃圾短信）
2、URL去重 : 網頁爬蟲對URL的去重，避免爬取相同的URL位址
3、單詞拼寫檢查
4、Key-Value緩存系統的Key校驗 (緩存穿透) : 緩存穿透，将所有可能存在的資料緩存放到布隆過濾器中，當黑客通路不存在的緩存時迅速傳回避免緩存及DB挂掉。
5、ID校驗，比如訂單系統查詢某個訂單ID是否存在，如果不存在就直接傳回。
參考資料
https://www.jianshu.com/p/4d31af4c08fb