1. 簡(jiǎn)介

客戶(hù)端：這個(gè)key存在嗎？

服務(wù)器：不存在/不知道

本質(zhì)上，布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，是一種比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)。它的特點(diǎn)是高效地插入和查詢(xún)。但我們要檢查一個(gè)key是否在某個(gè)結(jié)構(gòu)中存在時(shí)，通過(guò)使用布隆過(guò)濾器，我們可以快速了解到「這個(gè)key一定不存在或者可能存在」。相比于傳統(tǒng)的List、Set、Map這些數(shù)據(jù)結(jié)構(gòu)，它更加高效、占用的空間也越少，但是它返回的結(jié)果是概率性的，是不確切的。

布隆過(guò)濾器僅用于測(cè)試集合中的成員資格。使用布隆過(guò)濾器的經(jīng)典示例是減少對(duì)不存在的密鑰的昂貴磁盤(pán)（或網(wǎng)絡(luò)）查找。正如我們看到的那樣，布隆過(guò)濾器可以在O（k）恒定時(shí)間內(nèi)搜索密鑰，其中k是哈希函數(shù)的數(shù)量，測(cè)試密鑰的不存在將非常快。

2. 應(yīng)用場(chǎng)景

2.1 緩存穿透

為了提高訪問(wèn)效率，我們會(huì)將一些數(shù)據(jù)放在Redis緩存中。當(dāng)進(jìn)行數(shù)據(jù)查詢(xún)時(shí)，可以先從緩存中獲取數(shù)據(jù)，無(wú)需讀取數(shù)據(jù)庫(kù)。這樣可以有效地提升性能。
在數(shù)據(jù)查詢(xún)時(shí)，首先要判斷緩存中是否有數(shù)據(jù)，如果有數(shù)據(jù)，就直接從緩存中獲取數(shù)據(jù)。
但如果沒(méi)有數(shù)據(jù)，就需要從數(shù)據(jù)庫(kù)中獲取數(shù)據(jù)，然后放入緩存。如果大量訪問(wèn)都無(wú)法命中緩存，會(huì)造成數(shù)據(jù)庫(kù)要扛較大壓力，從而導(dǎo)致數(shù)據(jù)庫(kù)崩潰。而使用布隆過(guò)濾器，當(dāng)訪問(wèn)不存在的緩存時(shí)，可以迅速返回避免緩存或者DB crash。

2.2 判斷某個(gè)數(shù)據(jù)是否在海量數(shù)據(jù)中存在

HBase中存儲(chǔ)著非常海量數(shù)據(jù)，要判斷某個(gè)ROWKEYS、或者某個(gè)列是否存在，使用布隆過(guò)濾器，可以快速獲取某個(gè)數(shù)據(jù)是否存在。但有一定的誤判率。但如果某個(gè)key不存在，一定是準(zhǔn)確的。

3. HashMap的問(wèn)題

要判斷某個(gè)元素是否存在其實(shí)用HashMap效率是非常高的。HashMap通過(guò)把值映射為HashMap的Key，這種方式可以實(shí)現(xiàn)O(1)常數(shù)級(jí)時(shí)間復(fù)雜度。
但是，如果存儲(chǔ)的數(shù)據(jù)量非常大的時(shí)候（例如：上億的數(shù)據(jù)），HashMap將會(huì)耗費(fèi)非常大的內(nèi)存大小。而且也根本無(wú)法一次性將海量的數(shù)據(jù)讀進(jìn)內(nèi)存。

4. 理解布隆過(guò)濾器

工作原理圖：

布隆過(guò)濾器是一個(gè)bit數(shù)組或者稱(chēng)為一個(gè)bit二進(jìn)制向量
這個(gè)數(shù)組中的元素存的要么是0、要么是1
k個(gè)hash函數(shù)都是彼此獨(dú)立的，并將每個(gè)hash函數(shù)計(jì)算后的結(jié)果對(duì)數(shù)組的長(zhǎng)度m取模，并將對(duì)一個(gè)的bit設(shè)置為1（藍(lán)色單元格）
我們將每個(gè)key都按照這種方式設(shè)置單元格，就是「布隆過(guò)濾器」

5. 根據(jù)布隆過(guò)濾器查詢(xún)?cè)?/h2>

