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

1、海量數(shù)據(jù)處理常用思路和方法大數(shù)據(jù)量，海量數(shù)據(jù) 處理方法總結(jié)最近有點忙，稍微空閑下來，發(fā)篇總結(jié)貼。 大數(shù)據(jù)量的問題是很多面試筆試中經(jīng)常出現(xiàn)的問題，比如baidu google 騰訊 這樣的一些涉及到海量數(shù)據(jù)的公司經(jīng)常會問到。下面的方法是我對海量數(shù)據(jù)的處理方法進行了一個一般性的總結(jié)，當然這些方法可能并不能完全覆蓋所有的問題，但是這樣的一些方法也基本可以處理絕大多數(shù)遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優(yōu)，如果你有更好的處理方法，歡迎與我討論。 1.Bloom filter 適用范圍：可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重，或者集合求交集

2、 基本原理及要點： 對于原理來說很簡單，位數(shù)組+k個獨立hash函數(shù)。將hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有hash函數(shù)對應(yīng)位都是1說明存在，很明顯這個過程并不保證查找的結(jié)果是100%正確的。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。 還有一個比較重要的問題，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于

3、E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應(yīng)該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應(yīng)該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。 舉個例子我們假設(shè)錯誤率為0.01，則此時m應(yīng)大概是n的13倍。這樣k大概是8個。 注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。 擴展： Bloom filter將集合中的元素映射到

4、位數(shù)組中，用k（k為哈希函數(shù)個數(shù)）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數(shù)組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。 問題實例：給你A,B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？ 根據(jù)這個問題我們來計算下內(nèi)存的占用，4G=232大概是40億*8大概是340億，n=5

5、0億，如果按出錯率0.01算需要的大概是650億個bit?，F(xiàn)在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡單了。 2.Hashing 適用范圍：快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存 基本原理及要點： hash函數(shù)選擇，針對字符串，整數(shù)，排列，具體相應(yīng)的hash方法。 碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。 擴展： d-lef

6、t hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數(shù)，h1和h2。在存儲一個新的key時，同時用兩個哈希函數(shù)進行計算，得出兩個地址h1key和h2key。這時需要檢查T1中的h1key位置和T2中的h2key位置，哪一個位置已經(jīng)存儲的（有碰撞的）key比較多，然后將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進

7、行兩次hash，同時查找兩個位置。 問題實例： 1).海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。 IP的數(shù)目還是有限的，最多232個，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進行統(tǒng)計。 3.bit-map 適用范圍：可進行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下 基本原理及要點：使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼 擴展：bloom filter可以看做是對bit-map的擴展 問題實例： 1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，

8、統(tǒng)計不同號碼的個數(shù)。 8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內(nèi)存即可。 2)2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。 將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上?；蛘呶覀儾挥?bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map。 4.堆 適用范圍：海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存 基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆

9、里的最大元素，如果它小于最大元素，則應(yīng)該替換那個最大元素。這樣最后得到的n個元素就是最小的n個。適合大數(shù)據(jù)量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。 擴展：雙堆，一個最大堆與一個最小堆結(jié)合，可以用來維護中位數(shù)。 問題實例： 1)100w個數(shù)中找最大的前100個數(shù)。 用一個100個元素大小的最小堆即可。 5.雙層桶劃分 -其實本質(zhì)上就是【分而治之】的思想，重在“分”的技巧上！適用范圍：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字 基本原理及要點：因為元素范圍很大，不能利用直接尋址表，所以通過多

10、次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進行?？梢酝ㄟ^多次縮小，雙層只是一個例子。 擴展： 問題實例： 1).2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。 有點像鴿巢原理，整數(shù)個數(shù)為232,也就是，我們可以將這232個數(shù)，劃分為28個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。 2).5億個int找它們的中位數(shù)。 這個例子比上面那個更明顯。首先我們將int劃分為216個區(qū)域

