往期內(nèi)容：

面試官問我：Redis處理點(diǎn)贊，如果瞬時(shí)涌入大量用戶點(diǎn)贊（千萬(wàn)級(jí)），應(yīng)當(dāng)如何進(jìn)行處理？【后端八股文（1）】-CSDN博客

本文為【布隆過濾器八股文合集】初版，后續(xù)還會(huì)進(jìn)行優(yōu)化更新，歡迎大家評(píng)論交流~

大家第一眼看到這個(gè)標(biāo)題，不知道心中是否有答案了？在面試當(dāng)中，面試官經(jīng)常對(duì)項(xiàng)目亮點(diǎn)進(jìn)行深挖，來考察你對(duì)這個(gè)項(xiàng)目亮點(diǎn)的理解以及思考！這個(gè)時(shí)候，你如果可以回答出面試官的問題，甚至是主動(dòng)說出自己的思考，那在面試中是大大加分的~

布隆過濾器

具體實(shí)現(xiàn)

（1）使用開源的谷歌開源工具類Guava

Spring Boot(七十四)：集成Guava 庫(kù)實(shí)現(xiàn)布隆過濾器（Bloom Filter）_guava bloomfilter.create 設(shè)置-CSDN博客

（2） 開源Redisson的RBloomFilter

（3） Redis官方提供布隆過濾器插件

（4） Redis提供的bitMap，需要自己實(shí)現(xiàn)

各自的缺點(diǎn)：

Guava存儲(chǔ)在機(jī)器當(dāng)中，只適合單機(jī)，不適合分布式環(huán)境當(dāng)中；

Redis插件需要復(fù)雜的配置和高成本支持；

Redis的bitMap需要額外自己去實(shí)現(xiàn)；

Redisson 連接Redis即可使用

底層原理？/布隆過濾器如何判斷那個(gè)字段在緩存中的呢？

一種數(shù)據(jù)結(jié)構(gòu)，用于判斷一個(gè)元素是否在一個(gè)集合中。它是一種概率型算法，能夠快速判斷一個(gè)元素是否在一個(gè)集合中，但不能保證 100% 準(zhǔn)確。
布隆過濾器通常用于大數(shù)據(jù)場(chǎng)景中，例如垃圾郵件過濾、網(wǎng)絡(luò)爬蟲中的 URL 去重等。它的優(yōu)點(diǎn)是快速判斷一個(gè)元素是否在集合中，時(shí)間復(fù)雜度為 O(1)，空間復(fù)雜度為 O(n)，可以滿足高并發(fā)場(chǎng)景的需求。

原理（一個(gè)元素多個(gè)哈希函數(shù)）
將一個(gè)元素通過多個(gè)哈希函數(shù)計(jì)算得到多個(gè)哈希值，然后將這些哈希值對(duì)應(yīng)到一個(gè)長(zhǎng)度為 m 的位數(shù)組上，將位數(shù)組中對(duì)應(yīng)位置置為 1。當(dāng)判斷一個(gè)元素是否在集合中時(shí)，需要再次計(jì)算多個(gè)哈希值，然后判斷位數(shù)組中對(duì)應(yīng)位置是否為 1，如果都為 1 則認(rèn)為元素在集合中，否則認(rèn)為元素不在集合中。

或者

①初始化：首先，布隆過濾器會(huì)初始化一個(gè)位數(shù)組，所有位都被設(shè)置為0。

②添加元素：當(dāng)要將一個(gè)元素加入到布隆過濾器中時(shí)，將該元素通過多個(gè)哈希函數(shù)計(jì)算出多個(gè)哈希值，然后將位數(shù)組中對(duì)應(yīng)的位置設(shè)置為1。

③查詢?cè)?#xff1a;當(dāng)要查詢一個(gè)元素是否存在于布隆過濾器中時(shí)，將該元素通過相同的哈希函數(shù)計(jì)算出多個(gè)哈希值，然后檢查對(duì)應(yīng)的位數(shù)組位置是否都為1。如果所有位置都為1，則該元素可能存在于布隆過濾器中；如果存在任何一個(gè)位置為0，則該元素一定不存在于布隆過濾器

會(huì)發(fā)生錯(cuò)誤，可能把不存在的認(rèn)為存在，但是不會(huì)把存在的認(rèn)為不存在。

為什么需要多個(gè)hash函數(shù)，有多少個(gè)bitmap實(shí)現(xiàn)的？/ 為什么布隆過濾器為什么要有5個(gè)特殊值？ 布隆過濾器只有一個(gè)特殊值可以嗎？

