---

前言

---

提示：人生之中總有空白，但有時(shí)，我們稱它為人生的副歌。在一些或長或短的時(shí)間段里，您聽不見它，于是以為已經(jīng)忘記了這段副歌。然后，有一天，在您獨(dú)自一人，周邊又沒有什么可以分散注意力的時(shí)候，這段副歌忽然又響起來。就像兒歌的歌詞，它依舊充滿魔力。 --帕特里克·莫迪亞諾《隱形墨水》

理解前面的題目，是不是很難，但是抓住重點(diǎn)理解起來是很容易的，這里再強(qiáng)調(diào)一些經(jīng)典問題（查找

從40個(gè)億中產(chǎn)生一個(gè)不存在的整數(shù)

題目要求：給定一個(gè)輸入文件，包含40億個(gè)非負(fù)整數(shù)，請?jiān)O(shè)計(jì)一個(gè)算法，產(chǎn)生一個(gè)不存在該文件的整數(shù)，假如你有1GB的內(nèi)存，你該怎么完成這個(gè)任務(wù)。

• 進(jìn)階：如果只有10MB的內(nèi)存呢，你該怎么處理

這里不用寫代碼，如果你能將方法說明白，我們看看這里要怎么做。

位圖存儲數(shù)據(jù)的原理

假設(shè)用哈希表來存儲出現(xiàn)過的數(shù)，如果是40億個(gè)數(shù)都不相同，那么哈希表的記錄數(shù)為40億條，存一個(gè)32為的整數(shù)需要4B，所以最差的情況需要40億*4B = 160億字節(jié)，大約需要16GB的空間，這很不符合要求。

40億*4B = 160億字節(jié)，大約需要16GB的空間

40億/8字節(jié) = 5億字節(jié)，大約需要0.5GB的空間，就可以存儲了。

1 字節(jié) = 8 位
1 B（字節(jié)）= 8 bit（位）
1 GB（千兆字節(jié)）= 1024 MB = 1024 * 1024 KB = 1024 * 1024 * 1024 B

數(shù)據(jù)量很大，采用位的方式（俗稱位圖）存儲數(shù)據(jù)是常用的思路，那位圖如何存儲元素呢？我們可以使用BitMap的方式來表示數(shù)出現(xiàn)的情況，具體來說，是申請一個(gè)長度位 4295967295 的類型的數(shù)組bitArr（就是boolean類型），bitArr上的每一個(gè)位置只可以表示0或者1狀態(tài)，8個(gè)bit為1B，所以長度就是 4295967295 的bit數(shù)組占用空間為500MB，這樣就滿足題目要求了。

4294967295 是一個(gè)能容納 40億個(gè)不同數(shù)的最小 2 的冪次減 1的值。也就是說，2的32次方（4294967296）可以表示的不同數(shù)的個(gè)數(shù)是40億，再減去1就得到了4294967295。

那么使用bitArr需要注意什么？就是遍歷這40一個(gè)數(shù)，遇到所有的數(shù)時(shí)，就把bitArr相對應(yīng)得位置設(shè)置為1.例如遇到1024，就將bitArr[1024] = 1。

遍歷完成后，再次遍歷bitArr,看看哪個(gè)位置上沒有被設(shè)置為1，這個(gè)數(shù)就是不存在40億個(gè)數(shù)中。當(dāng)然如果bitArr[5243] == 0，就可以將這個(gè)數(shù)輸出出來。

位存儲得核心是：我們存儲得并不是這40億個(gè)數(shù)據(jù)本身，而是其對應(yīng)得位置。這一點(diǎn)明白就很簡單了不是。

使用10MB來存儲

如果只有10MB得內(nèi)存，使用位圖就不行了，就需要另辟蹊徑了。這里我們采用分塊得思想，拿時(shí)間換空間，通過兩次遍歷來搞定。

40億個(gè)數(shù)需要500MB得空間，如果只有10MB得空間至少需要50塊才可以。

一般來說，我們劃分得是使用2得整數(shù)倍，因此分成64塊最合理。

