點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
作者 | 張維鵬
來源 | urlify.cn/i6jUJb
基礎(chǔ)知識(shí)：
海量數(shù)據(jù)處理概述：
所謂海量數(shù)據(jù)處理，就是指數(shù)據(jù)量太大，無法在較短時(shí)間內(nèi)迅速解決，或者無法一次性裝入內(nèi)存。而解決方案就是：針對(duì)時(shí)間，可以采用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)，如 Bloom filter/Hashmap/bit-map/堆/數(shù)據(jù)庫/倒排索引/trie樹；針對(duì)空間，大而化小，分而治之（hash映射），把規(guī)模大化為規(guī)模小的，各個(gè)擊破。所以，海量數(shù)據(jù)處理的基本方法總結(jié)起來分為以下幾種：
一、分而治之/hash映射 + hashmap統(tǒng)計(jì) + 快速/歸并/堆排序
這種方法是典型的“分而治之”的策略，是解決空間限制最常用的方法，即海量數(shù)據(jù)不能一次性讀入內(nèi)存，而我們需要對(duì)海量數(shù)據(jù)進(jìn)行的計(jì)數(shù)、排序等操作?；舅悸啡缦聢D所示：先借助哈希算法，計(jì)算每一條數(shù)據(jù)的 hash 值，按照 hash 值將海量數(shù)據(jù)分布存儲(chǔ)到多個(gè)桶中。根據(jù) hash 函數(shù)的唯一性，相同的數(shù)據(jù)一定在同一個(gè)桶中。如此，我們?cè)僖来翁幚磉@些小文件，最后做合并運(yùn)算即可。
問題1：海量日志數(shù)據(jù)，統(tǒng)計(jì)出某日訪問百度次數(shù)最多的那個(gè)IP
解決方式：IP地址最多有 2^32 = 4G 種取值情況，所以不能完全加載到內(nèi)存中進(jìn)行處理，采用 hash分解+ 分而治之 + 歸并 方式：
（1）按照 IP 地址的 Hash(IP)%1024 值，把海量IP日志分別存儲(chǔ)到1024個(gè)小文件中。這樣，每個(gè)小文件最多包含4MB個(gè)IP地址；
（2）對(duì)于每一個(gè)小文件，構(gòu)建一個(gè)IP為key，出現(xiàn)次數(shù)為value的Hash map，同時(shí)記錄當(dāng)前出現(xiàn)次數(shù)最多的那個(gè)IP地址
（3）然后再在這1024組最大的IP中，找出那個(gè)頻率最大的IP
問題2：有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。
解決思想：hash分解+ 分而治之 + 歸并
（1）順序讀文件中，對(duì)于每個(gè)詞x，按照 hash(x)/(1024*4) 存到4096個(gè)小文件中。這樣每個(gè)文件大概是250k左右。如果其中的有的文件超過了1M大小，還可以按照hash繼續(xù)往下分，直到分解得到的小文件的大小都不超過1M。
（2）對(duì)每個(gè)小文件，可以采用 trie樹/hashmap 統(tǒng)計(jì)每個(gè)文件中出現(xiàn)的詞以及相應(yīng)的頻率，并使用 100個(gè)節(jié)點(diǎn)的小頂堆取出出現(xiàn)頻率最大的100個(gè)詞，并把100個(gè)詞及相應(yīng)的頻率存入文件。這樣又得到了4096個(gè)文件。
（3）下一步就是把這4096個(gè)文件進(jìn)行歸并的過程了
問題3：有a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？
解決方案1：如果內(nèi)存中想要存入所有的 url，共需要 50億 * 64= 320G大小空間，所以采用 hash 分解+ 分而治之 + 歸并 的方式：
（1）遍歷文件a，對(duì)每個(gè) url 根據(jù)某種hash規(guī)則，求取hash(url)/1024，然后根據(jù)所取得的值將 url 分別存儲(chǔ)到1024個(gè)小文件（a0~a1023）中。這樣每個(gè)小文件的大約為300M。如果hash結(jié)果很集中使得某個(gè)文件ai過大，可以在對(duì)ai進(jìn)行二級(jí)hash(ai0~ai1024)，這樣 url 就被hash到 1024 個(gè)不同級(jí)別的文件中。
（2）分別比較文件，a0 VS b0，…… ，a1023 VS b1023，求每對(duì)小文件中相同的url時(shí)：把其中一個(gè)小文件的 url 存儲(chǔ)到 hashmap 中，然后遍歷另一個(gè)小文件的每個(gè)url，看其是否在剛才構(gòu)建的 hashmap 中，如果是，那么就是共同的url，存到文件中。
（3）把1024個(gè)文件中的相同 url 合并起來
解決方案2：Bloom filter
如果允許有一定的錯(cuò)誤率，可以使用 Bloom filter，4G內(nèi)存大概可以表示 340 億bit，n = 50億，如果按照出錯(cuò)率0.01算需要的大概是650億個(gè)bit，現(xiàn)在可用的是340億，相差并不多，這樣可能會(huì)使出錯(cuò)率上升些，將其中一個(gè)文件中的 url 使用 Bloom filter 映射為這340億bit，然后挨個(gè)讀取另外一個(gè)文件的url，檢查是否與Bloom filter，如果是，那么該url應(yīng)該是共同的url（注意會(huì)有一定的錯(cuò)誤率）
問題4：有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行存放的都是用戶的 query，每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序。
解決方案1：hash分解+ 分而治之 +歸并
（1）順序讀取10個(gè)文件 a0~a9，按照 hash(query)%10 的結(jié)果將 query 寫入到另外10個(gè)文件（記為 b0~b9）中，這樣新生成的文件每個(gè)的大小大約也1G
（2）找一臺(tái)內(nèi)存2G左右的機(jī)器，依次使用 hashmap(query, query_count) 來統(tǒng)計(jì)每個(gè) query 出現(xiàn)的次數(shù)。利用 快速/堆/歸并排序 按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的query和對(duì)應(yīng)的query_cout輸出到文件中。這樣得到了10個(gè)排好序的文件c0~c9。
（3）對(duì)這10個(gè)文件 c0~c9 進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。每次取 c0~c9 文件的 m 個(gè)數(shù)據(jù)放到內(nèi)存中，進(jìn)行 10m 個(gè)數(shù)據(jù)的歸并，即使把歸并好的數(shù)據(jù)存到 d結(jié)果文件中。如果 ci 對(duì)應(yīng)的m個(gè)數(shù)據(jù)全歸并完了，再從 ci 余下的數(shù)據(jù)中取m個(gè)數(shù)據(jù)重新加載到內(nèi)存中。直到所有ci文件的所有數(shù)據(jù)全部歸并完成。
解決方案2：Trie樹
如果query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對(duì)于所有的query，一次性就可以加入到內(nèi)存了。在這種情況下，可以采用 trie樹/hashmap 等直接來統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。
問題5：海量數(shù)據(jù)分布在100臺(tái)電腦中，請(qǐng)高效統(tǒng)計(jì)出這批數(shù)據(jù)的TOP10
解決思想：分而治之 + 歸并
（注意：該題的 TOP10 是取最大值或最小值，如果取頻率TOP10，就應(yīng)該先hash分解，將相同的數(shù)據(jù)移動(dòng)到同一臺(tái)電腦中，再使用hashmap分別統(tǒng)計(jì)出現(xiàn)的頻率）
問題6：在 2.5 億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，內(nèi)存不足以容納這2.5億個(gè)整數(shù)
解決方案1：hash 分解+ 分而治之 + 歸并
解決方案2 ：2-Bitmap
如果內(nèi)存夠1GB的話，采用 2-Bitmap 進(jìn)行統(tǒng)計(jì)，共需內(nèi)存 2^32 * 2bit = 1GB內(nèi)存。2-bitmap 中，每個(gè)數(shù)分配 2bit（00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義），然后掃描這 2.5 億個(gè)整數(shù)，查看Bitmap中相對(duì)應(yīng)位，如果是00，則將其置為01；如果是01，將其置為10；如果是10，則保持不變。所描完成后，查看bitmap，把對(duì)應(yīng)位是01的整數(shù)輸出即可。（如果是找出重復(fù)的數(shù)據(jù)，可以用1-bitmap。第一次bit位由0變1，第二次查詢到相應(yīng)bit位為1說明是重復(fù)數(shù)據(jù)，輸出即可）
二、Trie樹+紅黑樹+hashmap
Trie樹、紅黑樹 和 hashmap 可以認(rèn)為是第一部分中分而治之算法的具體實(shí)現(xiàn)方法之一。
其中，Trie樹適合處理海量字符串?dāng)?shù)據(jù)，尤其是大量的字符串?dāng)?shù)據(jù)中存在前綴時(shí)。Trie樹在字典的存儲(chǔ)，字符串的查找，求取海量字符串的公共前綴，以及字符串統(tǒng)計(jì)等方面發(fā)揮著重要的作用。
用于存儲(chǔ)時(shí)，Trie樹因?yàn)椴恢貜?fù)存儲(chǔ)公共前綴，節(jié)省了大量的存儲(chǔ)空間；
用于以字符串的查找時(shí)，Trie樹依靠其特殊的性質(zhì)，實(shí)現(xiàn)了在任意數(shù)據(jù)量的字符串集合中都能以O(shè)(len)的時(shí)間復(fù)雜度完成查找（len為要檢索的字符串長度）；
在字符串統(tǒng)計(jì)中，Trie樹能夠快速記錄每個(gè)字符串出現(xiàn)的次數(shù)
問題1：上千萬或上億數(shù)據(jù)（有重復(fù)），統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前N個(gè)數(shù)據(jù)。
解決方案：hashmap/紅黑樹 + 堆排序
問題2：一個(gè)文本文件，大約有一萬行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，并給出時(shí)間復(fù)雜度
解決思路：trie樹 + 堆排序
總的時(shí)間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的那一個(gè)。
問題3：有一千萬個(gè)字符串記錄（這些字符串的重復(fù)率比較高，雖然總數(shù)是1千萬，但是如果去除重復(fù)和，不超過3百萬個(gè)），每個(gè)查詢串的長度為1-255字節(jié)。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串（重復(fù)度越高，說明越熱門），要求使用的內(nèi)存不能超過1G。
解決方案：
內(nèi)存不能超過 1G，每條記錄是 255byte，1000W 條記錄需要要占據(jù)2.375G內(nèi)存，這個(gè)條件就不滿足要求了，但是去重后只有 300W 條記錄，最多占用0.75G內(nèi)存，因此可以將它們都存進(jìn)內(nèi)存中去。使用 trie樹（或者使用hashmap），關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)。最后用10個(gè)元素的最小堆來對(duì)出現(xiàn)頻率進(jìn)行排序?？偟臅r(shí)間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的那一個(gè)。
問題4：1000萬字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。
解決方案：trie樹
三、BitMap 與 Bloom Filter：
1、BitMap 就是通過 bit 位為 1 或 0 來標(biāo)識(shí)某個(gè)狀態(tài)存不存在?？捎糜跀?shù)據(jù)的快速查找，判重，刪除，一般來說適合的處理數(shù)據(jù)范圍小于 8bit *2^32。否則內(nèi)存超過4G，內(nèi)存資源消耗有點(diǎn)多。
2、Bloom Filter 主要是用于判定目標(biāo)數(shù)據(jù)是否存在于一個(gè)海量數(shù)據(jù)集 以及 集合求交集。以存在性判定為例，Bloom Filter 通過對(duì)目標(biāo)數(shù)據(jù)的映射，能夠以 O(k) 的時(shí)間復(fù)雜度判定目標(biāo)數(shù)據(jù)的存在性，其中k為使用的hash函數(shù)個(gè)數(shù)。這樣就能大大縮減遍歷查找所需的時(shí)間。
問題1：已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。
解決思路：
8位最多99 999 999，需要 100M個(gè)bit 位，不到12M的內(nèi)存空間。我們把 0-99 999 999的每個(gè)數(shù)字映射到一個(gè)Bit位上，這樣，就用了小小的12M左右的內(nèi)存表示了所有的8位數(shù)的電話
問題2：2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。
解決方案：使用 2-bitmap，詳情見上文
問題3：給40億個(gè)不重復(fù)的 unsigned int 的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中
解決方案：使用 Bitmap，申請(qǐng) 512M 的內(nèi)存，一個(gè)bit位代表一個(gè) unsigned int 值。讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。
問題4：現(xiàn)有兩個(gè)各有20億行的文件，每一行都只有一個(gè)數(shù)字，求這兩個(gè)文件的交集。
解決方案：采用 bitmap 進(jìn)行問題解決，因?yàn)?int 的最大數(shù)是 2^32 = 4G，用一個(gè)二進(jìn)制的下標(biāo)來表示一個(gè) int 值，大概需要4G個(gè)bit位，即約4G/8 = 512M的內(nèi)存，就可以解決問題了。
① 首先遍歷文件，將每個(gè)文件按照數(shù)字的正數(shù)，負(fù)數(shù)標(biāo)記到2個(gè) bitmap 上，為：正數(shù) bitmapA_positive，負(fù)數(shù) bitmapA_negative
② 遍歷另為一個(gè)文件，生成正數(shù)：bitmapB_positive，bitmapB_negative
③ 取 bitmapA_positive and bitmapB_positive 得到2個(gè)文件的正數(shù)的交集，同理得到負(fù)數(shù)的交集。
④ 合并，問題解決
這里一次只能解決全正數(shù)，或全負(fù)數(shù)，所以要分兩次
問題5：與上面的問題4類似，只不過現(xiàn)在不是A和B兩個(gè)大文件，而是A, B, C, D….多個(gè)大文件，求集合的交集
解決方案：
（1）依次遍歷每個(gè)大文件中的每條數(shù)據(jù)，遍歷每條數(shù)據(jù)時(shí)，都將它插入 Bloom Filter；
（2）如果已經(jīng)存在，則在另外的集合（記為S）中記錄下來；
（3）如果不存在，則插入Bloom Filter；
（4）最后，得到的S即為所有這些大文件中元素的交集
四、多層劃分：
多層劃分本質(zhì)上還是分而治之的思想，重在“分”的技巧上！因?yàn)樵胤秶艽螅枰ㄟ^多次劃分，逐步確定范圍，然后最后在一個(gè)可以接受的范圍內(nèi)進(jìn)行。適用用于：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字
問題1：求取海量整數(shù)的中位數(shù)
解決方案：
依次遍歷整數(shù)，按照其大小將他們分揀到n個(gè)桶中。如果有的桶數(shù)據(jù)量很小，有的則數(shù)據(jù)量很大，大到內(nèi)存放不下了；對(duì)于那些太大的桶，再分割成更小的桶；
之后根據(jù)桶數(shù)量的統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到哪個(gè)桶中，如果該桶中還有子桶，就判斷在其哪個(gè)子桶中，直到最后找出目標(biāo)。
問題2：一共有N個(gè)機(jī)器，每個(gè)機(jī)器上有N個(gè)數(shù)，每個(gè)機(jī)器最多存 N 個(gè)數(shù)，如何找到 N^2 個(gè)數(shù)中的中數(shù)？
解決方案1：hash分解 + 排序
按照升序順序把這些數(shù)字，hash劃分為N個(gè)范圍段。假設(shè)數(shù)據(jù)范圍是2^32 的unsigned int 類型。理論上第一臺(tái)機(jī)器應(yīng)該存的范圍為0~(2^32)/N，第i臺(tái)機(jī)器存的范圍是(2^32)*(i-1)/N~(2^32)*i/N。hash過程可以掃描每個(gè)機(jī)器上的N個(gè)數(shù)，把屬于第一個(gè)區(qū)段的數(shù)放到第一個(gè)機(jī)器上，屬于第二個(gè)區(qū)段的數(shù)放到第二個(gè)機(jī)器上，…，屬于第N個(gè)區(qū)段的數(shù)放到第N個(gè)機(jī)器上。注意這個(gè)過程每個(gè)機(jī)器上存儲(chǔ)的數(shù)應(yīng)該是O(N)的。
然后我們依次統(tǒng)計(jì)每個(gè)機(jī)器上數(shù)的個(gè)數(shù)，依次累加，直到找到第k個(gè)機(jī)器，在該機(jī)器上累加的數(shù)大于或等于（N^2）/2，而在第k-1個(gè)機(jī)器上的累加數(shù)小于（N^2）/2，并把這個(gè)數(shù)記為x。那么我們要找的中位數(shù)在第k個(gè)機(jī)器中，排在第（N^2）/2-x位。然后我們對(duì)第k個(gè)機(jī)器的數(shù)排序，并找出第（N^2）/2-x個(gè)數(shù)，即為所求的中位數(shù)的復(fù)雜度是O（N^2）的。
解決方案2： 分而治之 + 歸并
先對(duì)每臺(tái)機(jī)器上的數(shù)進(jìn)行排序。排好序后，我們采用歸并排序的思想，將這N個(gè)機(jī)器上的數(shù)歸并起來得到最終的排序。找到第（N^2）/2個(gè)便是所求。復(fù)雜度是O（N^2 * lgN^2）的
