1巧骚、題目：每一個ip訪問百度吭产，其ip地址都會被記錄到后臺日志文件中个从，假設一天的訪問日志有100G脉幢，求出一天中訪問百度次數(shù)最多的ip地址，可以使用的內(nèi)存大小是1G嗦锐。

解題

1M `=10^6B 1G`=10^9B

首先解決大文件問題嫌松，也就是如何處理100G的一個大文件，這個通常的解決方法就是將大文件分解成許多小文件奕污。我們可以通過對IP地址求hash然后對1024取模將一個100G的大文件分解成1024個小文件（file0,file1......file1023）萎羔，注意這里的1024個文件并不是平均分的，也就是每個文件大小并不是（100G/1204）碳默。當然我們考慮的時候可以假設文件是平均分的贾陷，那么每個文件大小為100M缘眶，這樣一個100M的文件是可以全部讀入大小為1G內(nèi)存中。這樣就解決了第一個文件太大不能一次讀入內(nèi)存的問題髓废。

考慮到ip地址是32為巷懈，那么總共有2^32=4G種可能出現(xiàn)的ip地址，每個ip地址出現(xiàn)的次數(shù)不確定慌洪，這個具體是由100G大文件決定的顶燕。對每個小文件進行處理，我們知道前面每個文件中的ip是通過hash(ip)%1024冈爹。這樣相當于將2^32=4G種ip地址進行了分段涌攻，每個文件中可能出現(xiàn)的ip最大范圍是4G/1024=4M。創(chuàng)建一個hashmap频伤，讀取小文件中的每個ip地址恳谎，判斷hashmap中是否有這個ip，如果沒有剂买，這往haspmap中插入一個的鍵值對惠爽，即hashmap.put(ip,1)；如果haspmap中已經(jīng)存在了這個ip瞬哼，那么求出這個ip所對應的值count=haspmap.get(ip)婚肆，然后往修改這個ip所對應的value，使其數(shù)量增加1坐慰，即hashmap.set(ip,count+1)较性。

當我們求出每個文件中出現(xiàn)次數(shù)最大的ip地址以后，我們在比較這1024個文件中的那個ip出現(xiàn)次數(shù)最大

關于本題结胀，注意兩點：

Hash取模是一種等價映射赞咙，不會存在同一個元素分散到不同小文件中去的情況，即這里采用的是%1000算法糟港，那么同一個IP在hash后攀操，只可能落在同一個文件中，不可能被分散的秸抚。

那到底什么是hash映射呢速和？簡單來說，就是為了便于計算機在有限的內(nèi)存中處理big數(shù)據(jù)剥汤，從而通過一種映射散列的方式讓數(shù)據(jù)均勻分布在對應的內(nèi)存位置(如大數(shù)據(jù)通過取余的方式映射成小樹存放在內(nèi)存中颠放，或大文件映射成多個小文件)，而這個映射散列方式便是我們通常所說的hash函數(shù)吭敢，設計的好的hash函數(shù)能讓數(shù)據(jù)均勻分布而減少沖突碰凶。盡管數(shù)據(jù)映射到了另外一些不同的位置，但數(shù)據(jù)還是原來的數(shù)據(jù)，只是代替和表示這些原始數(shù)據(jù)的形式發(fā)生了變化而已欲低。

2辕宏、搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)砾莱。假設目前一個日志文件中有一千萬個記錄（這些查詢串的重復度比較高匾效，雖然總數(shù)是1千萬，但如果除去重復后恤磷，不超過3百萬個面哼。一個查詢串的重復度越高，說明查詢它的用戶越多扫步，也就是越熱門）魔策，請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G河胎。

解答：

1M `=10^6B 1G`=10^9B

