大數(shù)據(jù)常見(jiàn)處理方法總結(jié)

《海量數(shù)據(jù)處理常用思路和方法》大數(shù)據(jù)量，海量數(shù)據(jù)處理方法總結(jié)最近有點(diǎn)忙，稍微空閑下來(lái)，發(fā)篇總結(jié)貼。大數(shù)據(jù)量的問(wèn)題是很多面試筆試中經(jīng)常出現(xiàn)的問(wèn)題，比如baidugoogle騰訊這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會(huì)問(wèn)到。下面的方法是我對(duì)海量數(shù)據(jù)的處理方法進(jìn)行了一個(gè)一般性的總結(jié)，當(dāng)然這些方法可能并不能完全覆蓋所有的問(wèn)題，但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問(wèn)題。下面的一些問(wèn)題基本直接來(lái)源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討論。l.Bloomfilter適用范圍：可以用來(lái)實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集基本原理及要點(diǎn)：對(duì)于原理來(lái)說(shuō)很簡(jiǎn)單，位數(shù)組+k個(gè)獨(dú)立hash函數(shù)。將hash函數(shù)對(duì)應(yīng)的值的位數(shù)組置1，查找時(shí)如果發(fā)現(xiàn)所有hash函數(shù)對(duì)應(yīng)位都是1說(shuō)明存在，很明顯這個(gè)過(guò)程并不保證查找的結(jié)果是100%正確的。同時(shí)也不支持刪除一個(gè)已經(jīng)插入的關(guān)鍵字，因?yàn)樵撽P(guān)鍵字對(duì)應(yīng)的位會(huì)牽動(dòng)到其他的關(guān)鍵字。所以一個(gè)簡(jiǎn)單的改進(jìn)就是countingBloomfilter，用一個(gè)counter數(shù)組代替位數(shù)組，就可以支持刪除了。還有一個(gè)比較重要的問(wèn)題，如何根據(jù)輸入元素個(gè)數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個(gè)數(shù)。當(dāng)hash函數(shù)個(gè)數(shù)k=(ln2)*(m/n)時(shí)錯(cuò)誤率最小。在錯(cuò)誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個(gè)元素的集合。但m還應(yīng)該更大些，因?yàn)檫€要保證bit數(shù)組里至少一半為0，則m應(yīng)該＞=nlg(1/E)*lge大概就是nlg(1/E)1.44倍(lg表示以2為底的對(duì)數(shù))。舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01，則此時(shí)m應(yīng)大概是n的13倍。這樣k大概是8個(gè)。注意這里m與n的單位不同，m是bit為單位，而n則是以元素個(gè)數(shù)為單位(準(zhǔn)確的說(shuō)是不同元素的個(gè)數(shù))。通常單個(gè)元素的長(zhǎng)度都是有很多bit的。所以使用bloomfilter內(nèi)存上通常都是節(jié)省的。擴(kuò)展：Bloomfilter將集合中的元素映射到位數(shù)組中，用k(k為哈希函數(shù)個(gè)數(shù))個(gè)映射位是否全1表示元素在不在這個(gè)集合中。Countingbloomfilter(CBF)將位數(shù)組中的每一位擴(kuò)展為一個(gè)counter，從而支持了元素的刪除操作。SpectralBloomFilter(SBF)將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來(lái)近似表示元素的出現(xiàn)頻率。問(wèn)題實(shí)例：給你A,B兩個(gè)文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個(gè)乃至n個(gè)文件呢？根據(jù)這個(gè)問(wèn)題我們來(lái)計(jì)算下內(nèi)存的占用，4G=2八32大概是40億*8大概是340億，n=50億，如果按出錯(cuò)率0.01算需要的大概是650億個(gè)bit。現(xiàn)在可用的是340億，相差并不多，這樣可能會(huì)使出錯(cuò)率上升些。另外如果這些urlip是一一對(duì)應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡(jiǎn)單了。2.Hashing適用范圍：快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存基本原理及要點(diǎn)：hash函數(shù)選擇，針對(duì)字符串，整數(shù)，排列，具體相應(yīng)的hash方法。碰撞處理，一種是openhashing，也稱(chēng)為拉鏈法；另一種就是closedhashing，也稱(chēng)開(kāi)地址法，openedaddressingo擴(kuò)展：d-lefthashing中的d是多個(gè)的意思，我們先簡(jiǎn)化這個(gè)問(wèn)題，看一看2-lefthashing。2-lefthashing指的是將一個(gè)哈希表分成長(zhǎng)度相等的兩半，分別叫做T1和T2,給T1和T2分別配備一個(gè)哈希函數(shù)，h1和h2。在存儲(chǔ)一個(gè)新的key時(shí)，同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1[key]和h2[key]。這時(shí)需要檢查T(mén)1中的h1[key]位置和T2中的h2[key]位置，哪一個(gè)位置已經(jīng)存儲(chǔ)的（有碰撞的）key比較多，然后將新key存儲(chǔ)在負(fù)載少的位置。如果兩邊一樣多，比如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key,就把新key存儲(chǔ)在左邊的T1子表中，2-left也由此而來(lái)。在查找一個(gè)key時(shí)，必須進(jìn)行兩次hash,同時(shí)查找兩個(gè)位置。問(wèn)題實(shí)例：1）.海量日志數(shù)據(jù)，提取出某日訪問(wèn)百度次數(shù)最多的那個(gè)IPoIP的數(shù)目還是有限的，最多2人32個(gè)，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進(jìn)行統(tǒng)計(jì)。3.bitmap適用范圍：可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來(lái)說(shuō)數(shù)據(jù)范圍是int的10倍以下基本原理及要點(diǎn)：使用bit數(shù)組來(lái)表示某些元素是否存在，比如8位電話(huà)號(hào)碼擴(kuò)展：bloomfilter可以看做是對(duì)bit-map的擴(kuò)展問(wèn)題實(shí)例：1）已知某個(gè)文件內(nèi)包含一些電話(huà)號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。8位最多99999999,大概需要99m個(gè)bit,大概10幾m字節(jié)的內(nèi)存即可。2）2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。將bit-map擴(kuò)展一下，用2bit表示一個(gè)數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上。或者我們不用2bit來(lái)進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map。.堆適用范圍：海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存基本原理及要點(diǎn)：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當(dāng)前元素與最大堆里的最大元素，如果它小于最大元素，則應(yīng)該替換那個(gè)最大元素。這樣最后得到的n個(gè)元素就是最小的n個(gè)。適合大數(shù)據(jù)量，求前n小，n的大小比較小的情況，這樣可以?huà)呙枰槐榧纯傻玫剿械那皀元素，效率很高。擴(kuò)展：雙堆，一個(gè)最大堆與一個(gè)最小堆結(jié)合，可以用來(lái)維護(hù)中位數(shù)。問(wèn)題實(shí)例：1)100w個(gè)數(shù)中找最大的前100個(gè)數(shù)。用一個(gè)100個(gè)元素大小的最小堆即可。.雙層桶劃分----其實(shí)本質(zhì)上就是【分而治之】的思想，重在''分"的技巧上！適用范圍：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字基本原理及要點(diǎn)：因?yàn)樵胤秶艽?，不能利用直接尋址表，所以通過(guò)多次劃分，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行?？梢酝ㄟ^(guò)多次縮小，雙層只是一個(gè)例子。擴(kuò)展：?jiǎn)栴}實(shí)例：.2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。有點(diǎn)像鴿巢原理，整數(shù)個(gè)數(shù)為2八32,也就是，我們可以將這2人32個(gè)數(shù)，劃分為2八8個(gè)區(qū)域(比如用單個(gè)文件代表一個(gè)區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說(shuō)只要有足夠的磁盤(pán)空間，就可以很方便的解決。.5億個(gè)int找它們的中位數(shù)。這個(gè)例子比上面那個(gè)更明顯。首先我們將int劃分為2八16個(gè)區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個(gè)區(qū)域里的數(shù)的個(gè)數(shù)，之后我們根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到那個(gè)區(qū)域，同時(shí)知道這個(gè)區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計(jì)落在這個(gè)區(qū)域中的那些數(shù)就可以了。實(shí)際上，如果不是int是int64,我們可以經(jīng)過(guò)3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2人24個(gè)區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2人20個(gè)子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個(gè)數(shù)只有2八20，就可以直接利用directaddrtable進(jìn)行統(tǒng)計(jì)了。.數(shù)據(jù)庫(kù)索引適用范圍：大數(shù)據(jù)量的增刪改查基本原理及要點(diǎn)：利用數(shù)據(jù)的設(shè)計(jì)實(shí)現(xiàn)方法，對(duì)海量數(shù)據(jù)的增刪改查進(jìn)行處理。擴(kuò)展：?jiǎn)栴}實(shí)例：.倒排索引(Invertedindex)適用范圍：搜索引擎，關(guān)鍵字查詢(xún)基本原理及要點(diǎn)：為何叫倒排索引？一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。以英文為例，下面是要被索引的文本：T0="itiswhatitis"T1="whatisit"T2="itisabanana"我們就能得到下面的反向文件索引："a": {2}"banana":{2}"is": {0,1,2}"it": {0,1,2}"what":{0,1}檢索的條件"what","is"和"it"將對(duì)應(yīng)集合的交集。正向索引開(kāi)發(fā)出來(lái)用來(lái)存儲(chǔ)每個(gè)文檔的單詞的列表。正向索引的查詢(xún)往往滿(mǎn)足每個(gè)文檔有序頻繁的全文查詢(xún)和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢(xún)。在正向索引中，文檔占據(jù)了中心的位置，每個(gè)文檔指向了一個(gè)它所包含的索引項(xiàng)的序列。也就是說(shuō)文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個(gè)反向的關(guān)系。擴(kuò)展：?jiǎn)栴}實(shí)例：文檔檢索系統(tǒng)，查詢(xún)那些文件包含了某單詞，比如常見(jiàn)的學(xué)術(shù)論文的關(guān)鍵字搜索。.外排序適用范圍：大數(shù)據(jù)的排序，去重基本原理及要點(diǎn)：外排序的歸并方法，置換選擇敗者樹(shù)原理，最優(yōu)歸并樹(shù)擴(kuò)展：?jiǎn)栴}實(shí)例：.有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16個(gè)字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。這個(gè)數(shù)據(jù)具有很明顯的特點(diǎn)，詞的大小為16個(gè)字節(jié)，但是內(nèi)存只有1m做hash有些不夠，所以可以用來(lái)排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用。.trie樹(shù)適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類(lèi)小可以放入內(nèi)存基本原理及要點(diǎn)：實(shí)現(xiàn)方式，節(jié)點(diǎn)孩子的表示方式擴(kuò)展：壓縮實(shí)現(xiàn)。問(wèn)題實(shí)例：.有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行都存放的是用戶(hù)的query，每個(gè)文件的query都可能重復(fù)。要你按照query的頻度排序。.1000萬(wàn)字符串，其中有些是相同的(重復(fù))，需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串。請(qǐng)問(wèn)怎么設(shè)計(jì)和實(shí)現(xiàn)？.尋找熱門(mén)查詢(xún)：查詢(xún)串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)，每個(gè)不超過(guò)255字節(jié)。.分布式處理mapreduce適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類(lèi)小可以放入內(nèi)存基本原理及要點(diǎn)：將數(shù)據(jù)交給不同的機(jī)器去處理，數(shù)據(jù)劃分，結(jié)果歸約。1.Bloom-Filter算法簡(jiǎn)介Bloom-Filter,即布隆過(guò)濾器，1970年由Bloom中提出。它可以用于檢索一個(gè)元素是否在一個(gè)集合中。BloomFilter（BF）是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。它是一個(gè)判斷元素是否存在集合的快速的概率算法。BloomFilter有可能會(huì)出現(xiàn)錯(cuò)誤判斷，但不會(huì)漏掉判斷。也就是BloomFilter判斷元素不再集合，那肯定不在。如果判斷元素存在集合中，有一定的概率判斷錯(cuò)誤。因此，BloomFilter不適合那些"零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，BloomFilter比其他常見(jiàn)的算法（如hash，折半查找）極大節(jié)省了空間。它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。BloomFilter的詳細(xì)介紹：B100m^^2、Bloom-Filter的基本思想Bloom-Filter算法的核心思想就是利用多個(gè)不同的Hash函數(shù)來(lái)解決"沖突"。計(jì)算某元素x是否在一個(gè)集合中，首先能想到的方法就是將所有的已知元素保存起來(lái)構(gòu)成一個(gè)集合R，然后用元素x跟這些R中的元素一一比較來(lái)判斷是否存在于集合R中；我們可以采用鏈表等數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。但是，隨著集合R中元素的增加，其占用的內(nèi)存將越來(lái)越大。試想，如果有幾千萬(wàn)個(gè)不同網(wǎng)頁(yè)需要下載，所需的內(nèi)存將足以占用掉整個(gè)進(jìn)程的內(nèi)存地址空間。即使用MD5，UUID這些方法將URL轉(zhuǎn)成固定的短小的字符串，內(nèi)存占用也是相當(dāng)巨大的。于是，我們會(huì)想到用Hashtable的數(shù)據(jù)結(jié)構(gòu)，運(yùn)用一個(gè)足夠好的Hash函數(shù)將一個(gè)URL映射到二進(jìn)制位數(shù)組（位圖數(shù)組）中的某一位。如果該位已經(jīng)被置為1，那么表示該URL已經(jīng)存在。Hash存在一個(gè)沖突（碰撞）的問(wèn)題，用同一個(gè)Hash得到的兩個(gè)URL的值有可能相同。為了減少?zèng)_突，我們可以多引入幾個(gè)Hash，如果通過(guò)其中的一個(gè)Hash值我們得出某元素不在集合中，那么該元素肯定不在集合中。只有在所有的Hash函數(shù)告訴我們?cè)撛卦诩现袝r(shí)，才能確定該元素存在于集合中。這便是Bloom-Filter的基本思想。原理要點(diǎn)：一是位數(shù)組，而是k個(gè)獨(dú)立hash函數(shù)。1）位數(shù)組：假設(shè)BloomFilter使用一個(gè)m比特的數(shù)組來(lái)保存信息，初始狀態(tài)時(shí)，BloomFilter是一個(gè)包含m位的位數(shù)組，每一位都置為0，即BF整個(gè)數(shù)組的元素都設(shè)置為0。00°P00Q000002）添加元素，k個(gè)獨(dú)立hash函數(shù)為了表達(dá)S=｛x1,x2,…,xn｝這樣一個(gè)n個(gè)元素的集合,BloomFilter使用k個(gè)相互獨(dú)立的哈希函數(shù)（HashFunction），它們分別將集合中的每個(gè)元素映射到｛1,…,m｝的范圍中。當(dāng)我們往BloomFilter中增加任意一個(gè)元素x時(shí)候，我們使用k個(gè)哈希函數(shù)得到k個(gè)哈希值，然后將數(shù)組中對(duì)應(yīng)的比特位設(shè)置為1o即第i個(gè)哈希函數(shù)映射的位置hashj(x)就會(huì)被置為1(IWiWk)。注意，如果一個(gè)位置多次被置為1,那么只有第一次會(huì)起作用，后面幾次將沒(méi)有任何效果。在下圖中，k=3,且有兩個(gè)哈希函數(shù)選中同一個(gè)位置(從左邊數(shù)第五位，即第二個(gè)“1”處)。3)判斷元素是否存在集合在判斷y是否屬于這個(gè)集合時(shí)，我們只需要對(duì)y使用k個(gè)哈希函數(shù)得到k個(gè)哈希值，如果所有hashi(y)的位置都是1(IWiWk)，即k個(gè)位置都被設(shè)置為1了，那么我們就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。下圖中y1就不是集合中的元素(因?yàn)閥1有一處指向了“0”位)。y2或者屬于這個(gè)集合，或者剛好是一個(gè)falsepositiveo顯然這個(gè)判斷并不保證查找的結(jié)果是100%正確的。BloomFilter的缺點(diǎn)：1)BloomFilter無(wú)法從BloomFilter集合中刪除一個(gè)元素。因?yàn)樵撛貙?duì)應(yīng)的位會(huì)牽動(dòng)到其他的元素。所以一個(gè)簡(jiǎn)單的改進(jìn)就是countingBloomfilter用一個(gè)counter數(shù)組代替位數(shù)組，就可以支持刪除了。此外，BloomFilter的hash函數(shù)選擇會(huì)影響算法的效果。2)還有一個(gè)比較重要的問(wèn)題，如何根據(jù)輸入元素個(gè)數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個(gè)數(shù)，即hash函數(shù)選擇會(huì)影響算法的效果。當(dāng)hash函數(shù)個(gè)數(shù)k=(ln2)*(m/n)時(shí)錯(cuò)誤率最小。在錯(cuò)誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個(gè)元素的集合。但m還應(yīng)該更大些，因?yàn)檫€要保證bit數(shù)組里至少一半為0，則m應(yīng)該＞=川9(1隹)*內(nèi)6，大概就是nlg(1/E)1.44倍(lg表示以2為底的對(duì)數(shù))。舉個(gè)例子我們假設(shè)錯(cuò)誤率為0.01，則此時(shí)m應(yīng)大概是n的13倍。這樣k大概是8個(gè)。注意：這里m與n的單位不同，m是bit為單位，而n則是以元素個(gè)數(shù)為單位。隹確的說(shuō)是不同元素的個(gè)數(shù)）。通常單個(gè)元素的長(zhǎng)度都是有很多bit的。所以使用bloomfilter內(nèi)存上通常都是節(jié)省的。一般BF可以與一些key-value的數(shù)據(jù)庫(kù)一起使用，來(lái)加快查詢(xún)。由于BF所用的空間非常小，所有BF可以常駐內(nèi)存。這樣子的話(huà)，對(duì)于大部分不存在的元素，我們只需要訪問(wèn)內(nèi)存中的BF就可以判斷出來(lái)了，只有一小部分，我們需要訪問(wèn)在硬盤(pán)上的key-value數(shù)據(jù)庫(kù)。從而大大地提高了效率。一個(gè)BloomFilter有以下參數(shù):m bit數(shù)組的寬度（bit數(shù)）n 加入其中的key的數(shù)量k 使用的hash函數(shù)的個(gè)數(shù)f FalsePositive的比率由于k必須取整數(shù)，我們?cè)贐loomFilter的程序?qū)崿F(xiàn)中，還應(yīng)該使用上面的公式來(lái)求得實(shí)際的f：f=(1-e-kn/m)k ⑶以上3個(gè)公式是程序?qū)崿F(xiàn)BloomFilter的關(guān)鍵公式。3、擴(kuò)展CounterBloomFilterCounterBloomFilterBloomFilter有個(gè)缺點(diǎn)，就是不支持刪除操作，因?yàn)樗恢滥骋粋€(gè)位從屬于哪些向量。那我們可以給BloomFilter加上計(jì)數(shù)器，添加時(shí)增加計(jì)數(shù)器，刪除時(shí)減少計(jì)數(shù)器。但這樣的Filter需要考慮附加的計(jì)數(shù)器大小，假如同個(gè)元素多次插入的話(huà)，計(jì)數(shù)器位數(shù)較少的情況下，就會(huì)出現(xiàn)溢出問(wèn)題。如果對(duì)計(jì)數(shù)器設(shè)置上限值的話(huà)，會(huì)導(dǎo)致CacheMiss，但對(duì)某些應(yīng)用來(lái)說(shuō)，這并不是什么問(wèn)題，如WebSharingoCompressedBloomFilter為了能在服務(wù)器之間更快地通過(guò)網(wǎng)絡(luò)傳輸BloomFilter,我們有方法能在已完成BloomFilter之后，得到一些實(shí)際參數(shù)的情況下進(jìn)行壓縮。將元素全部添加入BloomFilter后，我們能得到真實(shí)的空間使用率，用這個(gè)值代入公式計(jì)算出一個(gè)比m小的值，重新構(gòu)造BloomFilter,對(duì)原先的哈希值進(jìn)行求余處理，在誤判率不變的情況下，使得其內(nèi)存大小更合適。4、Bloom-Filter的應(yīng)用Bloom-Filter一般用于在大數(shù)據(jù)量的集合中判定某元素是否存在。例如郵件服務(wù)器中的垃圾郵件過(guò)濾器。在搜索引擎領(lǐng)域，Bloom-Filter最常用于網(wǎng)絡(luò)蜘蛛(Spider)的URL過(guò)濾，網(wǎng)絡(luò)蜘蛛通常有一個(gè)URL列表，保存著將要下載和已經(jīng)下載的網(wǎng)頁(yè)的URL，網(wǎng)絡(luò)蜘蛛下載了一個(gè)網(wǎng)頁(yè)，從網(wǎng)頁(yè)中提取到新的URL后，需要判斷該URL是否已經(jīng)存在于列表中。此時(shí)，Bloom-Filter算法是最好的選擇。l.key-value加快查詢(xún)一般Bloom-Filter可以與一些key-value的數(shù)據(jù)庫(kù)一起使用，來(lái)加快查詢(xún)。一般key-value存儲(chǔ)系統(tǒng)的values存在硬盤(pán)，查詢(xún)就是件費(fèi)時(shí)的事。將Storage的數(shù)據(jù)都插入Filter，在Filter中查詢(xún)都不存在時(shí)，那就不需要去Storage查詢(xún)了。當(dāng)FalsePosition出現(xiàn)時(shí)，只是會(huì)導(dǎo)致一次多余的Storage查詢(xún)。由于Bloom-Filter所用的空間非常小，所有BF可以常駐內(nèi)存。這樣子的話(huà)，對(duì)于大部分不存在的元素，我們只需要訪問(wèn)內(nèi)存中的Bloom-Filter就可以判斷出來(lái)了，只有一小部分，我們需要訪問(wèn)在硬盤(pán)上的key-value數(shù)據(jù)庫(kù)。從而大大地提高了效率。如圖：FI1TER STORAGEDoyouhavtk卬ITFils：Stonjc:NoNoIfon?essaxydiskaccessStuiagc: -fcrYesYssYes:heieisYes: i3kejz?FilscFijsitiiieFiltti：unriscesjaxi.rdiskaccessStciaje;NoYG5No.Google的BigTableGoogle的BigTable也使用了BloomFilter，以減少不存在的行或列在磁盤(pán)上的查詢(xún)，大大提高了數(shù)據(jù)庫(kù)的查詢(xún)操作的性能。.Proxy-Cache在InternetCacheProtocol中的Proxy-Cache很多都是使用BloomFilter存儲(chǔ)URLs,除了高效的查詢(xún)外，還能很方便得傳輸交換Cache信息。.網(wǎng)絡(luò)應(yīng)用1）P2P網(wǎng)絡(luò)中查找資源操作，可以對(duì)每條網(wǎng)絡(luò)通路保存BloomFilter,當(dāng)命中時(shí)，則選擇該通路訪問(wèn)。2）廣播消息時(shí)，可以檢測(cè)某個(gè)IP是否已發(fā)包。3）檢測(cè)廣播消息包的環(huán)路，將BloomFilter保存在包里，每個(gè)節(jié)點(diǎn)將自己添力口入BloomFilter。4）信息隊(duì)列管理，使用CounterBloomFilter管理信息流量。.垃圾郵件地址過(guò)濾像網(wǎng)易，QQ這樣的公眾電子郵件（email）提供商，總是需要過(guò)濾來(lái)自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的email地址。由于那些發(fā)送者不停地在注冊(cè)新的地址，全世界少說(shuō)也有幾十億個(gè)發(fā)垃圾郵件的地址，將他們都存起來(lái)則需要大量的網(wǎng)絡(luò)服務(wù)器。如果用哈希表，每存儲(chǔ)一億個(gè)email地址，就需要1.6GB的內(nèi)存（用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè)email地址對(duì)應(yīng)成一個(gè)八字節(jié)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲(chǔ)效率一般只有50%,因此一個(gè)email地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要1.6GB,即十六億字節(jié)的內(nèi)存）。因此存貯幾十億個(gè)郵件地址可能需要上百GB的內(nèi)存。而B(niǎo)loomFilter只需要哈希表1/8到1/4的大小就能解決同樣的問(wèn)題。BloomFilter決不會(huì)漏掉任何一個(gè)在黑名單中的可疑地址。而至于誤判問(wèn)題，常見(jiàn)的補(bǔ)救辦法是在建立一個(gè)小的白名單，存儲(chǔ)那些可能別誤判的郵件地址。5、Bloom-Filter的具體實(shí)現(xiàn)c語(yǔ)言實(shí)現(xiàn)：stdafx.h:#pragmaonce#include<stdio.h>#include"stdlib.h"#include<iostream>#include<time.h>usingnamespacestd;

