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