當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

布隆过滤器

發布時間：2024/3/12 编程问答 37 豆豆

生活随笔收集整理的這篇文章主要介紹了布隆过滤器小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

布隆過濾器介紹

布隆過濾器在wiki上的介紹: 布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難

為什么要用布隆過濾器？

??????? HashMap 的問題: 講述布隆過濾器的原理之前，我們先思考一下，通常你判斷某個元素是否存在用的是什么？應該蠻多人回答 HashMap 吧，確實可以將值映射到 HashMap 的 Key，然后可以在 O(1) 的時間復雜度內返回結果，效率奇高。但是 HashMap 的實現也有缺點，例如存儲容量占比高，考慮到負載因子的存在，通常空間是不能被用滿的，而一旦你的值很多例如上億的時候，那 HashMap 占據的內存大小就變得很可觀了。

?????? 還比如說你的數據集存儲在遠程服務器上，本地服務接受輸入，而數據集非常大不可能一次性讀進內存構建 HashMap 的時候，也會存在問題。

??????? 事實上，布隆過濾器被廣泛用于網頁黑名單系統、垃圾郵件過濾系統、爬蟲的網址判重系統以及解決緩存穿透問題。通過介紹已經知曉布隆過濾器的作用是檢索一個元素是否在集合中?？赡苡腥苏J為這個功能非常簡單，直接放在redis中或者數據庫中查詢就好了。又或者當數據量較小，內存又足夠大時，使用hashMap或者hashSet等結構就好了。但是如果當這些數據量很大，數十億甚至更多，內存裝不下且數據庫檢索又極慢的情況，我們應該如何去處理？這個時候我們不妨考慮下布隆過濾器，因為它是一個空間效率占用極少和查詢時間極快的算法，但是需要業務可以忍受一個判斷失誤率。

哈希函數

哈希函數的性質:

經典的哈希函數都有無限大的輸入值域(無窮大)。

經典的哈希函數的輸出域都是固定的范圍(有窮大，假設輸出域為S)

當給哈希函數傳入相同的值時，返回值必一樣

當給哈希函數傳入不同的輸入值時，返回值可能一樣，也可能不一樣。

輸入值會盡可能均勻的分布在S上

??????? 前三點都是哈希函數的基礎，第四點描述了哈希函數存在哈希碰撞的現象，因為輸入域無限大，輸出域有窮大，這是必然的，輸入域中會有不同的值對應到輸入域S中。第五點事評價一個哈希函數優劣的關鍵，哈希函數越優秀，分布就越均勻且與輸入值出現的規律無關。比如存在"hash1","hash2","hash3"三個輸入值比較類似，經過哈希函數計算后的結果應該相差非常大，可以通過常見的MD5和SHA1算法來驗證這些特性。如果一個優秀的函數能夠做到不同的輸入值所得到的返回值可以均勻的分布在S中，將其返回值對m取余(%m),得到的返回值可以認為也會均勻的分布在0~m-1位置上。

基于緩存業務分析布隆過濾器原理

??????? 在大多應用中，當業務系統中發送一個請求時，會先從緩存中查詢；若緩存中存在，則直接返回；若返回中不存在，則查詢數據庫。其流程如下圖所示:

?????? 緩存穿透：當請求數據庫中不存在的數據，這時候所有的請求都會打到數據庫上，這種情況就是緩存穿透。如果當請求較多的話，這將會嚴重浪費數據庫資源甚至導致數據庫假死。

?????? 接下來開始介紹布隆過濾器。有一個長度為m的bit型數組，如我們所知，每個位置只占一個bit，每個位置只有0和1兩種狀態。假設一共有k個哈希函數相互獨立，輸入域都為s且都大于等于m，那么對同一個輸入對象（可以想象為緩存中的一個key），經過k個哈希函數計算出來的結果也都是獨立的。對算出來的每一個結果都對m取余，然后在bit數組上把相應的位置設置為1(描黑)，如下圖所示：

?????? 至此一個輸入對象對bit array集合的影響過程就結束了，我們可以看到會有多個位置被描黑，也就是設置為1。接下來所有的輸入對象都按照這種方式去描黑數組，最終一個布隆過濾器就生成了，它代表了所有輸入對象組成的集合。
?????? 那么如何判斷一個對象是否在過濾器中呢？假設一個輸入對象為hash1,我們需要通過看k個哈希函數算出k個值，然后把k個值取余（%m），就得到了k個[0,m-1]的值。然后我們判斷bit array上這k個值是否都為黑，如果有一個不為黑，那么肯定hash1肯定不在這個集合里。如果都為黑，則說明hash1在集合里，但有可能誤判。因為當輸入對象過多，而集合過小，會導致集合中大多位置都會被描黑，那么在檢查hash1時，有可能hash1對應的k個位置正好被描黑了，然后錯誤的認為hash1存在集合里。

