所謂海量數(shù)據(jù)處理，是指基于海量數(shù)據(jù)的存儲、處理或操作。因為數(shù)據(jù)量太大，導致要么無法在較短時間內迅速解決，要么無法一次性裝入內存。

事實上，對于時間問題，可以采用巧妙的算法搭配合適的數(shù)據(jù)結構（如布隆過濾器、散列、位圖、堆、數(shù)據(jù)庫、倒排索引、Trie 樹）來解決；對于空間問題，可以采取分而治之的方法（如利用散列映射），把規(guī)模大的數(shù)據(jù)轉化為規(guī)模小的，最終各個擊破。

處理海量數(shù)據(jù)問題有很多種方法，本文介紹5種典型方法：散列分治、多層劃分、位圖、布隆過濾器、Trie樹。

散列分治

方法介紹

對于海量數(shù)據(jù)而言，由于無法將其一次性裝進內存進行處理，不得不將其通過散列映射的方法分割成相應的小塊數(shù)據(jù)，然后再針對各個小塊數(shù)據(jù)通過hash_map進行統(tǒng)計或其他操作。

那么什么是散列映射呢？簡單來說，為了方便計算機在有限的內存中處理大量數(shù)據(jù)，通過映射的方式讓數(shù)據(jù)均勻分布在對應的內存位置上（例如，大數(shù)據(jù)通過取余的方式映射成小數(shù)據(jù)存放在內存中，或把大文件映射成多個小文件），而這種映射的方式通常通過散列函數(shù)進行映射，好的散列函數(shù)能讓數(shù)據(jù)均勻分布而減少沖突。

問題實例

尋找Top IP

從海量日志數(shù)據(jù)中提取出某日訪問百度（www.baidu.com）次數(shù)最多的那個IP。

分析： 百度作為國內第一大搜索引擎，每天訪問它的IP數(shù)量巨大，如果想一次性把所有IP數(shù)據(jù)裝進內存處理，內存容量通常不夠，故針對數(shù)據(jù)量太大、內存受限的情況，可以把大文件轉化成（取模映射）小文件，從而大而化小，逐個處理。簡言之，先映射，而后統(tǒng)計，最后排序。

解法： 具體分為下述三個步驟。

（1）分而治之/散列映射。先將該日訪問百度的所有IP從訪問日志中提取出來，然后逐個寫入一個大文件中，接著采取散列映射的方法（如hash(IP) % 1000），把整個大文件的數(shù)據(jù)映射到1000個小文件中2。

（2）hash_map統(tǒng)計。大文件轉化成了小文件，便可以采用hash_map(ip, value)分別對1000個小文件的IP進行頻率統(tǒng)計，找出每個小文件中出現(xiàn)頻率最高的IP，總共1000個IP。

（3）堆/快速排序。統(tǒng)計出1000個頻率最高的IP后，依據(jù)它們各自頻率的大小進行排序（可采取堆排序），找出最終那個出現(xiàn)頻率最高的IP，即為所求。

尋找熱門查詢

搜索引擎會通過日志文件把用戶每次檢索所使用的所有查詢串都記錄下來，每個查詢串的長度為1～255字節(jié)。假設目前有1000萬條查詢記錄（但是，因為這些查詢串的重復度比較高，所以雖然總數(shù)是 1000 萬，但如果除去重復后，查詢串query不超過300萬個），請統(tǒng)計其中最熱門的10個查詢串，要求使用的內存不能超過1 GB。

分析： 一個查詢串的重復度越高說明查詢它的用戶越多，也就是越熱門。如果是1億個IP求Top 10，可先%1000將IP分到1000個小文件中去，并保證一個IP只出現(xiàn)在一個文件中，再對每個小文件中的IP進行hash_map統(tǒng)計并按數(shù)量排序，最后用歸并或者最小堆依次處理每個小文件中的Top 10以得到最后的結果。

但是對于本題，是否也需要先把大文件弄成小文件呢？根據(jù)題目描述，雖然有1000萬個查詢，但是因為重復度比較高，去除重復后，事實上只有300萬個查詢，每個查詢?yōu)?55字節(jié)，所以可以考慮把它們全部放進內存中去（假設300萬個字符串沒有重復，都是最大長度，那么最多占用內存3000000 × 255 = 765MB=0.765GB，所以可以將所有字符串都存放在內存中進行處理）。

考慮到本題中的數(shù)據(jù)規(guī)模比較小，能一次性裝入內存，因而放棄分而治之/散列映射的步驟，直接用hash_map統(tǒng)計，然后排序。事實上，針對此類典型的Top k問題，采取的對策一般都是“分而治之/散列映射（如有必要）+ hash_map+堆”。

解法：

（1）hash_map統(tǒng)計。對這批海量數(shù)據(jù)進行預處理，用hash_map完成頻率統(tǒng)計。具體做法是：維護一個鍵為query、value為該query出現(xiàn)次數(shù)的hash_map，即hash_map(query, value)，每次讀取一個query，如果該query不在hash_map中，那么將該query放入hash_map中，并將它的value值設為1；如果該query在hash_map中，那么將該query的計數(shù)value加1即可。最終我們用hash_map在O(n)的時間復雜度內完成了所有query的頻率統(tǒng)計。

（2）堆排序。借助堆這種數(shù)據(jù)結構，找出Top k，時間復雜度為O(n'logk)。也就是說，借助堆可以在對數(shù)級的時間內查找或調整移動。因此，維護一個k（該題目中是10）大小的最小堆，然后遍歷300萬個query，分別和根元素進行比較，最終的時間復雜度是O(n) + O(n'logk)，其中n為1000萬，n'為300萬。

