---

前言

---

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

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

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

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

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

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

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

假設(shè)用哈希表來存儲出現(xiàn)過的數(shù)，如果是40億個數(shù)都不相同，那么哈希表的記錄數(shù)為40億條，存一個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)的情況，具體來說，是申請一個長度位 4295967295 的類型的數(shù)組bitArr（就是boolean類型），bitArr上的每一個位置只可以表示0或者1狀態(tài)，8個bit為1B，所以長度就是 4295967295 的bit數(shù)組占用空間為500MB，這樣就滿足題目要求了。

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

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

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

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

使用10MB來存儲

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

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

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

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

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

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

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

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

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

1. 申請長度為67108864的BitMap，這占用的空間大約是8M，記為bitArr[0…67108863].
2. 遍歷這40億個數(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億個數(shù)之后，在bitArr上必然存在沒有被設(shè)置1的位置，假設(shè)第i個位置上面的值沒有被設(shè)置成1，那么對應(yīng)的67108864*37 + i，這個數(shù)就是沒有出現(xiàn)過的數(shù)。

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

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

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

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

這里主要是保證第二次遍歷每塊都能放進去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ù)

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

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

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

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

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

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

從100億個URL中查找的問題

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

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

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

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

補充問題：

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

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

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

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

首先，可以使用bitmap的方式來表示出現(xiàn)的情況，具體來說，是申請一個長度為4294967295 * 2的bit類型數(shù)組bitArr，用2個位置來表示一個數(shù)出現(xiàn)的詞頻，1B占用8bit，所以長度為4294967295 * 2的bit類型的數(shù)組占用1GB的空間，那么怎么使用這個bitArr數(shù)組呢？遍歷這40億個無符號數(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ù)流處理

---

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

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

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