11、，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(shù)落到那個區(qū)域，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。 實際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成224個區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成220個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有220，就可以直接利用direct addr table進行統(tǒng)計了。 6.數(shù)據(jù)庫索引 適用范圍：大數(shù)據(jù)量的增刪改查 基本原理及要點：

12、利用數(shù)據(jù)的設(shè)計實現(xiàn)方法，對海量數(shù)據(jù)的增刪改查進行處理。 擴展： 問題實例： 7.倒排索引(Inverted index) 適用范圍：搜索引擎，關(guān)鍵字查詢 基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。 以英文為例，下面是要被索引的文本： T0 = "it is what it is" T1 = "what is it" T2 = "it is a banana" 我

13、們就能得到下面的反向文件索引： "a":      2 "banana": 2 "is":     0, 1, 2 "it":     0, 1, 2 "what":   0, 1 檢索的條件"what", "is" 和 "it"

14、 將對應(yīng)集合的交集。 正向索引開發(fā)出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據(jù)了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關(guān)系。 擴展： 問題實例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。 8.外排序 適用范圍：大數(shù)據(jù)的排序，去重 基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優(yōu)歸并樹&#

15、160;擴展： 問題實例： 1).有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16個字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。 這個數(shù)據(jù)具有很明顯的特點，詞的大小為16個字節(jié)，但是內(nèi)存只有1m做hash有些不夠，所以可以用來排序。內(nèi)存可以當輸入緩沖區(qū)使用。 9.trie樹 適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存 基本原理及要點：實現(xiàn)方式，節(jié)點孩子的表示方式 擴展：壓縮實現(xiàn)。 問題實例： 1).有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query

16、，每個文件的query都可能重復(fù)。要你按照query的頻度排序 。 2).1000萬字符串，其中有些是相同的(重復(fù)),需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。請問怎么設(shè)計和實現(xiàn)？ 3).尋找熱門查詢：查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個，每個不超過255字節(jié)。10.分布式處理 mapreduce 適用范圍：數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存 基本原理及要點：將數(shù)據(jù)交給不同的機器去處理，數(shù)據(jù)劃分，結(jié)果歸約。 1. Bloom-Filter算法簡介       

17、60;Bloom-Filter，即布隆過濾器，1970年由Bloom中提出。它可以用于檢索一個元素是否在一個集合中。       Bloom Filter（BF）是一種空間效率很高的隨機數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。它是一個判斷元素是否存在集合的快速的概率算法。Bloom Filter有可能會出現(xiàn)錯誤判斷，但不會漏掉判斷。也就是Bloom Filter判斷元素不再集合，那肯定不在。如果判斷元素存在集合中，有一定的概率判斷錯誤。因此，Bloom Filter不適合那些“零錯誤”的應(yīng)用場合。而在能容忍低錯誤率的

18、應(yīng)用場合下，Bloom Filter比其他常見的算法（如hash，折半查找）極大節(jié)省了空間。       它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。      Bloom Filter的詳細介紹：Bloom Filter2、 Bloom-Filter的基本思想       Bloom-Filter算法的核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”。       計算某元素x是否在一個集合

19、中，首先能想到的方法就是將所有的已知元素保存起來構(gòu)成一個集合R，然后用元素x跟這些R中的元素一一比較來判斷是否存在于集合R中；我們可以采用鏈表等數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。但是，隨著集合R中元素的增加，其占用的內(nèi)存將越來越大。試想，如果有幾千萬個不同網(wǎng)頁需要下載，所需的內(nèi)存將足以占用掉整個進程的內(nèi)存地址空間。即使用MD5，UUID這些方法將URL轉(zhuǎn)成固定的短小的字符串，內(nèi)存占用也是相當巨大的。      于是，我們會想到用Hash table的數(shù)據(jù)結(jié)構(gòu)，運用一個足夠好的Hash函數(shù)將一個URL映射到二進制位數(shù)組（位圖數(shù)組）中的某一位。如果該位已經(jīng)被置為1，那么表示該URL已經(jīng)

