海量數據處理在面試中是經常會被問的一些問題，處理大量數據的基本功在平常工作中確實是會用到的，今天我就整理了一些這方面的問題。
所謂海量數據處理， 指的是大數據量上進行的各種數據操作，但因為數據量龐大，會出現程序的運行時間過長，單機的存儲空間不夠或一些程序在運行過程中內存不足的情況，因而需要一些特別的處理方法，本文就儘可能的把這些特別的處理方法彙總，同時希望各路大神幫忙補充。本文裡的各種方法對應的面試題內容也會在博客中持續更新。（ 可以點擊閱讀原文查看博客內容）。
通過網絡上各種文章的收集以及自己平時面試中的一些積累，掌握海量數據問題的處理方法首先要學會兩個方法：一是用分治的方法將大數據問題變成小數據問題，其中分治的方法最常用的就是用hash，之後再對各小塊問題的結果進行統計、彙總或排序；另一個方法就是用bit map。 其它網絡上經常會提到的Trie樹，Hadoop等當然能掌握是更好的。本文就先詳細舉例介紹分治法和bit map方法。其中部份舉例題目來源於網絡，相信有這方面準備經驗的同學可能早就看過了。
分治法
大多用來hash映射來將大文件或大量數據進行分而治之的處理，分到不同的機器或節點上，再進行處理。處理的結果可能需要再用hash進行統計彙總，進行歸併排序或再用堆排序找出TopK。這裡值得一得的是面試過程中如果答出用hash來分治，很可能會引出新的關於hash的問題，比如怎麼做hash，處理hash中衝突的方法等，最好都提前準備好。
下面是關於這方面的幾個題目：（篇幅原因，只舉例兩題，博客上會持續大量更新）
海量日誌數據，提取出某日訪次數最多的那個IP
這題是典型的求TopK，TopK問題最先能想到的肯定是堆排序，但這裡因為記錄很多，還是可以用分治的方法先打散文件。
這裡注意到IP是32位的，最多有個2^32個IP，可以採用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現頻率最大的IP（可以採用hash_map進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。然後再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。
因為IP地址最多有2^32=4G種取值情況，所以不能完全加載到內存中處理，我們用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日誌分別存儲到1024個小文件中。這樣，每個小文件最多包含4MB個IP地址。對於每一個小文件，可以構建一個IP為key，出現次數為value的Hash map，同時記錄當前出現次數最多的那個IP地址。可以得到1024個小文件中的出現次數最多的IP，再依據常規的排序算法得到總體上出現次數最多的IP。如果1024個小文件中有嚴重的數據傾斜，則需要再進行進一步的分治打散小文件來處理。
給定a、b兩個文件，各存放50億個url，每個url各佔64字節，內存限制是4G，讓你找出a、b文件共同的url？
這裡明確給出了每個url佔用的字節數和內存限制，那麼這個內存裡存不下URL明顯是需要計算難一下的。從條件中可以算出每個文件的大小為5G×64=320G，遠遠大於內存限制的4G。所以不可能將其完全加載到內存中處理。考慮採取分而治之的方法。
遍歷文件a，對每個url取模 ，這裡將大文件分散到小文件的方法有很多種，最直觀的，按前N個字母打散也行，重點是要找到一種方法，讓所有文件裡的URL數量儘可能的均勻，否則出現很大的傾斜的話，還需要再次的打散。
然後根據所取得的值將url分別存儲到1000個小文件中。這樣每個小文件的大約為300M。遍歷文件b，採取和a相同的方式將url分別存儲到1000小文件中。這樣處理後，所有可能相同的url都在對應的小文件中，不對應的小文件不可能有相同的url。然後我們只要求出1000對小文件中相同的url即可。如果因為hash的過程中導致小文件的大小不是均勻分佈，而出現有些文件還是太大，則可進行再次的hash分治，直至單個文件可以單機處理為止。
接著用hash進行統計 ：求每對小文件中相同的url時，可以把其中一個小文件的url存儲到hash_set中。然後遍歷另一個小文件的每個url，看其是否在剛才構建的hash_set中，如果是，那麼就是共同的url，存到文件裡面就可以了。
Bit-Map
所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由於採用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。但在面試過程中可能會讓你用自己熟悉的語言來寫一個Bit-map的程序，最好也提前準備好吧。
下面是關於這方面的幾個題目：（篇幅原因，只舉例兩題，博客上會持續大量更新）
在2.5億個整數中找出不重複的整數，內存不足以容納這2.5億個整數。
方案1：採用Bit-Map（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需內存2^32*2bit=1GB內存，還可以接受。然後掃描這2.5億個整數，查看Bit-map中相對應位，如果是00變01，01變10，10保持不變。所描完事後，查看Bit-map，把對應位是01的整數輸出即可。
方案2：也可採用上題類似的方法，進行劃分小文件的方法。然後在小文件中找出不重複的整數，並排序。然後再進行歸併，注意去除重複的元素。
已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。
8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。 （可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==12MBytes，這樣，就用了小小的12M左右的內存表示了所有的8位數的電話）
5億個int找它們的中位數
這題也可以用Bit-Map來實現。
首先我們將int劃分為2^16個區域，然後讀取數據統計落到各個區域裡的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。
實際上，如果不是int是int64，我們可以用分治的方法，經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然後確定區域的第幾大數，在將該區域分成2^20個子區域，然後確定是子區域的第幾大數，然後子區域裡的數的個數只有2^20，就可以直接進行統計了。
歡迎各位大神不吝貢獻更多的海量數據處理相關的內容，一同分享，一同進步。
底部自營廣告即是我。