關于上述過程中的第2步（堆排序），進一步講，可以維護k個元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個數(shù)，并假設它們就是最大的k個數(shù)，建堆費時O(k)，有k1 > k2 >…> kmin（設kmin為最小堆中最小元素）。繼續(xù)遍歷整個數(shù)列剩下的n?k個元素，每次遍歷一個元素x，將其與堆頂元素進行比較，若x > kmin則更新堆（x入堆，每次調整堆費時O(log k)），否則不更新堆。這樣下來，總費時O(k + (n?k)log k ) = O(nlogk)。此方法得益于在堆中查找等各項操作的時間復雜度均為O(log k)。

當然，也可以采用Trie樹，結點里存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)則為0，最后用10個元素的最小堆來對出現(xiàn)頻率進行排序。

尋找出現(xiàn)頻率最高的100個詞

有一個1 GB大小的文件，里面每一行是一個詞，每個詞的大小不超過16字節(jié)，內存大小限制是1 MB。請返回出現(xiàn)頻率最高的100個詞。

解法：

（1）分而治之/散列映射。按先后順序讀取文件，對于每個詞x，執(zhí)行hash(x)%5000，然后將該值存到5000個小文件（記為x0, x1,…, x4999）中。此時，每個小文件的大小大概是200 KB。當然，如果其中有的小文件超過了1 MB，則可以按照類似的方法繼續(xù)往下分，直到分解得到的所有小文件都不超過1MB。

（2）hash_map統(tǒng)計。對每個小文件采用hash_map/Trie樹等數(shù)據(jù)結構，統(tǒng)計每個小文件中出現(xiàn)的詞及其相應的出現(xiàn)次數(shù)。

（3）堆排序或者歸并排序。取出出現(xiàn)次數(shù)最多的100個詞（可以用含100個結點的最小堆）后，再把100個詞及相應的出現(xiàn)次數(shù)存入文件中，這樣又得到5000個文件。最后對這5000個文件進行歸并（可以用歸并排序）。

尋找Top 10

有海量數(shù)據(jù)分布在100臺電腦中，請想個辦法高效統(tǒng)計出這批數(shù)據(jù)出現(xiàn)次數(shù)最多的Top 10。

解法一： 如果同一個數(shù)據(jù)元素只出現(xiàn)在某一臺機器中，那么可以采取以下步驟統(tǒng)計出現(xiàn)次數(shù)為Top 10的數(shù)據(jù)元素。

（1）堆排序。在每臺電腦上求出Top 10，可以采用包含10個元素的堆完成。（求Top 10小用最大堆，求Top 10大用最小堆。比如，求Top 10大，首先取前10個元素調整成最小堆，假設這10個元素就是Top 10大，然后掃描后面的數(shù)據(jù)，并與堆頂元素進行比較，如果比堆頂元素大，那么用該元素替換堆頂，然后再調整為最小堆，否則不調整。最后堆中的元素就是Top 10大。）

（2）組合歸并。求出每臺電腦上的Top 10后，把這100臺電腦上的Top 10組合起來，共1000個數(shù)據(jù)，再根據(jù)這1000個數(shù)據(jù)求出Top 10就可以了。

解法二： 但是，如果同一個元素重復出現(xiàn)在不同的電腦中呢？舉個例子，給定兩臺機器，第一臺機器的數(shù)據(jù)及各自出現(xiàn)的次數(shù)為a（53）、b（52）、c（49）、d（49）、e（0）、f（0）（括號里的數(shù)字代表某個數(shù)據(jù)出現(xiàn)的次數(shù)），第二臺機器的數(shù)據(jù)及各自出現(xiàn)的次數(shù)為a（0）、b（0）、c（49）、d（49）、e（51）、f（50），求所有數(shù)據(jù)中出現(xiàn)次數(shù)最多的Top 2。

很明顯，如果先求出第一臺機器的Top 2——a（53）和b（52），然后再求出第二臺機器的Top 2——e（51）和f（50），最后歸并a（53）、b（52）、e（51）和f（50），得出最終的Top 2——a（53）和b（52）并非實際的Top 2，因為實際的Top 2是c（49 + 49）和d（49 + 49）。

有兩種方法可以解決這個問題。

• 遍歷一遍所有數(shù)據(jù)，重新散列取模，使同一個元素只出現(xiàn)在單獨的一臺電腦中，然后采取上面所說的方法，統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)，找出Top 10，繼而組合100臺電腦上的Top 10，找出最終的Top 10。

• 蠻力求解，直接統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)，然后把同一個元素在不同機器中的出現(xiàn)次數(shù)相加，最終從所有數(shù)據(jù)中找出Top 10。

查詢串的重新排列

有10個文件，每個文件的大小是1 GB，每個文件的每一行存放的都是用戶的查詢串query，每個文件的query都可能重復。請按照query的頻度排序。

解法一： 分為以下三個步驟。

（1）散列映射。順序讀取10個文件，按照hash(query)%10的結果將query寫入另外10個文件（記為a0, a1,…, a9）中。這樣，新生成的每個文件的大小約為1 GB（假設散列函數(shù)是隨機的）。

（2）hash_map統(tǒng)計。找一臺內存在2 GB左右的機器，依次用hash_map(query, query_count)來統(tǒng)計每個query出現(xiàn)的次數(shù)。注意，hash_map(query, query_count)是用來統(tǒng)計每個 query 的出現(xiàn)次數(shù)的，而不是存儲它們的值，query 出現(xiàn)一次則query_count+1。

