天天看點

Google Guava 中布隆過濾器的介紹和使用

布隆過濾器(Bloom Filter)是非常經典的,以空間換時間的算法。布隆過濾器由布隆在 1970 年提出。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法,缺點是有一定的誤識别率和删除困難

一、簡介

布隆過濾器(Bloom Filter)是非常經典的,以空間換時間的算法。布隆過濾器由布隆在 1970 年提出。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法,缺點是有一定的誤識别率和删除困難。

二、實作原理

布隆過濾器的核心實作是一個超大的位數組和幾個哈希函數。假設位數組的長度為 m,哈希函數的個數為 k。

Google Guava 中布隆過濾器的介紹和使用

以上圖為例,具體的操作流程:假設集合裡面有 3 個元素 {x, y, z},哈希函數的個數為 3。首先将位數組進行初始化,将裡面每個位都設定位 0。對于集合裡面的每一個元素,将元素依次通過 3 個哈希函數進行映射,每次映射都會産生一個哈希值,這個值對應位數組上面的一個點,然後将位數組對應的位置标記為 1。查詢 W 元素是否存在集合中的時候,同樣的方法将 W 通過哈希映射到位數組上的 3 個點。如果 3 個點的其中有一個點不為 1,則可以判斷該元素一定不存在集合中。反之,如果 3 個點都為 1,則該元素可能存在集合中。注意:此處不能判斷該元素是否一定存在集合中,可能存在一定的誤判率。可以從圖中可以看到:假設某個元素通過映射對應下标為 4、5、6 這 3 個點。雖然這 3 個點都為 1,但是很明顯這 3 個點是不同元素經過哈希得到的位置,是以這種情況說明元素雖然不在集合中,也可能對應的都是 1,這是誤判率存在的原因。

1、布隆過濾器添加元素

  • 将要添加的元素給 k 個哈希函數
  • 得到對應于位數組上的 k 個位置
  • 将這 k 個位置設為 1

2、布隆過濾器查詢元素

  • 将要查詢的元素給 k 個哈希函數
  • 如果 k 個位置有一個為 0,則肯定不在集合中
  • 如果 k 個位置全部為 1,則可能在集合中

3、布隆過濾器的優缺點

優點

相比于其它的資料結構,布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數。另外,Hash 函數互相之間沒有關系,友善由硬體并行實作。布隆過濾器不需要存儲元素本身,在某些對保密要求非常嚴格的場合有優勢。

布隆過濾器可以表示全集,其它任何資料結構都不能。

缺點

但是布隆過濾器的缺點和優點一樣明顯。誤算率(False Positive)是其中之一。随着存入的元素數量增加,誤算率随之增加(誤判補救方法是:再建立一個小的白名單,存儲那些可能被誤判的資訊)。但是如果元素數量太少,則使用散清單足矣。

另外,一般情況下不能從布隆過濾器中删除元素。我們很容易想到把位列陣變成整數數組,每插入一個元素相應的計數器加 1, 這樣删除元素時将計數器減掉就可以了。然而要保證安全的删除元素并非如此簡單。首先我們必須保證删除的元素的确在布隆過濾器裡面. 這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

三、使用 Guava 的布隆過濾器

1、添加依賴

Maven:

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>22</version>
    </dependency>
      

Gradle:

// https://mvnrepository.com/artifact/com.google.guava/guava
compile group: 'com.google.guava', name: 'guava', version: '22'
      

2、使用方法

建立 BloomFilter 對象,需要傳入 Funnel 對象,預估的元素個數,誤判率。

BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 1000,0.01);      

使用 put 方法添加元素:

filter.put("test");      

使用 mightContain 方法判斷元素是否存在:

filter.mightContain("test");      

3、例子

這個例子中我向布隆過濾器中添加了 10000000 條資料,将 fpp(誤判率)設定為 0.001(0.1%)。

public class BloomFilterTest {

    private static int insertions = 10000000;

    public static void main(String[] args) {

        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), insertions, 0.001);

        Set<String> sets = new HashSet<String>(insertions);

        List<String> lists = new ArrayList<String>(insertions);

        for (int i = 0; i < insertions; i++) {
            String uid = UUID.randomUUID().toString();
            bloomFilter.put(uid);
            sets.add(uid);
            lists.add(uid);
        }

        int right = 0;
        int wrong = 0;

        for (int i = 0; i < 10000; i++) {
            String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
            if (bloomFilter.mightContain(data)) {
                if (sets.contains(data)) {
                    right++;
                    continue;
                }
                wrong++;
            }
        }

        NumberFormat percentFormat = NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2);
        float percent = (float) wrong / 9900;
        float bingo = (float) (9900 - wrong) / 9900;

        System.out.println("在 " + insertions + " 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:" + right);
        System.out.println("在 " + insertions + " 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:" + wrong);
        System.out.println("命中率為:" + percentFormat.format(bingo) + ",誤判率為:" + percentFormat.format(percent));
    }

}      

經過我多次測試,執行結果中的誤判率基本保持在 0.1% 左右,誤差不會太大。

在 10000000 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:100
在 10000000 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:8
命中率為:99.92%,誤判率為:0.08%

在 10000000 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:100
在 10000000 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:9
命中率為:99.91%,誤判率為:0.09%

在 10000000 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:100
在 10000000 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:10
命中率為:99.9%,誤判率為:0.1%

在 10000000 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:100
在 10000000 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:15
命中率為:99.85%,誤判率為:0.15%

在 10000000 條資料中,判斷 100 實際存在的元素,布隆過濾器認為存在的數量為:100
在 10000000 條資料中,判斷 9900 實際不存在的元素,布隆過濾器誤認為存在的數量為:10
命中率為:99.9%,誤判率為:0.1%      

四、應用場景

利用布隆過濾器減少磁盤 IO 或者網絡請求,因為一旦一個值必定不存在的話,我們可以不用進行後續昂貴的查詢請求,比如以下場景:

1、大資料去重;

2、網頁爬蟲對 URL 的去重,避免爬取相同的 URL 位址;

3、反垃圾郵件,從數十億個垃圾郵件清單中判斷某郵箱是否垃圾郵箱;

4、緩存擊穿,将已存在的緩存放到布隆中,當黑客通路不存在的緩存時迅速傳回避免緩存及資料庫挂掉。

作者:Charles Zhang

出處:https://www.cnblogs.com/weisenz/

本站使用「署名 4.0 國際」創作共享協定,轉載請在文章明顯位置注明作者及出處。