為了降低布隆過濾器的誤判率

優(yōu)點(diǎn)

1. 空間效率高：布隆過濾器只需要使用一個(gè)位數(shù)組和多個(gè)哈希函數(shù)來表示集合，相比使用傳統(tǒng)的哈希表或者樹等數(shù)據(jù)結(jié)構(gòu)，布隆過濾器的空間占用更小。

2. 查詢效率高：布隆過濾器通過多個(gè)哈希函數(shù)將元素映射到多個(gè)位置，所以查詢一個(gè)元素只需要進(jìn)行幾次位操作，時(shí)間復(fù)雜度較低。

3. 可擴(kuò)展性好：布隆過濾器支持動(dòng)態(tài)添加元素，可以根據(jù)需要進(jìn)行擴(kuò)展。

布隆過濾器有什么缺點(diǎn)？

1、誤判：可能將某個(gè)不存在的元素判斷為存在

“布隆過濾器說某個(gè)元素存在，則大概率在。布隆過濾器說某個(gè)元素不在，則一定不在”

2、無法刪除： 不支持元素的刪除：由于多個(gè)元素可能映射到同一個(gè)位，所以無法準(zhǔn)確地刪除一個(gè)元素，只能通過重新構(gòu)建布隆過濾器來實(shí)現(xiàn)。

布隆過濾器的元素能否刪除？

不能，因?yàn)閯h除一個(gè)元素會(huì)影響其他元素的判斷結(jié)果

布隆過濾器怎么刪除key？

（1）重新構(gòu)建布隆過濾器（ Scalable Bloom Filter 原理 ）

流程如下：

① 創(chuàng)建一個(gè)新的空布隆過濾器

② 將原布隆過濾器中的所有元素（除了要?jiǎng)h除的元素）重新添加到新的布隆過濾器中

③ 用新的布隆過濾器替換原有的布隆過濾器

（2）使用計(jì)數(shù)器

在原有基礎(chǔ)上，加上計(jì)數(shù)器，當(dāng)元素加入時(shí)，計(jì)數(shù)器加一，反之，計(jì)數(shù)器減一。當(dāng)計(jì)數(shù)器為零時(shí)，key被刪除。

布隆過濾器如何提高容錯(cuò)能力？/ 怎么降低誤判率 / 布隆過濾器的01數(shù)組發(fā)生哈希沖突怎么辦？

布隆過濾器本質(zhì)上就是哈希函數(shù) + 位圖
減少誤判的兩種方法：① 增加哈希函數(shù)的數(shù)量；② 增加位圖（位數(shù)組）的長(zhǎng)度

布隆過濾器如何實(shí)現(xiàn)？/ 讓你設(shè)計(jì)布隆過濾器，你會(huì)怎么設(shè)計(jì)？/ 布隆過濾器如何計(jì)算？

1. 初始化一個(gè)全 0 的位數(shù)組
2. 定義 k 個(gè)獨(dú)立的哈希函數(shù)
3. 對(duì)于每個(gè)要插入的元素:

使用 k 個(gè)哈希函數(shù)計(jì)算出 k 個(gè)索引

將位數(shù)組中對(duì)應(yīng)的 k 個(gè)位置設(shè)為 1

???? 4. 查詢?cè)貢r(shí):

使用 k 個(gè)哈希函數(shù)計(jì)算出 k 個(gè)索引

檢查位數(shù)組中對(duì)應(yīng)的 k 個(gè)位置是否全為 1，如果有一個(gè)為 0 則表示元素不存在

布隆過濾器如何評(píng)估大小？/ 考慮過對(duì)于上億的數(shù)據(jù)布隆過濾器的數(shù)據(jù)量會(huì)很大嗎？

布隆過濾器的主要參數(shù)包括：位數(shù)組長(zhǎng)度m、哈希函數(shù)個(gè)數(shù)k、預(yù)計(jì)要插入的元素個(gè)數(shù)n

其中p為預(yù)期的最大誤判率（一般為： 0.1%或更低 ）

m = -(n * ln(p)) / (ln(2)^2)
k = (m/n) * ln(2)

以1億為例，

m = -(100,000,000 * ln(0.001)) / (ln(2)^2) ≈ 479,430,000

即需要一個(gè)長(zhǎng)度為約 4.79 億比特的位數(shù)組

計(jì)算哈希函數(shù)的數(shù)量:

k = (m/n) * ln(2) ≈ 7

所以需要使用 7 個(gè)相互獨(dú)立的哈希函數(shù)