例子：將30000加入布隆過濾器中。底層用的是int類型的數組，長度為1000。

30000的含義是將數組中第30000個bit描黑，并非實際的數字。
數組長度1000，一共可容納32*1000個bit。

控制布隆過濾器的誤判率

??????? 如果bit array集合的大小m相比于輸入對象的個數過小，失誤率就會變高。這里直接引入一個已經得到證明的公式，根據輸入對象數量n和我們想要達到的誤判率為p計算出布隆過濾器的大小m和哈希函數的個數k.

布隆過濾器的大小m公式:

哈希函數的個數k公式:

布隆過濾器真實失誤率p公式：

假設我們的緩存系統，key為userId，value為user。如果我們有10億個用戶，規定失誤率不能超過0.01%，通過計算器計算可得m=19.17n，向上取整為20n，也就是需要200億個bit，換算之后所需內存大小就是2.3G。通過第二個公式可計算出所需哈希函數k=14.因為在計算m的時候用了向上取整，所以真是的誤判率絕對小于等于0.01%。

快速集成BloomFilter

關于布隆過濾器，我們不需要自己實現，谷歌已經幫我們實現好了。

pom引入依賴

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>25.1-jre</version> </dependency>

核心api

/*** Creates a {@link BloomFilter BloomFilter<T>} with the expected number of* insertions and expected false positive probability.** Note that overflowing a {@code BloomFilter} with significantly more elements* than specified, will result in its saturation, and a sharp deterioration of its* false positive probability.** The constructed {@code BloomFilter<T>} will be serializable if the provided* {@code Funnel<T>} is.** It is recommended that the funnel be implemented as a Java enum. This has the* benefit of ensuring proper serialization and deserialization, which is important* since {@link #equals} also relies on object identity of funnels.** @param funnel the funnel of T's that the constructed {@code BloomFilter<T>} will use* @param expectedInsertions the number of expected insertions to the constructed* {@code BloomFilter<T>}; must be positive* @param fpp the desired false positive probability (must be positive and less than 1.0)* @return a {@code BloomFilter}*/public static <T> BloomFilter<T> create(Funnel<T> funnel, int expectedInsertions /* n */, double fpp) {checkNotNull(funnel);checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0",expectedInsertions);checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);if (expectedInsertions == 0) {expectedInsertions = 1;}/** TODO(user): Put a warning in the javadoc about tiny fpp values,* since the resulting size is proportional to -log(p), but there is not* much of a point after all, e.g. optimalM(1000, 0.0000000000000001) = 76680* which is less than 10kb. Who cares!*/long numBits = optimalNumOfBits(expectedInsertions, fpp);int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);try {return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel,BloomFilterStrategies.MURMUR128_MITZ_32);} catch (IllegalArgumentException e) {throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);}} /*** Returns {@code true} if the element might have been put in this Bloom filter,* {@code false} if this is definitely not the case.*/public boolean mightContain(T object) {return strategy.mightContain(object, funnel, numHashFunctions, bits);}

一個小例子

public static void main(String... args){/*** 創建一個插入對象為一億，誤報率為0.01%的布隆過濾器*/BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 100000000, 0.0001);bloomFilter.put("121");bloomFilter.put("122");bloomFilter.put("123");System.out.println(bloomFilter.mightContain("121"));}

redis中的布隆過濾器

??????? 在redis中的布隆過濾器的支持是在redis4.0后支持插件的情況下，通過插件的方式實現的，redis的布隆過濾器插件地址：https://github.com/RedisLabsModules/rebloom

??????? 它的操作也很簡單，以下為幾個主要命令，其它命令請參考文檔?https://github.com/RedisLabsModules/rebloom/blob/master/docs/Bloom_Commands.md

BF.RESERVE {key} {error_rate} {size}?? 創建一個布隆過濾器?? key為redis存儲鍵值，error_rate 為錯誤率（大于0，小于1），size為預計存儲的數量（size是比較關鍵的，需要根據自己的需求情況合理估計，設置太小的話會增大錯誤率，設置太大會占用過多不必要的空間）
BF.ADD {key} {item}? 添加值到布隆過濾器中（當過濾器不存在的時候會，會以默認值自動創建一個，建議最好提前創建好）。redis存儲鍵值，item為值（如需要添加多個，請使用BF.MADD 可同時添加多個）
BF.EXISTS {key} {item}? 判斷值是否存在過濾器中? true（表示很可能存在） false （表示絕對不存在）

參考文章：

https://segmentfault.com/a/1190000015482091

總結

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

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

过滤器