首先就是將0~4294967295（2^32 -1)這個(gè)范圍平均分成64個(gè)區(qū)間，每個(gè)區(qū)間是67108864個(gè)數(shù)，例如

• 第0區(qū)間（0~67108863）
• 第1區(qū)間（67108864~134217728）
• …
• 第i區(qū)間（67108864*i~67108864（I+ 1） - 1）
• 第63區(qū)間（4227858432~4294967295）

因?yàn)橐还?0億個(gè)數(shù)，所以，如果統(tǒng)計(jì)羅在每個(gè)區(qū)間上得數(shù)有多少，肯定有至少一個(gè)區(qū)間上得計(jì)數(shù)是小于67108864。利用這一點(diǎn)就可以找出其中一個(gè)沒有出現(xiàn)過得數(shù)，具體過程是通過兩次遍歷來搞定。

第一次遍歷：先申請長度為64得整數(shù)數(shù)組countArr[0…63],countArr[i]用來統(tǒng)計(jì)區(qū)間i上得有多少個(gè)，遍歷40億個(gè)數(shù)，根據(jù)當(dāng)前數(shù)是多少決定哪個(gè)區(qū)間上得計(jì)數(shù)增加。例如67108865，67108865/67108864 = 1，所以第1區(qū)間上得計(jì)數(shù)增加countArr[1]++，遍歷完這40億個(gè)數(shù)之后遍歷countArr,必然會有某個(gè)位置上得值（countArr[i]小于67108864，表示第i區(qū)間上至少有一個(gè)數(shù)沒有出現(xiàn)過。我們肯定會找到至少一個(gè)這樣得區(qū)間。

此時(shí)使用得內(nèi)存就是countArr的大小（64*4B）是一個(gè)非常小的數(shù)。

假設(shè)找到第37區(qū)間上的計(jì)數(shù)小于67108864，那么我們對這40億個(gè)數(shù)據(jù)進(jìn)行第二次遍歷

1. 申請長度為67108864的BitMap，這占用的空間大約是8M，記為bitArr[0…67108863].
2. 遍歷這40億個(gè)數(shù)，此時(shí)只需要關(guān)注落在第37區(qū)間上的數(shù)，即為num(num 滿足 num/67108864 == 37)，其他區(qū)間的數(shù)全部忽略。
3. 如果步驟2的num在第37區(qū)間，將bitArr[num - 67108864*37]的值設(shè)置為1，也就是只做第37區(qū)間上的數(shù)的bitArr映射。
4. 遍歷完40億個(gè)數(shù)之后，在bitArr上必然存在沒有被設(shè)置1的位置，假設(shè)第i個(gè)位置上面的值沒有被設(shè)置成1，那么對應(yīng)的67108864*37 + i，這個(gè)數(shù)就是沒有出現(xiàn)過的數(shù)。

總結(jié)一下進(jìn)階解法：

1. 根據(jù)10MB 的內(nèi)存限制，確定統(tǒng)計(jì)區(qū)間的大小，就是第二次遍歷時(shí)bitArr大小
2. 利用區(qū)間計(jì)數(shù)的方式，找到那個(gè)計(jì)數(shù)不去的區(qū)間，這個(gè)區(qū)間上肯定有沒有出現(xiàn)的數(shù)
3. 對這個(gè)區(qū)間上的數(shù)做bitmap映射，在遍歷一遍bitmap，找到一個(gè)沒有出現(xiàn)的數(shù)即可

如何確定分塊的區(qū)間

上面的例子中，我們可以采用連詞遍歷，第一次將數(shù)據(jù)分成64塊剛好解決問題。那么我們?yōu)槭裁床皇?28、32，16或者其他類型呢？

這里主要是保證第二次遍歷每塊都能放進(jìn)去10MB的空間中，

2^23 < 10MB < 2 ^ 24,而2^23 = 8388608大約是8MB，也就是說我們依次分塊的大小只能為8MB左右，在上面我們也看到了，第二次遍歷如果分塊是64，剛好滿足要求。

所以這里我們最少要分64塊，當(dāng)然如果分成128塊，256塊也是可以的。

用2GB內(nèi)存在20億的整數(shù)中找到出現(xiàn)次數(shù)最多的數(shù)