20、存在。      Hash存在一個沖突（碰撞）的問題，用同一個Hash得到的兩個URL的值有可能相同。為了減少沖突，我們可以多引入幾個Hash，如果通過其中的一個Hash值我們得出某元素不在集合中，那么該元素肯定不在集合中。只有在所有的Hash函數(shù)告訴我們該元素在集合中時，才能確定該元素存在于集合中。這便是Bloom-Filter的基本思想。原理要點：一是位數(shù)組， 而是k個獨立hash函數(shù)。1）位數(shù)組：        假設(shè)Bloom Filter使用一個m比特的數(shù)組來保存信息，初始狀態(tài)時，Bloom Filter是

21、一個包含m位的位數(shù)組，每一位都置為0，即BF整個數(shù)組的元素都設(shè)置為0。2）添加元素，k個獨立hash函數(shù)       為了表達S=x1, x2,xn這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的哈希函數(shù)（Hash Function），它們分別將集合中的每個元素映射到1,m的范圍中。         當我們往Bloom Filter中增加任意一個元素x時候，我們使用k個哈希函數(shù)得到k個哈希值，然后將數(shù)組中對應(yīng)的比特位設(shè)置為1。即第i個哈希函數(shù)映射的位置hashi(x)就會被置為

22、1（1ik）。 注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個哈希函數(shù)選中同一個位置（從左邊數(shù)第五位，即第二個“1“處）。    3）判斷元素是否存在集合    在判斷y是否屬于這個集合時，我們只需要對y使用k個哈希函數(shù)得到k個哈希值，如果所有hashi(y)的位置都是1（1ik），即k個位置都被設(shè)置為1了，那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。下圖中y1就不是集合中的元素（因為y1有一處指向了“0”位）。y2或者屬于這個

23、集合，或者剛好是一個false positive。      顯然這 個判斷并不保證查找的結(jié)果是100%正確的。Bloom Filter的缺點：       1）Bloom Filter無法從Bloom Filter集合中刪除一個元素。因為該元素對應(yīng)的位會牽動到其他的元素。所以一個簡單的改進就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了。 此外，Bloom Filter的hash函數(shù)選擇會影響算法的效果。       2

24、）還有一個比較重要的問題，如何根據(jù)輸入元素個數(shù)n，確定位數(shù)組m的大小及hash函數(shù)個數(shù)，即hash函數(shù)選擇會影響算法的效果。當hash函數(shù)個數(shù)k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大于E的情況 下，m至少要等于n*lg(1/E) 才能表示任意n個元素的集合。但m還應(yīng)該更大些，因為還要保證bit數(shù)組里至少一半為0，則m應(yīng) 該>=nlg(1/E)*lge ，大概就是nlg(1/E)1.44倍(lg表示以2為底的對數(shù))。 舉個例子我們假設(shè)錯誤率為0.01，則此時m應(yīng)大概是n的13倍。這樣k大概是8個。  注意：    &#

25、160;    這里m與n的單位不同，m是bit為單位，而n則是以元素個數(shù)為單位(準確的說是不同元素的個數(shù))。通常單個元素的長度都是有很多bit的。所以使用bloom filter內(nèi)存上通常都是節(jié)省的。        一般BF可以與一些key-value的數(shù)據(jù)庫一起使用，來加快查詢。由于BF所用的空間非常小，所有BF可以常駐內(nèi)存。這樣子的話，對于大部分不存在的元素，我們只需要訪問內(nèi)存中的BF就可以判斷出來了，只有一小部分，我們需要訪問在硬盤上的key-value數(shù)據(jù)庫。從而大大地提高了效率。一個Bloom Filter有以下

