普通版尋找Top-K問題
用HashMap+priorityQueue
HashMap<key, 次數(shù)>
然后根據(jù)HashMap的每個(gè)Key 創(chuàng)建Node辩块，Node里面包含data和frequency信息。
然后把Node放入PriorityQueue里莲兢，comparator按照frequency來存儲(chǔ)菩浙。
進(jìn)階版：如果Input的data很大侄旬，Single Machine的內(nèi)存裝不下
Naive做法就是直接分成好幾個(gè)部分分配個(gè)多臺(tái)機(jī)器
但是這里錯(cuò)誤很明顯所森！
假設(shè)Google被分到各個(gè)機(jī)器了溪窒。然后每個(gè)機(jī)器算出每臺(tái)的Top K。Google雖然總次數(shù)排名第一舌菜，但是分散到了每個(gè)機(jī)器在每個(gè)機(jī)器都不是第一萌壳，這樣我們的結(jié)果就是錯(cuò)的！
所以應(yīng)該：
這里其實(shí)是不對的，NBA總次數(shù)有30呢袱瓮！而且NBA其實(shí)也沒用group到一臺(tái)機(jī)器缤骨。
Divide-rehash:
進(jìn)階：
如果是實(shí)時(shí)計(jì)算Top-K
空間大部分會(huì)留給那些熱搜度很低的詞，很浪費(fèi)尺借。所以用Approx Top K
之前是每個(gè)單詞有一個(gè)空間“砥穑現(xiàn)在是按hash來分空間。同一個(gè)Hash的都去一個(gè)地方燎斩。
這樣有可能會(huì)有一些error 比如說單詞A出現(xiàn)99次虱歪，單詞B沒出現(xiàn)過 但是由于hash一樣，它直接你能夠算作出現(xiàn)了99+1次
Solution:
別的方法：
Map-reduce的word count
還是會(huì)用到treeMap. 當(dāng)mapreduce每算出一個(gè)key的結(jié)果栅表，先存在Map里实蔽，如果有更高的結(jié)果，再把之前的kick out谨读。