#include"stdafx.h"#defineARRAY_SIZE256/*wegetthe256charsofeachline*/#defineSIZE/*sizeshouldbe1/8ofmax*/#defineMAX/*themaxbitspace*/#defineSETBIT(ch,n)ch[n/8]|=1<<(7-n%8)#defineGETBIT(ch,n)(ch[n/8]&1<<(7-n%8))>>(7-n%8)unsignedintlen(char*ch);/*functionstocalculatethelengthoftheurl*/unsignedintRSHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintJSHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintPJWHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintELFHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintBKDRHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintSDBMHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintDJBHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintDEKHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintBPHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintFNVHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintAPHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintHFLPHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintHFHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintStrHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/unsignedintTianlHash(char*str,unsignedintlen);/*functionstocalculatethehashvalueoftheurl*/29.

intmain()(inti,num,num2=0;/*thenumbertorecordtherepeatedurlsandthetotalofit*/unsignedinttt=0;intflag; /*ithelpstocheckweathertheurlhasalreadyexisted*/charbuf[257]; /*ithelpstoprintthestarttimeoftheprogram*/time_ttmp=time(NULL);char file1[100],file2[100];FILE *fp1,*fp2;/*pointer to thefile*/char ch[ARRAY_SIZE]；char *vector;/*thebit space*/vector=(char*)calloc(SlZE,sizeof(char));printf("Pleaseenterthefilewithrepeatedurls:\n");scanf("%s”,&file1);if((fp1=fopen(file1,"rb"))==NULL){/*openthegoalfile*/printf("Connotopenthefile%s!\n",file1);}printf("Pleaseenterthefileyouwanttosaveto:\n");scanf("%s”,&file2);if((fp2=fopen(file2,"w"))==NULL){printf("Connotopenthefile%s\n",file2);TOC\o"1-5"\h\z}strftime(buf,32,"%Y-%m-%d %H:%M:%S",localtime(&tmp));printf("%s\n",buf); /*print the system time*/for(i=0;i<SIZE;i++) {vector[i]=0;/*set0*/}while(!feof(fp1)){/*thecheckprocess*/fgets(ch,ARRAY_SIZE,fp1)；flag=0;tt++;if(GETBIT(vector,HFLPHash(ch,len(ch))%MAX)){flag++;}else{SETBIT(vector,HFLPHash(ch,len(ch))%MAX);}if(GETBIT(vector,StrHash(ch,len(ch))%MAX)){

flag++;}else{SETBIT(vector,StrHash(ch,len(ch))%MAX);TOC\o"1-5"\h\z}if(GETBIT(vector, HFHash(ch,len(ch))%MAX)) {flag++;}else{SETBIT(vector,HFHash(ch,len(ch))%MAX);}if(GETBIT(vector, DEKHash(ch,len(ch))%MAX)){flag++;}else{SETBIT(vector,DEKHash(ch,len(ch))%MAX);}if(GETBIT(vector, TianlHash(ch,len(ch))%MAX)){flag++;}else{SETBIT(vector,TianlHash(ch,len(ch))%MAX);}if(GETBIT(vector, SDBMHash(ch,len(ch))%MAX)){flag++;}else{SETBIT(vector,SDBMHash(ch,len(ch))%MAX);}if(flag<6)num2++;elsefputs(ch,fp2);/*printf("%d",flag);*/}/*theresult*/printf("\nThere are %d urls!\n",tt);printf("\nThere are %d notrepeatedurls!\n",num2);printf("Thereare%drepeatedurls!\n",tt-num2);fclose(fp1);fclose(fp2);return0;}