題目要求：有一個(gè)包含20億個(gè)全是32位整數(shù)的大文件，在其中找出出現(xiàn)次數(shù)最多的數(shù)。

要求：內(nèi)存限制為2GB

想要在很多整數(shù)中找出現(xiàn)次數(shù)最多的數(shù)，通常的做法是使用哈希表出現(xiàn)的每一個(gè)數(shù)做詞頻統(tǒng)計(jì)，哈希表的key是某個(gè)整數(shù)，value是這個(gè)整數(shù)出現(xiàn)的次數(shù)。就本題目來說，一共20億個(gè)數(shù)，哪怕只有一個(gè)數(shù)出現(xiàn)20依次，用32為的整數(shù)也是可以便是出現(xiàn)依次而不會產(chǎn)生溢出，所以哈希表的key需要占用4B，value也是4B。那么哈希表中的一條數(shù)據(jù)就要占用8B，當(dāng)哈希表中的記錄數(shù)有20億時(shí)，需要至少1.6GB的內(nèi)存。

如果20億個(gè)數(shù)中不同數(shù)超過2億中，最極端的情況時(shí)20億個(gè)數(shù)都不同，那么在哈希變種可能要產(chǎn)生20億條數(shù)據(jù)，顯然這樣的內(nèi)存時(shí)不夠用的，所以一次性用哈希表統(tǒng)計(jì)20億個(gè)數(shù)的辦法行不通的。

解決辦法是把包含20億個(gè)數(shù)的大文件用哈希函數(shù)分成16個(gè)小文件，根基哈希函數(shù)的性質(zhì)，同一種數(shù)不能能被散列到不同的小文件上，同時(shí)每個(gè)小文件中不同的數(shù)一定不會找過2億中，假設(shè)哈希函數(shù)足夠優(yōu)秀。然后對每一個(gè)小文件用哈希表來統(tǒng)計(jì)其中每種出現(xiàn)的次數(shù)，我們就能得到16個(gè)小文件中各自出現(xiàn)最多的數(shù)，還有各自的統(tǒng)計(jì)次數(shù)。接下來就是在個(gè)16個(gè)小文件各自的第一名相互比較，找到次數(shù)最多的那個(gè)。

把一個(gè)大的集合通過哈希函數(shù)分配到多臺機(jī)器中，或者分配到多個(gè)文件中，這種技巧也是處理大數(shù)據(jù)面試時(shí)最常見的方法之一。但是到底分配多少臺機(jī)器，分配到多少個(gè)文件中，在解題一定要先確定下來?？赡茉谂c面試官溝通的過程中面試官指定，也可能時(shí)根據(jù)具體的限制來確定，比如本體確定分成16個(gè)文件，就是根據(jù)內(nèi)存限制2GB的條件來確定的。

從100億個(gè)URL中查找的問題

題目：有一個(gè)包含100億URL的大文件，假設(shè)每個(gè)URL占用時(shí)64B，請找出其中重復(fù)的URL。

補(bǔ)充題目：某搜索公司一天的用戶搜索詞匯時(shí)海量的（百億數(shù)據(jù)量），請?jiān)O(shè)計(jì)出一種可以求出每天熱門top100詞匯的可行辦法。

解答：原問題的加法使用解決大數(shù)據(jù)問題的一種常規(guī)套路：把大文件通過哈希函數(shù)分配到機(jī)器或者通過哈希函數(shù)把大文件拆成小文件。一直進(jìn)行這種劃分，直到滿足結(jié)果要求的資源限制。首先需要確認(rèn)面試官時(shí)候存在資源上限，時(shí)間等。在明確限制要求之后，可以將每條URL通過哈希函數(shù)分配到若干臺機(jī)器中或者拆分成小文件。這里的“若干”是由具體的資源限制計(jì)算出來的數(shù)量。

