哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)倘感。也就是說帚湘，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度关面。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表十厢。
哈希表的做法其實(shí)很簡單等太，就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對數(shù)組長度進(jìn)行取余蛮放，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)缩抡，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。
而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候包颁，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)瞻想，并定位到該空間獲取value，如此一來娩嚼，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位内边。
實(shí)戰(zhàn)一把：
有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬待锈，但如果除去重復(fù)后漠其，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高竿音，說明查詢它的用戶越多和屎，也就是越熱門。）春瞬，請你統(tǒng)計(jì)最熱門的10個(gè)查詢串柴信。
有一千萬個(gè)Query，但是由于重復(fù)度比較高宽气，因此事實(shí)上只有300萬的Query随常，每個(gè)Query255Byte，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去萄涯，而現(xiàn)在只是需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)绪氛，在這里，Hash Table絕對是我們優(yōu)先的選擇涝影，因?yàn)镠ash Table的查詢速度非常的快枣察，幾乎是O(1)的時(shí)間復(fù)雜度。
那么，我們的算法就有了：維護(hù)一個(gè)Key為Query字串序目，Value為該Query出現(xiàn)次數(shù)的HashTable臂痕，每次讀取一個(gè)Query，如果該字串不在Table中猿涨，那么加入該字串握童，并且將Value值設(shè)為1；如果該字串在Table中叛赚，那么將該字串的計(jì)數(shù)加一即可舆瘪。最終我們在O(N)的時(shí)間復(fù)雜度內(nèi)完成了對該海量數(shù)據(jù)的處理。
找出Top 10
算法一：普通排序
我想對于排序算法大家都已經(jīng)不陌生了红伦，這里不在贅述，我們要注意的是排序算法的時(shí)間復(fù)雜度是NlgN淀衣，在本題目中昙读，三百萬條記錄，用1G內(nèi)存是可以存下的膨桥。
算法二：部分排序
題目要求是求出Top 10蛮浑，因此我們沒有必要對所有的Query都進(jìn)行排序，我們只需要維護(hù)一個(gè)10個(gè)大小的數(shù)組只嚣，初始化放入10個(gè)Query沮稚，按照每個(gè)Query的統(tǒng)計(jì)次數(shù)由大到小排序，然后遍歷這300萬條記錄册舞，每讀一條記錄就和數(shù)組最后一個(gè)Query對比蕴掏，如果小于這個(gè)Query，那么繼續(xù)遍歷调鲸，否則盛杰，將數(shù)組中最后一條數(shù)據(jù)淘汰，加入當(dāng)前的Query藐石。最后當(dāng)所有的數(shù)據(jù)都遍歷完畢之后即供，那么這個(gè)數(shù)組中的10個(gè)Query便是我們要找的Top10了。
不難分析出于微，這樣逗嫡，算法的最壞時(shí)間復(fù)雜度是N*K， 其中K是指top多少株依。
算法三：堆
在算法二中驱证，我們已經(jīng)將時(shí)間復(fù)雜度由NlogN優(yōu)化到NK，不得不說這是一個(gè)比較大的改進(jìn)了恋腕，可是有沒有更好的辦法呢雷滚？
分析一下，在算法二中吗坚，每次比較完成之后祈远，需要的操作復(fù)雜度都是K呆万，因?yàn)橐言夭迦氲揭粋€(gè)線性表之中，而且采用的是順序比較车份。這里我們注意一下谋减，該數(shù)組是有序的，一次我們每次查找的時(shí)候可以采用二分的方法查找扫沼，這樣操作的復(fù)雜度就降到了logK出爹，可是，隨之而來的問題就是數(shù)據(jù)移動(dòng)缎除，因?yàn)橐苿?dòng)數(shù)據(jù)次數(shù)增多了严就。不過，這個(gè)算法還是比算法二有了改進(jìn)器罐。
基于以上的分析梢为，我們想想，有沒有一種既能快速查找轰坊，又能快速移動(dòng)元素的數(shù)據(jù)結(jié)構(gòu)呢铸董？回答是肯定的，那就是堆肴沫。
借助堆結(jié)構(gòu)粟害，我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此到這里颤芬，我們的算法可以改進(jìn)為這樣悲幅，維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷300萬的Query站蝠，分別和根元素進(jìn)行對比夺艰。
思想與上述算法二一致，只是算法在算法三沉衣，我們采用了最小堆這種數(shù)據(jù)結(jié)構(gòu)代替數(shù)組郁副，把查找目標(biāo)元素的時(shí)間復(fù)雜度有O（K）降到了O（logK）。
那么這樣豌习，采用堆數(shù)據(jù)結(jié)構(gòu)存谎，算法三，最終的時(shí)間復(fù)雜度就降到了N‘logK肥隆，和算法二相比既荚，又有了比較大的改進(jìn)。
總結(jié)：
至此栋艳，算法就完全結(jié)束了恰聘，經(jīng)過上述第一步、先用Hash表統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，O（N）晴叨；然后第二步凿宾、采用堆數(shù)據(jù)結(jié)構(gòu)找出Top 10，N*O（logK）兼蕊。所以初厚，我們最終的時(shí)間復(fù)雜度是：O（N） + N’*O（logK）。（N為1000萬孙技，N’為300萬）产禾。如果各位有什么更好的算法，歡迎留言評(píng)論牵啦。
