求TopN熱搜關(guān)鍵詞[大數(shù)據(jù)算法]

搜索引擎的熱門搜索排行榜功能你用過(guò)嗎?你知道這個(gè)功能是如何實(shí)現(xiàn)的嗎?實(shí)際上，它的實(shí)現(xiàn)并不復(fù)雜。搜索引擎每天會(huì)接收大量的用戶搜索請(qǐng)求，它會(huì)把這些用戶輸入的搜索關(guān)鍵詞記錄下來(lái)，然后再離線地統(tǒng)計(jì)分析，得到最熱門的 Top 10 搜索關(guān)鍵詞。

那請(qǐng)你思考下，假設(shè)現(xiàn)在我們有一個(gè)包含 10 億個(gè)搜索關(guān)鍵詞的日志文件，如何能快速獲取到熱門榜 Top 10 的搜索關(guān)鍵詞呢?

這個(gè)問(wèn)題就可以用堆來(lái)解決，這也是堆這種數(shù)據(jù)結(jié)構(gòu)一個(gè)非常典型的應(yīng)用。上一節(jié)我們講了堆和堆排序的一些理論知識(shí)，今天我們就來(lái)講一講，堆這種數(shù)據(jù)結(jié)構(gòu)幾個(gè)非常重要的應(yīng)用：優(yōu)先級(jí)隊(duì)列、求 Top K 和求中位數(shù)?！就扑]了解：大數(shù)據(jù)培訓(xùn)課程】

堆的應(yīng)用一：優(yōu)先級(jí)隊(duì)列

首先，我們來(lái)看第一個(gè)應(yīng)用場(chǎng)景：優(yōu)先級(jí)隊(duì)列。

優(yōu)先級(jí)隊(duì)列，顧名思義，它首先應(yīng)該是一個(gè)隊(duì)列。我們前面講過(guò)，隊(duì)列最大的特性就是先進(jìn)先出。不過(guò)，在優(yōu)先級(jí)隊(duì)列中，數(shù)據(jù)的出隊(duì)順序不是先進(jìn)先出，而是按照優(yōu)先級(jí)來(lái)，優(yōu)先級(jí)最高的，最先出隊(duì)。

如何實(shí)現(xiàn)一個(gè)優(yōu)先級(jí)隊(duì)列呢?方法有很多，但是用堆來(lái)實(shí)現(xiàn)是最直接、最高效的。這是因?yàn)?，堆和?yōu)先級(jí)隊(duì)列非常相似。一個(gè)堆就可以看作一個(gè)優(yōu)先級(jí)隊(duì)列。很多時(shí)候，它們只是概念上的區(qū)分而已。往優(yōu)先級(jí)隊(duì)列中插入一個(gè)元素，就相當(dāng)于往堆中插入一個(gè)元素;從優(yōu)先級(jí)隊(duì)列中取出優(yōu)先級(jí)最高的元素，就相當(dāng)于取出堆頂元素。

你可別小看這個(gè)優(yōu)先級(jí)隊(duì)列，它的應(yīng)用場(chǎng)景非常多。我們后面要講的很多數(shù)據(jù)結(jié)構(gòu)和算法都要依賴它。比如，赫夫曼編碼、圖的最短路徑、最小生成樹(shù)算法等等。不僅如此，很多語(yǔ)言中，都提供了優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)，比如，Java 的 PriorityQueue，C++ 的 priority_queue 等。

只講這些應(yīng)用場(chǎng)景比較空泛，現(xiàn)在，我舉兩個(gè)具體的例子，讓你感受一下優(yōu)先級(jí)隊(duì)列具體是怎么用的。

1. 合并有序小文件

假設(shè)我們有 100 個(gè)小文件，每個(gè)文件的大小是 100MB，每個(gè)文件中存儲(chǔ)的都是有序的字符串。我們希望將這些 100 個(gè)小文件合并成一個(gè)有序的大文件。這里就會(huì)用到優(yōu)先級(jí)隊(duì)列。

