1.什么是布隆過濾器？

本質上布隆過濾器是一種數(shù)據(jù)結構，比較巧妙的概率型數(shù)據(jù)結構（probabilistic data structure），特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”。

2布隆過濾器數(shù)據(jù)結構

我們可以把它看作由二進制向量（或者說位數(shù)組）和一系列隨機映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結構,相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結構，它更高效、占用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。

布隆過濾器示意圖.png

位數(shù)組中的每個元素都只占用 1 bit ，并且每個元素只能是 0 或者 1。這樣申請一個 100w 個元素的位數(shù)組只占用 1000000 / 8 = 125000 B = 125000 byte ≈ 125kb 的空間。

總結：一個名叫 Bloom 的人提出了一種來檢索元素是否在給定大集合中的數(shù)據(jù)結構，這種數(shù)據(jù)結構是高效且性能很好的，但缺點是具有一定的錯誤識別率和刪除難度。并且，理論情況下，添加到集合中的元素越多，誤報的可能性就越大。

3布隆過濾器的原理介紹

3.1 數(shù)據(jù)添加

1.使用布隆過濾器中的哈希函數(shù)對元素值進行計算，得到哈希值（有幾個哈希函數(shù)得到幾個哈希值）。
2.根據(jù)得到的哈希值，在位數(shù)組中把對應下標的值置為 1。

3.2校驗數(shù)據(jù)是否存在

1.對給定元素再次進行相同的哈希計算；
2.得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。

圖例.png

如圖所示，當字符串存儲要加入到布隆過濾器中時，該字符串首先由多個哈希函數(shù)生成不同的哈希值，然后在對應的位數(shù)組的下表的元素設置為 1（當位數(shù)組初始化時 ，所有位置均為0）。當?shù)诙未鎯ο嗤址畷r，因為先前的對應位置已設置為1，所以很容易知道此值已經(jīng)存在（去重非常方便）。

如果我們需要判斷某個字符串是否在布隆過濾器中時，只需要對給定字符串再次進行相同的哈希計算，得到值之后判斷位數(shù)組中的每個元素是否都為 1，如果值都為 1，那么說明這個值在布隆過濾器中，如果存在一個值不為 1，說明該元素不在布隆過濾器中。
備注：不同的字符串可能哈希出來的位置相同，這種情況我們可以適當增加位數(shù)組大小或者調整我們的哈希函數(shù)。

4.布隆過濾器使用場景

重點：布隆過濾器說某個元素存在，小概率會誤判。布隆過濾器說某個元素不在，那么這個元素一定不在
1.判斷給定數(shù)據(jù)是否存在：海量數(shù)據(jù)（數(shù)據(jù)億級）存儲校驗、防止緩存穿透、郵箱的垃圾郵件過濾、黑名單功能等；
2.去重功能

5.計算公式（結合實際場景應用推導更加直觀）

場景：不安全網(wǎng)頁的黑名單包含100億個黑名單網(wǎng)頁，每個網(wǎng)頁的URL最多占用64字節(jié)?，F(xiàn)在想要實現(xiàn)一種網(wǎng)頁過濾系統(tǒng)，可以根據(jù)網(wǎng)頁的URL判斷該網(wǎng)站是否在黑名單上，請設計該系統(tǒng)。要求該系統(tǒng)允許有萬分之一以下的判斷失誤率，并且使用的額外空間不要超過30G。
思路：布隆過濾器的bitarray大小如何確定？
變量說明：

• m:容量大小
• n:樣本元素數(shù)量
• p:失誤率
• k:hash函數(shù)個數(shù)

1.設bit array大小為m，樣本數(shù)量為n，失誤率為p。
2.由題可知 n = 100億，p = 0.01%
3.單個樣本大小不影響布隆過濾器大小，因為樣本會通過哈希函數(shù)得到輸出值。
4.使用樣本數(shù)量n和失誤率p可以算出m，公式為：

image.png

求得 m = 19.19n，向上取整為 20n。所以2000億bit，約為25G。
所使用哈希函數(shù)個數(shù)k可以由以下公式求得：

image.png

image.png