寫(xiě)在前面

在大數(shù)據(jù)與云計(jì)算發(fā)展的時(shí)代舒憾，我們經(jīng)常會(huì)碰到這樣的問(wèn)題控轿。我們是否能高效的判斷一個(gè)用戶(hù)是否訪問(wèn)過(guò)某網(wǎng)站的主頁(yè)（每天訪問(wèn)量上億）或者需要統(tǒng)計(jì)網(wǎng)站的pv叶雹、uv解阅。最直接的想法是將所有的訪問(wèn)者存起來(lái)柄瑰，然后每次用戶(hù)訪問(wèn)的時(shí)候與之前集合進(jìn)行比較闸氮。不管是將訪問(wèn)信息存在內(nèi)存（或數(shù)據(jù)庫(kù)）都會(huì)對(duì)服務(wù)器造成非常大的壓力。那是否存在一種方式狱意，容忍一定的錯(cuò)誤率湖苞，高效（計(jì)算復(fù)雜度、空間復(fù)雜度）的實(shí)現(xiàn)訪問(wèn)量信息的跟蹤详囤、統(tǒng)計(jì)呢财骨？接下來(lái)介紹的布隆過(guò)濾器（BloomFilter）就可以滿(mǎn)足當(dāng)前的使用場(chǎng)景（注釋?zhuān)夯鶖?shù)計(jì)數(shù)法同樣能滿(mǎn)足pv、uv的統(tǒng)計(jì)）藏姐。

布隆過(guò)濾器簡(jiǎn)介

布隆過(guò)濾器（BloomFilter）是1970年由布隆提出的一種空間空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)隆箩，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并判斷一個(gè)元素是否屬于這個(gè)集合羔杨。使用布隆過(guò)濾器捌臊，存在第一類(lèi)出錯(cuò)（Falsepositive），但是不會(huì)存在第二類(lèi)錯(cuò)誤（Falsenegative）兜材，因此理澎，布隆過(guò)濾器擁有100%的召回率。也就是說(shuō)曙寡，布隆過(guò)濾器能夠準(zhǔn)確判斷一個(gè)元素不在集合內(nèi)糠爬，但只能判斷一個(gè)元素可能在集合內(nèi)。因此举庶，BloomFilter不適合“零錯(cuò)誤”的應(yīng)用場(chǎng)合执隧。在能夠容忍低錯(cuò)誤的應(yīng)用場(chǎng)合下，BloomFilter通過(guò)極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省户侥。我們可以向布隆過(guò)濾器里添加元素镀琉，但是不能從中移除元素（普通布隆過(guò)濾器，增強(qiáng)的布隆過(guò)濾器是可以移除元素的）蕊唐。隨著布隆過(guò)濾器中元素的增加屋摔，犯第一類(lèi)錯(cuò)誤的可能性也隨之增大。

算法描述

一個(gè)空的布隆過(guò)濾器有長(zhǎng)度為M比特的bit數(shù)組構(gòu)成替梨，且所有位都初始化0钓试。一個(gè)元素通過(guò)K個(gè)不同的hash函數(shù)隨機(jī)散列到bit數(shù)組的K個(gè)位置上署尤，K必須遠(yuǎn)小于M。K和M的大小由錯(cuò)誤率（falsepositiverate）決定亚侠。

Bloom Filter的一個(gè)例子集合S｛x，y俗扇，z｝硝烂。帶有顏色的箭頭表示元素經(jīng)過(guò)k（k＝3）hash函數(shù)的到在M（bit數(shù)組）中的位置。元素W不在S集合中铜幽，因?yàn)樵豔經(jīng)過(guò)k個(gè)hash函數(shù)得到在M（bit數(shù)組）的k個(gè)位置中存在值為0的位置滞谢。

向集合S中添加元素x：x經(jīng)過(guò)k個(gè)散列函數(shù)后，在M中得到k個(gè)位置除抛，然后狮杨，將這k個(gè)位置的值設(shè)置為1。

判斷x元素是否在集合S中：x經(jīng)過(guò)k個(gè)散列函數(shù)后到忽，的到k個(gè)位置的值橄教，如果這k個(gè)值中間存在為0的，說(shuō)明元素x不在集合中——元素x曾經(jīng)插入到過(guò)集合S喘漏，則M中的k個(gè)位置會(huì)全部置為1护蝶；如果M中的k個(gè)位置全為1，則有兩種情形翩迈。情形一：這個(gè)元素在這個(gè)集合中持灰；情形二：曾經(jīng)有元素插入的時(shí)候?qū)⑦@k個(gè)位置的值置為1了（第一類(lèi)錯(cuò)誤產(chǎn)生的原因FalsePositive）。簡(jiǎn)單的布隆過(guò)濾器無(wú)法區(qū)分這兩種情況负饲，在增強(qiáng)版中解決了這個(gè)問(wèn)題堤魁。