整體思路有點(diǎn)像歸并排序中的合并函數(shù)。我們從這 100 個(gè)文件中，各取第一個(gè)字符串，放入數(shù)組中，然后比較大小，把最小的那個(gè)字符串放入合并后的大文件中，并從數(shù)組中刪除。

假設(shè)，這個(gè)最小的字符串來(lái)自于 13.txt 這個(gè)小文件，我們就再?gòu)倪@個(gè)小文件取下一個(gè)字符串，并且放到數(shù)組中，重新比較大小，并且選擇最小的放入合并后的大文件，并且將它從數(shù)組中刪除。依次類推，直到所有的文件中的數(shù)據(jù)都放入到大文件為止。

這里我們用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，來(lái)存儲(chǔ)從小文件中取出來(lái)的字符串。每次從數(shù)組中取最小字符串，都需要循環(huán)遍歷整個(gè)數(shù)組，顯然，這不是很高效。有沒(méi)有更加高效方法呢?

這里就可以用到優(yōu)先級(jí)隊(duì)列，也可以說(shuō)是堆。我們將從小文件中取出來(lái)的字符串放入到小頂堆中，那堆頂?shù)脑?，也就是?yōu)先級(jí)隊(duì)列隊(duì)首的元素，就是最小的字符串。我們將這個(gè)字符串放入到大文件中，并將其從堆中刪除。然后再?gòu)男∥募腥〕鱿乱粋€(gè)字符串，放入到堆中。循環(huán)這個(gè)過(guò)程，就可以將 100 個(gè)小文件中的數(shù)據(jù)依次放入到大文件中。

我們知道，刪除堆頂數(shù)據(jù)和往堆中插入數(shù)據(jù)的時(shí)間復(fù)雜度都是 O(logn)，n 表示堆中的數(shù)據(jù)個(gè)數(shù)，這里就是 100。是不是比原來(lái)數(shù)組存儲(chǔ)的方式高效了很多呢?

2. 高性能定時(shí)器

假設(shè)我們有一個(gè)定時(shí)器，定時(shí)器中維護(hù)了很多定時(shí)任務(wù)，每個(gè)任務(wù)都設(shè)定了一個(gè)要觸發(fā)執(zhí)行的時(shí)間點(diǎn)。定時(shí)器每過(guò)一個(gè)很小的單位時(shí)間(比如 1 秒)，就掃描一遍任務(wù)，看是否有任務(wù)到達(dá)設(shè)定的執(zhí)行時(shí)間。如果到達(dá)了，就拿出來(lái)執(zhí)行。

但是，這樣每過(guò) 1 秒就掃描一遍任務(wù)列表的做法比較低效，主要原因有兩點(diǎn)：第一，任務(wù)的約定執(zhí)行時(shí)間離當(dāng)前時(shí)間可能還有很久，這樣前面很多次掃描其實(shí)都是徒勞的;第二，每次都要掃描整個(gè)任務(wù)列表，如果任務(wù)列表很大的話，勢(shì)必會(huì)比較耗時(shí)。

針對(duì)這些問(wèn)題，我們就可以用優(yōu)先級(jí)隊(duì)列來(lái)解決。我們按照任務(wù)設(shè)定的執(zhí)行時(shí)間，將這些任務(wù)存儲(chǔ)在優(yōu)先級(jí)隊(duì)列中，隊(duì)列首部(也就是小頂堆的堆頂)存儲(chǔ)的是最先執(zhí)行的任務(wù)。

這樣，定時(shí)器就不需要每隔 1 秒就掃描一遍任務(wù)列表了。它拿隊(duì)首任務(wù)的執(zhí)行時(shí)間點(diǎn)，與當(dāng)前時(shí)間點(diǎn)相減，得到一個(gè)時(shí)間間隔 T。

