何謂海量資料處理？
所謂海量資料處理，無非就是基於海量資料上的儲存、處理、操作。何謂海量，就是資料量太大，所以導致要麼是無法在較短時間內迅速解決，要麼是資料太大，導致無法一次性裝入記憶體。
那解決辦法呢?針對時間，我們可以採用巧妙的演算法搭配合適的資料結構，如bloom filter/hash/bit-map/堆/資料庫或倒排索引/trie樹，針對空間，無非就乙個辦法：大而化小：
分而治之/hash對映，你不是說規模太大嘛，那簡單啊，就把規模大化為規模小的，各個擊破不就完了嘛。
至於所謂的單機及集群問題，通俗點來講，單機就是處理裝載資料的機器有限(只要考慮cpu，記憶體，硬碟的資料互動)，而集群，機器有多輛，適合分布式處理，平行計算(更多考慮節點和節點間的資料互動)。
再者，通過本blog內的有關海量資料處理的文章：big data processing，我們已經大致知道，處理海量資料問題，無非就是：
1. 分而治之/hash對映 + hash統計 + 堆/快速/歸併排序；
2. 雙層桶劃分
3. bloom filter/bitmap；
4. trie樹/資料庫/倒排索引；
5. 外排序；
6. 分布式處理之hadoop/mapreduce。
下面，本文第一部分、從set/map談到hashtable/hash_map/hash_set，簡要介紹下set/map/multiset/multimap，及hash_set/hash_map/hash_multiset/hash_multimap之區別(萬丈高樓平地起，基礎最重要)，而本文第二部分，則針對上述那6種方法模式結合對應的海量資料處理面試題分別具體闡述。
第一部分、從set/map談到hashtable/hash_map/hash_set
稍後本文第二部分中將多次提到hash_map/hash_set，下面稍稍介紹下這些容器，以作為基礎準備。一般來說，stl容器分兩種，
序列式容器(vector/list/deque/stack/queue/heap)，
關聯式容器。關聯式容器又分為set(集合)和map(對映表)兩大類，以及這兩大類的衍生體multiset(多鍵集合)和multimap(多鍵對映表)，這些容器均以rb-tree完成。此外，還有第3類關聯式容器，如hashtable(雜湊表)，以及以hashtable為底層機制完成的 hash_set(雜湊集合)/hash_map(雜湊對映表)/hash_multiset(雜湊多鍵集合)/hash_multimap(雜湊多鍵對映表)。
也就是說，set/map/multiset/multimap都內含乙個rb-tree，而hash_set/hash_map/hash_multiset/hash_multimap都內含乙個hashtable。
所謂關聯式容器，類似關聯式資料庫，每筆資料或每個元素都有乙個鍵值(key)和乙個實值(value)，即所謂的key-value(鍵-值對)。當元素被插入到關聯式容器中時，容器內部結構(rb-tree/hashtable)便依照其鍵值大小，以某種特定規則將這個元素放置於適當位置。
比如，在mongodb中，文件(document)是最基本的資料組織形式，每個文件以key-value（鍵-值對）的方式組織起來。乙個文件可以有多個key-value組合，每個value可以是不同的型別，比如string、integer、list等等。
set/map/multiset/multimap
set，同map一樣，所有元素都會根據元素的鍵值自動被排序，因為set/map兩者的所有各種操作，都只是轉而呼叫rb-tree的操作行為，不過，值得注意的是，兩者都不允許兩個元素有相同的鍵值。
不同的是：set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，而map的所有元素都是pair，同時擁有實值(value)和鍵值(key)，pair的第乙個元素被視為鍵值，第二個元素被視為實值。
至於multiset/multimap，他們的特性及用法和set/map完全相同，唯一的差別就在於它們允許鍵值重複，即所有的插入操作基於rb-tree的insert_equal()而非insert_unique()。
hash_set/hash_map/hash_multiset/hash_multimap
hash_set/hash_map，兩者的一切操作都是基於hashtable之上。不同的是，hash_set同set一樣，同時擁有實值和鍵值，且實質就是鍵值，鍵值就是實值，而hash_map同map一樣，每乙個元素同時擁有乙個實值(value)和乙個鍵值(key)，所以其使用方式，和上面的map基本相同。但由於hash_set/hash_map都是基於hashtable之上，所以不具備自動排序功能。
為什麼?因為hashtable 沒有自動排序功能。
至於hash_multiset/hash_multimap的特性與上面的multiset/multimap完全相同，唯一的差別就是它們的底層實現機制是hashtable，所以它們的元素都不會被自動排序，不過也都允許鍵值重複。
所以，綜上，說白了，什麼樣的結構決定其什麼樣的性質，因為set/map/multiset/multimap都是基於rb-tree之上，所以有自動排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基於hashtable之上，所以不含有自動排序功能，至於加個字首multi_無非就是允許鍵值重複而已。
此外，關於什麼hash，請看此篇文章：關於紅黑樹，請參看blog內系列文章：關於hash_map的具體使用，可看看此篇文章：
ok，接下來，請看本文第二部分、處理海量資料問題之六把密匙。
第二部分、處理海量資料問題之六把密匙
密匙一、分而治之/hash對映 + hash統計 + 堆/快速/歸併排序
1、海量日誌資料，提取出某日訪問百度次數最多的那個ip。
既然是海量資料處理，那麼可想而知，給我們的資料那就一定是海量的。針對這個資料的海量，我們如何著手呢?對的，無非就是分而治之/hash對映 + hash統計 + 堆/快速/歸併排序，說白了，就是先對映，而後統計，最後排序：
1. 分而治之/hash對映：針對資料太大，記憶體受限，只能是：把大檔案化成(取模對映)小檔案，即16字方針：大而化小，各個擊破，縮小規模，逐個解決
2. hash統計：當大檔案轉化了小檔案，那麼我們便可以採用常規的hash_map(ip，value)來進行頻率統計。
3. 堆/快速排序：統計完了之後，便進行排序(可採取堆排序)，得到次數最多的ip。
具體而論，則是： 「首先是這一天，並且是訪問百度的日誌中的ip取出來，逐個寫入到乙個大檔案中。注意到ip是32位的，最多有個2^32個ip。
同樣可以採用對映的方法，比如模1000，把整個大檔案對映為1000個小檔案，再找出每個小文中出現頻率最大的ip（可以採用hash_map進行頻率統計，然後再找出頻率最大的幾個）及相應的頻率。然後再在這1000個最大的ip中，找出那個頻率最大的ip，即為所求。」--十道海量資料處理面試題與十個方法大總結。
注：hash取模是一種等價對映，不會存在同乙個元素分散到不同小檔案中去的情況，即這裡採用的是mod1000演算法，那麼相同的ip在hash後，只可能落在同乙個檔案中，不可能被分散的。
那到底什麼是hash對映呢？我換個角度舉個淺顯直白的例子，如本文的url是：當我把這個url發表在微博上，便被對映成了：
於此，我們發現url本身的長度被縮短了，但這兩個url對應的文章的是同一篇即本文。ok，有興趣的，還可以再了解下一致性hash演算法，見此文第五部分：
2、搜尋引擎會通過日誌檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-節。
假設目前有一千萬個記錄（這些查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個。乙個查詢串的重複度越高，說明查詢它的使用者越多，也就是越熱門），請你統計最熱門的10個查詢串，要求使用的記憶體不能超過1g。
由上面第1題，我們知道，資料大則劃為小的，但如果資料規模比較小，能一次性裝入記憶體呢?比如這第2題，雖然有一千萬個query，但是由於重複度比較高，因此事實上只有300萬的query，每個query255byte，因此我們可以考慮把他們都放進記憶體中去，而現在只是需要乙個合適的資料結構，在這裡，hash table絕對是我們優先的選擇。所以我們摒棄分而治之/hash對映的方法，直接上hash統計，然後排序。
so，1. hash 統計：先對這批海量資料預處理(維護乙個key為query字串，value為該query出現次數的hashtable，即 hash_map(query，value)，每次讀取乙個query，如果該字串不在table中，那麼加入該字串，並且將value值設為1；如果該字串在table中，那麼將該字串的計數加一即可。
最終我們在o(n)的時間複雜度內用hash表完成了統計；
2. 堆排序：第二步、借助堆這個資料結構，找出top k，時間複雜度為n『logk。
即借助堆結構，我們可以在log量級的時間內查詢和調整/移動。因此，維護乙個k(該題目中是10)大小的小根堆，然後遍歷300萬的query，分別和根元素進行對比所以，我們最終的時間複雜度是：o（n） + n'*o（logk），（n為1000萬，n』為300萬）。
別忘了這篇文章中所述的堆排序思路：「維護k個元素的最小堆，即用容量為k的最小堆儲存最先遍歷到的k個數，並假設它們即是最大的k個數，建堆費時o（k），並調整堆（費時o（logk））後， 有k1>k2>...kmin（kmin設為小頂堆中最小元素）。
繼續遍歷數列，每次遍歷乙個元素x，與堆頂元素比較，若 x>kmin，則更新堆（用時logk），否則不更新堆。這樣下來，總費時o（k*logk+（n-k）*logk）=o（n*logk）。此方法得益於在堆中，查詢等各項操作時間複雜度均為logk。
」--第三章續、top k演算法問題的實現。
當然，你也可以採用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最後用10個元素的最小推來對出現頻率進行排序。
海量資料處理筆試面試題
1.給定a b兩個檔案，各存放50億個url，每個url各佔64位元組，記憶體限制是4g，讓你找出a b檔案共同的url？方案1 可以估計每個檔案安的大小為50g 64 320g，遠遠大於記憶體限制的4g。所以不可能將其完全載入到記憶體中處理。考慮採取分而治之的方法。s 遍歷檔案a，對每個url求取...
十七道海量資料處理面試題
十七道海量資料處理面試題與bit map詳解 作者 小橋流水，redfox66，july。文章性質 整理。前言 本部落格內曾經整理過有關海量資料處理的10道面試題 十道海量資料處理面試題與十個方法大總結 此次除了重複了之前的10道面試題之後，重新多整理了7道。僅作各位參考，不作它用。同時，程式設計師...
十道海量資料處理面試題
table of contents 第一部分 十道海量資料處理面試題 1 1 海量日誌資料，提取出某日訪問次數最多的那個ip。1 2 搜尋引擎會通過日誌檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1 節。2 3 有乙個1g大小的乙個檔案，裡面每一行是乙個詞，詞的大小不超過16位...