1000萬條記錄闯袒，每條記錄最大為255Byte，那么日志文件最大有2.5G左右游岳，大于1G內(nèi)存政敢。但是題目中又提到這樣的1000萬條記錄中有許多是重復的，出去重復的話只有300萬條記錄胚迫，存儲這樣的300萬條記錄需要0.75G左右的內(nèi)存喷户，小于1G內(nèi)存。那么我們可以考慮將這些無重復的記錄裝入內(nèi)存访锻，這是我們需要一種數(shù)據(jù)結構褪尝，這種數(shù)據(jù)結構即能夠存儲查詢串，又能存儲查詢串的出現(xiàn)次數(shù)期犬，我們可以通過hashmap來保存河哑。讀取文件，創(chuàng)建一個hashmap龟虎，如果hashmap中存儲了遍歷到的query璃谨，則修改該query所對應的count值，使其+1鲤妥；如果hashmap中沒有這個query佳吞，那么往haspmap中插入。這樣我們就創(chuàng)建好了一個包含所有query和次數(shù)的hashmap旭斥。

然后我們創(chuàng)建一個長度為10最小堆MinHeap（求最多的要用最小堆容达，求最小的要用最大堆）古涧，(這里需要假定這個小頂堆是大頂堆)垂券。最小堆的堆頂元素最小，如果堆頂這個最小的元素都大于其他非堆元素了，那么堆中的其他元素必定大于其他非堆中元素菇爪。遍歷hashmap算芯，如果MinHeap未滿，那么往MinHeap中插入這個鍵值對凳宙，如果MinHeap滿了熙揍，則比較遍歷到的元素的count值堆頂?shù)腸ount，如果遍歷到元素的count大于堆頂count值氏涩，刪除堆頂元素届囚，插入當前遍歷到的元素。遍歷完整個hashmap以后是尖，在MinHeap中存儲的就是最熱門10個查詢串意系。

3、將query按照出現(xiàn)的頻度排序（10個1G大小的文件）饺汹。有10個文件蛔添，每個文件1G，每個文件的每一行都存放的是用戶的query兜辞，每個文件的query都可能重復迎瞧。如何按照query的頻度排序？求出Top10逸吵？

1）讀取10個文件凶硅，按照hash(query)%10的結果將query寫到對應的10個文件（file0,file1....file9）中，這樣的10個文件不同于原先的10個文件扫皱。這樣我們就有了10個大小約為1G的文件咏尝。任意一個query只會出現(xiàn)在某個文件中。

2）對于1）中獲得的10個文件啸罢，分別進行如下操作

利用hash_map（query编检，query_count）來統(tǒng)計每個query出現(xiàn)的次數(shù)。

創(chuàng)建一個長度為10的堆來保存一個文件中出現(xiàn)次數(shù)最多的hash_map（query扰才，query_count）允懂，最后將這10個鍵值對輸出到result文件中。

3）通過2）獲得的result文件保存著每個文件出現(xiàn)次數(shù)最多的10條記錄衩匣，對其中的100條記錄按照query_count進行排序蕾总，最后輸出query_count最大的10條query。

來源：http://www.cnblogs.com/xwdreamer

4琅捏、有一個1G大小的一個文件生百，里面每一行是一個詞，詞的大小不超過16字節(jié)柄延，內(nèi)存限制大小是1M蚀浆。返回頻數(shù)最高的100個詞。