（3）堆排序、快速排序或者歸并排序。利用快速排序、堆排序或者歸并排序按照出現(xiàn)次數(shù)進行排序，將排好序的query和對應的query_cout輸出到文件中。這樣就得到了10個排好序的文件（記為b0, b1,…, b9）。最后，對這10個文件進行歸并排序（內排序與外排序相結合）。

解法二： 一般情況下，query的總量是有限的，只是重復的次數(shù)比較多而已，對于所有的query，可能一次性就可以加入內存。這樣就可以采用Trie樹、hash_map等直接統(tǒng)計每個query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速排序、堆排序或者歸并排序就可以了。

解法三： 與解法一類似，但在做完散列，分成多個文件后，可以交給多個文件，采用分布式架構來處理（如MapReduce），最后再進行合并。

尋找共同的URL

給定a和b兩個文件，各存放50億個URL，每個URL占64字節(jié)，內存限制是4 GB。請找出a和b文件中共同的URL。

解法： 可以估計出每個文件的大小為5000000000×64=320 GB，遠遠大于內存限制的4 GB，所以不可能將其完全加載到內存中處理?？紤]采取分而治之的方法。

（1）分而治之/散列映射。遍歷文件a，對每個URL求取hash(URL)%1000，然后根據(jù)所取得的值將URL分別存儲到1000個小文件中（記為 a0, a1,…, a999）。這樣每個小文件大約為300 MB。遍歷文件b，采取和a相同的方式將URL分別存儲到1000小文件中（記為b0, b1,…, b999）。這樣處理后，所有可能相同的URL都在對應的小文件中（a0對應b0, a1對應b1,…, a999對應b999），不對應的小文件不可能有相同的URL。然后只要求出1000對小文件中相同的URL即可。

（2）hash_set統(tǒng)計。求每對小文件中相同的URL時，可以把其中一個小文件的URL存儲到hash_set中，然后遍歷另一個小文件的每個URL，看其是否在剛才構建的hash_set中，如果在，就是共同的URL，保存到文件里就可以了。

舉一反三

尋找最大的100個數(shù)

從100萬個數(shù)中找出最大的100個數(shù)。

提示：

選取前100個元素并排序，記為序列L。然后依次掃描剩余的元素x，與排好序的100個元素中最小的元素比較，如果比這個最小的元素大，就把這個最小的元素刪除，利用插入排序的思想將x插入到序列L中。依次循環(huán)，直到掃描完所有的元素。復雜度為O(108×100)。也可以利用快速排序的思想，每次分割之后只考慮比主元大的一部分，直到比主元大的一部分比100多的時候，采用傳統(tǒng)排序算法排序，取前100個。復雜度為O(108× 100)。此外，還可以用一個含100個元素的最小堆來完成，復雜度為O(108× log100)。

統(tǒng)計10個出現(xiàn)次數(shù)最多的詞

一個文本文件有上億行甚至10億行，每行中存放一個詞，要求統(tǒng)計出其中出現(xiàn)次數(shù)最多的前10個詞。

解法一： 如果文件比較大，無法一次性讀入內存，可以采用散列取模的方法，將大文件分解為多個小文件，對單個小文件利用hash_map統(tǒng)計出每個小文件中10個出現(xiàn)次數(shù)最多的詞，然后再進行歸并處理，找出最終的10個出現(xiàn)次數(shù)最多的詞。

解法二： 通過散列取模將大文件分解為多個小文件后，除了可以用hash_map統(tǒng)計出每個小文件中10個出現(xiàn)次數(shù)的詞，也可以用Trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，最終同樣找出出現(xiàn)次數(shù)最多的前10個詞（可用堆來實現(xiàn)）。

尋找出現(xiàn)次數(shù)最多的數(shù)

怎樣在海量數(shù)據(jù)中找出重復次數(shù)最多的一個？

提示：

先做散列，然后求模，映射為小文件，求出每個小文件中重復次數(shù)最多的一個數(shù)，并記錄重復次數(shù)，最后找出上一步求出的數(shù)據(jù)中重復次數(shù)最多的一個，即是所求。

統(tǒng)計出現(xiàn)次數(shù)最多的前n個數(shù)據(jù)

有上千萬或上億個數(shù)據(jù)（有重復），統(tǒng)計其中出現(xiàn)次數(shù)最多的前n個數(shù)據(jù)。

提示：

上千萬或上億個數(shù)據(jù)在現(xiàn)在的機器的內存中應該能存下，所以考慮采用hash_map、搜索二叉樹、紅黑樹等來進行次數(shù)統(tǒng)計，然后取出前n個出現(xiàn)次數(shù)最多的數(shù)據(jù)，這一步可以用堆完成。

1000萬個字符串的去重

有1000萬個字符串，其中有些字符串是重復的，請把重復的字符串全部去掉，保留沒有重復的字符串。

提示：

本題用Trie樹比較合適，hash_map也行。當然，也可以先散列成小文件分開處理再綜合。

多層劃分

方法介紹

多層劃分法本質上還是遵循分而治之的思想。因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后在一個可以接受的范圍內進行查找。

問題實例

尋找不重復的數(shù)

在2.5億個整數(shù)中找出不重復的整數(shù)的個數(shù)。注意，內存空間不足以容納這2.5億個整數(shù)。