假設(shè)輸入一個(gè)key，我們使用之前的k個(gè)hash函數(shù)求哈希，得到k個(gè)值
判斷這k個(gè)值是否都為藍(lán)色，如果有一個(gè)不是藍(lán)色，那么這個(gè)key一定不存在
如果都有藍(lán)色，那么key是可能存在（布隆過(guò)濾器會(huì)存在誤判）
因?yàn)槿绻斎雽?duì)象很多，而集合比較小的情況，會(huì)導(dǎo)致集合中大多位置都會(huì)被描藍(lán)，那么檢查某個(gè)key時(shí)候?yàn)樗{(lán)色時(shí)，剛好某個(gè)位置正好被設(shè)置為藍(lán)色了，此時(shí)，會(huì)錯(cuò)誤認(rèn)為該key在集合中
示例：

6. 可以刪除么

傳統(tǒng)的布隆過(guò)濾器并不支持刪除操作。但是名為 Counting Bloom filter 的變種可以用來(lái)測(cè)試元素計(jì)數(shù)個(gè)數(shù)是否絕對(duì)小于某個(gè)閾值，它支持元素刪除。詳細(xì)理解可以參考文章Counting Bloom Filter 的原理和實(shí)現(xiàn)， 寫(xiě)的很詳細(xì)。

7. 如何選擇哈希函數(shù)個(gè)數(shù)和布隆過(guò)濾器長(zhǎng)度

很顯然，過(guò)小的布隆過(guò)濾器很快所有的 bit 位均為 1，那么查詢(xún)?nèi)魏沃刀紩?huì)返回“可能存在”，起不到過(guò)濾的目的了。布隆過(guò)濾器的長(zhǎng)度會(huì)直接影響誤報(bào)率，布隆過(guò)濾器越長(zhǎng)其誤報(bào)率越小。

另外，哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡，個(gè)數(shù)越多則布隆過(guò)濾器 bit 位置位 1 的速度越快，且布隆過(guò)濾器的效率越低；但是如果太少的話，那我們的誤報(bào)率會(huì)變高。

從上圖可以看出，增加哈希函數(shù)k的數(shù)量將大大降低錯(cuò)誤率p。

好像是WTF？不用擔(dān)心，實(shí)際上我們實(shí)際上需要確定我們的m和k。因此，如果我們自己設(shè)置容錯(cuò)值p和元素?cái)?shù)n，則可以使用以下公式來(lái)計(jì)算這些參數(shù)：

我們可以根據(jù)過(guò)濾器的大小m，哈希函數(shù)的數(shù)量k和插入的元素的數(shù)量n來(lái)計(jì)算誤報(bào)率p，公式如下：由上面，又怎么選擇適合業(yè)務(wù)的 k 和 m 值呢？
公式：

k 為哈希函數(shù)個(gè)數(shù)，m 為布隆過(guò)濾器長(zhǎng)度，n 為插入的元素個(gè)數(shù)，p 為誤報(bào)率。
至于如何推導(dǎo)這個(gè)公式，我在知乎發(fā)布的文章有涉及，感興趣可以看看，不感興趣的話記住上面這個(gè)公式就行了。

我還要在這里提到另一個(gè)重要的觀點(diǎn)。由于使用Bloom篩選器的唯一目的是搜索速度更快，所以我們不能使用慢速哈希函數(shù)，對(duì)嗎？加密散列函數(shù)（例如Sha-1，MD5）對(duì)于bloom過(guò)濾器不是一個(gè)好選擇，因?yàn)樗鼈冇悬c(diǎn)慢。因此，從更快的哈希函數(shù)實(shí)現(xiàn)中更好的選擇是murmur，fnv系列哈希，Jenkins哈希和HashMix。

更多應(yīng)用場(chǎng)景

在給定的示例中您已經(jīng)看到，我們可以使用它來(lái)警告用戶(hù)輸入弱密碼。
您可以使用布隆過(guò)濾器，以防止用戶(hù)從訪問(wèn)惡意網(wǎng)站。
您可以先使用Bloom Bloom篩選器進(jìn)行廉價(jià)的查找檢查，而不用查詢(xún)SQL數(shù)據(jù)庫(kù)來(lái)檢查是否存在具有特定電子郵件的用戶(hù)。如果電子郵件不存在，那就太好了！如果確實(shí)存在，則可能必須對(duì)數(shù)據(jù)庫(kù)進(jìn)行額外的查詢(xún)。您也可以執(zhí)行同樣的操作來(lái)搜索“用戶(hù)名已被占用”。
您可以根據(jù)網(wǎng)站訪問(wèn)者的IP地址保留一個(gè)Bloom過(guò)濾器，以檢查您網(wǎng)站的用戶(hù)是“回頭用戶(hù)”還是“新用戶(hù)”。“回頭用戶(hù)”的一些誤報(bào)不會(huì)傷害您，對(duì)嗎？
您也可以通過(guò)使用Bloom過(guò)濾器跟蹤詞典單詞來(lái)進(jìn)行拼寫(xiě)檢查。

以上就是布隆過(guò)濾器算法圖文詳解的詳細(xì)內(nèi)容，更多關(guān)于布隆過(guò)濾器算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論