場景
這是一個 ip 地址 127.0.0.1
假設(shè)有100億個這樣的 ip 地址存在文件中
這個文件大小大約是 100GB
問題：要統(tǒng)計出100億個 ip 中，重復(fù)出現(xiàn)次數(shù)最多的前10個
分析
100GB 幾乎不可能一次加載進內(nèi)存進行操作蝎土，所以必須要拆分
那么可以利用分治的思想视哑，把規(guī)模大的問題化小，然后解決各個小的問題誊涯，最后得出結(jié)果挡毅。
實現(xiàn)思路
- ipv4 地址是一個 32 位的整數(shù)，可以用 uint 保存暴构。
- 我先設(shè)計一個哈希函數(shù)跪呈，把100個G的文件分成10000份，每份大約是 10MB取逾，可以加載進內(nèi)存了耗绿。
例如：我設(shè)計一個簡單的哈希函數(shù)是 f(ip) = ip % 10000，(ip 是個32位整數(shù))
那么 5 % 10000 = 5砾隅，不管 5 在哪個地方 5 % 10000 的結(jié)果都是 5缭乘，這就保證了相同的 ip 會被放在同一個子文件中，方便統(tǒng)計琉用，相同的元素經(jīng)過同一個哈希函數(shù)堕绩，得出的哈希值是一樣的。
那么我把100億個 ip邑时，都進行 ip % 10000 的操作奴紧，就完成了 100GB 文件分解成 10000個子文件的任務(wù)了。當(dāng)然實際中哈希函數(shù)的選取很重要晶丘，盡量使得元素分布均勻黍氮，哈希沖突少的函數(shù)才是最好的唐含。
記住，我把上面這個分解的過程叫做 Map沫浆，由一臺叫 master 的計算機完成這個工作捷枯。
- 10MB 的小文件加進內(nèi)存，統(tǒng)計出出現(xiàn)次數(shù)最多的那個ip
10MB 的小文件里面存著很多 ip专执，他們雖然是亂序的淮捆，但是相同的 ip 會映射到同一個文件中來！
那么可以用二叉樹統(tǒng)計出現(xiàn)次數(shù)本股，二叉樹節(jié)點保存（ip, count）的信息攀痊，把所有 ip 插入到二叉樹中，如果這個 ip 不存在拄显，那么新建一個節(jié)點, count 標記 1苟径，如果有，那么把 count++躬审，最終遍歷一遍樹棘街，就能找出 count 最大的 ip 了。
我把這個過程叫做 Reduce承边，由很多臺叫 worker 的計算機來完成蹬碧。
每個 worker 至少要找出最大的前10個 ip 返回給 master，master 最后會收集到 10000 * 10 個 ip炒刁，大約 400KB恩沽，然后再找出最大的前 10 個 ip 就可以了。
最簡單的遍歷10遍翔始，每次拿個最大值出來就可以了罗心，或者用快速排序，堆排序城瞎，歸并排序等等方法渤闷，找出最大前 k 個數(shù)也行。
MapReduce
我剛剛除了介紹了一種海量數(shù)據(jù)的哈希分治算法之外脖镀，還穿插了一個谷歌的 MapReduce 分布式并行編程模型飒箭，原理就是上面說的那些了，有興趣的可以去詳細了解蜒灰。
哈希函數(shù)是什么弦蹂？哈希函數(shù)是把大空間的元素映射到一個小空間里。
說完了原理强窖，我已經(jīng)根據(jù)上面的原理寫了一個實驗程序凸椿，有興趣的可以去看看，地址在 這里
可以下載來看翅溺，代碼是C++的脑漫，vs2008 編譯環(huán)境髓抑。