分析： 類似于鴿巢原理，因為整數(shù)個數(shù)為232，所以，可以將這232個數(shù)劃分為28個區(qū)域（比如，用一個文件代表一個區(qū)域），然后將數(shù)據(jù)分到不同的區(qū)域，最后不同的區(qū)域再利用位圖進行統(tǒng)計就可以直接解決了。也就是說，只要有足夠的內存空間，就可以很方便地解決。

尋找中位數(shù)

找出5億個int型數(shù)的中位數(shù)。

分析： 首先將這5億個int型數(shù)劃分為216個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，根據(jù)統(tǒng)計結果就可以判斷中位數(shù)落到哪個區(qū)域，并知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后，第二次掃描只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。

實際上，如果不是int型而是int64型，經過3次這樣的劃分即可降低到能夠接受的程度。也就是說，可以先將5億個int64型數(shù)劃分為224個區(qū)域，確定每個數(shù)是其所在區(qū)域的第幾大數(shù)，然后再將該區(qū)域分成220個子區(qū)域，確定是子區(qū)域的第幾大數(shù)，最后當子區(qū)域里的數(shù)的個數(shù)只有220個時，就可以利用直接尋址表進行統(tǒng)計。

6.4　MapReduce

方法介紹

MapReduce是一種計算模型，簡單地說就是將大批量的工作或數(shù)據(jù)分解執(zhí)行（稱之為Map），然后再將結果合并成最終結果（稱之為Reduce）。這樣做的好處是，可以在任務被分解后通過大量機器進行分布式并行計算，減少整個操作的時間?？梢哉f，MapReduce的原理就是一個歸并排序，它的適用范圍為數(shù)據(jù)量大而數(shù)據(jù)種類少以致可以放入內存的場景。MapReduce模式的主要思想是將要執(zhí)行的問題（如程序）自動拆分成Map和Reduce的方式，其流程如圖6-2所示。

在數(shù)據(jù)被分割后，通過Map函數(shù)將數(shù)據(jù)映射到不同的區(qū)塊，分配給計算機集群處理，以達到分布式計算的效果，再通過Reduce函數(shù)的程序將結果匯總，從而輸出需要的結果。

MapReduce 借鑒了函數(shù)式程序設計語言的設計思想，其軟件實現(xiàn)是指定一個Map函數(shù)，把鍵值對映射成新的鍵值對，形成一系列中間結果構成的鍵值對，然后把它們傳給 Reduce 函數(shù)，把具有相同中間形式的鍵值對合并在一起。Map 函數(shù)和Reduce函數(shù)具有一定的關聯(lián)性。

問題實例

尋找n2個數(shù)的中數(shù)

一共有n臺機器，每臺機器上有n個數(shù)，每臺機器最多存O(n)個數(shù)并對它們進行操作。如何找到n2個數(shù)的中數(shù)（median）？

6.5　外排序

方法介紹

顧名思義，所謂外排序就是在內存外面的排序。當要處理的數(shù)據(jù)量很大而不能一次性裝入內存時，只能將數(shù)據(jù)放在讀寫較慢的外存儲器（通常是硬盤）上。

外排序通常采用的是一種“排序-歸并”的策略。在排序階段，先讀入能放在內存中的數(shù)據(jù)，將其排序后輸出到一個臨時文件，依次進行，將待排序數(shù)據(jù)組織為多個有序的臨時文件，而后在歸并階段將這些臨時文件組合為一個大的有序文件，即為排序結果。

舉個例子。假定現(xiàn)在有一個含有20個數(shù)據(jù){5, 11, 0, 18, 4, 14, 9, 7, 6, 8, 12, 17, 16, 13, 19, 10, 2, 1, 3, 15}的文件A，但使用的是一次只能裝4個數(shù)據(jù)的內存，所以可以每趟對4個數(shù)據(jù)進行排序，即5路歸并，具體方法如下述步驟所示。

首先把“大”文件A分割為a1、a2、a3、a4、a5這5個小文件，每個小文件包含4個數(shù)據(jù)：

• a1文件的內容為{5, 11, 0, 18}；

• a2文件的內容為{4, 14, 9, 7}；

• a3文件的內容為{6, 8, 12, 17}；

• a4文件的內容為{16, 13, 19, 10}；

• a5文件的內容為{2, 1, 3, 15}。

然后依次對5個小文件進行排序：

• a1文件完成排序后的內容為{0, 5, 11, 18}；

• a2文件完成排序后的內容為{4, 7, 9, 14}；

• a3文件完成排序后的內容為{6, 8, 12, 17}；

• a4文件完成排序后的內容為{10, 13, 16, 19}；

• a5文件完成排序后的內容為{1, 2, 3, 15}。

最終進行多路歸并，完成整個排序。最后，整個大文件A文件完成排序后變?yōu)閧0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}。

問題實例

給107個數(shù)據(jù)的磁盤文件排序

給定一個文件，里面最多含有n個不重復的正整數(shù)（也就是說可能含有少于n個不重復的正整數(shù)），且其中每個數(shù)都小于等于n（n = 107）。請輸出一個按從小到大升序排列的包含所有輸入整數(shù)的列表。假設最多有大約1 MB的內存空間可用，但磁盤空間足夠。要求運行時間在5分鐘以內，10秒為最佳結果。

解法一：位圖方案

你可能會想到把磁盤文件進行歸并排序，但題目假設只有1 MB的內存空間可用，所以歸并排序這種方法不行。

熟悉位圖的人可能會想到用位圖來表示這個文件集合3。比如，用一個20位長的字符串來表示一個所有元素都小于20的簡單的非負整數(shù)集合，如集合{1, 2, 3, 5, 8, 13}，在字符串中將集合中各個數(shù)對應的位置置為1，沒有對應的數(shù)的位置置為0，用字符串表示為01110100100001000000。

