在上篇文章海量數(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，說明該元素不在布隆過濾器中。

image.png

布隆過濾器最大的用處，就是可以用來判斷一個元素是否在一個集合中，很常用的一個功能是用來去重。比如可以用來解決下面的需求

需求一：不安全網(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ù)宕機(jī)，他們會構(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));
}