系統(tǒng)如何設(shè)計(jì)才能更快地查詢(xún)到數(shù)據(jù)？
“開(kāi)通微信時(shí)，系統(tǒng)如何判斷你輸入的手機(jī)號(hào)沒(méi)被注冊(cè)？如何使用更少的存儲(chǔ)空間、更快的速度解決這個(gè)問(wèn)題？”
對(duì)于這個(gè)問(wèn)題，最暴力的方法為：
通過(guò)遍歷來(lái)判斷是否被注冊(cè)。那么時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度也是O(n)。
稍微學(xué)過(guò)算法的同學(xué)會(huì)說(shuō)：
使用HashMap，時(shí)間復(fù)雜度瞬間降到O(1)。
精通算法的同學(xué)可能會(huì)說(shuō)：
使用Bitmap，因?yàn)锽itmap只需要存儲(chǔ)數(shù)據(jù)的狀態(tài)信息（0和1），這樣空間復(fù)雜度為O(max_value)。
下面問(wèn)題又來(lái)了：
如果n=10億，將會(huì)占據(jù)多少內(nèi)存？
假設(shè)整數(shù)為64bit=8Byte，
Hashmap：10億整數(shù)需要8G的內(nèi)存
Bitmap:
雖然速度提上去了，內(nèi)存占有量無(wú)法想象的…大！
那如何既保證查詢(xún)效率，又保證低內(nèi)存占用？
下面我們的主角閃亮登場(chǎng)——布隆過(guò)濾器。
一、Bloom過(guò)濾器的簡(jiǎn)介
Bloom過(guò)濾器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。
它實(shí)際上是由一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)組成。
它的目標(biāo)是——占用更小的空間的前提下，檢索一個(gè)元素是否在一個(gè)集合中。
二、原理介紹
下面我從三個(gè)方面來(lái)介紹布隆過(guò)濾器：構(gòu)造、檢索、效果。
1.構(gòu)造
構(gòu)造主要包括以下三個(gè)步驟：
選擇k個(gè)哈希函數(shù)
將待檢索字符串分別做Hash映射
每個(gè)映射的值對(duì)應(yīng)的bit數(shù)組置為“1”
我舉一個(gè)簡(jiǎn)單的例子：
假設(shè)我們有3個(gè)哈希函數(shù)，有兩個(gè)待檢索字符串"jimboooo"和"luckyyyyy"。
對(duì)于字符串"jimboooo"，經(jīng)過(guò)三個(gè)哈希函數(shù)映射后，將1,4,8的位置置為“1”。
同理，對(duì)于字符串“l(fā)uckyyyyy"，我們經(jīng)過(guò)哈希函數(shù)映射后，將位置2,4,7置為“1”。
那么，我們的布隆過(guò)濾器已經(jīng)構(gòu)造完畢了。
2.檢索
將待檢索的字符串通過(guò)k個(gè)哈希函數(shù)映射；
查看映射的整數(shù)對(duì)應(yīng)的位置是否1，如果都為1，說(shuō)明待檢索字符串是存在的。
下圖是我們構(gòu)造過(guò)程得到的數(shù)組，如果要檢索"jimbooo"，哈希映射后是2,4,7，這三個(gè)位置都為1，說(shuō)明此字符串是存在的。如果要檢索"fukuoka"，映射后是1,3,4，因?yàn)?的位置為0，很明顯它是不存在的。
3.效果
布隆過(guò)濾器的原理已介紹完畢，看起來(lái)十分簡(jiǎn)單。那可能會(huì)出現(xiàn)什么問(wèn)題呢？
如果要檢索的字符串（原本不存在）映射后數(shù)組每個(gè)位置恰好都為1，那就出現(xiàn)了誤判！
我們來(lái)通過(guò)公式了解下它的誤判率、布隆過(guò)濾器長(zhǎng)度以及哈希函數(shù)個(gè)數(shù)之間的關(guān)系吧。
先上公式（推理見(jiàn)附錄）：
k 為哈希函數(shù)個(gè)數(shù)，m 為布隆過(guò)濾器長(zhǎng)度，n 為插入的元素個(gè)數(shù)（待檢索元素總數(shù)），p 為誤報(bào)率，
當(dāng)且僅當(dāng)：
誤報(bào)率p取得最優(yōu)解：
根據(jù)公式就可以得到布隆過(guò)濾器的長(zhǎng)度、誤識(shí)率、待插入元素個(gè)數(shù)（待檢索元素總數(shù)）的關(guān)系了。
如下圖所示，x軸為m/n，含義為每個(gè)元素占有的bit數(shù)，y軸為誤識(shí)率。
得出的結(jié)論是，對(duì)于一個(gè)擁有最優(yōu)k值且誤判率在1%的布隆過(guò)濾器，每個(gè)元素只需要9.6bits（與元素的大小無(wú)關(guān)）。若給每個(gè)元素增加4.8bits左右，誤判率將會(huì)減少十倍。
三、應(yīng)用
可應(yīng)用于很多方面：
1.網(wǎng)頁(yè)爬蟲(chóng)對(duì)URL的去重
避免爬取相同的URL地址。
2.緩存擊穿
將已存在的緩存放到布隆中，當(dāng)黑客訪(fǎng)問(wèn)不存在的緩存時(shí)迅速返回避免緩存及DB掛掉。
3.HTTP緩存服務(wù)器
當(dāng)本地局域網(wǎng)中的PC發(fā)起一條HTTP請(qǐng)求時(shí)，緩存服務(wù)器會(huì)先查看一下這個(gè)URL是否已經(jīng)存在于緩存之中，如果存在的話(huà)就沒(méi)有必要去原始的服務(wù)器拉取數(shù)據(jù)了(為了簡(jiǎn)單起見(jiàn)，我們假設(shè)數(shù)據(jù)沒(méi)有發(fā)生變化)，這樣既能節(jié)省流量，還能加快訪(fǎng)問(wèn)速度，以提高用戶(hù)體驗(yàn)。
4.黑/白名單
類(lèi)似反垃圾郵件。
四、結(jié)論
布隆過(guò)濾器用于判斷一個(gè)元素是否在一個(gè)集合中，不會(huì)有假負(fù)例（將在集合中的元素誤判不在集合中），但會(huì)有一定的誤識(shí)率（將不在集合中的元素誤判為在集合中）。
方案對(duì)比結(jié)論：
五、附錄
1.公式推導(dǎo)
（1）k次哈希函數(shù)某一bit(長(zhǎng)度為m）未被置為1的概率為：
（2）插入n個(gè)元素后依舊為 0 的概率和為 1 的概率分別是：
（3）k個(gè)位置均被設(shè)為1的概率：
2.如何讓誤識(shí)率降到最低？
3.哈希函數(shù)怎么設(shè)計(jì)？
要點(diǎn)：
Independent 相互獨(dú)立
Uniformly distributed.離散型均勻分布（概率相同）
They should also be as fast as possible. 要快
案例分享：
Chromium uses HashMix
python-bloomfilter uses cryptographic hashes（cryptographic hashes）
Plan9 uses a simple hash as proposed in Mitzenmacher 2005
Sdroege Bloom filter uses fnv1a (included just because I wanted to show one that uses fnv.)Squid uses MD5
4.參考文章
（1）布隆過(guò)濾器應(yīng)用：
https://www.pdai.tech/md/algorithm/alg-domain-bigdata-bloom-filter.html
（2）Hash函數(shù)設(shè)計(jì)：
https://llimllib.github.io/bloomfilter-tutorial/
（3）函數(shù)推導(dǎo)參考：
https://blog.csdn.net/quiet_girl/article/details/88523974
作者簡(jiǎn)介
杭天夢(mèng)
微信支付數(shù)據(jù)開(kāi)發(fā)工程師
微信支付數(shù)據(jù)開(kāi)發(fā)工程師。畢業(yè)于清華大學(xué)，碩士學(xué)位。2018年加入騰訊。現(xiàn)在從事大數(shù)據(jù)相關(guān)工作，現(xiàn)研究方向主要包括異動(dòng)數(shù)據(jù)歸因分析、多源數(shù)據(jù)策略選擇、知識(shí)圖譜實(shí)體對(duì)齊等。
推薦閱讀