已知1 字節(jié) = 8 比特

那么位數(shù)組所需的存儲(chǔ)空間為:
479,430,000 / 8 = 59,928,750 字節(jié)

再轉(zhuǎn)換為 GB:
59,928,750 / (1024 * 1024 * 1024) = 55.85 GB

綜上所述，對(duì)于存儲(chǔ) 1 億個(gè)元素,允許 0.1% 最大誤判率的布隆過濾器,需要約 55.85 GB 的存儲(chǔ)空間。

千萬(wàn)級(jí)數(shù)據(jù)用布隆過濾器初始化的時(shí)候 redis 太慢了，有沒有什么好方法？

（1）分批初始化

將大量數(shù)據(jù)分批次進(jìn)行初始化,每次初始化一部分

這樣可以減輕 Redis 單次操作的壓力

可以考慮利用多線程或異步任務(wù)的方式來加速

（2）使用本地內(nèi)存初始化

先在本地內(nèi)存中構(gòu)建好布隆過濾器

然后一次性將整個(gè)布隆過濾器數(shù)據(jù)同步到 Redis 中

這樣可以利用內(nèi)存的高速計(jì)算能力來加速初始化

（3）采用分布式架構(gòu)

將布隆過濾器拆分到多個(gè) Redis 實(shí)例中

每個(gè)實(shí)例負(fù)責(zé)部分?jǐn)?shù)據(jù)的初始化和查詢

這樣可以利用分布式計(jì)算的優(yōu)勢(shì)來提升性能

布隆過濾器在異常情況下，也會(huì)出現(xiàn)緩存擊穿，怎么考慮的？

使用多級(jí)緩存結(jié)構(gòu)：

除了布隆過濾器,還可以使用其他緩存手段,形成多級(jí)緩存

當(dāng)布隆過濾器判斷數(shù)據(jù)不存在時(shí),可以嘗試訪問其他緩存層

實(shí)現(xiàn)布隆過濾器（1.增量數(shù)據(jù)怎么放入布隆過濾器；2.怎么合并兩個(gè)布隆過濾器）？

（1）當(dāng)有新的數(shù)據(jù)需要加入時(shí),可以采用以下方法:

創(chuàng)建一個(gè)新的、更大的布隆過濾器。

將原有的布隆過濾器中的所有數(shù)據(jù) hash 并設(shè)置到新的布隆過濾器中。

再將新的數(shù)據(jù) hash 并設(shè)置到新的布隆過濾器中。

（2）合并兩個(gè)布隆過濾器的具體做法

確保兩個(gè)布隆過濾器的大小（位數(shù)組長(zhǎng)度）相同。

對(duì)兩個(gè)布隆過濾器的對(duì)應(yīng)位進(jìn)行邏輯或操作(OR),得到合并后的新布隆過濾器。

布隆過濾器的缺陷（不能擴(kuò)容和刪除），目前有沒有能夠利用到的數(shù)據(jù)結(jié)構(gòu)來做一個(gè)替代呢？

（1）可擴(kuò)容：

Scalable Bloom Filter (SBF)：（動(dòng)態(tài)擴(kuò)容原理）重新計(jì)算新的布隆過濾器，將舊的過濾器遷移至新的

（2）可刪除：

Counting Bloom Filter (CBF)：（計(jì)數(shù)布隆過濾器）插入的時(shí)候，會(huì)將該位對(duì)應(yīng)的值+1，刪除則減一

場(chǎng)景題：有千萬(wàn)級(jí)數(shù)據(jù)，如何判斷一個(gè)整數(shù)是否存在?

使用布隆過濾器

場(chǎng)景題：10億數(shù)據(jù)，5億內(nèi)存，如何查找重復(fù)元素？

布隆過濾器

場(chǎng)景題：大數(shù)據(jù)量的情況下如何進(jìn)行去重？

布隆過濾器

場(chǎng)景題：布隆過濾器使用一年后和一年前相比有什么不同？

元素個(gè)數(shù)增加,導(dǎo)致誤判率上升

需要調(diào)整參數(shù)來重新控制誤判率

內(nèi)存占用顯著增加,可能影響系統(tǒng)性能

?---------------------------------------------------------------------------------------------------------------

?更多精彩內(nèi)容以及一手消息請(qǐng)關(guān)注公眾號(hào)：絕命Coding

公眾號(hào)私信回復(fù)“免費(fèi)資料”可免費(fèi)獲取簡(jiǎn)歷模板以及技術(shù)亮點(diǎn)合集等免費(fèi)資料