阿里高頻面試題：如何快速判斷元素是不是在集合里？
時間：2021-11-04 16:08:20
手機看文章
掃描二維碼
隨時隨地手機看文章
[導讀]如何快速判斷一個元素是不是在一個集合里？這個題目是我最近面試的時候常問的一個問題，這個問題不同人都有很多不同的回答。今天想介紹一個很少有人會提及到的方案，那就是借助布隆過濾器。什么叫布隆過濾器布隆過濾器（BloomFilter）是一個叫做Bloom的老哥于1970年提出的。實際上...
如何快速判斷一個元素是不是在一個集合里？這個題目是我最近面試的時候常問的一個問題，這個問題不同人都有很多不同的回答。
今天想介紹一個很少有人會提及到的方案，那就是借助布隆過濾器。
什么叫布隆過濾器布隆過濾器（Bloom Filter）是一個叫做 Bloom 的老哥于1970年提出的。實際上可以把它看作由二進制向量（或者說位數(shù)組）和一系列隨機映射函數(shù)（哈希函數(shù)）兩部分組成的數(shù)據(jù)結構。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。
實現(xiàn)原理先來一張圖
作用布隆過濾器是可以用于判斷一個元素是不是（可能）在一個集合里，并且相比于其它的數(shù)據(jù)結構，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。注意上面的一個詞：可能。這里先預留一個懸念，下文會詳細分析到。
使用場景
- 判斷給定數(shù)據(jù)是否存在
- 防止緩存穿透（判斷請求的數(shù)據(jù)是否有效避免直接繞過緩存請求數(shù)據(jù)庫）等等、郵箱的垃圾郵件過濾、黑名單功能等等。
具體實現(xiàn)看完了布隆過濾器的算法思想，那就開始具體的實現(xiàn)的講解。我先來舉個例子，假設有旺財和小強兩個字符串，他們分別經(jīng)過三次的 hash 算法，然后根據(jù) hash 的結果將對應的數(shù)組（假設數(shù)組長度為 16）的索引位置的值置為1，先來看下旺財這個詞組:
代碼的實現(xiàn)作為 java 程序員，我們真的是很幸福了，我們使用到很多的框架和工具，基本都被封裝好了，布隆過濾器，我們就使用 google 封裝好的工具類。首先添加依賴?
?
????
????guava
????
import?com.google.common.hash.Funnels;
import?java.nio.charset.Charset;
public?class?BloomFilterDemo?{
????public?static?void?main(String[]?args)?{
????????/**
?????????*?創(chuàng)建一個插入對象為一億，誤報率為0.01%的布隆過濾器
?????????*?不存在一定不存在
?????????*?存在不一定存在
?????????*?----------------
?????????*? Funnel 對象：預估的元素個數(shù)，誤判率
?????????*? mightContain ：方法判斷元素是否存在
?????????*/
????????BloomFilter
????????bloomFilter.put("死");
????????bloomFilter.put("磕");
????????bloomFilter.put("Redis");
????????System.out.println(bloomFilter.mightContain("Redis"));
????????System.out.println(bloomFilter.mightContain("Java"));
????}
}
實戰(zhàn)我們來模擬這樣的場景：通過布隆過濾器來解決緩存穿透。首先你的知道什么叫緩存穿透吧？緩存穿透是指用戶訪問一個緩存和數(shù)據(jù)庫中都沒有的數(shù)據(jù)，因為緩存中不存在，所以就會去訪問數(shù)據(jù)庫，如果并發(fā)很高。很容易會擊垮數(shù)據(jù)庫那布隆過濾器是如何解決這個問題的呢？他的原理是這樣子的：將數(shù)據(jù)庫中所有的查詢條件，放入布隆過濾器中，當一個查詢請求過來時，先經(jīng)過布隆過濾器進行查，如果判斷請求查詢值存在，則繼續(xù)查；如果判斷請求查詢不存在，直接丟棄。其代碼如下：String?get(String?key)?{
????String?value?=?redis.get(key);?????
????if?(value??==?null)?{
????????if(!bloomfilter.mightContain(key)){
????????????return?null;?
????????}else{
????????????value?=?db.get(key);?
????????????redis.set(key,?value);?
????????}????
????}
????return?value；
}
小結本文詳細介紹了布隆過濾器是什么？有什么作用？實現(xiàn)原理以及從代碼層面多方面來闡述布隆過濾器。學習能為各位在學習進階的路上添磚加瓦。
下載文檔