1G`=10^6M

方案：順序讀文件中，對于每個詞x市俊，取hash(x)%5000杨凑，然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右摆昧。

如果其中的有的文件超過了1M大小撩满，還可以按照類似的方法繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M绅你。

?對每個小文件伺帘，統(tǒng)計每個文件中出現(xiàn)的詞以及相應的頻率（可以采用trie樹/hash_map等），并取出出現(xiàn)頻率最大的100個詞（可以用含100個結點的最小堆）忌锯，并把100個詞及相應的頻率存入文件曼追，這樣又得到了5000個文件。

下一步就是把這5000個文件進行歸并（類似與歸并排序）的過程了汉规。這個時候就和上面的第三題很類似了礼殊，相同的Hashcode%1000放在一個文件中.

5、 給定a针史、b兩個文件晶伦，各存放50億個url，每個url各占64字節(jié)啄枕，內(nèi)存限制是4G婚陪，讓你找出a、b文件共同的url频祝？

方案1：可以估計每個文件安的大小為5G×64=320G泌参，遠遠大于內(nèi)存限制的4G。所以不可能將其完全加載到內(nèi)存中處理常空」烈唬考慮采取分而治之的方法。

1. 遍歷文件a漓糙，對每個url求取hash(url)%1000铣缠，然后根據(jù)所取得的值將url分別存儲到1000個小文件（記為a0,a1,...,a999）中。這樣每個小文件的大約為300M昆禽。

2. 遍歷文件b蝗蛙，采取和a相同的方式將url分別存儲到1000小文件（記為b0,b1,...,b999）。這樣處理后醉鳖，所有可能相同的url都在對應的小文件（a0vsb0,a1vsb1,...,a999vsb999）中捡硅，不對應的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可盗棵。

3. 求每對小文件中相同的url時壮韭，可以把其中一個小文件的url存儲到hash_set中北发。然后遍歷另一個小文件的每個url，看其是否在剛才構建的hash_set中泰涂，如果是，那么就是共同的url辐怕，存到文件里面就可以了逼蒙。

方案2：如果允許有一定的錯誤率，可以使用Bloom filter寄疏，4G內(nèi)存大概可以表示340億bit是牢。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url陕截，檢查是否與Bloom filter驳棱，如果是，那么該url應該是共同的url（注意會有一定的錯誤率）农曲。

Bloom filter日后會在本BLOG內(nèi)詳細闡述社搅。

6、在2.5億個整數(shù)中找出不重復的整數(shù)乳规，注形葬，內(nèi)存不足以容納這2.5億個整數(shù)。

方案1：采用2-Bitmap（每個數(shù)分配2bit暮的，00表示不存在笙以，01表示出現(xiàn)一次，10表示多次冻辩，11無意義）進行猖腕，共需內(nèi)存內(nèi)存，還可以接受恨闪。然后掃描這2.5億個整數(shù)倘感，查看Bitmap中相對應位，如果是00變01咙咽，01變10侠仇，10保持不變。所描完事后犁珠，查看bitmap逻炊，把對應位是01的整數(shù)輸出即可

方案2：

遍歷文件求hash(num)%10000，分成1萬個小文件犁享，對每個小文件找出不充分的數(shù)

對于每個小文件,利用Hash key = num,value =次數(shù)余素，最后發(fā)現(xiàn)此時是1的就是只出現(xiàn)一次的整數(shù)

匯總1萬個小文件的結果

如果分成1萬個小文件，部分文件過大炊昆，也可以繼續(xù)進行分成小文件

7桨吊、給40億個不重復的unsigned int的整數(shù)威根，沒排過序的，然后再給一個數(shù)视乐，如何快速判斷這個數(shù)是否在那40億個數(shù)當中洛搀？

與上第6題類似，我的第一反應時快速排序+二分查找佑淀。以下是其它更好的方法：方案1：oo留美，申請512M的內(nèi)存，一個bit位代表一個unsigned int值伸刃。讀入40億個數(shù)谎砾，設置相應的bit位，讀入要查詢的數(shù)捧颅，查看相應bit位是否為1景图，為1表示存在，為0表示不存在碉哑。

dizengrong：方案2：這個問題在《編程珠璣》里有很好的描述挚币，大家可以參考下面的思路，探討一下：又因為2^32為40億多扣典，所以給定一個數(shù)可能在忘晤，也可能不在其中；這里我們把40億個數(shù)中的每一個用32位的二進制來表示假設這40億個數(shù)開始放在一個文件中激捏。

然后將這40億個數(shù)分成兩類: 1.最高位為0 2.最高位為1 并將這兩類分別寫入到兩個文件中设塔，其中一個文件中數(shù)的個數(shù)<=20億，而另一個>=20億（這相當于折半了）远舅；與要查找的數(shù)的最高位比較并接著進入相應的文件再查找

再然后把這個文件為又分成兩類: 1.次最高位為0 2.次最高位為1

并將這兩類分別寫入到兩個文件中闰蛔，其中一個文件中數(shù)的個數(shù)<=10億，而另一個>=10億（這相當于折半了）图柏； 與要查找的數(shù)的次最高位比較并接著進入相應的文件再查找序六。 ....... 以此類推，就可以找到了,而且時間復雜度為O(logn)蚤吹，方案2完例诀。

上面講的無法理解

我感覺這樣應該也可以：

計算Hash（num）%10000,分成1萬個小文件，求hash(target)%10000,找到所在的小文件區(qū)域裁着，若與1萬個文件的hash(num)%10000值不一樣繁涂，說明不存在。

對于存在的時候二驰，找到這個小文件扔罪，繼續(xù)進行上面的操作，（%1000桶雀，或者更小矿酵，這里根據(jù)內(nèi)存大小而定）

若果存在一個小文件的hash（num）%1000 == hash(target)%1000 唬复，只需要順序的遍歷判斷是否存在這個數(shù)了。

附：這里全肮，再簡單介紹下敞咧，位圖方法： 使用位圖法判斷整形數(shù)組是否存在重復 判斷集合中存在重復是常見編程任務之一，當集合中數(shù)據(jù)量比較大時我們通常希望少進行幾次掃描辜腺，這時雙重循環(huán)法就不可取了休建。

位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個長度為max+1的新數(shù)組哪自，然后再次掃描原數(shù)組丰包，遇到幾就給新數(shù)組的第幾位置上1禁熏，如遇到5就給新數(shù)組的第六個元素置1壤巷，這樣下次再遇到5想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是1了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復瞧毙。這種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法胧华。它的運算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效率還能提高一倍宙彪。

8矩动、怎么在海量數(shù)據(jù)中找出重復次數(shù)最多的一個？

方案1：先做hash释漆，然后求模映射為小文件悲没，求出每個小文件中重復次數(shù)最多的一個，并記錄重復次數(shù)男图。然后找出上一步求出的數(shù)據(jù)中重復次數(shù)最多的一個就是所求（具體參考前面的題）示姿。

9、上千萬或上億數(shù)據(jù)（有重復）逊笆，統(tǒng)計其中出現(xiàn)次數(shù)最多的N個數(shù)據(jù)栈戳。

方案1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機器的內(nèi)存應該能存下难裆。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統(tǒng)計次數(shù)子檀。然后就是取出前N個出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第2題提到的堆機制完成乃戈。

10褂痰、一個文本文件，大約有一萬行症虑，每行一個詞脐恩，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想侦讨，給出時間復雜度分析驶冒。

方案1：這題是考慮時間效率苟翻。用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，時間復雜度是O(n*le)（le表示單詞的平準長度）骗污。然后是找出出現(xiàn)最頻繁的前10個詞崇猫，可以用堆來實現(xiàn)，前面的題中已經(jīng)講到了需忿，時間復雜度是O(n*lg10)诅炉。所以總的時間復雜度，是O(n*le)與O(n*lg10)中較大的哪一個屋厘。

附涕烧、100w個數(shù)中找出最大的100個數(shù)。

方案1：在前面的題中汗洒，我們已經(jīng)提到了议纯，用一個含100個元素的最小堆完成。復雜度為O(100w*lg100)溢谤。

方案2：采用快速排序的思想瞻凤，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時候世杀，采用傳統(tǒng)排序算法排序阀参，取前100個。復雜度為O(100w*100)瞻坝。

方案3：采用局部淘汰法蛛壳。選取前100個元素，并排序所刀，記為序列L衙荐。然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比勉痴，如果比這個最小的要大赫模，那么把這個最小的元素刪除，并把x利用插入排序的思想蒸矛，插入到序列L中瀑罗。依次循環(huán)，知道掃描了所有的元素雏掠。復雜度為O(100w*100)枕稀。

來源:http://www.cnblogs.com/zuoyuan/p/4747635.html