1、Question
有一個 1GB 大小的檔案，檔案裡每一行是一個詞，每個詞的大小不超過 16B，記憶體大小限制是 1MB，要求傳回頻數最高的 100 個詞(Top 100)。
2、分析
仍然是大資料量的處理問題。由于檔案大小遠超過記憶體大小。是以仍然采用分治思路。把大檔案拆分多分。如果5000份，每份200KB。如果2000份，每份500KB。此處分成5000份，每份200KB。每次處理200KB的檔案。
思路如下：
首先把大檔案差分成可以加載到記憶體中的小檔案，然後周遊各個小檔案，對周遊到的每個詞x，執行
hash(x) % 5000
，将結果為 i 的詞存放到檔案ai中。周遊結束後，我們可以得到 5000 個小檔案。每個小檔案的大小為 200KB 左右。如果有的小檔案大小仍然超過 1MB，則采用同樣的方式繼續進行分解。
接着統計每個小檔案中出現頻數最高的 100 個詞。最簡單的方式是使用 HashMap 來實作。其中 key 為詞，value 為該詞出現的頻率。具體方法是：對于周遊到的詞 x，如果在 map 中不存在，則執行
map.put(x, 1)
；若存在，則執行
map.put(x, map.get(x)+1)
，将該詞頻數加 1。
上面我們統計了每個小檔案單詞出現的頻數。接下來，我們可以通過維護一個小頂堆來找出所有詞中出現頻數最高的 100 個。具體方法是：依次周遊每個小檔案，建構一個小頂堆，堆大小為 100。如果周遊到的詞的出現次數大于堆頂詞的出現次數，則用新詞替換堆頂的詞，然後重新調整為小頂堆，周遊結束後，小頂堆上的詞就是出現頻數最高的 100 個詞。
總結
- 分而治之，進行哈希取餘；
- 使用 HashMap 統計頻數；
- 求解最大的 TopN 個，用小頂堆；求解最小的 TopN 個，用大頂堆