這個(gè)時(shí)間間隔 T 就是，從當(dāng)前時(shí)間開(kāi)始，需要等待多久，才會(huì)有第一個(gè)任務(wù)需要被執(zhí)行。這樣，定時(shí)器就可以設(shè)定在 T 秒之后，再來(lái)執(zhí)行任務(wù)。從當(dāng)前時(shí)間點(diǎn)到(T-1)秒這段時(shí)間里，定時(shí)器都不需要做任何事情。

當(dāng) T 秒時(shí)間過(guò)去之后，定時(shí)器取優(yōu)先級(jí)隊(duì)列中隊(duì)首的任務(wù)執(zhí)行。然后再計(jì)算新的隊(duì)首任務(wù)的執(zhí)行時(shí)間點(diǎn)與當(dāng)前時(shí)間點(diǎn)的差值，把這個(gè)值作為定時(shí)器執(zhí)行下一個(gè)任務(wù)需要等待的時(shí)間。

這樣，定時(shí)器既不用間隔 1 秒就輪詢一次，也不用遍歷整個(gè)任務(wù)列表，性能也就提高了。

堆的應(yīng)用二：利用堆求 Top K

剛剛我們學(xué)習(xí)了優(yōu)先級(jí)隊(duì)列，我們現(xiàn)在來(lái)看，堆的另外一個(gè)非常重要的應(yīng)用場(chǎng)景，那就是“求 Top K 問(wèn)題”。

我把這種求 Top K 的問(wèn)題抽象成兩類。一類是針對(duì)靜態(tài)數(shù)據(jù)集合，也就是說(shuō)數(shù)據(jù)集合事先確定，不會(huì)再變。另一類是針對(duì)動(dòng)態(tài)數(shù)據(jù)集合，也就是說(shuō)數(shù)據(jù)集合事先并不確定，有數(shù)據(jù)動(dòng)態(tài)地加入到集合中。

針對(duì)靜態(tài)數(shù)據(jù)，如何在一個(gè)包含 n 個(gè)數(shù)據(jù)的數(shù)組中，查找前 K 大數(shù)據(jù)呢?我們可以維護(hù)一個(gè)大小為 K 的小頂堆，順序遍歷數(shù)組，從數(shù)組中取出取數(shù)據(jù)與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，并且將這個(gè)元素插入到堆中;如果比堆頂元素小，則不做處理，繼續(xù)遍歷數(shù)組。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了。

遍歷數(shù)組需要 O(n) 的時(shí)間復(fù)雜度，一次堆化操作需要 O(logK) 的時(shí)間復(fù)雜度，所以最壞情況下，n 個(gè)元素都入堆一次，所以時(shí)間復(fù)雜度就是 O(nlogK)。

針對(duì)動(dòng)態(tài)數(shù)據(jù)求得 Top K 就是實(shí)時(shí) Top K。怎么理解呢?我舉一個(gè)例子。一個(gè)數(shù)據(jù)集合中有兩個(gè)操作，一個(gè)是添加數(shù)據(jù)，另一個(gè)詢問(wèn)當(dāng)前的前 K 大數(shù)據(jù)。

如果每次詢問(wèn)前 K 大數(shù)據(jù)，我們都基于當(dāng)前的數(shù)據(jù)重新計(jì)算的話，那時(shí)間復(fù)雜度就是 O(nlogK)，n 表示當(dāng)前的數(shù)據(jù)的大小。實(shí)際上，我們可以一直都維護(hù)一個(gè) K 大小的小頂堆，當(dāng)有數(shù)據(jù)被添加到集合中時(shí)，我們就拿它與堆頂?shù)脑貙?duì)比。如果比堆頂元素大，我們就把堆頂元素刪除，并且將這個(gè)元素插入到堆中;如果比堆頂元素小，則不做處理。這樣，無(wú)論任何時(shí)候需要查詢當(dāng)前的前 K 大數(shù)據(jù)，我們都可以里立刻返回給他。

堆的應(yīng)用三：利用堆求中位數(shù)

前面我們講了如何求 Top K 的問(wèn)題，現(xiàn)在我們來(lái)講下，如何求動(dòng)態(tài)數(shù)據(jù)集合中的中位數(shù)。