設(shè)計(jì)k個(gè)相互獨(dú)立的hash函數(shù)可能工作量比較大，但是一個(gè)好的hash函數(shù)是降低誤判率的關(guān)鍵返十。一個(gè)良好的hash函數(shù)應(yīng)該有寬輸出妥泉，他們之間的沖突應(yīng)盡量低，這樣k個(gè)hash函數(shù)能靜可能的將值hash的更多的位置吧慢。hash函數(shù)的設(shè)計(jì)是我們可以將k個(gè)不同的值（?0, 1, ...,?k???1）作為參數(shù)傳入涛漂，或者將它們加入主鍵中。對(duì)于大的M或者k检诗，hash函數(shù)之間的獨(dú)立性對(duì)誤判率影響非常大（(Dillinger & Manolios (2004a),Kirsch & Mitzenmacher (2006))）,Dillinger在k個(gè)散列函數(shù)中匈仗，多次使用同一個(gè)函數(shù)散列，分析對(duì)誤判率的影響逢慌。

對(duì)于簡(jiǎn)單布隆過(guò)濾器來(lái)說(shuō)悠轩，從集合S中移除元素x是不可能的，且falsenegatives不允許攻泼。元素散列到k個(gè)位置火架，盡管可以 將這k個(gè)位置的值置為0來(lái)移除這個(gè)元素鉴象，但是這同事也移除了那些散落后，有值落在這k位中的元素何鸡。因此纺弊，沒(méi)有一種方法可以判斷移除這個(gè)元素后是否影響其它已經(jīng)加入集合中的元素，將k個(gè)位置置為0會(huì)引入二類(lèi)誤差（falsenegative）骡男。

時(shí)間復(fù)雜度和空間復(fù)雜度

在falsepositives的情況下淆游，布隆過(guò)濾器相比其它的集合（平衡二叉樹(shù)、樹(shù)隔盛、hash表犹菱、數(shù)組、鏈表）只需要少量的存儲(chǔ)空間吮炕。布隆過(guò)濾器的添加和檢查元素是否在集合內(nèi)的復(fù)雜度為O(K)腊脱。Hash表的平均復(fù)雜度比布隆過(guò)濾器更低。Bloom過(guò)濾器在誤差最優(yōu)的情況下龙亲，平均每個(gè)元素大概是1.44bit陕凹。

錯(cuò)誤率估計(jì)

布隆過(guò)濾器判斷一個(gè)元素是否屬于它表示的集合時(shí)會(huì)存在已定的錯(cuò)誤率（falsepositiverate），接下來(lái)就估計(jì)錯(cuò)誤率的大小俱笛。在估計(jì)誤差前捆姜，我們假設(shè)kn<m(k哈希函數(shù)的個(gè)數(shù)，n集合中元素的個(gè)數(shù)迎膜，mbit數(shù)組的長(zhǎng)度）且哈希函數(shù)之間時(shí)相互獨(dú)立的泥技，哈希函數(shù)散列的bit數(shù)組M中的位置時(shí)完全隨機(jī)的。

一個(gè)長(zhǎng)度為m的bit數(shù)組磕仅，元素在插入時(shí)經(jīng)過(guò)一次哈希散列后bit數(shù)組的某個(gè)位置的值沒(méi)有被置為1的概率為

經(jīng)過(guò)k個(gè)哈希函數(shù)散列后珊豹，還未被置為1的概率為

如果插入n個(gè)元素后，該位置還未被置為1的概率為

所以被置為1的概率為

現(xiàn)在判斷一個(gè)元素是否在結(jié)合中榕订，經(jīng)過(guò)k個(gè)函數(shù)散列到k個(gè)bit數(shù)組的不同位置店茶。所有這些位置的值為1的概率——誤判率。

這里使用了極限

這種計(jì)算方法不嚴(yán)格劫恒，因?yàn)榍懊婕僭O(shè)哈希函數(shù)和散列后值的分布是相互獨(dú)立的贩幻。但是，這個(gè)假設(shè)隨著m和n的增大誤判率更接近真實(shí)的誤判率两嘴。

Mitzenmacher and Upfal證明無(wú)假設(shè)情況下的誤判率的期望值相同丛楚。

最優(yōu)的哈希函數(shù)個(gè)數(shù)

既然布隆過(guò)濾器將集合映射到位數(shù)組中，那么選多少個(gè)hash函數(shù)才是錯(cuò)誤率最低的情況憔辫。這里有兩個(gè)互斥的理由：如果哈希函數(shù)的個(gè)數(shù)多趣些，那么在對(duì)一個(gè)不屬于集合的元素進(jìn)行查詢(xún)時(shí)得到0的概率就大；但另一方面贰您，如果哈希函數(shù)的個(gè)數(shù)少坏平，那么位數(shù)組中的0就多拢操。為了得到最優(yōu)的哈希函數(shù)個(gè)數(shù)，我們需要根據(jù)上一小節(jié)中的錯(cuò)誤率公式進(jìn)行計(jì)算舶替。