118./^functionsmaybeusedinthemain*/unsignedintlen(char*ch)(intm=0;while(ch[m]!='\0'){m++;}returnm;}unsignedintRSHash(char*str,unsignedintlen){131.unsignedintb=;132.unsignedinta=63689;133.unsignedinthash=0;134.unsignedinti=0;for(i=0;i<len;str++,i++){hash=hash*a+(*str);a=a*b;}returnhash;}/*EndOfRSHashFunction*/unsignedintJSHash(char*str,unsignedintlen){unsignedinthash=;unsignedinti =0;for(i=0;i<len;str++,i++){hashA=((hash<<5)+(*str)+(hash>>2));}returnhash;}/*EndOfJSHashFunction*/unsignedintPJWHash(char*str,unsignedintlen){constunsignedintBitsInUnsignedInt=(unsignedint)(sizeof(unsignedint)*8);constunsignedintThreeQuarters=(unsignedint)((BitsInUnsignedInt*3)/4);

constunsignedintOneEighth=(unsignedint)(BitsInUnsignedInt/8);constunsignedintHighBits=(unsignedint)(0xFFFFFFFF)<<(BitsInUnsignedInt-OneEighth);unsignedinthash=0;unsignedinttest=0;unsignedinti=0;for(i=0;i<len;str++,i++){hash=(hash<<OneEighth)+(*str);if((test=hash&HighBits)!=0){hash=((hash八(test>>ThreeQuarters))&(?HighBits));}}returnhash;}/*EndOfP.J.WeinbergerHashFunction*/unsignedintELFHash(char*str,unsignedintlen){TOC\o"1-5"\h\zunsigned int hash = 0;unsigned int x = 0;unsigned int i = 0;for(i=0;i<len;str++,i++){hash =(hash <<4) + (*str);if((x= hash &0xFL) != 0) {hash八二(x>>24);}hash &= ~x;}returnhash;}/*EndOfELFHashFunction*/unsignedintBKDRHash(char*str,unsignedintlen){unsigned int seed = 131; /*31131131313131etc..*/TOC\o"1-5"\h\zunsigned int hash = 0;unsigned int i = 0;for(i=0;i<len;str++,i++){

hash=(hash*seed)+(*str);}returnhash;}/*EndOfBKDRHashFunction*/unsignedintSDBMHash(char*str,unsignedintlen)(unsignedinthash=0;unsignedinti =0;for(i=0;i<len;str++,i++){hash=(*str)+(hash<<6)+(hash<<16)-hash;}returnhash;}/*EndOfSDBMHashFunction*/unsignedintDJBHash(char*str,unsignedintlen){unsignedinthash=5381;unsignedinti =0;for(i=0;i<len;str++,i++){hash=((hash<<5)+hash)+(*str);}returnhash;}/*EndOfDJBHashFunction*/unsignedintDEKHash(char*str,unsignedintlen){unsignedinthash=len;unsignedinti =0;for(i=0;i<len;str++,i++){hash=((hash<<5)八(hash>>27))八(*str);}

returnhash;}/*EndOfDEKHashFunction*/unsignedintBPHash(char*str,unsignedintlen)(257.258.unsignedinthash=0;unsignedinti=0;259.for(i=0;i<len;str++,i++){260.hash=hash<<7八(*str);}returnhash;}/*EndOfBPHashFunction*/unsignedintFNVHash(char*str,unsignedintlen)(constunsignedintfnv_prime=0x811C9DC5;271.unsignedinthash =0;272.unsignedinti =0;273.274.for(i=0;i<len;str++,i++){hash*=fnv_prime;hash八=(*str);}returnhash;}/*EndOfFNVHashFunction*/unsignedintAPHash(char*str,unsignedintlen)(unsignedinthash=0xAAAAAAAA;TOC\o"1-5"\h\zunsignedinti =0;for(i= 0; i< len; str++,i++){hash A= ((i &1) ==0)?((hash << 7)八(*str) * (hash >> 3))(~((hash << 11) + (*str)八(hash >> 5)))}

returnhash;}/*EndOfAPHashFunction*/unsignedintHFLPHash(char*str,unsignedintlen)(unsignedintn=0;inti;char*b=(char*)&n;for(i=0;i<strlen(str);++i){b[i%4]八=str[i];}returnn%len;}/*EndOfHFLPHashFunction*/unsignedintHFHash(char*str,unsignedintlen){intresult=0;char*ptr=str;intc;inti=0;for(i=1;c=*ptr++;i++)result+=c*3*i;if(result<0)result=-result;returnresult%len;}/*EndOfHKHashFunction*/unsignedintStrHash(char*str,unsignedintlen){registerunsignedinth;registerunsignedchar*p;for(h=0,p=(unsignedchar*)str;*p;p++){h=31*h+*p;}329.330.returnh;331.}/*EndOfStrHashFunction*/334.unsignedintTianlHash(char*str,unsignedintlen){unsignedlongurlHashValue=0;

intilength=strlen(str);inti;unsignedcharucChar;if(!ilength){return0;}if(ilength<=256){urlHashValue=*(ilength-1);}else{urlHashValue=;TOC\o"1-5"\h\z}if(ilength<=96){for(i=1;i<=ilength;i++){ucChar=str[i-1];if(ucChar<='Z'&&ucChar>='A') {ucChar=ucChar+32;}355. urlHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%;}}else{for(i=1;i<=96;i++){ucChar=str[i+ilength-96-1];if(ucChar<='Z'&&ucChar>='A'){ucChar=ucChar+32;}365. urlHashValue+=(3*i*ucChar*ucChar+5*i*ucChar+7*i+11*ucChar)%;}}returnurlHashValue;369..}./*EndOfTianlHashFunction*/網(wǎng)上找到的php簡(jiǎn)單實(shí)現(xiàn):<?php3./**3./***ImplementsaBloomFilter*/*ImplementsaBloomFilter*/classBloomFilter{7./**8.*Sizeofthebitarray9.10.*@varint11.*/12.protected7./**8.*Sizeofthebitarray9.10.*@varint11.*/12.protected$m;13.TOC\o"1-5"\h\z14, /***Numberofhashfunctions**@var int*/protected$k;/*** Number ofelementsinthefilter** @var int*/protected$n;/*** Thebitsetholdingthefilterinformation** @vararray*/protected$bitset;/***計(jì)算最優(yōu)的hash函數(shù)個(gè)數(shù)：當(dāng)hash函數(shù)個(gè)數(shù)k=(ln2)*(m/n)時(shí)錯(cuò)誤率最小** @param int $m bit數(shù)組的寬度(bit數(shù))* @param int $n加入布隆過(guò)濾器的key的數(shù)量* @returnint*/publicstaticfunctiongetHashCount($m,$n){returnceil(($m/$n)*10g(2));}/*** ConstructaninstanceoftheBloom filter** @param int $m bit數(shù)組的寬度(bit數(shù))Sizeof the bit array* @param int $k hash函數(shù)的個(gè)數(shù)Number ofdifferent hash functionstouse

TOC\o"1-5"\h\z*/publicfunction__construct($m,$k){$this->m = $m;$this->k = $k;$this->n = 0;/*Initializethebitset*/$this->bitset=array_fill(0,$this->m-1,false);)/*** False Positive的比率：f =(1 -e-kn/m)k* Returns the probability for afalse positivetooccur,giventhecurrentnumberofitemsinthefilter**@return double*/publicfunctiongetFalsePositiveProbability(){$exp=(-1*$this->k*$this->n)/$this->m;returnpow(1-exp($exp),$this->k);TOC\o"1-5"\h\z)/***Adds anewitemtothefilter** @parammixedEither astring holding asingleitemor an array of* string holdingmultiple items.Inthe latter case,all* itemsareadded onebyoneinternally.*/publicfunctionadd($key){if(is_array($key)){foreach($keyas$k){$this->add($k);}return;}$this->n++;foreach($this->getSlots($key)as$slot){$this->bitset[$slot]=true;}}

/*** Queries theBloomfilterforanelement** IfthismethodreturnFALSE,itis100%certainthattheelementhas* notbeenaddedtothefilterbefore.Incontrast,ifTRUEisreturned,* theelement*may*havebeenaddedtothefilterpreviously.However with* aprobabilityindicatedbygetFalsePositiveProbability()theelement has* notbeenaddedtothefilterwithcontains()stillreturningTRUE.** @parammixed Eitherastringholdingasingleitemoranarrayof* stringsholdingmultipleitems.Inth