中位數(shù)，顧名思義，就是處在中間位置的那個(gè)數(shù)。如果數(shù)據(jù)的個(gè)數(shù)是奇數(shù)，把數(shù)據(jù)從小到大排列，那第 n/2+1 個(gè)數(shù)據(jù)就是中位數(shù);如果數(shù)據(jù)的個(gè)數(shù)是偶數(shù)的話，那處于中間位置的數(shù)據(jù)有兩個(gè)，第n/2 個(gè)和第 n/2+1 個(gè)數(shù)據(jù)，這個(gè)時(shí)候，我們可以隨意取一個(gè)作為中位數(shù)，比如取兩個(gè)數(shù)中靠前的那個(gè)，就是第 n/2 個(gè)數(shù)據(jù)。

對(duì)于一組靜態(tài)數(shù)據(jù)，中位數(shù)是固定的，我們可以先排序，第 n/2 個(gè)數(shù)據(jù)就是中位數(shù)。每次詢問(wèn)中位數(shù)的時(shí)候，我們直接返回這個(gè)固定的值就好了。所以，盡管排序的代價(jià)比較大，但是邊際成本會(huì)很小。但是，如果我們面對(duì)的是動(dòng)態(tài)數(shù)據(jù)集合，中位數(shù)在不停地變動(dòng)，如果再用先排序的方法，每次詢問(wèn)中位數(shù)的時(shí)候，都要先進(jìn)行排序，那效率就不高了。

借助堆這種數(shù)據(jù)結(jié)構(gòu)，我們不用排序，就可以非常高效地實(shí)現(xiàn)求中位數(shù)操作。我們來(lái)看看，它是如何做到的?

我們需要維護(hù)兩個(gè)堆，一個(gè)大頂堆，一個(gè)小頂堆。大頂堆中存儲(chǔ)前半部分?jǐn)?shù)據(jù)，小頂堆中存儲(chǔ)后半部分?jǐn)?shù)據(jù)，且小頂堆中的數(shù)據(jù)都大于大頂堆中的數(shù)據(jù)。

也就是說(shuō)，如果有 n 個(gè)數(shù)據(jù)，n 是偶數(shù)，我們從小到大排序，那前 n/2 個(gè)數(shù)據(jù)存儲(chǔ)在大頂堆中，后 n/2 個(gè)數(shù)據(jù)存儲(chǔ)在小頂堆中。這樣，大頂堆中的堆頂元素就是我們要找的中位數(shù)。如果 n 是奇數(shù)，情況是類似的，大頂堆就存儲(chǔ) n/2+1 個(gè)數(shù)據(jù)，小頂堆中就存儲(chǔ) n/2 個(gè)數(shù)據(jù)。

我們前面也提到，數(shù)據(jù)是動(dòng)態(tài)變化的，當(dāng)新添加一個(gè)數(shù)據(jù)的時(shí)候，我們?nèi)绾握{(diào)整兩個(gè)堆，讓大頂堆中的堆頂元素繼續(xù)是中位數(shù)呢?

如果新加入的數(shù)據(jù)小于等于大頂堆的堆頂元素，我們就將這個(gè)新數(shù)據(jù)插入到大頂堆;如果新加入的數(shù)據(jù)大于等于小頂堆的堆頂元素，我們就將這個(gè)新數(shù)據(jù)插入到小頂堆。

這個(gè)時(shí)候就有可能出現(xiàn)，兩個(gè)堆中的數(shù)據(jù)個(gè)數(shù)不符合前面約定的情況：如果 n 是偶數(shù)，兩個(gè)堆中的數(shù)據(jù)個(gè)數(shù)都是n/2;如果 n 是奇數(shù)，大頂堆有 n/2+1 個(gè)數(shù)據(jù)，小頂堆有 n/2 個(gè)數(shù)據(jù)。這個(gè)時(shí)候，我們可以從一個(gè)堆中不停地將堆頂元素移動(dòng)到另一個(gè)堆，通過(guò)這樣的調(diào)整，來(lái)讓兩個(gè)堆中的數(shù)據(jù)滿足上面的約定。

于是，我們就可以利用兩個(gè)堆，一個(gè)大頂堆、一個(gè)小頂堆，實(shí)現(xiàn)在動(dòng)態(tài)數(shù)據(jù)集合中求中位數(shù)的操作。插入數(shù)據(jù)因?yàn)樾枰婕岸鸦?，所以時(shí)間復(fù)雜度變成了 O(logn)，但是求中位數(shù)我們只需要返回大頂堆的堆頂元素就可以了，所以時(shí)間復(fù)雜度就是 O(1)。

