假設(shè)遇到這樣一個(gè)問題：
一個(gè)網(wǎng)站有 20 億 url 存在一個(gè)黑名單中，這個(gè)黑名單要怎么存津肛？若此時(shí)隨便輸入一個(gè) url章喉，你如何快速判斷該 url 是否在這個(gè)黑名單中？并且需在給定內(nèi)存空間（比如：500M）內(nèi)快速判斷出
可能很多人首先想到的會(huì)是使用 HashSet快耿，因?yàn)?HashSet基于 HashMap囊陡，理論上時(shí)間復(fù)雜度為：O(1)。達(dá)到了快速的目的掀亥，但是空間復(fù)雜度呢撞反？URL字符串通過Hash得到一個(gè)Integer的值，Integer占4個(gè)字節(jié)搪花，那20億個(gè)URL理論上需要：20億*4/1024/1024/1024=7.45G的內(nèi)存遏片，不滿足空間復(fù)雜度的要求。
這里就引出本文要介紹的“布隆過濾器”撮竿。
何為布隆過濾器
百科上對(duì)布隆過濾器的介紹是這樣的：
布隆過濾器（Bloom Filter）是1970年由布隆提出的吮便。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中幢踏。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多髓需，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。
是不是描述的比較抽象房蝉？那就直接了解其原理吧僚匆！
還是以上面的例子為例：
哈希算法得出的Integer的哈希值最大為：Integer.MAX_VALUE=2147483647，意思就是任何一個(gè)URL的哈希都會(huì)在0~2147483647之間搭幻。
那么可以定義一個(gè)2147483647長(zhǎng)度的byte數(shù)組咧擂，用來存儲(chǔ)集合所有可能的值。為了存儲(chǔ)這個(gè)byte數(shù)組檀蹋，系統(tǒng)只需要：2147483647/8/1024/1024=256M松申。
比如：某個(gè)URL（X）的哈希是2，那么落到這個(gè)byte數(shù)組在第二位上就是1俯逾，這個(gè)byte數(shù)組將是：000….00000010贸桶，重復(fù)的，將這20億個(gè)數(shù)全部哈希并落到byte數(shù)組中桌肴。
判斷邏輯：
如果byte數(shù)組上的第二位是1刨啸，那么這個(gè)URL（X）可能存在。為什么是可能识脆？因?yàn)橛锌赡芷渌黆RL因哈希碰撞哈希出來的也是2，這就是誤判。
但是如果這個(gè)byte數(shù)組上的第二位是0灼捂，那么這個(gè)URL（X）就一定不存在集合中离例。
多次哈希：
為了減少因哈希碰撞導(dǎo)致的誤判概率，可以對(duì)這個(gè)URL（X）用不同的哈希算法進(jìn)行N次哈希悉稠，得出N個(gè)哈希值宫蛆，落到這個(gè)byte數(shù)組上，如果這N個(gè)位置沒有都為1的猛，那么這個(gè)URL（X）就一定不存在集合中耀盗。
Guava的BloomFilter
Guava框架提供了布隆過濾器的具體實(shí)現(xiàn)：BloomFilter，使得開發(fā)不用再自己寫一套算法的實(shí)現(xiàn)卦尊。
創(chuàng)建BloomFilter
BloomFilter提供了幾個(gè)重載的靜態(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ù)期需要存儲(chǔ)的數(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)
1正驻、因使用哈希判斷弊攘，時(shí)間效率很高〔ν兀空間效率也是其一大優(yōu)勢(shì)肴颊。2、有誤判的可能渣磷，需針對(duì)具體場(chǎng)景使用婿着。3、因?yàn)闊o法分辨哈希碰撞醋界，所以不是很好做刪除操作竟宋。
使用場(chǎng)景
1、黑名單 2形纺、URL去重 3丘侠、單詞拼寫檢查 4、Key-Value緩存系統(tǒng)的Key校驗(yàn) 5逐样、ID校驗(yàn)蜗字，比如訂單系統(tǒng)查詢某個(gè)訂單ID是否存在打肝，如果不存在就直接返回。
優(yōu)化背景：查詢訂單需要關(guān)聯(lián)預(yù)警訂單數(shù)據(jù)挪捕，由于每查詢一筆預(yù)警就要查詢一次預(yù)警表粗梭，效率低，即是判斷該訂單是否預(yù)警
可以先將預(yù)警的訂單放到布隆過濾器中存放一份级零，則查詢訂單的時(shí)候可以用于關(guān)聯(lián)
應(yīng)用該場(chǎng)景的原因：大部分訂單還是正常的断医，所以沒不要每次去關(guān)聯(lián)
先去布隆過濾器查詢?cè)撚唵问欠翊嬖冢淮嬖趧t直接返回正常奏纪，存在則去預(yù)警表查詢鉴嗤，允許一定的誤差率
Bloom Filter實(shí)戰(zhàn)
使用goole guava輕松實(shí)現(xiàn)bloom filter
源碼分析 bitArray,numHashFunction,funnel,Strategy,put(),
Demo實(shí)例
場(chǎng)景描述：100w字符串放入布隆過濾器，另外隨機(jī)生成1w字符串序调，判斷他們?cè)?00w里面是否存在
目的醉锅，了解布隆過濾器的簡(jiǎn)單使用；
了解誤判率對(duì)hash函數(shù)個(gè)數(shù)以及bit數(shù)組長(zhǎng)度的影響
使用bloom filter解決緩存擊穿的問題
public class BloomFilterTest {
private static final int insertions = 1000000; //100w
@Test
public void bfTest(){
//初始化一個(gè)存儲(chǔ)string數(shù)據(jù)的布隆過濾器炕置，初始化大小100w,不能設(shè)置為0
BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001);
//初始化一個(gè)存儲(chǔ)string數(shù)據(jù)的set荣挨，初始化大小100w
Set<String> sets = new HashSet<>(insertions);
//初始化一個(gè)存儲(chǔ)string數(shù)據(jù)的set，初始化大小100w
List<String> lists = new ArrayList<String>(insertions);
//向三個(gè)容器初始化100萬個(gè)隨機(jī)并且唯一的字符串---初始化操作
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
int wrong = 0;//布隆過濾器錯(cuò)誤判斷的次數(shù)
int right = 0;//布隆過濾器正確判斷的次數(shù)
for (int i = 0; i < 10000; i++) {
String test = i%100==0?lists.get(i/100):UUID.randomUUID().toString();//按照一定比例選擇bf中肯定存在的字符串
if(bf.mightContain(test)){
if(sets.contains(test)){
right ++;
}else{
wrong ++;
}
}
}
System.out.println("=================right====================="+right);//100
System.out.println("=================wrong====================="+wrong);
}
}
解決緩存擊穿
private BloomFilter<String> bf;
@postConstruct ------------->初始化的方法
private void init(){
//將唯一編碼加進(jìn)來
//初始化布隆過濾器
bf = BloomFiler.create(Funnels.stringFunner(Charsets.UTF_8),編碼.size()*1.2);
for(String str:ucodes){
bf.put(str);
}
========將布隆過濾器的數(shù)據(jù)放到單個(gè)服務(wù)，和業(yè)務(wù)代碼分開
使用多線程放進(jìn)去
if(bf.mightContain(usercode)){
return null;
}
