布隆過濾器

布隆過濾器是一種由位數組和多個哈希函數組成概率數據結構，返回兩種結果?可能存在?和?一定不存在。

布隆過濾器里的一個元素由多個狀態值共同確定。位數組存儲狀態值，哈希函數計算狀態值的位置。

根據它的算法結構，有如下特征：

• 使用有限位數組表示大于它長度的元素數量，因為一個位的狀態值可以同時標識多個元素。
• 不能刪除元素。因為一個位的狀態值可能同時標識著多個元素。
• 添加元素永遠不會失敗。只是隨著添加元素增多，誤判率會上升。
• 如果判斷元素不存在，那么它一定不存在。

比如下面，X,Y,Z 分別由 3個狀態值共同確定元素是否存在，狀態值的位置通過3個哈希函數分別計算。

數學關系

誤判概率

關于誤判概率，因為每個位的狀態值可能同時標識多個元素，所以它存在一定的誤判概率。如果位數組滿，當判斷元素是否存在時，它會始終返回true，對于不存在的元素來說，它的誤判率就是100%。

那么，誤判概率和哪些因素有關，已添加元素的數量，布隆過濾器長度（位數組大小），哈希函數數量。

根據維基百科推理誤判概率?PfpPfp?有如下關系：

Pfp=(1?[1?1m]kn)k≈(1?e?knm)kPfp=(1?[1?1m]kn)k≈(1?e?knm)k

• mm?是位數組的大小；
• nn?是已經添加元素的數量；
• kk?是哈希函數數量；
• ee?數學常數，約等于2.718281828。

由此可以得到，當添加元素數量為0時，誤報率為0；當位數組全都為1時，誤報率為100%。

不同數量哈希函數下，PfpPfp?和?nn?的關系如下圖：

根據誤判概率公式可以做一些事

• 估算最佳布隆過濾器長度。
• 估算最佳哈希函數數量。

最佳布隆過濾器長度

當?nn?添加元素和?PfpPfp誤報概率確定時，mm?等于：

m=?nlnPfp(ln2)2≈?1.44?nlog2Pfpm=?nln?Pfp(ln?2)2≈?1.44?nlog2?Pfp

最佳哈希函數數量

當?nn?和?PfpPfp?確定時，kk?等于：

k=?lnPfpln2=?log2Pfpk=?ln?Pfpln?2=?log2?Pfp

當?nn?和?mm?確定時，kk?等于：

k=mnln2k=mnln?2

實現布隆過濾器

使用布隆過濾器前，我們一般會評估兩個因素。

• 預期添加元素的最大數量。
• 業務對錯誤的容忍程度。比如1000個允許錯一個，那么誤判概率應該在千分之一內。

很多布隆過濾工具都提供了預期添加數量和誤判概率配置參數，它們會根據配置的參數計算出最佳的長度和哈希函數數量。

Java中有一些不錯的布隆過濾工具包。

• Guava?中?BloomFilter。
• redisson?中?RedissonBloomFilter?可以redis 中使用。

看下?Guava?中?BloomFilter?的簡單實現，創建前先計算出位數組長度和哈希函數數量。

static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {/*** expectedInsertions：預期添加數量* fpp：誤判概率*/long numBits = optimalNumOfBits(expectedInsertions, fpp);int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);try {return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);} catch (IllegalArgumentException e) {throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);}}

根據最佳布隆過濾器長度公式，計算最佳位數組長度。

static long optimalNumOfBits(long n, double p) {if (p == 0) {p = Double.MIN_VALUE;}return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));}

根據最佳哈希函數數量公式，計算最佳哈希函數數量。

static int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));}

在redisson?中?RedissonBloomFilter?計算方法也是一致。

private int optimalNumOfHashFunctions(long n, long m) {return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));}private long optimalNumOfBits(long n, double p) {if (p == 0) {p = Double.MIN_VALUE;}return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));}

內存占用

設想一個手機號去重場景，每個手機號占用22 Byte，估算邏輯內存如下。

expectedHashSetfpp=0.0001fpp=0.0000001

100萬	18.28MB	2.29MB	4MB
1000萬	182.82MB	22.85MB	40MB
1億	1.78G	228.53MB	400MB

注：實際物理內存占用大于邏輯內存。

誤判概率?pp?和已添加的元素?nn，位數組長度?mm，哈希函數數量?kk?關系如下：

應用場景

弱密碼檢測；

垃圾郵件地址過濾。

瀏覽器檢測釣魚網站；

緩存穿透。

弱密碼檢測

維護一個哈希過弱密碼列表。當用戶注冊或更新密碼時，使用布隆過濾器檢查新密碼，檢測到提示用戶。

垃圾郵件地址過濾

維護一個哈希過垃圾郵件地址列表。當用戶接收郵件，使用布隆過濾器檢測，檢測到標識為垃圾郵件。

瀏覽器檢測釣魚網站

使用布隆過濾器來查找釣魚網站數據庫中是否存在某個網站的 URL。

緩存穿透

緩存穿透是指查詢一個根本不存在的數據，緩存層和數據庫都不會命中。當緩存未命中時，查詢數據庫

數據庫不命中，空結果不會寫回緩存并返回空結果。

數據庫命中，查詢結果寫回緩存并返回結果。

一個典型的攻擊，模擬大量請求查詢不存在的數據，所有請求落到數據庫，造成數據庫宕機。

其中一種解決方案，將存在的緩存放入布隆過濾器，在請求前進行校驗過濾。

小結

對于千萬億級別的數據來說，使用布隆過濾器具有一定優勢，另外根據業務場景合理評估預期添加數量和誤判概率是關鍵。

總結

以上是生活随笔為你收集整理的面试官问：什么是布隆过滤器？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。