實(shí)際上，利用兩個(gè)堆不僅可以快速求出中位數(shù)，還可以快速求其他百分位的數(shù)據(jù)，原理是類似的。還記得我們?cè)?ldquo;為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法”里的這個(gè)問(wèn)題嗎?“如何快速求接口的 99% 響應(yīng)時(shí)間?”我們現(xiàn)在就來(lái)看下，利用兩個(gè)堆如何來(lái)實(shí)現(xiàn)。

在開(kāi)始這個(gè)問(wèn)題的講解之前，我先解釋一下，什么是“99% 響應(yīng)時(shí)間”。

中位數(shù)的概念就是將數(shù)據(jù)從小到大排列，處于中間位置，就叫中位數(shù)，這個(gè)數(shù)據(jù)會(huì)大于等于前面 50% 的數(shù)據(jù)。99 百分位數(shù)的概念可以類比中位數(shù)，如果將一組數(shù)據(jù)從小到大排列，這個(gè) 99 百分位數(shù)就是大于前面 99% 數(shù)據(jù)的那個(gè)數(shù)據(jù)。

如果你還是不太理解，我再舉個(gè)例子。假設(shè)有 100 個(gè)數(shù)據(jù)，分別是 1，2，3，……，100，那 99 百分位數(shù)就是 99，因?yàn)樾∮诘扔?99 的數(shù)占總個(gè)數(shù)的 99%。

弄懂了這個(gè)概念，我們?cè)賮?lái)看 99% 響應(yīng)時(shí)間。如果有 100 個(gè)接口訪問(wèn)請(qǐng)求，每個(gè)接口請(qǐng)求的響應(yīng)時(shí)間都不同，比如 55 毫秒、100 毫秒、23 毫秒等，我們把這 100 個(gè)接口的響應(yīng)時(shí)間按照從小到大排列，排在第 99 的那個(gè)數(shù)據(jù)就是 99% 響應(yīng)時(shí)間，也叫 99 百分位響應(yīng)時(shí)間。

我們總結(jié)一下，如果有 n 個(gè)數(shù)據(jù)，將數(shù)據(jù)從小到大排列之后，99 百分位數(shù)大約就是第 n*99% 個(gè)數(shù)據(jù)，同類，80 百分位數(shù)大約就是第 n*80% 個(gè)數(shù)據(jù)。

弄懂了這些，我們?cè)賮?lái)看如何求 99% 響應(yīng)時(shí)間。

我們維護(hù)兩個(gè)堆，一個(gè)大頂堆，一個(gè)小頂堆。假設(shè)當(dāng)前總數(shù)據(jù)的個(gè)數(shù)是 n，大頂堆中保存 n*99% 個(gè)數(shù)據(jù)，小頂堆中保存 n*1% 個(gè)數(shù)據(jù)。大頂堆堆頂?shù)臄?shù)據(jù)就是我們要找的 99% 響應(yīng)時(shí)間。

每次插入一個(gè)數(shù)據(jù)的時(shí)候，我們要判斷這個(gè)數(shù)據(jù)跟大頂堆和小頂堆堆頂數(shù)據(jù)的大小關(guān)系，然后決定插入到哪個(gè)堆中。如果這個(gè)新插入的數(shù)據(jù)比大頂堆的堆頂數(shù)據(jù)小，那就插入大頂堆;如果這個(gè)新插入的數(shù)據(jù)比小頂堆的堆頂數(shù)據(jù)大，那就插入小頂堆。

