1.引言

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

2.問題背景

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

3.散列表方法

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

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

顯然，這樣的存儲(chǔ)需求是不可行的，因?yàn)樗鼘?duì)內(nèi)存的要求太高。

4.布隆過(guò)濾器介紹

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

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

5.布隆過(guò)濾器原理

布隆過(guò)濾器由一個(gè)很長(zhǎng)的二進(jìn)制位數(shù)組和一系列隨機(jī)映射函數(shù)（哈希函數(shù)）組成。

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

插入元素

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

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

查詢?cè)?/h4>

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

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

6.計(jì)算布隆過(guò)濾器參數(shù)

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

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

假設(shè)我們?cè)试S的誤判率為0.01%，我們可以使用以下公式來(lái)計(jì)算m和K：

圖片

其中，n是集合中的元素?cái)?shù)量，p是允許的誤判率。

具體計(jì)算如下：

圖片

代入公式：

圖片

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

7.布隆過(guò)濾器的實(shí)現(xiàn)

下面是布隆過(guò)濾器的Java實(shí)現(xiàn)，包括初始化、添加元素和查詢?cè)氐拇a。

圖片

圖片

代碼說(shuō)明

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

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

END

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