26、參數(shù)：mbit數(shù)組的寬度（bit數(shù)）n加入其中的key的數(shù)量k使用的hash函數(shù)的個數(shù)fFalse Positive的比率Bloom Filter的f滿足下列公式：在給定m和n時，能夠使f最小化的k值為：此時給出的f為：根據(jù)以上公式，對于任意給定的f，我們有：n = m ln(0.6185) / ln(f)    1同時，我們需要k個hash來達成這個目標：k = - ln(f) / ln(2)             2由于k必須取整數(shù)，我們在

27、Bloom Filter的程序?qū)崿F(xiàn)中，還應(yīng)該使用上面的公式來求得實際的f：f = (1 e-kn/m)k             3以上3個公式是程序?qū)崿F(xiàn)Bloom Filter的關(guān)鍵公式。3、 擴展 CounterBloom FilterCounterBloom FilterBloomFilter有個缺點，就是不支持刪除操作，因為它不知道某一個位從屬于哪些向量。那我們可以給Bloom Filter加上計數(shù)器，添加時增加計數(shù)器，刪除時減少計數(shù)器。但這樣的F

28、ilter需要考慮附加的計數(shù)器大小，假如同個元素多次插入的話，計數(shù)器位數(shù)較少的情況下，就會出現(xiàn)溢出問題。如果對計數(shù)器設(shè)置上限值的話，會導(dǎo)致Cache Miss，但對某些應(yīng)用來說，這并不是什么問題，如Web Sharing。Compressed Bloom Filter為了能在服務(wù)器之間更快地通過網(wǎng)絡(luò)傳輸Bloom Filter，我們有方法能在已完成Bloom Filter之后，得到一些實際參數(shù)的情況下進行壓縮。將元素全部添加入Bloom Filter后，我們能得到真實的空間使用率，用這個值代入公式計算出一個比m小的值，重新構(gòu)造Bloom Filter，對原先的哈希值進行求余處理，在誤判率不變的

29、情況下，使得其內(nèi)存大小更合適。4、 Bloom-Filter的應(yīng)用        Bloom-Filter一般用于在大數(shù)據(jù)量的集合中判定某元素是否存在。例如郵件服務(wù)器中的垃圾郵件過濾器。在搜索引擎領(lǐng)域，Bloom-Filter最常用于網(wǎng)絡(luò)蜘蛛(Spider)的URL過濾，網(wǎng)絡(luò)蜘蛛通常有一個URL列表，保存著將要下載和已經(jīng)下載的網(wǎng)頁的URL，網(wǎng)絡(luò)蜘蛛下載了一個網(wǎng)頁，從網(wǎng)頁中提取到新的URL后，需要判斷該URL是否已經(jīng)存在于列表中。此時，Bloom-Filter算法是最好的選擇。1.key-value 加快查詢     

30、;  一般Bloom-Filter可以與一些key-value的數(shù)據(jù)庫一起使用，來加快查詢。       一般key-value存儲系統(tǒng)的values存在硬盤，查詢就是件費時的事。將Storage的數(shù)據(jù)都插入Filter，在Filter中查詢都不存在時，那就不需要去Storage查詢了。當False Position出現(xiàn)時，只是會導(dǎo)致一次多余的Storage查詢。       由于Bloom-Filter所用的空間非常小，所有BF可以常駐內(nèi)存。這樣子的話，對于大部分不存在的元素，我們只需要訪問內(nèi)存中的Bl

31、oom-Filter就可以判斷出來了，只有一小部分，我們需要訪問在硬盤上的key-value數(shù)據(jù)庫。從而大大地提高了效率。如圖：          2 .Google的BigTable        Google的BigTable也使用了Bloom Filter，以減少不存在的行或列在磁盤上的查詢，大大提高了數(shù)據(jù)庫的查詢操作的性能。3. Proxy-Cache      在Internet Cache Protocol中的Proxy-Cache很多都是使用