針對本題的107個數(shù)據(jù)的磁盤文件排序問題，可以這么考慮：由于每個7位十進制整數(shù)表示一個小于1000萬的整數(shù)，所以可以使用一個具有1000萬個位的字符串來表示這個文件，當且僅當整數(shù)i在文件中存在時，字符串中的第i位置為1。

采取這個位圖的方案是因為考慮到本問題的特殊性：

• 輸入數(shù)據(jù)限制在相對較小的范圍內；

• 數(shù)據(jù)沒有重復；

• 其中的每條記錄都是單一的整數(shù)，沒有任何其他與之關聯(lián)的數(shù)據(jù)。

所以，此問題用位圖的方案可以分為以下三步進行解決。

（1）將所有的位都初始化為0。

（2）通過讀入文件中的每個整數(shù)來建立集合，將每個整數(shù)對應的位都置為1。

（3）檢驗每一位，如果該位為1，就輸出對應的整數(shù)。

經過以上三步后，就產生了一個有序的輸出文件。令n為位圖向量中的位數(shù)（本例中為10 000 000），偽代碼表示如下：

// 磁盤文件排序位圖方案的偽代碼 // 第一步：將所有的位都初始化為0  for i ={0,....n}　　  
　　 bit[i]=0;  
// 第二步：通過讀入文件中的每個整數(shù)來建立集合，將每個整數(shù)對應的位都置為1for each i in the input file　　 
　　 bit[i]=1;  
// 第三步：檢驗每一位，如果該位為1，就輸出對應的整數(shù)  for i={0...n}　　  
　　 if bit[i]==1　　　　
　　　　 write i on the output file

上述的位圖方案共需要掃描輸入數(shù)據(jù)兩次，具體執(zhí)行步驟如下。

（1）第一次只處理1～5 000 000的數(shù)據(jù)，這些數(shù)都是小于5 000 000的。對這些數(shù)進行位圖排序，只需要約5 000 000/8=625 000字節(jié)，即0.625 MB，排序后輸出。

（2）第二次掃描輸入文件時，只處理5 000 001～10 000 000的數(shù)據(jù)，也只需要0.625 MB（可以使用第一次處理申請的內存）。因此，這種位圖的方法總共只需要0.625 MB。

但是，很快我們就意識到，用位圖方案的話，需要約1.2 MB（若每條記錄是8位的正整數(shù)，則空間消耗約等于107/(102410248)≈ 192 MB）的空間，而現(xiàn)在只有1 MB的可用存儲空間，所以嚴格來說，用位圖方法還是不行4。那么究竟該如何處理呢？

解法二：多路歸并

誠然，在面對本題時，通過計算分析出可以用上述解法一這樣的位圖法解決。但實際上，很多時候我們都面臨著這樣一個問題：文件太大，無法一次性放入內存中計算處理。這時候應該怎么辦呢？分而治之，大而化小，也就是把整個大文件分為若干大小的幾塊，然后分別對每一塊進行排序，最后完成整個過程的排序。k趟算法可以在O(kn)的時間開銷內和O(n/k)的空間開銷內完成對最多n個小于n的無重復正整數(shù)的排序。比如，可分為2塊（k=2時，一趟反正占用的內存只有1.25/2 MB），即1～5 000 000和5 000 001～10 000 000。先遍歷一趟，排序處理1～5 000 000的整數(shù)（用5 000 000/8=625 000字節(jié)的存儲空間來排序1～5 000 000的整數(shù)），然后再第二趟，對5 000 001～1 000 000的整數(shù)進行排序處理。

解法總結

本節(jié)中位圖和多路歸并兩種方案的時間復雜度及空間復雜度的比較如表6-1所示。

表6-1

多路歸并的時間復雜度為O(k × n/k × log n/k) = O(nlogn)5。但嚴格來說，還要加上讀寫磁盤的時間，而此算法的絕大部分時間也正是浪費在讀寫磁盤的步驟上。

位圖

方法介紹

什么是位圖

所謂位圖，就是用一個位（bit）來標記某個元素對應的值，而鍵就是該元素。由于采用了位為單位來存儲數(shù)據(jù)，因此可以大大節(jié)省存儲空間。

位圖通過使用位數(shù)組來表示某些元素是否存在，可進行數(shù)據(jù)的快速查找、判重、刪除。

來看一個具體的例子。假設我們要對0～7中的5個元素（4, 7, 2, 5, 3）進行排序（假設這些元素沒有重復），此時就可以采用位圖的方法來達到排序的目的。因為要表示8個數(shù)，所以只需要8位，由于8位等于1字節(jié)，所以開辟1字節(jié)的空間，并將這個空間的所有位都置為0，如圖6-3所示。

然后遍歷這5個元素。因為待排序序列的第一個元素是4，所以把4對應的位重置為1（可以這樣操作：p + (i/8) | (001 << (i % 8)) 。當然，這里的操作涉及big-endian和little-endian6的情況，這里默認為big-endian），又由于是從0開始計數(shù)的，所以把第5位重置為1，如圖6-4所示。

然后再處理待排序序列的第二個元素7，將第8個位重置為1。接著再處理待排序序列的第三個元素2，一直到處理完所有的元素。將相應的位置為1后，這時候內存的位的狀態(tài)如圖6-5所示。

現(xiàn)在遍歷一遍這個位區(qū)域，將某位是1的位的編號（2, 3, 4, 5, 7）輸出，這樣就達到了排序的目的。