但是，為了保持大頂堆中的數(shù)據(jù)占 99%，小頂堆中的數(shù)據(jù)占 1%，在每次新插入數(shù)據(jù)之后，我們都要重新計(jì)算，這個(gè)時(shí)候大頂堆和小頂堆中的數(shù)據(jù)個(gè)數(shù)，是否還符合 99:1 這個(gè)比例。如果不符合，我們就將一個(gè)堆中的數(shù)據(jù)移動(dòng)到另一個(gè)堆，直到滿足這個(gè)比例。移動(dòng)的方法類似前面求中位數(shù)的方法，這里我就不啰嗦了。

通過(guò)這樣的方法，每次插入數(shù)據(jù)，可能會(huì)涉及幾個(gè)數(shù)據(jù)的堆化操作，所以時(shí)間復(fù)雜度是 O(logn)。每次求 99% 響應(yīng)時(shí)間的時(shí)候，直接返回大頂堆中的堆頂數(shù)據(jù)即可，時(shí)間復(fù)雜度是 O(1)。

解答開(kāi)篇

學(xué)懂了上面的一些應(yīng)用場(chǎng)景的處理思路，我想你應(yīng)該能解決開(kāi)篇的那個(gè)問(wèn)題了吧。假設(shè)現(xiàn)在我們有一個(gè)包含 10 億個(gè)搜索關(guān)鍵詞的日志文件，如何快速獲取到 Top 10 最熱門的搜索關(guān)鍵詞呢?

處理這個(gè)問(wèn)題，有很多高級(jí)的解決方法，比如使用 MapReduce 等。但是，如果我們將處理的場(chǎng)景限定為單機(jī)，可以使用的內(nèi)存為 1GB。那這個(gè)問(wèn)題該如何解決呢?

因?yàn)橛脩羲阉鞯年P(guān)鍵詞，有很多可能都是重復(fù)的，所以我們首先要統(tǒng)計(jì)每個(gè)搜索關(guān)鍵詞出現(xiàn)的頻率。我們可以通過(guò)散列表、平衡二叉查找樹(shù)或者其他一些支持快速查找、插入的數(shù)據(jù)結(jié)構(gòu)，來(lái)記錄關(guān)鍵詞及其出現(xiàn)的次數(shù)。

假設(shè)我們選用散列表。我們就順序掃描這 10 億個(gè)搜索關(guān)鍵詞。當(dāng)掃描到某個(gè)關(guān)鍵詞時(shí)，我們?nèi)ド⒘斜碇胁樵?。如果存在，我們就將?duì)應(yīng)的次數(shù)加一;如果不存在，我們就將它插入到散列表，并記錄次數(shù)為 1。以此類推，等遍歷完這 10 億個(gè)搜索關(guān)鍵詞之后，散列表中就存儲(chǔ)了不重復(fù)的搜索關(guān)鍵詞以及出現(xiàn)的次數(shù)。

然后，我們?cè)俑鶕?jù)前面講的用堆求 Top K 的方法，建立一個(gè)大小為 10 的小頂堆，遍歷散列表，依次取出每個(gè)搜索關(guān)鍵詞及對(duì)應(yīng)出現(xiàn)的次數(shù)，然后與堆頂?shù)乃阉麝P(guān)鍵詞對(duì)比。如果出現(xiàn)次數(shù)比堆頂搜索關(guān)鍵詞的次數(shù)多，那就刪除堆頂?shù)年P(guān)鍵詞，將這個(gè)出現(xiàn)次數(shù)更多的關(guān)鍵詞加入到堆中。

以此類推，當(dāng)遍歷完整個(gè)散列表中的搜索關(guān)鍵詞之后，堆中的搜索關(guān)鍵詞就是出現(xiàn)次數(shù)最多的 Top 10 搜索關(guān)鍵詞了。