32、Bloom Filter存儲URLs，除了高效的查詢外，還能很方便得傳輸交換Cache信息。4.網(wǎng)絡(luò)應(yīng)用      1）P2P網(wǎng)絡(luò)中查找資源操作，可以對每條網(wǎng)絡(luò)通路保存Bloom Filter，當命中時，則選擇該通路訪問。      2）廣播消息時，可以檢測某個IP是否已發(fā)包。      3）檢測廣播消息包的環(huán)路，將Bloom Filter保存在包里，每個節(jié)點將自己添加入Bloom Filter。     4）信息隊列管理，使用Counter Bloom Filter管理信息

33、流量。5. 垃圾郵件地址過濾        像網(wǎng)易，QQ這樣的公眾電子郵件（email）提供商，總是需要過濾來自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個辦法就是記錄下那些發(fā)垃圾郵件的 email地址。由于那些發(fā)送者不停地在注冊新的地址，全世界少說也有幾十億個發(fā)垃圾郵件的地址，將他們都存起來則需要大量的網(wǎng)絡(luò)服務(wù)器。如果用哈希表，每存儲一億個 email地址，就需要 1.6GB的內(nèi)存（用哈希表實現(xiàn)的具體辦法是將每一個 email地址對應(yīng)成一個八字節(jié)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲效率一

34、般只有 50%，因此一個 email地址需要占用十六個字節(jié)。一億個地址大約要 1.6GB，即十六億字節(jié)的內(nèi)存）。因此存貯幾十億個郵件地址可能需要上百 GB的內(nèi)存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解決同樣的問題。BloomFilter決不會漏掉任何一個在黑名單中的可疑地址。而至于誤判問題，常見的補救辦法是在建立一個小的白名單，存儲那些可能別誤判的郵件地址。5、 Bloom-Filter的具體實現(xiàn)c語言實現(xiàn)：stdafx.h：1. #pragma once 

35、60;2. #include <stdio.h>    3. #include "stdlib.h"  4. #include <iostream>  5. #include <time.h>  6. using namespace std;  1. #include "stdafx.h"  2.  &

36、#160;3.   4. #define ARRAY_SIZE 256 /*we get the 256 chars of each line*/  5. #define SIZE 48000000 /* size should be 1/8 of max*/  6. #define MAX  384000000/*t

37、he max bit space*/  7.   8. #define SETBIT(ch,n) chn/8|=1<<(7-n%8)  9. #define GETBIT(ch,n) (chn/8&1<<(7-n%8)>>(7-n%8)  10.   11. unsigned int len(char *ch);/* functions

38、0;to calculate the length of the url*/  12.   13. unsigned int RSHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  14. unsigne

39、d int JSHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  15. unsigned int PJWHash(char* str, unsigned int len);/* functions to cal

40、culate the hash value of the url*/  16. unsigned int ELFHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  17. unsigned int BKD

41、RHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  18. unsigned int SDBMHash(char* str, unsigned int len);/* functions to calculate the&

42、#160;hash value of the url*/  19. unsigned int DJBHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  20. unsigned int DEKHash(char* 

43、str, unsigned int len);/* functions to calculate the hash value of the url*/  21. unsigned int BPHash(char* str, unsigned int len);/* functions to calculate the hash valu

44、e of the url*/  22. unsigned int FNVHash(char* str, unsigned int len);/* functions to calculate the hash value of the url*/  23. unsigned int APHash(char* str, unsigned&#

45、160;int len);/* functions to calculate the hash value of the url*/  24. unsigned int HFLPHash(char* str,unsigned int len);/* functions to calculate the hash value of the 

46、url*/  25. unsigned int HFHash(char* str,unsigned int len);/* functions to calculate the hash value of the url*/  26. unsigned int StrHash( char* str,unsigned int len);/* func

47、tions to calculate the hash value of the url*/  27. unsigned int TianlHash(char* str,unsigned int len);/* functions to calculate the hash value of the url*/  28.  &#

