什么是布隆過濾器
??布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多烁设，缺點是有一定的誤識別率和刪除困難。
實現(xiàn)思想：
??對寫入的數(shù)據(jù)做 H 次 hash 運算定位到數(shù)組中的位置，同時將數(shù)據(jù)改為 1砸彬。當有數(shù)據(jù)查詢時也是同樣的方式定位到數(shù)組中颠毙。比如二進制數(shù)組長度為10，插入元素A砂碉，對A第一次hash過對10取模為1蛀蜜，第二次取模為5，那么將1增蹭、5處的值修改為1滴某。當判斷A是否存在時，按照寫入的計算方式滋迈，計算如果值都為1霎奢，則A存在，否則A不存在饼灿。
public class BloomFilterTest {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int capacity = 10000000;
BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), capacity, 0.01);
for (int i = 0; i < capacity; i++) {
integerBloomFilter.put(i);
}
System.out.println(integerBloomFilter.mightContain(99992));
long end = System.currentTimeMillis();
System.out.println(end-start);
}
}
google 的guava的實現(xiàn)：構(gòu)造方法中有兩個比較重要的參數(shù)幕侠，一個是預計存放多少數(shù)據(jù)，一個是可以接受的誤報率碍彭。guava 會通過你預計的數(shù)量以及誤報率幫你計算出你應當會使用的數(shù)組大小 numBits 以及需要計算幾次 hash 函數(shù) numHashFunctions
場景
??針對緩存穿透的場景晤硕，可以在init的時候?qū)⑿枰彺娴臄?shù)據(jù)放在布隆過濾器中。如果緩存沒有命中庇忌，先用布隆過濾器判斷是否存在舞箍，如果不存在，在請求數(shù)據(jù)庫漆枚。因為bloomFilter是jdk自帶的创译，只適用單機環(huán)境，集群下init數(shù)據(jù)最好放在redis -BizMap中(最大512M)墙基。
缺點及改進
??布隆過濾器的缺點主要是有一定的誤識別率和刪除困難软族，錯誤識別率可以使用google工具來指定識別率，但是無法達到100%残制。
??目前我們知道布隆過濾器可以支持 add 和 isExist 操作立砸，那么 delete 操作可以么，答案是不可以初茶，例如上圖中的 bit 位 4 被兩個值共同覆蓋的話颗祝，一旦你刪除其中一個值例如 “tencent” 而將其置位 0，那么下次判斷另一個值例如 “baidu” 是否存在的話恼布，會直接返回 false螺戳，而實際上你并沒有刪除它。
??如何解決這個問題折汞，答案是計數(shù)刪除倔幼。但是計數(shù)刪除需要存儲一個數(shù)值，而不是原先的 bit 位爽待，會增大占用的內(nèi)存大小损同。這樣的話翩腐，增加一個值就是將對應索引槽上存儲的值加一，刪除則是減一膏燃，判斷是否存在則是看值是否大于0茂卦。