問題實例

電話號碼的統(tǒng)計

已知某個文件內包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。8位數(shù)字最多組成99 999 999個號碼，大概需要99兆位，大概十幾兆字節(jié)的內存即可。

2.5億個整數(shù)的去重

在2.5億個整數(shù)中找出不重復的整數(shù)。注意，內存不足以容納這2.5億個整數(shù)。

分析： 采用2位圖（每個數(shù)分配2位，00表示不存在，01表示出現(xiàn)一次，10表示出現(xiàn)多次，11無意義），共需內存232 × 2=1 GB內存，可以接受。然后掃描這2.5億個整數(shù)，查看位圖中相對應的位，如果是00就變?yōu)?1，如果是01就變?yōu)?0，如果是10就保持不變。掃描完之后，查看位圖，把對應位是01的整數(shù)輸出即可。也可以先劃分成小文件，然后在小文件中找出不重復的整數(shù)，并排序，最后歸并，歸并的同時去除重復的數(shù)。

整數(shù)的快速查詢

給定40億個不重復的沒排過序的unsigned int型整數(shù)，然后再給定一個數(shù)，如何快速判斷這個數(shù)是否在這40億個整數(shù)當中？

分析： 可以用位圖的方法，申請512 MB的內存，一個位代表一個unsigned int型的值。讀入40億個數(shù)，設置相應的位，讀入要查詢的數(shù)，查看相應位是否為1，如果為1表示存在，如果為0表示不存在。

布隆過濾器

方法介紹

我們經常會遇到這樣的問題：判斷一個元素是否在一個集合中。常見的做法是用散列表實現(xiàn)集合，然后遇到一個新的元素時，在散列表中查找：如果能找到則意味著存在于集合中，反之不存在。但是散列表有一個弊端，它耗費的空間太大。本節(jié)來看一種新的方法，即布隆過濾器（Bloom filter）。

布隆過濾器是一種空間效率很高的隨機數(shù)據(jù)結構，它可以看成是對位圖的擴展。其結構是長度為n（如何計算最優(yōu)n，后面會給出）的位數(shù)組，初始化為全0。當一個元素被加入集合中時，通過k個散列函數(shù)將這個元素映射成一個位數(shù)組中的k個點，并將這k個點全部置為1。

在檢索一個元素是否在一個集合中時，我們只要看看這個元素被映射成位陣列的k個點是不是都是1，就能大致判斷出集合中有沒有那個元素：如果這k個點中有任何一個點為0，則被檢索元素在集合中一定不存在；如果這k個點都是1，則被檢索元素很可能在集合中。

但是，布隆過濾器也有它的缺點或不足，即它有一定的誤判率——在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤判為屬于這個集合。因此，它不適合那些“零誤判”的應用場合。而在能容忍低誤判率的應用場合下，布隆過濾器通過極少的誤判換取了存儲空間的極大節(jié)省。

集合表示和元素查詢

下面我們來具體看看布隆過濾器是如何用位數(shù)組表示集合的。如圖6-6所示，初始狀態(tài)時，布隆過濾器是一個包含m位的位數(shù)組，每一位都置為0。

對于S={x1, x2,…, xn}這樣一個n個元素的集合，布隆過濾器使用k個互相獨立的散列函數(shù)分別將集合S={x1, x2,…, xn}中的每個元素映射到{1,…, m}的范圍中。對于任意一個元素x，第i個散列函數(shù)映射的位置hi(x)就會被置為1（1≤i≤k）。

注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在圖6-7中，k=3且有兩個散列函數(shù)選中同一個位置（從左邊數(shù)第五位，即第二個1處）。

于此，在判斷y是否屬于圖6-6所示的集合S={x1, x2, …, xn}時，對y應用k次散列函數(shù)，如果所有hi(y)的位置都是1（1≤i≤k），那么就認為y是集合S={x1, x2, …, xn}中的元素，否則就認為y不是集合中的元素。

例如，圖6-8中的y1可以確定不是集合S={x1, x2, …, xn}中的元素，因為y1有兩處指向了0位，而y2可能屬于這個集合，也可能剛好是一個誤判。

誤判率估計

前面已經提到，布隆過濾器在判斷一個元素是否屬于它表示的集合時會有一定的誤判率（false positive rate），下面就來估計一下這個誤判率的大小。

為了簡化模型，假設kn < m且各個散列函數(shù)是完全隨機的。每插入一個新元素第一個散列函數(shù)就會把過濾器中的某個位置為1，因此任意一個位被置成1的概率為1/m，反之，它沒被置為1（依然是0）的概率為1?1/m。如果這個元素的k個散列函數(shù)都沒有把某個位置為1，即在做完k次散列后，某個位還是0（意味著k次散列都沒有選中它）的概率就是(1?1/m)k。如果插入第二個元素，某個位依然沒有被置為1的概率為(1?1/m)2k，所以如果插入n個元素都還沒有把某個位置為1的概率為(1?1/m)kn。

也就是說，當集合S = {x1, x2, …, xn}中的所有元素都被k個散列函數(shù)映射到m位的位數(shù)組中時，這個位數(shù)組中某一位還是0的概率是

為了簡化運算，可以令

，則有

如果令

為位數(shù)組中0的比例，則

的數(shù)學期望

。

在

已知的情況下，誤判率為

為位數(shù)組中1的比例，

表示k次散列都剛好選中1的區(qū)域，即誤判率。上式中的第二步近似在前面已經提到了，現(xiàn)在來看第一步近似。p'只是