48、160;29.   30. int main()  31.   32.     int i,num,num2=0; /* the number to record the repeated urls and the total of it*/  33.     unsigned 

49、int tt=0;  34.     int flag;         /*it helps to check weather the url has already existed */  35.     char buf257;  &

50、#160; /*it helps to print the start time of the program */  36.     time_t tmp = time(NULL);  37.   38.     char file1100,file2100;  39.  &#

51、160;  FILE *fp1,*fp2;/*pointer to the file */  40.     char chARRAY_SIZE;    41.     char *vector /* the bit space*/  42.     vector

52、60;= (char *)calloc(SIZE,sizeof(char);  43.   44.     printf("Please enter the  repeated urls:n");  45.     scanf("%s",&file1);     46.  

53、0;  if( (fp1 = fopen(file1,"rb") = NULL)   /* open the goal file*/  47.       printf("Connot open the !n",file1);  48.     &#

54、160; 49.   50.     printf("Please enter the  want to save to:n");  51.     scanf("%s",&file2);  52.     if( (fp2 = fopen(file2,&quo

55、t;w") = NULL)   53.         printf("Connot open the n",file2);  54.       55.     strftime(buf,32,"%Y-%m-%d %H:%M:%S",localtime(&a

56、mp;tmp);  56.     printf("%sn",buf); /*print the system time*/  57.   58.     for(i=0;i<SIZE;i+)   59.         vectori=0;  /*set

57、0;0*/  60.       61.   62.     while(!feof(fp1)  /* the check process*/  63.       64.         fgets(ch,ARRAY_SIZE,fp1); 

58、; 65.         flag=0;  66.         tt+;  67.         if( GETBIT(vector, HFLPHash(ch,len(ch)%MAX) )       

59、68.             flag+;  69.          else   70.             SETBIT(vector,HFLPHash(ch,len(ch)%MAX ); 

60、; 71.              72.   73.         if( GETBIT(vector, StrHash(ch,len(ch)%MAX) )    74.          &#

61、160;  flag+;  75.          else   76.             SETBIT(vector,StrHash(ch,len(ch)%MAX );  77.         &#

62、160; 78.           79.         if( GETBIT(vector, HFHash(ch,len(ch)%MAX) )     80.             flag+;

63、0; 81.          else   82.             SETBIT(vector,HFHash(ch,len(ch)%MAX );  83.           84.   8

64、5.         if( GETBIT(vector, DEKHash(ch,len(ch)%MAX) )   86.             flag+;  87.          else  

65、0;88.             SETBIT(vector,DEKHash(ch,len(ch)%MAX );  89.            90.           91.     

66、0;   if( GETBIT(vector, TianlHash(ch,len(ch)%MAX) )   92.             flag+;  93.          else   94.     

67、;        SETBIT(vector,TianlHash(ch,len(ch)%MAX );  95.           96.   97.         if( GETBIT(vector, SDBMHash(ch,len(ch)%MAX) )&

68、#160;   98.             flag+;  99.          else   100.             SETBIT(vector,SDBMHash(ch,

69、len(ch)%MAX );  101.           102.   103.         if(flag<6)  104.             num2+;    &#

70、160;  105.         else              106.            fputs(ch,fp2);  107.       108.

71、        /*  printf(" %d",flag); */        109.       110.     /* the result*/  111.     printf("

72、;nThere are %d urls!n",tt);  112.     printf("nThere are %d not repeated urls!n",num2);  113.     printf("There are %d repeated urls!n",tt-num2); 

73、0;114.     fclose(fp1);  115.     fclose(fp2);  116.     return 0;  117.   118.   119.   120. /*functions may be used in the main */ &#

74、160;121. unsigned int len(char *ch)  122.   123.     int m=0;  124.     while(chm!='0')   125.         m+;  126.     

75、  127.     return m;  128.   129.   130. unsigned int RSHash(char* str, unsigned int len)   131.    unsigned int b = 378551;  132.   &#

76、160;unsigned int a = 63689;  133.    unsigned int hash = 0;  134.    unsigned int i = 0;  135.   136.    for(i=0; i<len; str+, i+) &

77、#160; 137.       hash = hash*a + (*str);  138.       a = a*b;  139.      140.    return hash;  141.   142. /* End&#

78、160;Of RS Hash Function */  143.   144.   145. unsigned int JSHash(char* str, unsigned int len)  146.   147.    unsigned int hash = 1315423911;  148.  

79、;  unsigned int i    = 0;  149.   150.    for(i=0; i<len; str+, i+)   151.       hash = (hash<<5) + (*str) + (hash>>

80、;2);  152.      153.    return hash;  154.   155. /* End Of JS Hash Function */  156.   157.   158. unsigned int PJWHash(char* str, unsigned 

81、;int len)  159.   160.    const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);  161.    const unsigned int ThreeQuarters = (unsigned 

82、;int)(BitsInUnsignedInt  * 3) / 4);  162.    const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);  163.    const unsigned int HighBits = (unsig

83、ned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  164.    unsigned int hash = 0;  165.    unsigned int test = 0;  166.    unsigned int i

84、 = 0;  167.   168.    for(i=0;i<len; str+, i+)   169.       hash = (hash<<OneEighth) + (*str);  170.       if(test = hash

85、 & HighBits)  != 0)   171.          hash = (hash (test >> ThreeQuarters) & (HighBits);  172.         173.  

86、0;   174.   175.    return hash;  176.   177. /* End Of  P. J. Weinberger Hash Function */  178.   179.   180. unsigned int ELFHash(char* str,

87、60;unsigned int len)  181.   182.    unsigned int hash = 0;  183.    unsigned int x    = 0;  184.    unsigned int i    =

88、 0;  185.   186.    for(i = 0; i < len; str+, i+)   187.       hash = (hash << 4) + (*str);  188.      

89、60;if(x = hash & 0xF0000000L) != 0)   189.          hash = (x >> 24);  190.         191.       hash&

90、#160;&= x;  192.      193.    return hash;  194.   195. /* End Of ELF Hash Function */  196.   197.   198. unsigned int BKDRHash(char* str,&#

91、160;unsigned int len)  199.   200.    unsigned int seed = 131; /* 31 131 1313 13131 131313 etc. */  201.    unsigned int hash = 0;  202.

92、60;  unsigned int i    = 0;  203.   204.    for(i = 0; i < len; str+, i+)  205.      206.       hash = (has

93、h * seed) + (*str);  207.      208.   209.    return hash;  210.   211. /* End Of BKDR Hash Function */  212.   213.   214. unsigned

94、60;int SDBMHash(char* str, unsigned int len)  215.   216.    unsigned int hash = 0;  217.    unsigned int i    = 0;  218.   219.   

95、; for(i = 0; i < len; str+, i+)   220.       hash = (*str) + (hash << 6) + (hash << 16) - hash;  221.     

96、0;222.   223.    return hash;  224.   225. /* End Of SDBM Hash Function */  226.   227.   228. unsigned int DJBHash(char* str, unsigned int len)  229.

97、   230.    unsigned int hash = 5381;  231.    unsigned int i    = 0;  232.   233.    for(i = 0; i < len; str+, i+) &#

98、160; 234.       hash = (hash << 5) + hash) + (*str);  235.      236.   237.    return hash;  238.   239. /* End Of DJB&

99、#160;Hash Function */  240.   241.   242. unsigned int DEKHash(char* str, unsigned int len)  243.   244.    unsigned int hash = len;  245.    unsigned

100、 int i    = 0;  246.   247.    for(i = 0; i < len; str+, i+)   248.       hash = (hash << 5)  (hash >> 27)  (*str);  249.      250.    return hash; &