1.引言

大家好，我是小米，一個熱愛分享技術(shù)的小伙伴。今天我們來聊一聊在實際工作中如何使用布隆過濾器（Bloom Filter）來處理大規(guī)模URL黑名單的存儲和查詢問題。

2.問題背景

假設(shè)我們有一個規(guī)模達到100億的黑名單URL集合，每個URL的長度為64字節(jié)。如何高效地存儲和查詢這個黑名單呢？

3.散列表方法

我們先考慮一下常規(guī)的散列表方法。如果使用HashMap來存儲這些URL：

• 每個URL 64字節(jié)
• 100億個URL需要存儲：100億 * 64B = 640GB

顯然，這樣的存儲需求是不可行的，因為它對內(nèi)存的要求太高。

4.布隆過濾器介紹

這時候，我們可以引入布隆過濾器，它是一種高效的概率型數(shù)據(jù)結(jié)構(gòu)，用于檢測一個元素是否屬于一個集合。布隆過濾器具有以下特點：

• 占用空間小
• 查詢速度快
• 允許一定的誤判（即可能認為不存在的元素存在，但不會把存在的元素認為不存在）

5.布隆過濾器原理

布隆過濾器由一個很長的二進制位數(shù)組和一系列隨機映射函數(shù)（哈希函數(shù)）組成。

• 位數(shù)組：每個元素占用1 bit，初始時所有位都設(shè)為0。
• 哈希函數(shù)：假設(shè)有K個哈希函數(shù)，每個函數(shù)將輸入元素映射為位數(shù)組的一個下標。

插入元素

當(dāng)一個元素加入布隆過濾器時，執(zhí)行以下步驟：

• 使用K個哈希函數(shù)對元素進行哈希計算，得到K個哈希值。
• 將位數(shù)組中對應(yīng)哈希值位置的bit設(shè)為1。

查詢元素

查詢一個元素是否在布隆過濾器中時，執(zhí)行以下步驟：

1. 使用K個哈希函數(shù)對查詢元素進行哈希計算，得到K個哈希值。
2. 檢查位數(shù)組中對應(yīng)哈希值位置的bit是否都為1。如果都為1，則認為該元素存在；如果有一個為0，則認為該元素不存在。

6.計算布隆過濾器參數(shù)

為了更好地理解布隆過濾器的存儲效率，我們需要計算以下參數(shù)：

• 位數(shù)組長度（m）：我們需要選擇一個合適的位數(shù)組長度來保證較低的誤判率。
• 哈希函數(shù)數(shù)量（K）：哈希函數(shù)的數(shù)量也需要根據(jù)集合大小和位數(shù)組長度來確定。

假設(shè)我們允許的誤判率為0.01%，我們可以使用以下公式來計算m和K：

圖片

其中，n是集合中的元素數(shù)量，p是允許的誤判率。

具體計算如下：

圖片

代入公式：

圖片

通過計算，我們得出位數(shù)組的長度為287億bit（約合35.88GB），需要20個哈希函數(shù)。這樣，布隆過濾器的內(nèi)存占用從原來的640GB大幅減少到了35.88GB，且具有較高的查詢效率。

7.布隆過濾器的實現(xiàn)

下面是布隆過濾器的Java實現(xiàn)，包括初始化、添加元素和查詢元素的代碼。

圖片

圖片

代碼說明

• BitSet：用于存儲位數(shù)組。
• MessageDigest：用于生成哈希值。
• add：將一個URL添加到布隆過濾器中。
• check：檢查一個URL是否存在于布隆過濾器中。
• getHash：生成哈希值，并結(jié)合種子（seed）確保多個哈希函數(shù)的實現(xiàn)。
• intToBytes：將整數(shù)轉(zhuǎn)換為字節(jié)數(shù)組，用于哈希函數(shù)的種子。

這個實現(xiàn)使用了MD5哈希函數(shù)，可以根據(jù)需求選擇其他哈希函數(shù)。通過調(diào)整位數(shù)組大小和哈希函數(shù)數(shù)量，可以在存儲效率和誤判率之間取得平衡。

END

布隆過濾器作為一種高效的概率型數(shù)據(jù)結(jié)構(gòu)，能夠在大規(guī)模數(shù)據(jù)集上實現(xiàn)高效的存儲和查詢，特別適用于URL黑名單這樣的場景。通過合理地選擇位數(shù)組長度和哈希函數(shù)數(shù)量，我們可以在保證較低誤判率的前提下，大幅減少內(nèi)存使用。