QUERY中哈希表的剖析與算法研究

【摘 要】本文通過剖析搜索引擎的日志文件，總結(jié)出了快速找出TOP K的算法，在該算法中主要應(yīng)用哈希表算法，在比較多種哈希表算法的優(yōu)缺點(diǎn)后，研究設(shè)計(jì)了一個(gè)檢索速度最快的哈希表算法。

【關(guān)鍵詞】QUERY；算法研究

1.Query的剖析

百度是廣大網(wǎng)民經(jīng)常用來查詢信息的網(wǎng)站，但百度會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個(gè)記錄，這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。如何統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G，這是個(gè)值得探討的問題。要統(tǒng)計(jì)最熱門查詢，首先就是要統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，然后根據(jù)統(tǒng)計(jì)結(jié)果，找出Top 10。所以可以基于這個(gè)思路分兩步來設(shè)計(jì)該算法。

2.Query的統(tǒng)計(jì)方法

Query統(tǒng)計(jì)可以選擇以下兩種方法：

（1）直接排序法：首先對這個(gè)日志里面的所有Query都進(jìn)行排序，然后再遍歷排好序的Query，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)了。但是內(nèi)存不能超過1G，一千萬條記錄，每條記錄是255Byte，很顯然要占據(jù)2.375G內(nèi)存，這個(gè)條件就不滿足要求了。當(dāng)數(shù)據(jù)量比較大而且內(nèi)存無法裝下的時(shí)候，可以采用外排序的方法來進(jìn)行排序，這里可以采用歸并排序，因?yàn)闅w并排序有一個(gè)比較好的時(shí)間復(fù)雜度O（nlogn）。排完序之后再對已經(jīng)有序的Query文件進(jìn)行遍歷，統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，再次寫入文件中。綜合分析一下，排序的時(shí)間復(fù)雜度是O（nlogn），而遍歷的時(shí)間復(fù)雜度是O（n），因此該算法的總體時(shí)間復(fù)雜度就是O（n+nlogn）=O（nlogn）。

（2）Hash Table法：在第1個(gè)方法中，采用了排序的辦法來統(tǒng)計(jì)每個(gè)Query出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O（nlogn），那么能不能有更好的方法來存儲，而時(shí)間復(fù)雜度更低呢？雖然有一千萬個(gè)Query，但是由于重復(fù)度比較高，因此事實(shí)上只有300萬的Query，每個(gè)Query 255Byte，可以考慮把他們都放進(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ù)的處理。

本方法相比算法1：在時(shí)間復(fù)雜度上提高了一個(gè)數(shù)量級，為O（n），但不僅僅是時(shí)間復(fù)雜度上的優(yōu)化，該方法只需要IO數(shù)據(jù)文件一次，而算法1的IO次數(shù)較多的，因此該算法2比算法1在工程上有更好的可操作性。

3.找出Top 10

算法一：普通排序；對于排序算法是經(jīng)常編程用到的，要注意的是排序算法的時(shí)間復(fù)雜度是O（nlogn），在這里的三百萬條記錄，用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ù)移動，因?yàn)橐苿訑?shù)據(jù)次數(shù)增多了。不過，這個(gè)算法還是比算法二有了改進(jìn)。有沒有一種既能快速查找，又能快速移動元素的數(shù)據(jù)結(jié)構(gòu)呢？回答是肯定的，那就是堆。

借助堆結(jié)構(gòu)，可以在log量級的時(shí)間內(nèi)查找和調(diào)整/移動。因此到這里，算法可以改進(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é)束了，經(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萬）。

4.總結(jié)

這就是解決在搜索引擎查詢記錄Query中尋找出TOP K的最快的Hash表算法。當(dāng)然HASH表的算法設(shè)計(jì)是靈活多變的，在不同的數(shù)據(jù)處理中可以進(jìn)行不同的設(shè)計(jì)，以達(dá)到高效處理的目的。本人開發(fā)的某科學(xué)資源網(wǎng)站的搜索信息板塊也適當(dāng)采用了上述算法進(jìn)行數(shù)據(jù)的高效處理。

【參考文獻(xiàn)】

[1]曹珍富.公鑰密碼學(xué)[M].哈爾濱：黑龍江教育出版社，1993.