例如：將100億字節(jié)的大文件通過哈希函數(shù)分配到100臺機(jī)器上面，然后每一臺機(jī)器分別統(tǒng)計(jì)分給自己的URL中是否有重復(fù)的URL，同時(shí)哈希函數(shù)的性質(zhì)決定了同一條URL不可能分給不同的機(jī)器；或者將單機(jī)上的大文件通過哈希函數(shù)拆分成1000個(gè)小文件，對每個(gè)小文件再利用哈希表遍歷，找出重復(fù)的URL；還可以在非給機(jī)器差分完后對進(jìn)行排序，排序后再看看是否有重復(fù)的URL出現(xiàn)，總之，牢記一點(diǎn)，很多大數(shù)據(jù)問題都離不開分流，要么是使用哈希函數(shù)將大文件的內(nèi)容分配給不同的機(jī)器；要么是用哈希函數(shù)將大文件拆分成小文件，然后處理每個(gè)小文件的集合。

補(bǔ)充問題：

最開始還是用哈希分流的思想來處理，把包含百億數(shù)量的詞匯文件分流到不同的機(jī)器上面，具體多少機(jī)器由面試官規(guī)定的資源或者給出的限制來決定，對每一臺機(jī)器來說，如果分到的數(shù)據(jù)量依然很大的話，比如出現(xiàn)內(nèi)存不夠或者其他問題可以繼續(xù)使用哈希函數(shù)把每臺機(jī)器的分流文件再次拆分成小文件處理。處理小文件的時(shí)候，通過哈希表統(tǒng)計(jì)每種詞及其頻率，哈希表記錄建立完成后，在遍歷哈希表，遍歷哈希表的過程中使用大小為100的小根堆來選出每個(gè)小文件的top100（整體未排序的top100）。每一個(gè)文件都有自己詞頻的小根堆，將小根堆的的詞按照詞頻排序，就得到了每個(gè)小文件排序后的top100.然后把各個(gè)小文件排序后的top100進(jìn)行外排序或者繼續(xù)使用小根堆，就可以挑選出每臺機(jī)器上的top100.不同機(jī)器之間的top100在進(jìn)行外排序或者使用小根堆。最終求出整個(gè)百億數(shù)據(jù)量中top100**.對于TopK問題，除了使用哈希函數(shù)分流和用哈希表做詞頻統(tǒng)計(jì)外，還經(jīng)常使用堆結(jié)構(gòu)和外排序的手段進(jìn)行處理。**

40億個(gè)非負(fù)整數(shù)中找出兩次的數(shù)。

題目要求：32位無符號整數(shù)的范圍是0~4294967295，現(xiàn)在又10億個(gè)無符號整數(shù)，可以使用最多1GB的內(nèi)存，找出所有出現(xiàn)了兩次的數(shù)。

本體可以看看第一題的進(jìn)階，這里出現(xiàn)了限制在兩次。

首先，可以使用bitmap的方式來表示出現(xiàn)的情況，具體來說，是申請一個(gè)長度為4294967295 * 2的bit類型數(shù)組bitArr，用2個(gè)位置來表示一個(gè)數(shù)出現(xiàn)的詞頻，1B占用8bit，所以長度為4294967295 * 2的bit類型的數(shù)組占用1GB的空間，那么怎么使用這個(gè)bitArr數(shù)組呢？遍歷這40億個(gè)無符號數(shù)，如果初次遇到就把bitArr[num*2]和bitArr[num * 2 ]設(shè)置成01，第二次遇到設(shè)置成10，第三次遇到設(shè)置11.當(dāng)然以后在遇到就不關(guān)系了。遍歷完成之后，再次遍歷bitArr，如果發(fā)現(xiàn)bitArr[i * 2+1]和bitArr[i * 2]設(shè)置為10，那么i就是出現(xiàn)兩次的數(shù)。

---

總結(jié)

提示：大數(shù)據(jù)的處理方式；海量數(shù)據(jù)問題；大數(shù)據(jù)壓縮；大數(shù)據(jù)分塊；數(shù)據(jù)流處理

---

如果有幫助到你，請給題解點(diǎn)個(gè)贊和收藏，讓更多的人看到 ~ ("▔□▔)/

如有不理解的地方，歡迎你在評論區(qū)給我留言，我都會逐一回復(fù) ~

也歡迎你 關(guān)注我 ，喜歡交朋友，喜歡一起探討問題。