布隆過濾器是一個精巧而且經典的數據結構。

你可能沒想到：RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 這些知名項目中都有布隆過濾器的身影。

對于后端程序員來講，學習和理解布隆過濾器有很大的必要性。來吧，我們一起品味布隆過濾器的設計之美。

1 緩存穿透

我們先來看一個商品服務查詢詳情的接口：

public?Product?queryProductById?(Long?id){
???//?查詢緩存
???Product?product?=?queryFromCache(id);
???if(product?!=?null)?{
?????return?product?;
???}
???//?從數據庫查詢
???product?=?queryFromDataBase(id);
???if(product?!=?null)?{
???????saveCache(id?,?product);
???}
???return?product;
}

?

?

假設此商品既不存儲在緩存中，也不存在數據庫中，則沒有辦法回寫緩存 ，當有類似這樣大量的請求訪問服務時，數據庫的壓力就會極大。

這是一個典型的緩存穿透的場景。

為了解決這個問題呢，通常我們可以向分布式緩存中寫入一個過期時間較短的空值占位，但這樣會占用較多的存儲空間，性價比不足。

問題的本質是："如何以極小的代價檢索一個元素是否在一個集合中 ？"

我們的主角布隆過濾器 出場了，它就能游刃有余的平衡好時間和空間兩種維度 。

2 原理解析

布隆過濾器 （英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量 和一系列隨機映射函數 。

布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率 和查詢時間 都遠遠超過一般的算法 ，缺點是有一定的誤識別率和刪除困難。

布隆過濾器的原理：當一個元素被加入集合時，通過 K 個散列函數將這個元素映射成一個位數組中的 K 個點，把它們置為 1。檢索時，我們只要看看這些點是不是都是 1 就（大約）知道集合中有沒有它了：如果這些點有任何一個 0 ，則被檢元素一定不在 ；如果都是 1 ，則被檢元素很可能在 。

簡單來說就是準備一個長度為 m 的位數組并初始化所有元素為 0，用 k 個散列函數對元素進行 k 次散列運算跟 len (m) 取余得到 k 個位置并將 m 中對應位置設置為 1。

如上圖，位數組的長度是８，散列函數個數是 3，先后保持兩個元素ｘ，ｙ。這兩個元素都經過三次哈希函數生成三個哈希值，并映射到位數組的不同的位置，并置為1。元素 x 映射到位數組的第０位，第４位，第７位，元素ｙ映射到數組的位數組的第１位，第４位，第６位。

保存元素 x 后，位數組的第4位被設置為1之后，在處理元素 y 時第4位會被覆蓋，同樣也會設置為 1。

當布隆過濾器保存的元素越多 ，被置為 1 的 bit 位也會越來越多 ，元素 x 即便沒有存儲過，假設哈希函數映射到位數組的三個位都被其他值設置為 1 了，對于布隆過濾器的機制來講，元素 x 這個值也是存在的，也就是說布隆過濾器存在一定的誤判率 。

▍ 誤判率

布隆過濾器包含如下四個屬性：

k : 哈希函數個數

m : 位數組長度

n : 插入的元素個數

p : 誤判率

若位數組長度太小則會導致所有 bit 位很快都會被置為 1 ，那么檢索任意值都會返回”可能存在“ ， 起不到過濾的效果。位數組長度越大，則誤判率越小。

同時，哈希函數的個數也需要考量，哈希函數的個數越大，檢索的速度會越慢，誤判率也越小，反之，則誤判率越高。

從張圖我們可以觀察到相同位數組長度的情況下，隨著哈希函數的個人的增長，誤判率顯著的下降。

誤判率 p 的公式是

k 次哈希函數某一 bit 位未被置為 1 的概率為

插入 n 個元素后某一 bit 位依舊為 0 的概率為

那么插入 n 個元素后某一 bit 位置為1的概率為

整體誤判率為 當 m 足夠大時，誤判率會越小，該公式約等于

我們會預估布隆過濾器的誤判率 p 以及待插入的元素個數 n 分別推導出最合適的位數組長度 m 和 哈希函數個數 k。

▍ 布隆過濾器支持刪除嗎

布隆過濾器其實并不支持刪除元素，因為多個元素可能哈希到一個布隆過濾器的同一個位置，如果直接刪除該位置的元素，則會影響其他元素的判斷。

▍ 時間和空間效率

布隆過濾器的空間復雜度為 O(m) ，插入和查詢時間復雜度都是 O(k) 。存儲空間和插入、查詢時間都不會隨元素增加而增大。空間、時間效率都很高。

▍哈希函數類型

Murmur3，FNV 系列和 Jenkins 等非密碼學哈希函數適合，因為 Murmur3 算法簡單，能夠平衡好速度和隨機分布，很多開源產品經常選用它作為哈希函數。

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實現的后臺管理系統 + 用戶小程序，支持 RBAC 動態權限、多租戶、數據權限、工作流、三方登錄、支付、短信、商城等功能

項目地址：https://github.com/YunaiV/yudao-cloud

視頻教程：https://doc.iocoder.cn/video/

3 Guava實現

Google Guava是 Google 開發和維護的開源 Java開發庫，它包含許多基本的工具類，例如字符串處理、集合、并發工具、I/O和數學函數等等。

1、添加Maven依賴

????com.google.guava
????guava
????31.0.1-jre<

2、創建布隆過濾器