誤判率

兩邊取自然對(duì)數(shù)令境，

，只要g取最小值顾瞪，p就能取到最小值展父。由于p＝e^(-nk/m),我們可以將g改寫(xiě)為

根據(jù)對(duì)稱(chēng)法則可以得到當(dāng)p＝1/2時(shí)，也就是k＝ln2*(m/n)時(shí)玲昧，g取得最小值，在這種情況下篮绿，最小的錯(cuò)誤率p＝（1/2）^k≈(0.6185)^(m/n)孵延。p＝1/2對(duì)應(yīng)著位數(shù)組中0和1各半。換句話說(shuō)亲配，想保持錯(cuò)誤率低尘应，最好讓位數(shù)組有一半還空著。

位數(shù)組的大小

在給定n（集合中元素的個(gè)數(shù)）和錯(cuò)誤率（最優(yōu)函數(shù)個(gè)數(shù)k的的錯(cuò)誤率）的情況下吼虎，位數(shù)組M的大小計(jì)算犬钢，在最優(yōu)k的情況下

化簡(jiǎn)為

得到

這意味著在錯(cuò)誤率為p的情況下，布隆過(guò)濾器的長(zhǎng)度為m才能容納n個(gè)元素（以上計(jì)算基于n,m->∞）思灰。

布隆過(guò)濾器中元素個(gè)數(shù)的估算

Swamidass & Baldi (2007)給出了布隆過(guò)濾器元素個(gè)數(shù)估算的方法（詳細(xì)證明方式參考論文）

其中玷犹，n*表示布隆過(guò)濾元素個(gè)數(shù)的估算值，m表示布隆過(guò)濾器的大小洒疚，k表示哈希函數(shù)的個(gè)數(shù)歹颓，X表示布隆過(guò)濾器位值位1的個(gè)數(shù)。

布隆過(guò)濾器的并和交

布隆過(guò)濾器可以用來(lái)估算兩個(gè)集合之間的并合交油湖。一下給出兩個(gè)集合之間并的計(jì)算方式：

A和B之間的并集的個(gè)數(shù)為：

所以A*與B*之間的交集的個(gè)數(shù)為：

布隆過(guò)濾的特性

布隆過(guò)濾器能夠容納任意多的元素（誤判率會(huì)增加）巍扛，總是能向布隆過(guò)濾器中添加元素，不會(huì)報(bào)錯(cuò)（OutMemory等）;

布隆過(guò)濾器可以很方便的通過(guò)計(jì)算機(jī)的or \and操作計(jì)算兩個(gè)集合元素之間的交集（intersection）和并集（union）,但是同樣影響布隆過(guò)濾的準(zhǔn)確性乏德。

例子

Googlebigtable撤奸、apachehbase和apachecassandra使用bloom過(guò)濾器判斷是否存在該行（rows）或（colums），以減少對(duì)磁盤(pán)的訪問(wèn)喊括，提高數(shù)據(jù)庫(kù)的訪問(wèn)性能胧瓜；

比特幣使用布隆過(guò)濾判斷錢(qián)包是否同步OK。

總結(jié)

在計(jì)算機(jī)這個(gè)領(lǐng)域里瘾晃，我們常常碰到時(shí)間換空間\或空間換時(shí)間的情況贷痪，為了達(dá)到某一方面的性能，犧牲另外一方面蹦误。BloomFilter在時(shí)間和空間著兩者之間引入了另外一個(gè)概念——錯(cuò)誤率劫拢。也就是前文提到的布隆過(guò)濾不能準(zhǔn)確判斷一個(gè)元素是否在集合內(nèi)（類(lèi)似的設(shè)計(jì)還有基數(shù)統(tǒng)計(jì)法）肉津。引入錯(cuò)誤率后，極大的節(jié)省了存儲(chǔ)空間舱沧。

自從Burton Bloom在70年代提出Bloom Filter之后妹沙，Bloom Filter就被廣泛用于拼寫(xiě)檢查和數(shù)據(jù)庫(kù)系統(tǒng)中。近一二十年熟吏，伴隨著網(wǎng)絡(luò)的普及和發(fā)展距糖，Bloom Filter在網(wǎng)絡(luò)領(lǐng)域獲得了新生，各種Bloom Filter變種和新的應(yīng)用不斷出現(xiàn)牵寺『芬可以預(yù)見(jiàn)，隨著網(wǎng)絡(luò)應(yīng)用的不斷深入帽氓，新的變種和應(yīng)用將會(huì)繼續(xù)出現(xiàn)趣斤，Bloom Filter必將獲得更大的發(fā)展。

---------------------

作者：永不言棄01

來(lái)源：CSDN

原文：https://blog.csdn.net/lvsaixia/article/details/51503231

版權(quán)聲明：本文為博主原創(chuàng)文章黎休，轉(zhuǎn)載請(qǐng)附上博文鏈接浓领！