在上篇文章海量數(shù)據(jù)下的去重和查重（一）：BitMap位圖法的最后海渊，我們說到位圖法缺點汁胆，是其所占空間隨集合內(nèi)最大元素的增大而增大怠益。這就會帶來一個問題，如果查找的元素數(shù)量少但其中某個元素的值很大忧换，比如數(shù)字范圍是 1 到 1000 億恬惯，那消耗的空間不容樂觀。
針對這個缺點亚茬，有一種改進(jìn)是布隆過濾器酪耳。
布隆過濾器
所謂布隆過濾器，實際上就是一個位圖bitMap刹缝，我們現(xiàn)在假設(shè)有一個長度為m的bit類型的數(shù)組碗暗，以及 K 個互相獨立的優(yōu)秀的哈希函數(shù)，且這k個哈希函數(shù)的輸出域都大于或等于 m梢夯。
當(dāng)一個元素加入布隆過濾器中的時候言疗，會進(jìn)行如下操作：
- 使用 K 個哈希函數(shù)對元素值進(jìn)行 K 次計算，得到 K 個哈希值颂砸，我們將這K個值對m模運算噪奄，得到的 k 個值都在 0~m之間
- 根據(jù)得到的哈希值，在位數(shù)組中把對應(yīng)下標(biāo)的值置為 1人乓。
當(dāng)要判斷一個值是否在布隆過濾器中勤篮，對元素再次進(jìn)行哈希計算，得到值之后判斷位數(shù)組中的每個元素是否都為 1色罚，如果值都為 1叙谨，那么說明這個值在布隆過濾器中，如果存在一個值不為 1保屯，說明該元素不在布隆過濾器中。
布隆過濾器最大的用處涤垫，就是可以用來判斷一個元素是否在一個集合中姑尺，很常用的一個功能是用來去重。比如可以用來解決下面的需求
需求一：不安全網(wǎng)頁的黑名單包含100億個黑名單網(wǎng)頁蝠猬，每個網(wǎng)頁的URL最多占用64B切蟋，現(xiàn)在要實現(xiàn)一個網(wǎng)頁過濾系統(tǒng)，根據(jù)網(wǎng)頁的URL判斷該網(wǎng)頁是否在黑名單上榆芦。我們可以把黑名單url加載到數(shù)據(jù)庫或者redis中柄粹，但是數(shù)據(jù)庫存在效率問題喘鸟，redis存在內(nèi)存問題。
需求二：在爬蟲中驻右，目標(biāo)網(wǎng)站 URL 千千萬什黑，怎么判斷某個 URL 爬蟲是否寵幸過？簡單點可以爬蟲每采集過一個 URL堪夭，就把這個 URL 存入數(shù)據(jù)庫中愕把，每次一個新的 URL 過來就到數(shù)據(jù)庫查詢下是否訪問過。
但是隨著爬蟲爬過的 URL 越來越多森爽，每次請求前都要訪問數(shù)據(jù)庫一次恨豁，并且對于這種字符串的 SQL 查詢效率并不高。除了數(shù)據(jù)庫之外爬迟，使用 Redis 的 set 結(jié)構(gòu)也可以滿足這個需求橘蜜，并且性能優(yōu)于數(shù)據(jù)庫。而Redis 也存在一個問題：耗費過多的內(nèi)存付呕。
對于上述兩個問題计福，相比于數(shù)據(jù)庫和 Redis，使用布隆過濾器可以很好的避免性能和內(nèi)存占用的問題凡涩。
特點——寧可錯殺三千棒搜，絕不放過一個
從上面的介紹中可以看出，當(dāng)插入的元素越來越多活箕，位數(shù)組中被置為 1 的位置就越多力麸，當(dāng)一個不在布隆過濾器中的元素，經(jīng)過哈希計算之后育韩，得到的值在位數(shù)組中查詢克蚂，有可能這些位置也都被置為 1。這樣一個不存在布隆過濾器中的也有可能被誤判成在布隆過濾器中筋讨。但是如果布隆過濾器判斷說一個元素不在布隆過濾器中埃叭，那么這個值就一定不在布隆過濾器中。簡單來說：
布隆過濾器說某個元素在悉罕，可能會被誤判赤屋。
布隆過濾器說某個元素不在，那么一定不在壁袄。
這個布隆過濾器的缺陷放到上面爬蟲的需求中类早，可能存在某些沒有訪問過的 URL 可能會被誤判為訪問過，但是如果是訪問過的 URL 一定不會被誤判為沒訪問過嗜逻。在黑名單需求中涩僻，一個正常url可能會被誤判為是黑名單url，從而被攔截，但是一個黑名單url是肯定會被攔截的逆日。
雖然存在這個問題嵌巷，但是在這兩種需求中，相對于性能和內(nèi)存來說室抽，一點點的誤判率是可以接受的搪哪。
常見的補救辦法是建立白名單，存儲那些可能被誤判的元素狠半。 比如你苦等的offer 可能被系統(tǒng)丟在郵件垃圾箱（白名單）了噩死。
使用場景
布隆過濾器的最大的用處就是，能夠迅速判斷一個元素是否在一個集合中神年。因此它有如下三個使用場景:
- 網(wǎng)頁爬蟲對 URL 的去重已维，避免爬取相同的 URL 地址
- 進(jìn)行垃圾郵件過濾：反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱（同理已日，垃圾短信）
- 有的黑客為了讓服務(wù)宕機垛耳，他們會構(gòu)建大量不存在于緩存中的 key 向服務(wù)器發(fā)起請求，在數(shù)據(jù)量足夠大的情況下飘千，頻繁的數(shù)據(jù)庫查詢可能導(dǎo)致 DB 掛掉堂鲜。布隆過濾器很好的解決了緩存擊穿的問題，通過布隆過濾器
將所有的可用的key放入緩存护奈，當(dāng)請求進(jìn)來時缔莲，先去過濾器中校驗是否存在，如果不存在直接返回null霉旗。
項目中使用
1痴奏、redis布隆過濾器
<dependency>
<groupId>com.redislabs</groupId>
<artifactId>jrebloom</artifactId>
<version>1.0.2</version>
</dependency>
public class RedisBloomDemo {
public static void main(String[] args) {
String userIdBloomKey = "userid";
// 創(chuàng)建客戶端，jedis實例
Client client = new Client("localhost", 6378);
// 創(chuàng)建一個有初始值和出錯率的過濾器
client.createFilter(userIdBloomKey,100000,0.01);
// 新增一個<key,value>
boolean userid1 = client.add(userIdBloomKey,"101310222");
System.out.println("userid1 add " + userid1);
// 批量新增values
boolean[] booleans = client.addMulti(userIdBloomKey, "101310111", "101310222", "101310222");
System.out.println("add multi result " + booleans);
// 某個value是否存在
boolean exists = client.exists(userIdBloomKey, "101310111");
System.out.println("101310111 是否存在" + exists);
//某批value是否存在
boolean existsBoolean[] = client.existsMulti(userIdBloomKey, "101310111","101310222", "101310222","11111111");
System.out.println("某批value是否存在 " + existsBoolean);
}
}
2厌秒、Guava中的BloomFilter
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>22.0</version>
</dependency>
private static int size = 1000000;
private static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), size, 0.0001);
public void test2() {
String aa = "zjl";
bloomFilter.put(aa);
System.out.println(bloomFilter.mightContain(aa));
}