不知道你發(fā)現(xiàn)了沒(méi)有，上面的解決思路其實(shí)存在漏洞。10 億的關(guān)鍵詞還是很多的。我們假設(shè) 10 億條搜索關(guān)鍵詞中不重復(fù)的有 1 億條，如果每個(gè)搜索關(guān)鍵詞的平均長(zhǎng)度是 50 個(gè)字節(jié)，那存儲(chǔ) 1 億個(gè)關(guān)鍵詞起碼需要 5GB 的內(nèi)存空間，而散列表因?yàn)橐苊忸l繁沖突，不會(huì)選擇太大的裝載因子，所以消耗的內(nèi)存空間就更多了。而我們的機(jī)器只有 1GB 的可用內(nèi)存空間，所以我們無(wú)法一次性將所有的搜索關(guān)鍵詞加入到內(nèi)存中。這個(gè)時(shí)候該怎么辦呢?

我們?cè)诠Ｋ惴且还?jié)講過(guò)，相同數(shù)據(jù)經(jīng)過(guò)哈希算法得到的哈希值是一樣的。我們可以哈希算法的這個(gè)特點(diǎn)，將 10 億條搜索關(guān)鍵詞先通過(guò)哈希算法分片到 10 個(gè)文件中。

具體可以這樣做：我們創(chuàng)建 10 個(gè)空文件 00，01，02，……，09。我們遍歷這 10 億個(gè)關(guān)鍵詞，并且通過(guò)某個(gè)哈希算法對(duì)其求哈希值，然后哈希值同 10 取模，得到的結(jié)果就是這個(gè)搜索關(guān)鍵詞應(yīng)該被分到的文件編號(hào)。

對(duì)這 10 億個(gè)關(guān)鍵詞分片之后，每個(gè)文件都只有 1 億的關(guān)鍵詞，去除掉重復(fù)的，可能就只有 1000 萬(wàn)個(gè)，每個(gè)關(guān)鍵詞平均 50 個(gè)字節(jié)，所以總的大小就是 500MB。1GB 的內(nèi)存完全可以放得下。

我們針對(duì)每個(gè)包含 1 億條搜索關(guān)鍵詞的文件，利用散列表和堆，分別求出 Top 10，然后把這個(gè) 10 個(gè) Top 10 放在一塊，然后取這 100 個(gè)關(guān)鍵詞中，出現(xiàn)次數(shù)最多的 10 個(gè)關(guān)鍵詞，這就是這 10 億數(shù)據(jù)中的 Top 10 最頻繁的搜索關(guān)鍵詞了。

內(nèi)容小結(jié)

我們今天主要講了堆的幾個(gè)重要的應(yīng)用，它們分別是：優(yōu)先級(jí)隊(duì)列、求 Top K 問(wèn)題和求中位數(shù)問(wèn)題。

優(yōu)先級(jí)隊(duì)列是一種特殊的隊(duì)列，優(yōu)先級(jí)高的數(shù)據(jù)先出隊(duì)，而不再像普通的隊(duì)列那樣，先進(jìn)先出。實(shí)際上，堆就可以看作優(yōu)先級(jí)隊(duì)列，只是稱謂不一樣罷了。求 Top K 問(wèn)題又可以分為針對(duì)靜態(tài)數(shù)據(jù)和針對(duì)動(dòng)態(tài)數(shù)據(jù)，只需要利用一個(gè)堆，就可以做到非常高效率的查詢 Top K 的數(shù)據(jù)。求中位數(shù)實(shí)際上還有很多變形，比如求 99 百分位數(shù)據(jù)、90 百分位數(shù)據(jù)等，處理的思路都是一樣的，即利用兩個(gè)堆，一個(gè)大頂堆，一個(gè)小頂堆，隨著數(shù)據(jù)的動(dòng)態(tài)添加，動(dòng)態(tài)調(diào)整兩個(gè)堆中的數(shù)據(jù)，最后大頂堆的堆頂元素就是要求的數(shù)據(jù)。