原文地址：https://mp.weixin.qq.com/s/ZpXqneKmV5eAlLq1VpueSQ
假設(shè)遇到這樣一個問題：一個網(wǎng)站有 20 億 url 存在一個黑名單中，這個黑名單要怎么存污抬？若此時隨便輸入一個 url汞贸，你如何快速判斷該 url 是否在這個黑名單中？并且需在給定內(nèi)存空間（比如：500M）內(nèi)快速判斷出印机。
可能很多人首先想到的會是使用 HashSet矢腻，因?yàn)?HashSet基于 HashMap，理論上時間復(fù)雜度為：O(1)射赛。達(dá)到了快速的目的多柑，但是空間復(fù)雜度呢？URL字符串通過Hash得到一個Integer的值楣责，Integer占4個字節(jié)竣灌，那20億個URL理論上需要：20億*4/1024/1024/1024=7.45G的內(nèi)存，不滿足空間復(fù)雜度的要求秆麸。
這里就引出本文要介紹的“布隆過濾器”初嘹。
何為布隆過濾器
百科上對布隆過濾器的介紹是這樣的：
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)沮趣。布隆過濾器可以用于檢索一個元素是否在一個集合中屯烦。它的優(yōu)點(diǎn)是空間效率和查詢時間都比一般的算法要好的多，缺點(diǎn)是有一定的誤識別率和刪除困難兔毒。
是不是描述的比較抽象漫贞？那就直接了解其原理吧！
還是以上面的例子為例：
哈希算法得出的Integer的哈希值最大為：Integer.MAX_VALUE=2147483647育叁，意思就是任何一個URL的哈希都會在0~2147483647之間迅脐。
那么可以定義一個2147483647長度的byte數(shù)組，用來存儲集合所有可能的值豪嗽。為了存儲這個byte數(shù)組谴蔑，系統(tǒng)只需要：2147483647/8/1024/1024=256M豌骏。
比如：某個URL（X）的哈希是2，那么落到這個byte數(shù)組在第二位上就是1隐锭，這個byte數(shù)組將是：000….00000010窃躲，重復(fù)的，將這20億個數(shù)全部哈希并落到byte數(shù)組中钦睡。
判斷邏輯：
如果byte數(shù)組上的第二位是1蒂窒，那么這個URL（X）可能存在。為什么是可能荞怒？因?yàn)橛锌赡芷渌黆RL因哈希碰撞哈希出來的也是2洒琢，這就是誤判。
但是如果這個byte數(shù)組上的第二位是0褐桌，那么這個URL（X）就一定不存在集合中衰抑。
多次哈希：
為了減少因哈希碰撞導(dǎo)致的誤判概率，可以對這個URL（X）用不同的哈希算法進(jìn)行N次哈希荧嵌，得出N個哈希值呛踊，落到這個byte數(shù)組上，如果這N個位置沒有都為1啦撮，那么這個URL（X）就一定不存在集合中谭网。
Guava的BloomFilter
Guava框架提供了布隆過濾器的具體實(shí)現(xiàn)：BloomFilter，使得開發(fā)不用再自己寫一套算法的實(shí)現(xiàn)赃春。
創(chuàng)建BloomFilter
BloomFilter提供了幾個重載的靜態(tài) create方法來創(chuàng)建實(shí)例：
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);
最終還是調(diào)用：
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
// 參數(shù)含義：
// funnel 指定布隆過濾器中存的是什么類型的數(shù)據(jù)蜻底，有：IntegerFunnel，LongFunnel聘鳞，StringCharsetFunnel。
// expectedInsertions 預(yù)期需要存儲的數(shù)據(jù)量
// fpp 誤判率要拂，默認(rèn)是0.03抠璃。
BloomFilter里byte數(shù)組的空間大小由 expectedInsertions， fpp參數(shù)決定脱惰，見方法：
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數(shù)組維護(hù)在類：BitArray中搏嗡。
使用:
最后通過：put和 mightContain方法，添加元素和判斷元素是否存在拉一。
算法特點(diǎn)
- 因使用哈希判斷采盒，時間效率很高∥等螅空間效率也是其一大優(yōu)勢磅氨。
- 有誤判的可能，需針對具體場景使用嫡纠。
- 因?yàn)闊o法分辨哈希碰撞烦租，所以不是很好做刪除操作延赌。
使用場景
- 黑名單
- URL去重
- 單詞拼寫檢查
- Key-Value緩存系統(tǒng)的Key校驗(yàn)
- ID校驗(yàn)，比如訂單系統(tǒng)查詢某個訂單ID是否存在叉橱，如果不存在就直接返回挫以。