的數(shù)學期望，在實際中

的值有可能偏離它的數(shù)學期望值。M. Mitzenmacher已經證明，位數(shù)組中0的比例非常集中地分布在它的數(shù)學期望值的附近。因此，第一步近似得以成立。分別將p和p'代入上式中，得

與p'和f ' 相比，使用p 和f 通常在分析中更為方便。

最優(yōu)的散列函數(shù)個數(shù)

既然布隆過濾器要靠多個散列函數(shù)將集合映射到位數(shù)組中，那么應該選擇幾個散列函數(shù)才能使元素查詢時的誤判率降到最低呢？這里有兩個互斥的理由：如果散列函數(shù)的個數(shù)多，那么在對一個不屬于集合的元素進行查詢時得到0的概率就大；但是，如果散列函數(shù)的個數(shù)少，那么位數(shù)組中的0就多。為了得到最優(yōu)的散列函數(shù)個數(shù)，我們需要根據(jù)上一節(jié)中的誤判率公式進行計算。

先用p 和f 進行計算。注意到f = exp(k ln(1?ekn/m))，我們令g = k ln(1?ekn/m)，只要讓g取到最小，f 自然也取到最小。由于p = e?kn/m，可以將g寫成

根據(jù)對稱性法則可以很容易看出：當p = 1/2，也就是k = (m/n)ln2≈0.693m/n時，g取得最小值。在這種情況下，最小誤判率f等于(1/2)k≈(0.6185)m/n。另外，注意到p是位數(shù)組中某一位仍是0的概率，所以p = 1/2對應著位數(shù)組中0和1各一半。換句話說，要想保持誤判率低，最好讓位數(shù)組有一半還空著。

需要強調的一點是，p = 1/2時誤判率最小這個結果并不依賴于近似值p和f。同樣，對于f' = exp(k ln(1?(1?1/m)kn))，g' = k ln(1?(1?1/m)kn)，p' = (1?1/m)kn，可以將g'寫成

同樣，根據(jù)對稱性法則可以得到當p' = 1/2時，g'取得最小值。

位數(shù)組的大小

下面來看看在不超過一定誤判率的情況下，布隆過濾器至少需要多少位才能表示全集中任意n個元素的集合。假設全集中共有u個元素，允許的最大誤判率為?，下面來求位數(shù)組的位數(shù)m。

假設X為全集中任取n個元素的集合，F(xiàn)(X)是表示X的位數(shù)組。那么，對于集合X中任意一個元素x，在s = F(X)中查詢x都能得到肯定的結果，即s能夠接受x。顯然，由于布隆過濾器引入了誤判，s能夠接受的不僅僅是X中的元素，它還能夠接受?(u?n)個誤判。因此，對于一個確定的位數(shù)組來說，它能夠接受總共n +? (u?n)個元素。在n +? (u?n)個元素中，s真正表示的只有其中n個，所以一個確定的位數(shù)組可以表示

個集合。m位的位數(shù)組共有2m個不同的組合，進而可以推出，m位的位數(shù)組可以表示

個集合。全集中n個元素的集合總共有

個，因此要讓m位的位數(shù)組能夠表示所有n個元素的集合，必須有

即

上式中的近似前提是n和?u相比很小，這也是實際情況中常常發(fā)生的。根據(jù)上式，我們得出結論：在誤判率不大于?的情況下，m至少要等于n log2(1/?)才能表示任意n個元素的集合。

上一節(jié)中我們曾算出當k = m/n ln2時誤判率f最小，這時f = (1/2)k= (1/2)mln2 / n?，F(xiàn)在令f ≤?，可以推出

這個結果比前面算得的下界n log2(1/)大了log2≈1.44倍。這說明，在散列函數(shù)的個數(shù)取到最優(yōu)時，要讓誤判率不超過?，m至少需要取到最小值的1.44倍。

布隆過濾器可以用來實現(xiàn)數(shù)據(jù)字典，進行數(shù)據(jù)的判重或者集合求交集。

問題實例

尋找通過URL

給定A和B兩個文件，各存放50億條URL，每條URL占用64字節(jié)，內存限制是4 GB，請找出A和B兩個文件中共同的URL。

分析： 如果允許有一定的誤判率，可以使用布隆過濾器，4 GB內存大概可以表示340億位。將其中一個文件中的URL使用布隆過濾器映射到這340億位，然后挨個讀取另外一個文件中的URL，檢查這兩個URL是否相同，如果是，那么該URL應該是共同的URL。如果是3個乃至n個文件呢？讀者可以繼續(xù)獨立思考。

垃圾郵件過濾

用過電子郵箱的朋友都知道，經常會收到各種垃圾郵件，可能是廣告，可能是病毒，所以郵件提供商每天都需要過濾數(shù)以幾十億計的垃圾郵件，請想一個辦法過濾這些垃圾郵件。

分析： 比較直觀的想法是把常見的垃圾郵件地址存到一個巨大的集合中，然后遇到某個新郵件就將它的地址和集合中的全部垃圾郵件地址一一進行比較，如果有元素與之匹配，則判定新郵件為垃圾郵件。

雖然本節(jié)開始部分提到集合可以用散列表實現(xiàn)，但它太占空間。例如，存儲1億個電子郵件地址就需要1.6 GB內存，存儲幾十億個電子郵件地址就需要上百GB的內存，雖然現(xiàn)在有的機器內存達到了上百GB，但終究是少數(shù)。

事實上，如果允許一定的誤判率的話，可以使用布隆過濾器。解決了存儲的問題后，可以利用貝葉斯分類鑒別一份郵件是否為垃圾郵件，減少誤判率。