BloomFilter?filter?=?BloomFilter.create(
??//Funnel?是一個接口，用于將任意類型的對象轉換為字節流，
??//以便用于布隆過濾器的哈希計算。
??Funnels.integerFunnel(),?
??10000,??//?插入數據條目數量
??0.001??//?誤判率
);

3、添加數據

@PostConstruct
public?void?addProduct()?{
????logger.info("初始化布隆過濾器數據開始");
????//插入4個元素
?????filter.put(1L);
?????filter.put(2L);
?????filter.put(3L);
?????filter.put(4L);
?????logger.info("初始化布隆過濾器數據結束");
}

4、判斷數據是否存在

public?boolean?maycontain(Long?id)?{
????return?filter.mightContain(id);
}

接下來，我們查看 Guava 源碼中布隆過濾器是如何實現的 ？

static??BloomFilter?create(Funnel?funnel,?long?expectedInsertions,?double?fpp,?BloomFilter.Strategy?strategy)?{
????//?省略部分前置驗證代碼?
????//?位數組長度
????long?numBits?=?optimalNumOfBits(expectedInsertions,?fpp);
????//?哈希函數次數
????int?numHashFunctions?=?optimalNumOfHashFunctions(expectedInsertions,?numBits);
????try?{
??????return?new?BloomFilter(
????????????????????new?LockFreeBitArray(numBits),?
????????????????????numHashFunctions,?
????????????????????funnel,
????????????????????strategy
??????);
????}?catch?(IllegalArgumentException?e)?{
??????throw?new?IllegalArgumentException("Could?not?create?BloomFilter?of?"?+?numBits?+?"?bits",?e);
????}
}
//計算位數組長度
//n:插入的數據條目數量
//p:期望誤判率
@VisibleForTesting
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)));
}

//?計算哈希次數
@VisibleForTesting
static?int?optimalNumOfHashFunctions(long?n,?long?m)?{
????//?(m?/?n)?*?log(2),?but?avoid?truncation?due?to?division!
????return?Math.max(1,?(int)?Math.round((double)?m?/?n?*?Math.log(2)));
}

Guava 的計算位數組長度和哈希次數和原理解析這一節展示的公式保持一致。

重點來了，Bloom filter 是如何判斷元素存在的 ？

方法名就非常有 google 特色 ， ?”mightContain “ 的中文表意是：”可能存在“ 。方法的返回值為 true ，元素可能存在，但若返回值為 false ，元素必定不存在。

public??boolean?mightContain(
????@ParametricNullness?T?object,
????//Funnel?是一個接口，用于將任意類型的對象轉換為字節流，
????//以便用于布隆過濾器的哈希計算。
????Funnel?funnel,??
????//用于計算哈希值的哈希函數的數量
????int?numHashFunctions,
????//位數組實例，用于存儲布隆過濾器的位集
????LockFreeBitArray?bits)?{
??long?bitSize?=?bits.bitSize();
??//使用?MurmurHash3?哈希函數計算對象?object?的哈希值，
??//并將其轉換為一個 byte 數組。
??byte[]?bytes?=?Hashing.murmur3_128().hashObject(object,?funnel).getBytesInternal();
??long?hash1?=?lowerEight(bytes);
??long?hash2?=?upperEight(bytes);

??long?combinedHash?=?hash1;
??for?(int?i?=?0;?i?

	3 Redisson實現

	Redisson 是一個用 Java 編寫的 Redis 客戶端，它實現了分布式對象和服務，包括集合、映射、鎖、隊列等。Redisson的API簡單易用，使得在分布式環境下使用Redis 更加容易和高效。

	1、添加Maven依賴

???org.redisson
???redisson
???3.16.1



	2、配置 Redisson 客戶端
@Configuration
public?class?RedissonConfig?{

?Bean
?public?RedissonClient?redissonClient()?{
????Config?config?=?new?Config();
????config.useSingleServer().setAddress("redis://localhost:6379");
????return?Redisson.create(config);
?}
?
}3、初始化

	?

	?
RBloomFilter?bloomFilter?=?redissonClient.
??????????????????????????????????????getBloomFilter("myBloomFilter");
//10000表示插入元素的個數，0.001表示誤判率
bloomFilter.tryInit(10000,?0.001);
//插入4個元素
bloomFilter.add(1L);
bloomFilter.add(2L);
bloomFilter.add(3L);
bloomFilter.add(4L);
4、判斷數據是否存在
public?boolean?mightcontain(Long?id)?{
????return?bloomFilter.contains(id);
}


	好，我們來從源碼分析 Redisson 布隆過濾器是如何實現的 ？
public?boolean?tryInit(long?expectedInsertions,?double?falseProbability)?{
????//?位數組大小
????size?=?optimalNumOfBits(expectedInsertions,?falseProbability);
????//?哈希函數次數
????hashIterations?=?optimalNumOfHashFunctions(expectedInsertions,?size);
????CommandBatchService?executorService?=?new?CommandBatchService(commandExecutor);
????//?執行?Lua腳本，生成配置
????executorService.evalReadAsync(configName,?codec,?RedisCommands.EVAL_VOID,
????????????"local?size?=?redis.call('hget',?KEYS[1],?'size');"?+
????????????????????"local?hashIterations?=?redis.call('hget',?KEYS[1],?'hashIterations');"?+
????????????????????"assert(size?==?false?and?hashIterations?==?false,?'Bloom?filter?config?has?been?changed')",
????????????????????Arrays.