Bloom Filter 布隆過濾器

目錄

• • • Bloom Filter簡介
    • 布隆過濾器的原理
    • 布隆過濾器的實作
    • • 使用guava實作
      • 使用redis實作

Bloom Filter簡介

Bloom Filter 布隆過濾器，由一個叫布隆的小夥子提出，故而用他的名字來命名，可以判斷元素是否在指定集合中。

常見的應用場景

• 避免緩存擊穿
• 爬蟲：過濾新抓取到的url，已抓取存儲的就不再處理
• 黑白名單：過濾垃圾郵件（檢測發件郵箱是否在垃圾郵箱集合中），攔截騷擾電話（檢測手機号是否在指定号碼庫中）等等
• 過濾使用者：已簽到、未簽到，是否為新使用者、是否活躍。

優點

• 使用二進制向量（數組），記憶體占用極少，空間效率高，存儲集合占用的空間比哈希表小得多
• 存儲、查詢元素效率高，查詢花費的時間比一般算法少得多

缺點

• 有一定的誤判率。可以判斷某個資料一定不在集合中或者可能在集合中（也可能不在集合中），可能在集合中（也可能不在）這是必然事件，肯定是正确判斷；而一定在集合中則可能存在誤判，布隆過濾器判定該資料一定不在集合中，但實際可能在集合中。
• 删除困難，加載集合後難以删除集合中的元素

bloom filter能做到時間、空間上的高效，是以犧牲判斷的準确率、删除的便利性為代價的。

布隆過濾器的原理

布隆過濾器由一串很長的二進制向量和一系列随機映射函數組成，二進制向量可以将看做一個二進制數組，存放的元素是0、1，初始值預設為0。

當一個元素被加入集合時，通過K個散列函數将這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，如果這些點有任何一個0，則被檢元素一定不在集合中；如果都是1，則被檢元素可能在集合中。

Bloom Filter跟單哈希函數Bit-Map不同之處在于：Bloom Filter使用了k個哈希函數，每個資料跟k個bit對應。進而降低了沖突的機率。

使用bloom filter時，需要預估集合資料量n、确定期望的誤判率fpp。誤判指的是布隆過濾器判斷為一定不在集合中，而實際可能在集合中。

布隆過濾器的實作

布隆過濾器隻是一個理論，有多種實作方式，常見的方式有2種

• 使用google開源的guava實作
• 使用redis實作

guava使用本地記憶體存儲資料，如果集合元素數量級較大，會占用很大一部分堆記憶體，此時可以考慮使用專業的記憶體型伺服器redis，但與redis互動有網絡通信的時間開銷，初始化布隆過濾器時添加集合元素極慢，資料判斷也比guava慢一些。

使用guava實作

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1.1-jre</version>
</dependency> 
           

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * 使用Guava實作的BloomFilter
 */
public class GuavaBloomFilter {

    /**
     * 預計插入次數（集合中元素的預估數量），此處為 1百萬
     */
    private static final int expectedInsertions = 1000000;

    /**
     * 期待的誤判率，隻能為 (0,1) 上的小數，預設時預設為 0.03 即 3% 判斷100個資料大概有3個會誤判
     * 數值越大，對判斷結果的準确性要求越低，判斷速度越快，誤判發生的可能性越大、發生的誤判數量越多
     */
    private static final double fpp = 0.001;

    /**
     * 布隆過濾器，泛型指定集合元素的類型
     */
    // private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions);
    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

    public static void main(String[] args) {
        //加載集合元素
        for (int i = 0; i < expectedInsertions; i++) {
            bf.put(i);
        }
        System.out.println("集合元素加載完畢");

        //判斷檢測
        int errCount = 0;
        for (int i = 0; i < expectedInsertions + 1000; i++) {
            //mightContain()判斷元素是否可能在集合中，false——一定不在集合中（可能為誤判），true——可能在集合中也可能不在
            if (!bf.mightContain(i)) {
                System.out.printf("%d可能為誤判\n", i);
                errCount++;
            }
        }
        System.out.printf("判斷檢測完畢，可能的誤判次數為%d", errCount);
    }

}
           

使用redis實作

redis可通過Bitmap實作布隆過濾器，Bitmap是在字元串類型（Simple Dynamic String，SDS）之上定義的與比特相關的一系列操作，SDS作為bit數組，redis提供了setbit、getbit、bitcount等指令來操作二進制位。

jedis、spring data redis屬于操作redis的基礎類庫，引入基礎類庫自己實作布隆過濾器很麻煩，可以使用現成的輪子Redisson。Redisson是java中操作redis的一個類庫，提供了更上層的封裝，功能強大。

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.16.1</version>
</dependency>
           

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * 基于redis實作的布隆過濾器
 */
public class RedissonBloomFilter {

    /**
     * 預計插入次數（集合中元素的預估數量），此處為 1萬
     */
    private static final long expectedInsertions = 10000L;

    /**
     * 期待的誤判率，(0,1)上的小數
     * 數值越大，對判斷結果的準确性要求越低，判斷速度越快，誤判發生的可能性越大、發生的誤判數量越多
     */
    private static final double falseProbability = 0.001;

    /**
     * 擷取RedissonClient
     */
    public static RedissonClient getRedissonClient() {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        return Redisson.create(config);
    }

    public static void main(String[] args) {
        RedissonClient redissonClient = getRedissonClient();
        //會把布隆過濾器存儲為一個鍵值對，所有的元素作為一個string進行儲存，參數指定key的名稱，泛型指定集合元素的類型
        RBloomFilter<Integer> bf = redissonClient.getBloomFilter("xxx");
        //初始化布隆過濾器，指定預計插入次數、誤判率
        bf.tryInit(expectedInsertions, falseProbability);

        //加載集合元素
        for (int i = 0; i < expectedInsertions; i++) {
            bf.add(i);
        }
        System.out.println("集合元素加載完畢");

        //判斷檢測
        int errCount = 0;
        for (int i = 0; i < expectedInsertions + 1000; i++) {
            //contains判斷元素是否可能在集合中，false——一定不在集合中（可能為誤判），true——可能在集合中也可能不在
            if (!bf.contains(i)) {
                System.out.printf("%d可能為誤判\n", i);
                errCount++;
            }
        }
        System.out.printf("判斷檢測完畢，可能的誤判次數為%d", errCount);
    }

}
           

以上擷取的RedissonClient是單機版redis的，如果是redis叢集，可以參考https://blog.csdn.net/chy_18883701161/article/details/106380296