Trie樹

方法介紹

什么是Trie樹

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，常用于統(tǒng)計和排序大量字符串等場景中（但不僅限于字符串），且經常被搜索引擎用于文本詞頻統(tǒng)計。它的優(yōu)點是最大限度地減少無謂的字符串比較，查詢效率比較高。

Trie樹的核心思想是以空間換時間，利用字符串的公共前綴來降低查詢時間的開銷，以達到提高效率的目的。

它有以下三個基本性質。

（1）根結點不包含字符，除根結點外每一個結點都只包含一個字符。

（2）從根結點到某一結點的路徑上經過的字符連接起來，即為該結點對應的字符串。

（3）每個結點的所有子結點包含的字符都不相同。

Trie樹的構建

先來看一個問題：假如現(xiàn)在給定10萬個長度不超過10個字母的單詞，對于每一個單詞，要判斷它出沒出現(xiàn)過，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個位置。這個問題該怎么解決呢？

如果采取最笨拙的方法，對每一個單詞都去查找它前面的單詞中是否有它，那么這個算法的復雜度就是O(n2)。顯然對于10萬的范圍難以接受。

換個思路想：假設要查詢的單詞是abcd，那么在它前面的單詞中，以b，c，d，f之類開頭的顯然就不必考慮了，而只要找以a開頭的單詞中是否存在abcd就可以了。同樣，在以a開頭的單詞中，只要考慮以b作為第二個字母的，一次次縮小范圍和提高針對性，這樣一個樹的模型就漸漸清晰了。

因此，如果現(xiàn)在有b、abc、abd、bcd、abcd、efg和hii這6個單詞，可以構建一棵圖6-9所示的Trie樹。

如圖6-9所示，從根結點遍歷到每一個結點的路徑就是一個單詞，如果某個結點被標記為紅色（如圖中加黑點的節(jié)點），就表示這個單詞存在，否則不存在。那么，對于一個單詞，只要順著它從根結點走到對應的結點，再看這個結點是否被標記為紅色就可以知道它是否出現(xiàn)過了。把這個結點標記為紅色，就相當于插入了這個單詞。這樣一來，查詢和插入可以一起完成，所用時間僅僅為單詞長度（在這個例子中，便是10）。這就是一棵Trie樹。

我們可以看到，Trie樹每一層的結點數(shù)是26i級別的。所以，為了節(jié)省空間，還可以用動態(tài)鏈表，或者用數(shù)組來模擬動態(tài)，而空間的花費不會超過單詞數(shù)乘以單詞長度。

查詢

Trie 樹是簡單且實用的數(shù)據(jù)結構，通常用于實現(xiàn)字典查詢。我們做即時響應用戶輸入的Ajax搜索框時，就是以Trie樹為基礎數(shù)據(jù)結構的。本質上，Trie樹是一棵存儲多個字符串的樹。相鄰結點間的邊代表一個字符，這樣樹的每條分支代表一個子串，而樹的葉結點則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。

下面再舉一個例子。給出一組單詞inn、int、ate、age、adv、ant，可以得到圖6-10所示的Trie樹。

可以看出以下幾條。

• 每條邊對應一個字母。

• 每個結點對應一項前綴。葉結點對應最長前綴，即單詞本身。

• 單詞inn與單詞int有共同的前綴'in'，所以它們共享左邊的一條分支（根結點→i→in）。同理，ate、age、adv和ant共享前綴'a'，所以它們共享從根結點到結點a的邊。

查詢操縱非常簡單。例如，要查找int，順著路徑i→ in→int就找到了。

搭建Trie的基本算法也很簡單，無非是逐一把每個單詞的每個字母插入Trie樹。插入前先看前綴是否存在：如果存在，就共享，否則創(chuàng)建對應的結點和邊。例如，要插入單詞add，就有下面幾步。

（1）考察前綴'a'，發(fā)現(xiàn)邊a已經存在。于是順著邊a走到結點a。

（2）考察剩下的字符串'dd'的前綴'd'，發(fā)現(xiàn)從結點a出發(fā)，已經有邊d存在。于是順著邊d走到結點ad。

（3）考察最后一個字符'd'，這次從結點ad出發(fā)沒有邊d了，于是創(chuàng)建結點ad的子結點add，并把邊ad→add標記為d。

問題實例

10個頻繁出現(xiàn)的詞

在一個文本文件中大約有1萬行，每行1個詞，要求統(tǒng)計出其中出現(xiàn)次數(shù)最頻繁的10個詞。

分析： 用Trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，時間復雜度是O(nl)（l表示單詞的平均長度），最終找出出現(xiàn)最頻繁的前10個詞（可用堆來實現(xiàn)，時間復雜度是O(nlog10)。

尋找熱門查詢

搜索引擎會通過日志文件把用戶每次檢索使用的所有查詢串都記錄下來，每個查詢串的長度為1～255字節(jié)。假設目前有1000萬條記錄（因為查詢串的重復度比較高，雖然總數(shù)是1000萬，但是如果去除重復，不超過300萬個）。請統(tǒng)計最熱門的10個查詢串，要求使用的內存不能超過1 GB。（一個查詢串的重復度越高，說明查詢它的用戶越多，也就越熱門。）

分析： 可以利用Trie樹，觀察關鍵字在該查詢串出現(xiàn)的次數(shù)，若沒有出現(xiàn)則為0。最后用10個元素的最小堆來對出現(xiàn)頻率進行排序。