假設(shè)遇到這樣一個問題：
一個網(wǎng)站有 20 億 url 存在一個黑名單中，這個黑名單要怎么存？
若此時隨便輸入一個 url，你如何快速判斷該 url 是否在這個黑名單中？
并且需在給定內(nèi)存空間（比如：500M）內(nèi)快速判斷出。
#方案1:
可能很多人首先想到的會是使用 HashSet，因為 HashSet基于 HashMap，理論上時間復(fù)雜度為：O(1)。
達到了快速的目的，但是空間復(fù)雜度呢？
URL字符串通過Hash得到一個Integer的值，Integer占4個字節(jié)，那20億個URL理論上需要：
20億*4/1024/1024/1024=7.45G的內(nèi)存，不滿足空間復(fù)雜度的要求。
#方案2:
可以初始化一個很長的一個Bit數(shù)組，將數(shù)值對應(yīng)的Bit位置為true，然后根據(jù)是true還是false判斷對應(yīng)位置的數(shù)值是否存在。
例如現(xiàn)在有數(shù)值0、3、63，我們可以初始化一個長度為64的Bit數(shù)組，
將0、3、63置為true，然后通過get()方法查看對應(yīng)位置的數(shù)值是否存在。
#方案2局限
BitSet有兩個比較局限的地方：
>> 當(dāng)樣本分布極度不均勻的時候，BitSet會造成很大空間上的浪費。
舉個例子，比如你有5個數(shù)，分別是1、2、3、4、999，
那么這個BitSet至少得有1000位，中間的位置很多就被浪費掉了。
>> BitSet只面向數(shù)字比較，并且還得是正數(shù)，其他類型需要先轉(zhuǎn)換成int類型，
但是轉(zhuǎn)換過程中難免會出現(xiàn)重復(fù)，BitSet的準確性就會降低。
#針對以上兩個問題，解決思路就是：
分布不均勻的情況可以通過hash函數(shù)，將元素都映射到一個區(qū)間范圍內(nèi)，
減少大段區(qū)間閑置造成的浪費。然后可以把其他類型映射成整數(shù)，
映射時可以多hash幾次同時擴大數(shù)組的范圍，減少hash沖突的概率。
#方案3: 布隆過濾器
>>>>>>>>>>> 這里就引出本文要介紹的“布隆過濾器”。
先說結(jié)論
>> 布隆過濾器說某個元素在，可能會被誤判。
>> 布隆過濾器說某個元素不在，那么一定不在。
布隆過濾器的原理有一個很好的比喻，那就是在冬天一片白雪覆蓋的地面上，
如果你從上面走過，就會留下你的腳印。
如果地面上有你的腳印，那么就可以大概率斷定你來過這個地方，
但是也不一定，也許別人的鞋正好和你穿的一模一樣。
可是如果地面上沒有你的腳印，那么就可以 100% 斷定你沒來過這個地方。
1.基本概念
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。
它實際上是一個很長的二進制矢量和一系列隨機映射函數(shù)。
布隆過濾器可以用于檢索一個元素是否在一個集合中。
它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。
#布隆過濾器的本質(zhì)
布隆過濾器本質(zhì)是一個位數(shù)組, 位數(shù)組就是數(shù)組的每個元素都只占用1bit 。
每個元素只能是 0 或者 1。
這樣申請一個 10000 個元素的位數(shù)組只占用 10000 / 8 = 1250 B 的空間。
布隆過濾器除了一個位數(shù)組，還有 K 個哈希函數(shù)。
當(dāng)一個元素加入布隆過濾器中的時候，會進行如下操作：
>> 使用 K 個哈希函數(shù)對元素值進行 K 次計算，得到 K 個哈希值。
>> 根據(jù)得到的哈希值，在位數(shù)組中把對應(yīng)下標的值置為 1。
#作用
特點是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。
舉個例子
布隆過濾器是一個 bit 向量或者說 bit 數(shù)組
布隆過濾器初始態(tài).png
如果我們要映射一個值到布隆過濾器中，我們需要使用多個不同的哈希函數(shù)生成多個哈希值(假設(shè)為3個)，
并對每個生成的哈希值指向的 bit 位置 1。
例如針對值 “tianmao” 和三個不同的哈希函數(shù)分別生成了哈希值 1、3、5。
針對值 “tianmao” 和三個不同的哈希函數(shù)分別生成了哈希值 1、3、5.png
現(xiàn)在再存一個值 “tencent”，如果哈希函數(shù)返回 3、4、8。
值得注意的是，3 這個 bit 位由于兩個值的哈希函數(shù)都返回了這個 bit 位，因此它被覆蓋了。
現(xiàn)在再存一個值 “tencent”，如果哈希函數(shù)返回 3、4、8.png
現(xiàn)在我們?nèi)绻氩樵?“zhongxing” 這個值是否存在，哈希函數(shù)返回了 1、2、8三個值，
結(jié)果我們發(fā)現(xiàn) 2 這個 bit 位上的值為 0，說明沒有任何一個值映射到這個 bit 位上，
因此我們可以很確定地說 “zhongxing” 這個值不存在。
而當(dāng)我們需要查詢 “tianmao” 這個值是否存在的話，那么哈希函數(shù)必然會返回 1、3、5，
然后我們檢查發(fā)現(xiàn)這三個 bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么？
答案是不可以，只能是 “tianmao” 這個值可能存在。這是為什么呢？
因為隨著增加的值越來越多，被置為 1 的 bit 位也會越來越多，
這樣某個值 “shangtang” 即使沒有被存儲過，但是萬一哈希函數(shù)返回的三個 bit 位都被其他值置位了 1 ，
那么程序還是會判斷 “shangtang” 這個值存在。
1.1 優(yōu)缺點
#優(yōu)點
>> 相比于其它的數(shù)據(jù)結(jié)構(gòu)，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。
布隆過濾器存儲空間和插入/查詢時間都是常數(shù)（O(k)）。
>> 散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實現(xiàn)。
>> 布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢。
>> 布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；
>> k和m相同，使用同一組散列函數(shù)的兩個布隆過濾器的交并差運算可以使用位操作進行。
#缺點
>> 誤算率。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。
>> 一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，
每插入一個元素相應(yīng)的計數(shù)器加1, 這樣刪除元素時將計數(shù)器減掉就可以了。
然而要保證安全地刪除元素并非如此簡單。
首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。
另外計數(shù)器回繞也會造成問題。
>> 在降低誤算率方面，有不少工作，使得出現(xiàn)了很多布隆過濾器的變種。
布隆過濾器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以.
上圖中的 bit 位 3 被兩個值共同覆蓋的話，一旦你刪除其中一個值例如 “tencent” 而將其置位 0，
那么下次判斷另一個值例如 “tianmao” 是否存在的話，會直接返回 false，而實際上你并沒有刪除它。
如何解決這個問題，答案是計數(shù)刪除。
但是計數(shù)刪除需要存儲一個數(shù)值，而不是原先的 bit 位，會增大占用的內(nèi)存大小。
這樣的話，增加一個值就是將對應(yīng)索引槽上存儲的值加一，刪除則是減一，判斷是否存在則是看值是否大于0。
1.2 如何選擇哈希函數(shù)個數(shù)和布隆過濾器長度
這里可以找個靠譜的圖, 看看官網(wǎng)或github哪里有沒有
很顯然，過小的布隆過濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩祷亍翱赡艽嬖凇?，起不到過濾的目的了。
布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。
#哈希函數(shù)的個數(shù) (與錯誤率負相關(guān))
哈希函數(shù)越多則布隆過濾器 bit 位置為 1 的速度越快，且布隆過濾器的效率越低；
但是如果太少的話，那我們的誤報率會變高。
錯誤率: 允許布隆過濾器的錯誤率，值越低過濾器的位數(shù)組的大小越大，占用空間也就越大。
1.3 適用場景
1、黑名單
2、URL去重(如爬取網(wǎng)頁信息時)
3、單詞拼寫檢查
4、Key-Value緩存系統(tǒng)的Key校驗
5、ID校驗，比如訂單系統(tǒng)查詢某個訂單ID是否存在，如果不存在就直接返回。
6、Goolge在BigTable中就使用了BloomFilter，以避免在硬盤中尋找不存在的條目。
7、垃圾郵件過濾
3.Guava的BloomFilter (適合單機場景)
3.1 源碼解析
3.2 應(yīng)用示例
package com.zy.eureka.filter;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
/**
* Bloom Filter可以理解為是一個m位的數(shù)組，它有k個相互獨立的哈希函數(shù)。
* 每當(dāng)新來一個元素時，會使用這些哈希函數(shù)分別計算，將對應(yīng)位置置為1。
* 查詢時也要進行k次哈希運算，如果對應(yīng)的k個位置都為1，則表明元素可能存在。
*/
public class GuavaBloomFilter {
/**
* fpp: 默認的誤判率是 3%, 實際設(shè)置的誤判率越低, 所要求的內(nèi)存越大
* expectedInsertions: 參數(shù)設(shè)置過大, 可能導(dǎo)致: java.lang.OutOfMemoryError: Java heap space
*/
private static final BloomFilter<Integer> BLOOM_FILTER = BloomFilter.create(Funnels.integerFunnel(), 1024 * 1024 * 64, 0.0001d);
public static boolean keyExists(Integer key) {
return BLOOM_FILTER.mightContain(key);
}
public static synchronized void put(Integer key) {
BLOOM_FILTER.put(key);
}
}
// 注意事項
// 正確估計預(yù)期插入數(shù)量是很關(guān)鍵的一個參數(shù)。當(dāng)插入的數(shù)量接近或高于預(yù)期值的時候，
// 布隆過濾器將會填滿，這樣的話，它會產(chǎn)生很多無用的誤報點。
測試
public static void main(String[] args) {
for (int i = 0; i < 10000; i++) {
GuavaBloomFilter.put(i);
}
System.out.println(GuavaBloomFilter.keyExists(675));
}
4. Redis中的布隆過濾器 (適合分布式場景)
https://github.com/RedisBloom/RedisBloom (官網(wǎng) 4.0開始支持)
https://oss.redislabs.com/redisbloom/ (文檔)
http://www.dragonwins.com/domains/getteched/bbc/literature/Bloom70.pdf (論文)
redis 在 4.0 的版本中加入了 module 功能，布隆過濾器可以通過 module 的形式添加到 redis 中，
所以使用 redis 4.0 以上的版本可以通過加載 module 來使用 redis 中的布隆過濾器。
// redis 布隆過濾器主要就兩個命令：
>> bf.add 添加元素到布隆過濾器中：bf.add urls https://www.baidu.com。
>> bf.exists 判斷某個元素是否在過濾器中：bf.exists urls https://www.baidu.com。。
// 上面說過布隆過濾器存在誤判的情況，在 redis 中有兩個值決定布隆過濾器的準確率：
>> error_rate ：允許布隆過濾器的錯誤率，這個值越低過濾器的位數(shù)組的大小越大，占用空間也就越大。
>> initial_size ：布隆過濾器可以儲存的元素個數(shù)，當(dāng)實際存儲的元素個數(shù)超過這個值之后，過濾器的準確率會下降。
// redis 中有一個命令可以來設(shè)置這兩個值：
bf.reserve urls 0.01 100
// 三個參數(shù)的含義：
>> 第一個值是過濾器的名字。
>> 第二個值為 error_rate 的值。
>> 第三個值為 initial_size 的值。
// 使用這個命令要注意一點：
執(zhí)行這個命令之前過濾器的名字應(yīng)該不存在，如果執(zhí)行之前就存在會報錯：(error) ERR item exists
使用場景1
比如我們在使用新聞客戶端看新聞時，它會給我們不停地推薦新的內(nèi)容，
它每次推薦時要去重，去掉那些已經(jīng)看過的內(nèi)容。
問題來了，新聞客戶端推薦系統(tǒng)如何實現(xiàn)推送去重的？
Redis 官方提供的布隆過濾器到了 Redis 4.0 提供了插件功能之后才正式登場。
倘若數(shù)據(jù)量較小的情況下可以通過 查詢數(shù)據(jù)庫，過濾掉已經(jīng)推送過的信息，剩下的就是沒有被推送的了。
當(dāng)用戶量很大，每個用戶看過的新聞又很多的情況下，推薦系統(tǒng)的去重工作在性能上跟的上么？
如果歷史記錄存儲在關(guān)系數(shù)據(jù)庫里，去重就需要頻繁地對數(shù)據(jù)庫進行 exists 查詢，
當(dāng)系統(tǒng)并發(fā)量很高時，數(shù)據(jù)庫是很難扛住壓力的。
你可能又想到了緩存，但是如此多的歷史記錄全部緩存起來，那得浪費多大存儲空間啊？
而且這個存儲空間是隨著時間線性增長，你撐得住一個月，你能撐得住幾年么？
但是不緩存的話，性能又跟不上，這該怎么辦？
這時，布隆過濾器 (Bloom Filter) 閃亮登場了，它就是專門用來解決這種去重問題的。
使用場景2
比如業(yè)務(wù)系統(tǒng)的用戶狀態(tài)查詢接口，現(xiàn)在一個新用戶過來了，
它會先去緩存里查詢有沒有這個用戶的狀態(tài)數(shù)據(jù)。
因為是新用戶，所以肯定緩存里沒有。然后它就要去查數(shù)據(jù)庫，結(jié)果數(shù)據(jù)庫也沒有。
如果這樣的新用戶大批量瞬間涌入，那么可以預(yù)見數(shù)據(jù)庫的壓力會比較大，會存在大量的空查詢。
我們非常希望 Redis 里面有這樣的一個 set，它存放了所有用戶的 id，
這樣通過查詢這個 set 集合就知道是不是新用戶來了。
當(dāng)用戶量非常龐大的時候，維護這樣的一個集合需要的存儲空間是很大的。
這時候就可以使用布隆過濾器，它相當(dāng)于一個 set，
但是呢又不同于 set，它需要的存儲空間要小的多。
比如你存儲一個用戶 id 需要 64 個字節(jié)，而布隆過濾器存儲一個用戶 id 只需要 1個字節(jié)多點。
但是呢它存的不是用戶 id，而是用戶 id 的指紋，所以會存在一定的小概率誤判，它是一個具備模糊過濾能力的容器。
當(dāng)它說用戶 id 不在容器中時，那么就肯定不在。
當(dāng)它說用戶 id 在容器里時，99% 的概率下它是正確的，還有 1% 的概率它產(chǎn)生了誤判。
不過在這個案例中，這個誤判并不會產(chǎn)生問題，誤判的代價只是緩存穿透而已。
相當(dāng)于有 1% 的新用戶沒有得到布隆過濾器的保護直接穿透到數(shù)據(jù)庫查詢，
而剩下的 99% 的新用戶都可以被布隆過濾器有效的擋住，避免了緩存穿透。
參考資源
https://en.wikipedia.org/wiki/Bloom_filter (bloom過濾器wiki)
http://www.itdecent.cn/p/2104d11ee0a2 (bloom原理)
https://segmentfault.com/a/1190000016721700 (redis中的布隆過濾器)
https://baijiahao.baidu.com/s?id=1611754128562106165&wfr=spider&for=pc (redis中布隆過濾器數(shù)據(jù)估計)
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
https://my.oschina.net/LucasZhu/blog/1813110 (bloom過濾器算法)
