認識布隆過濾器

布隆過濾器的一些概念

主要包括：

簡介

算法

參數

優勢和劣勢

布隆過濾器簡介

布隆過濾器是「一種空間高效概率性的數據結構」（百科中原文是a space-efficient probabilistic data structure），該數據結構于1970年由Burton Howard Bloom提出，「作用是測試一個元素是否某個集合的一個成員」。布隆過濾器是可能出現false positive（這個是專有名詞"假陽性"，可以理解為誤判的情況，下文如果用到這個名詞會保留英文單詞使用）匹配的，換言之，布隆過濾器在使用的時候有可能返回結果"可能存在于集合中"或者"必定不存在于集合中"。

布隆過濾器算法描述

在場景復雜的網絡爬蟲中，爬取到的網頁URL依賴有可能成環，例如在URL-1頁面中展示了URL-2，然后又在URL-2中的頁面展示了URL-1，這個時候需要一種方案記錄和判斷歷史訪問過的URL。這個時候可能會想到下面的方案：

方案一：使用數據庫存儲已經訪問過的URL，例如MySQL表中基于URL建立唯一索引或者使用Redis的SET數據類型

方案二：使用HashSet（其實這里不局限于HashSet，鏈表、樹和散列表等數據結構都能滿足）存儲已經訪問過的URL

方案三：基于方案一和方案二進行優化，存儲URL的摘要，使用摘要算法如MD5、SHA-n算法針對URL字符串生成摘要

方案四：使用Hash函數處理對應的URL生成一個哈希碼，再把哈希碼通過一個映射函數映射到一個固定容量的BitSet中的某一個比特

對于方案一、方案二和方案三，在歷史訪問URL數據量極大的情況下，會消耗巨大的存儲空間（磁盤或者內存），對于方案四，如果URL有100億個，那么要把沖突幾率降低到1%，那么BitSet的容量需要設置為10000億。

冷飯新炒：理解布隆過濾器算法的實現原理

所以上面的四種方案都有明顯的不足之處，而布隆過濾器算法的基本思路跟方案四差不多，最大的不同點就是方案四中只提到使用了一個散列函數，而布隆過濾器中使用了k（k >= 1）個相互獨立的高效低沖突的散列函數。

一個初始化的布隆過濾器是一個所有比特都設置為0的長度為m的比特數組，也就是認知中的Bit Array、Bit Set或者Redis中的Bit Map概念。然后需要引入k個不同的散列函數，某個新增元素通過這k個散列函數處理之后，映射到比特數組m個比特中的k個，并且把這些命中映射的k個比特位設置為1，產生一個均勻的隨機分布。通常情況下，k的一個較小的常數，取決于所需的誤判率，而布隆過濾器容量m與散列函數個數k和需要添加元素數量呈正相關。

冷飯新炒：理解布隆過濾器算法的實現原理

當需要新增的所有元素都添加到布隆過濾器之后，那么比特數組中的很多比特都被設置為1。這個時候如果需要判斷一個元素是否存在于布隆過濾器中，只需要通過k個散列函數處理得到比特數組的k個下標，然后判斷比特數組對應的下標所在比特是否為

1。如果這k個下標所在比特中「至少存在一個0，那么這個需要判斷的元素必定不在布隆過濾器代表的集合中」；如果這k個下標所在比特全部都為1，那么那么這個需要判斷的元素「可能存在于」布隆過濾器代表的集合中或者剛好是一個False Positive，至于誤差率分析見下文的「布隆過濾器的相關參數」一節。False Positive出現的情況可以見下圖：

冷飯新炒：理解布隆過濾器算法的實現原理

當添加到布隆過濾器的元素數量比較大，并且布隆過濾器的容量設置不合理（過小），容易出現多個元素通過k個散列函數，映射到相同的k個位（如上圖的下標1、3、9所在的位），這個時候就無法準確判斷這k個位由具體那個元素映射而來。其實可以極端一點思考：假設布隆過濾器容量為24，散列函數只有一個，那么添加最多25個不同元素，必定有兩個不同的元素的映射結果落在同一個位。

布隆過濾器的相關參數

在算法描述一節已經提到過，布隆過濾器主要有下面的參數：

初始化比特數組容量m

散列函數個數k

誤判率ε（數學符號Epsilon，代表False Positive Rate）

需要添加到布隆過濾器的元素數量n

考慮到篇幅原因，這里不做這幾個值的關系推導，直接整理出結果和關系式。

誤判率ε的估算值為：[1 - e(-kn/m)]k

最優散列函數數量k的推算值：對于給定的m和n，當k = m/n * ln2的時候，誤判率ε最低

推算初始化比特容量m的值，當k = m/n * ln2的時候，m >= n * log2(e) * log2(1/ε)

這里貼一個參考資料中m/n、k和False Positive Rate之間的關系圖：

冷飯新炒：理解布隆過濾器算法的實現原理

image.png

冷飯新炒：理解布隆過濾器算法的實現原理

這里可以推算一下表格中最大參數所需要的空間極限，假設n為10億，m/n = 32，那么m為320億，而k為24，此時的誤判率為2.17e-07(0.000000217)，需要空間3814.69727m。一般規律是：

當k固定的時候，m/n越大，誤判率越小

當m/n固定的時候，k越大，誤判率越大

通常情況下，k需要固定，而n是無法確定準確值，最好要評估增長趨勢預先計算一個比較大的m值去降低誤判率，當然也要權衡m值過大導致空間消耗過大的問題。

既然參數的關系式都已經有推導結果，可以基于關系式寫一個參數生成器：

import java.math.BigDecimal; import java.math.RoundingMode; public class BloomFilterParamGenerator { public BigDecimal falsePositiveRate(int m, int n, int k) { double temp = Math.pow(1 - Math.exp(Math.floorDiv(-k * n, m)), k); return BigDecimal.valueOf(temp).setScale(10, RoundingMode.FLOOR); } public BigDecimal kForMinFalsePositiveRate(int m, int n) { BigDecimal k = BigDecimal.valueOf(Math.floorDiv(m, n) * Math.log(2)); return k.setScale(10, RoundingMode.FLOOR); } public BigDecimal bestM(int n, double falsePositiveRate) { double temp = log2(Math.exp(1) + Math.floor(1 / falsePositiveRate)); return BigDecimal.valueOf(n).multiply(BigDecimal.valueOf(temp)).setScale(10, RoundingMode.FLOOR); } public double log2(double x) { return Math.log(x) / Math.log(2); } public static void main(String[] args) { BloomFilterParamGenerator generator = new BloomFilterParamGenerator(); System.out.println(generator.falsePositiveRate(2, 1, 2)); // 0.3995764008 System.out.println(generator.kForMinFalsePositiveRate(32, 1)); // 22.1807097779 System.out.println(generator.bestM(1, 0.3995764009)); // 2.2382615950 } }

這里的計算沒有考慮嚴格的進位和截斷，所以和實際的結果可能有偏差，只提供一個參考的例子。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。