網(wǎng)友解答: 全文行文是基于面試題的分析基礎(chǔ)之上的，具體實踐過程中，還是得具體情況具體分析，且各個場景下需要考慮的細(xì)節(jié)也遠(yuǎn)比本文所描述的任何一種解決方法復(fù)雜得多。何謂海量數(shù)據(jù)處理？基于海量

網(wǎng)友解答:

全文行文是基于面試題的分析基礎(chǔ)之上的，具體實踐過程中，還是得具體情況具體分析，且各個場景下需要考慮的細(xì)節(jié)也遠(yuǎn)比本文所描述的任何一種解決方法復(fù)雜得多。

何謂海量數(shù)據(jù)處理？

基于海量數(shù)據(jù)上的存儲、處理、操作。何謂海量，就是數(shù)據(jù)量太大，導(dǎo)致要么是無法在較短時間內(nèi)迅速解決，要么是數(shù)據(jù)太大，導(dǎo)致無法一次性裝入內(nèi)存。

那解決辦法呢?

針對時間，我們可以采用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)，如Bloom filter/Hash/bit-map/堆/數(shù)據(jù)庫或倒排索引/trie樹針對空間，無非就一個辦法：大而化小，分而治之（hash映射），把規(guī)模大化為規(guī)模小的，各個擊破

至于單機(jī)及集群問題，通俗點(diǎn)來講

單機(jī)就是處理裝載數(shù)據(jù)的機(jī)器有限(只需考慮CPU，內(nèi)存，硬盤的數(shù)據(jù)交互)集群，機(jī)器有多臺，適合分布式處理，并行計算(更多考慮節(jié)點(diǎn)和節(jié)點(diǎn)間的數(shù)據(jù)交互)。

處理海量數(shù)據(jù)，不外乎

分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序雙層桶劃分Bloom filter/Bitmap；Trie樹/數(shù)據(jù)庫/倒排索引；外排序；分布式處理之Hadoop/Mapreduce。

本文第一部分、從談到，簡要介紹下，及之區(qū)別(萬丈高樓平地起，基礎(chǔ)最重要)，而本文第二部分，則針對上述那6種方法模式結(jié)合對應(yīng)的海量數(shù)據(jù)處理面試題分別具體闡述。

從set/map到hashtable/hashmap/hashset

序列式容器vector/list/deque/stack/queue/heap關(guān)聯(lián)式容器。關(guān)聯(lián)式容器又分為set(集合)和map(映射表)兩大類，還有第3類關(guān)聯(lián)式容器，如hashtable(散列表)類似關(guān)聯(lián)式數(shù)據(jù)庫，每筆數(shù)據(jù)或每個元素都有一個鍵值(key)和一個實值(value)，即所謂的Key-Value(鍵-值對)set/mapset，同map一樣，所有元素都會根據(jù)元素的鍵值自動被排序，值得注意的是，兩者都不允許兩個元素有相同的鍵值。不同的是：set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，而map的所有元素同時擁有實值(value)和鍵值(key)，pair的第一個元素被視為鍵值，第二個元素被視為實值。hash_set/hash_maphash_set/hash_map，兩者的一切操作都是基于hashtable之上。不同的是，hash_set同set一樣，同時擁有實值和鍵值，且實質(zhì)就是鍵值，鍵值就是實值，而hash_map同map一樣，每一個元素同時擁有一個實值(value)和一個鍵值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具備自動排序功能。為什么?因為hashtable沒有自動排序功能。

所以，綜上什么樣的結(jié)構(gòu)決定其什么樣的性質(zhì)，因為set/map都是基于RB-tree之上，所以有自動排序功能，而hash_set/hash_map都是基于hashtable之上，所以不含有自動排序功能，至于加個前綴multi_無非就是允許鍵值重復(fù)而已。

秘技一:分而治之/Hash映射 + HashMap統(tǒng)計 + 堆/快速/歸并排序

Hash，就是把任意長度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的函數(shù)。

Hash主要用于信息安全領(lǐng)域中加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做Hash值. 也可以說，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。

數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”

左邊很明顯是個數(shù)組，數(shù)組的每個成員包括一個指針，指向一個鏈表的頭，當(dāng)然這個鏈表可能為空，也可能元素很多。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征，找到正確的鏈表，再從鏈表中找出這個元素。

元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法就是散列法

除法散列法最直觀的一種，上圖使用的就是這種散列法，公式：學(xué)過匯編的都知道，求模數(shù)其實是通過一個除法運(yùn)算得到的，所以叫“除法散列法”。平方散列法求index是非常頻繁的操作，而乘法的運(yùn)算要比除法來得省時，所以我們考慮把除法換成乘法和一個位移操作。公式：如果數(shù)值分配比較均勻的話這種方法能得到不錯的結(jié)果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢出嗎？答案是會的，但我們這個乘法不關(guān)心溢出，因為我們根本不是為了獲取相乘結(jié)果，而是為了獲取index。斐波那契（Fibonacci）散列法平方散列法的缺點(diǎn)是顯而易見的，所以我們能不能找出一個理想的乘數(shù)，而不是拿value本身當(dāng)作乘數(shù)呢？答案是肯定的。1，對于16位整數(shù)而言，這個乘數(shù)是405032，對于32位整數(shù)而言，這個乘數(shù)是26544357693，對于64位整數(shù)而言，這個乘數(shù)是11400714819323198485

這幾個“理想乘數(shù)”是如何得出來的呢？這跟一個法則有關(guān)，叫黃金分割法則，而描述黃金分割法則的最經(jīng)典表達(dá)式無疑就是著名的斐波那契數(shù)列，如果你還有興趣，就到網(wǎng)上查找一下“斐波那契數(shù)列”等關(guān)鍵字，我數(shù)學(xué)水平有限，不知道怎么描述清楚為什么，另外斐波那契數(shù)列的值居然和太陽系八大行星的軌道半徑的比例出奇吻合，很神奇，對么？

對我們常見的32位整數(shù)而言，公式：index = (value * 2654435769) 28如果用這種斐波那契散列法的話，那我上面的圖就變成這樣了：

很明顯，用斐波那契散列法調(diào)整之后要比原來的取模散列法好很多。

適用范圍快速查找，刪除的基本數(shù)據(jù)結(jié)構(gòu)，通常需要總數(shù)據(jù)量可以放入內(nèi)存?；驹砑耙c(diǎn)Hash函數(shù)選擇，針對字符串，整數(shù)，排列，具體相應(yīng)的hash方法碰撞處理，一種是開放哈希法，亦拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。擴(kuò)展d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數(shù)，h1和h2。在存儲一個新的key時，同 時用兩個哈希函數(shù)進(jìn)行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經(jīng)存儲的（有碰撞的）key比較多，然后將新key存儲在負(fù)載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進(jìn)行兩次hash，同時查找兩個位置。海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP無非分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序，說白了，就是先映射，后統(tǒng)計，最后排序分而治之/hash映射針對數(shù)據(jù)太大，內(nèi)存受限，只能把大文件化成(取模映射)小文件HashMap統(tǒng)計：當(dāng)大文件轉(zhuǎn)化了小文件，便可以采用常規(guī)的HashMap(ip，value)進(jìn)行頻率統(tǒng)計堆/快速排序統(tǒng)計完了之后，進(jìn)行排序(可采取堆排序)，得到次數(shù)最多的IP

首先是這一天，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中。注意到IP是32位的，最多有個2^32個IP。同樣可以采用映射的方法，比如%1000，把整個大文件映射為1000個小文件，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用HashMap對那1000個文件中的所有IP進(jìn)行頻率統(tǒng)計，然后依次找出各個文件中頻率最大的那個IP）及相應(yīng)的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

還有幾個問題

Hash取模是一種等價映射，不會存在同一個元素分散到不同小文件中的情況，即這里采用的是mod 1000算法，那么相同的IP在hash取模后，只可能落在同一個文件中，不可能被分散那到底什么是hash映射呢？簡單來說，就是為了便于計算機(jī)在有限的內(nèi)存中處理大數(shù)據(jù)，從而通過一種映射散列的方式讓數(shù)據(jù)均勻分布在對應(yīng)的內(nèi)存位置(如大數(shù)據(jù)通過取余的方式映射成小樹存放在內(nèi)存中，或大文件映射成多個小文件)，而這個映射散列方式便是我們通常所說的hash函數(shù)，好的hash函數(shù)能讓數(shù)據(jù)均勻分布而減少沖突。盡管數(shù)據(jù)映射到了另外一些不同的位置，但數(shù)據(jù)還是原來的數(shù)據(jù)，只是代替和表示這些原始數(shù)據(jù)的形式發(fā)生了變化而已

堆

概念

堆是一種特殊的二叉樹,具備以下兩種性質(zhì)

每個節(jié)點(diǎn)的值都大于(或者都小于，即最小堆)其子節(jié)點(diǎn)的值樹完全平衡的，并且最后一層的樹葉都在最左邊

這樣就定義了一個最大堆

二叉堆一種完全二叉樹，其任意子樹的左右節(jié)點(diǎn)（如果有的話）的鍵值一定比根節(jié)點(diǎn)大，上圖其實就是一個二叉堆

最小的一個元素就是數(shù)組第一個元素,那么二叉堆這種有序隊列如何入隊呢

假設(shè)要在這個二叉堆里入隊一個單元，鍵值為2，那只需在數(shù)組末尾加入這個元素，然后盡可能把這個元素往上挪，直到挪不動，經(jīng)過了這種復(fù)雜度為Ο(logn)的操作，二叉堆還是二叉堆。

那如何出隊呢

出隊一定是出數(shù)組的第一個元素，這么來第一個元素以前的位置就成了空位，我們需要把這個空位挪至葉子節(jié)點(diǎn)，然后把數(shù)組最后一個元素插入這個空位，把這個“空位”盡量往上挪。這種操作的復(fù)雜度也是Ο(logn)

適用范圍海量數(shù)據(jù)前n大，并且n比較小，堆可以放入內(nèi)存基本原理及要點(diǎn)最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當(dāng)前元素與最大堆里的最大元素，如果它小于最大元素，則應(yīng)該替換那個最大元 素。這樣最后得到的n個元素就是最小的n個。適合大數(shù)據(jù)量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。擴(kuò)展雙堆，一個最大堆與一個最小堆結(jié)合，可以用來維護(hù)中位數(shù)。100w個數(shù)中找最大的前100個數(shù)用一個100個元素大小的最小堆即可。

尋找熱門查詢，300萬個查詢字符串中統(tǒng)計最熱門的10個查詢

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

解答：由上題，我們知道，數(shù)據(jù)大則劃為小的，如一億個IP求Top 10，可先將IP分到1000個小文件中去，并保證一種IP只出現(xiàn)在一個文件中，再對每個小文件中的IP進(jìn)行HashMap計數(shù)統(tǒng)計并按數(shù)量排序，最后歸并或者最小堆依次處理每個小文件的Top10以得到最后的結(jié)果

但如果數(shù)據(jù)規(guī)模比較小，能一次性裝入內(nèi)存呢?比如這題，雖然有一千萬個Query，但是由于重復(fù)度比較高，因此事實上只有300萬的Query，每個Query 255字節(jié)，因此我們可以考慮把他們都放進(jìn)內(nèi)存中去（300萬個字符串假設(shè)沒有重復(fù)，都是最大長度，那么最多占用內(nèi)存3M*1K/4=0.75G。所以可以將所有字符串都存放在內(nèi)存中進(jìn)行處理），而現(xiàn)在只是需要一個合適的數(shù)據(jù)結(jié)構(gòu)，在這里，HashMap絕對是我們優(yōu)先的選擇。

所以我們放棄分而治之hash映射的步驟，直接上hash統(tǒng)計，然后排序。針對此類典型的TOP K問題，采取的對策往往是：HashMap + 堆

HashMap統(tǒng)計對這批海量數(shù)據(jù)預(yù)處理維護(hù)一個Key為Query字串，Value為該串出現(xiàn)次數(shù)的HashMap，即，每次讀取一個Query，如果該字串不在HashMap中，則加入該串，并將Value設(shè)1若該串在HashMap，則將該串的計數(shù)加一最終我們在O(N)的時間復(fù)雜度內(nèi)用HashMap完成了統(tǒng)計堆排序借助堆這個數(shù)據(jù)結(jié)構(gòu)，找出Top K，時間復(fù)雜度為,即借助堆結(jié)構(gòu)，我們可以在log量級的時間內(nèi)查找和調(diào)整。因此，維護(hù)一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進(jìn)行對比。所以，我們最終的時間復(fù)雜度是，（N為1000萬，N’為300萬）。堆排序思路維護(hù)k個元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個數(shù)，并假設(shè)它們即是最大的k個數(shù)，建堆,調(diào)整堆后，有(kmin設(shè)為小頂堆中最小元素)繼續(xù)遍歷數(shù)列，每次遍歷一個元素x，與堆頂元素比較，若，則更新堆(x入堆，用時)，否則不更新堆。這樣下來，總費(fèi)時此方法得益于在堆中，查找等各項操作時間復(fù)雜度均為也可以采用trie樹，關(guān)鍵字域存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)為0最后用10個元素的最小堆來對出現(xiàn)頻率進(jìn)行排序。有一個1G的文件,每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞由上面那兩個例題，分而治之 + hash統(tǒng)計 + 堆/快速排序這個套路再多多驗證下。此題又是文件很大，又是內(nèi)存受限,無非還是分而治之/hash映射順序讀文件中，對于每個詞x，取,然后按照該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k。如果其中的有的文件超過了1M，還可以按照類似的方法繼續(xù)下分，直到分解得到的小文件都不超過1MHashMap統(tǒng)計對每個小文件，采用trie樹/HashMap等統(tǒng)計每個文件中出現(xiàn)的詞以及相應(yīng)的頻率堆/歸并排取出出現(xiàn)頻率最大的100個詞（可以用含100個結(jié)點(diǎn)的最小堆）后，再把100個詞及相應(yīng)的頻率存入文件，這樣又得到了5000個文件。最后就是把這5000個文件進(jìn)行歸并（類似于歸并排序）的過程了。海量數(shù)據(jù)分布在10臺電腦中,想個辦法高效統(tǒng)計出這批數(shù)據(jù)的TOP10,如果每個數(shù)據(jù)元素只出現(xiàn)一次，而且只出現(xiàn)在某一臺機(jī)器中，那么可以采取以下步驟統(tǒng)計出現(xiàn)次數(shù)TOP10的數(shù)據(jù)元素：堆排序在每臺電腦上求出TOP10，可以采用包含10個元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆，比如求TOP10大，我們首先取前10個元素調(diào)整成最小堆，如果發(fā)現(xiàn)，然后掃描后面的數(shù)據(jù)，并與堆頂元素比較，如果比堆頂元素大，那么用該元素替換堆頂，然后再調(diào)整為最小堆。最后堆中的元素就是TOP10大）。求出每臺電腦上的TOP10后，然后把這100臺電腦上的TOP10組合起來，共1000個數(shù)據(jù)，再利用上面類似的方法求出TOP10就可以了。如果同一個元素重復(fù)出現(xiàn)在不同的電腦中呢這個時候，你可以有兩種方法遍歷所有數(shù)據(jù)，重新hash取模，使同一個元素只出現(xiàn)在單獨(dú)的一臺電腦中，然后采用上面所說的方法，統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)找出TOP10，繼而組合100臺電腦上的TOP10，找出最終的TOP10暴力求解：直接統(tǒng)計每臺電腦中各個元素的出現(xiàn)次數(shù)，然后把同一個元素在不同機(jī)器中的出現(xiàn)次數(shù)相加，最終從所有數(shù)據(jù)中找出TOP1010個文件，每個1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求按照query的頻度排序方案1Hash映射順讀10個文件，按照將寫到另外10個文件(記為)中這樣新生成的文件每個的大小大約也1G)(假設(shè)hash函數(shù)較好)HashMap統(tǒng)計找一臺內(nèi)存在2G左右機(jī)器，依次用統(tǒng)計每個頻度注：HashMap(query,query_count)是統(tǒng)計每個query的出現(xiàn)次數(shù)，不是存儲他們的值，出現(xiàn)一次，則+1堆/快速/歸并排序利用快速/堆/歸并排序按頻率排序，將排序好的和對應(yīng)的輸出到文件，就得到了10個排好序的文件

最后，對這10個文件進(jìn)行歸并排序（內(nèi)/外排相結(jié)合）方案2一般query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對于所有的query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用trie樹/HashMap等直接統(tǒng)計每個query出現(xiàn)的次數(shù)，然后按次數(shù)做快速/堆/歸并排序方案3與方案1類似，但在做完hash，分成多個文件后，可以交給多個文件來處理，采用分布式的架構(gòu)來處理（比如MapReduce），最后再進(jìn)行合并給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，找出a、b文件共同的url可估計每個文件的大小為，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制。所以不可能將其完全加載到內(nèi)存中處理?？紤]采取分而治之的方法

分而治之/hash映射遍歷文件a，對每個url求取

然后根據(jù)所取得的值將url分別存儲到1000個小文件

(漏個a1)中。這樣每個小文件大約300M遍歷文件b，采取和a相同方式將url分別存儲到1000個小文件

這樣處理后，所有可能相同的url都在對應(yīng)的小文件

不對應(yīng)的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可

HashSet統(tǒng)計求每對小文件中相同的url時，可以把其中一個小文件的url存儲到HashSet然后遍歷另一個小文件的url，看其是否在剛才構(gòu)建的HashSet中，如果是，那么就是共同的url，存到文件即可

此即第一個秘技再看最后4道題

在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的

先hash然后求模映射為小文件，求出每個小文件中重復(fù)次數(shù)最多的，并記錄重復(fù)次數(shù)最后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的即為所求千萬或上億數(shù)據(jù)（有重復(fù)）,統(tǒng)計次數(shù)最多的前N個數(shù)據(jù)上千萬或上億的數(shù)據(jù)，現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下考慮采用HashMap/搜索二叉樹/紅黑樹等來進(jìn)行統(tǒng)計次數(shù)最后利用堆取出前N個出現(xiàn)次數(shù)最多的數(shù)據(jù)一個文本文件，約一萬行，每行一個詞，統(tǒng)計出其中最頻繁的10個詞，給出思想及時間復(fù)雜度分析方案1如果文件較大,無法一次性讀入內(nèi)存，可采用hash取模，將大文件分解為多個小文件對于單個小文件利用HashMap統(tǒng)計出每個小文件中10個最常出現(xiàn)的詞然后歸并找出最終的10個最常出現(xiàn)的詞方案2通過hash取模將大文件分解為多個小文件后-用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，時間復(fù)雜度(le:單詞平均長度），最終同樣找出出現(xiàn)最頻繁的前10個詞（可用堆來實現(xiàn)），時間復(fù)雜度是O(n*lg10)。

10. 1000萬字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。請怎么設(shè)計和實現(xiàn)？

方案1：這題用trie樹比較合適，hash_map也行。方案2：from xjbzju:，1000w的數(shù)據(jù)規(guī)模插入操作完全不現(xiàn)實，以前試過在stl下100w元素插入set中已經(jīng)慢得不能忍受，覺得基于hash的實現(xiàn)不會比紅黑樹好太多，使用vector+sort+unique都要可行許多，建議還是先hash成小文件分開處理再綜合。

一個文本文件，找出前10個經(jīng)常出現(xiàn)的詞，但這次文件比較長，說是上億行或十億行，總之無法一次讀入內(nèi)存，問最優(yōu)解

方案1：首先根據(jù)用hash并求模，將文件分解為多個小文件，對于單個文件利用上題的方法求出每個文件件中10個最常出現(xiàn)的詞。然后再進(jìn)行歸并處理，找出最終的10個最常出現(xiàn)的詞。

100w個數(shù)中找出最大的100個數(shù)方案1:局部淘汰法

取前100個元素，并排序，記為序列L然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那么把這個最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環(huán)，知道掃描了所有的元素。復(fù)雜度為O(100w*100)。方案2快速排序的思想，每次分割之后只考慮比軸大的部分，知道比軸大的一部分在比100多的時候，采用傳統(tǒng)排序算法排序，取前100個。復(fù)雜度為O(100w*100)方案3在前面的題中，我們已經(jīng)提到了，用一個含100個元素的最小堆完成。復(fù)雜度為O(100w*lg100)。接下來看第二種方法，雙層桶劃分秘技二:雙層桶劃分一種算法設(shè)計思想。面對大量的數(shù)據(jù)我們無法處理時，可以將其分成一個個小任務(wù)，然后根據(jù)一定的策略來處理這些小任務(wù)，從而達(dá)到目的。適用場景第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字基本原理及要點(diǎn)因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進(jìn)行。可以通過多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。

【擴(kuò)展】 當(dāng)有時候需要用一個小范圍的數(shù)據(jù)來構(gòu)造一個大數(shù)據(jù)，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題實例】 1).2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。

有點(diǎn)像鴿巢原理，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。 當(dāng)然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~

2).5億個int找它們的中位數(shù)。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)，之后我們根據(jù)統(tǒng)計結(jié)果就可以判斷中位數(shù)落到那個區(qū)域，同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后第二次掃描我們只統(tǒng)計落在這個區(qū)域中的那些數(shù)就可以了。

實際上，如果不是int是int64，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區(qū)域，然后確定區(qū)域的第幾 大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進(jìn)行統(tǒng)計了。

3).現(xiàn)在有一個0-30000的隨機(jī)數(shù)生成器。請根據(jù)這個隨機(jī)數(shù)生成器，設(shè)計一個抽獎范圍是0-350000彩票中獎號碼列表，其中要包含20000個中獎號碼。

這個題剛好和上面兩個思想相反，一個0到3萬的隨機(jī)數(shù)生成器要生成一個0到35萬的隨機(jī)數(shù)。那么我們完全可以將0-35萬的區(qū)間分成35/3=12個區(qū)間，然后每個區(qū)間的長度都小于等于3萬，這樣我們就可以用題目給的隨機(jī)數(shù)生成器來生成了，然后再加上該區(qū)間的基數(shù)。那么要每個區(qū)間生成多少個隨機(jī)數(shù)呢？計算公式就是：區(qū)間長度隨機(jī)數(shù)密度，在本題目中就是30000（20000/350000）。最后要注意一點(diǎn)，該題目是有隱含條件的：彩票，這意味著你生成的隨機(jī)數(shù)里面不能有重復(fù)，這也是我為什么用雙層桶劃分思想的另外一個原因。

其本質(zhì)上還是分而治之思想,重在"分"

適用范圍：第k大，中位數(shù)，不重復(fù)或重復(fù)的數(shù)字基本原理及要點(diǎn)：元素范圍很大，不能利用直接尋址表，所以多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內(nèi)進(jìn)行2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)整數(shù)個數(shù)為2^32, 也就是，我們可以將這2^32個數(shù),劃分為2^8個區(qū)域(如用單個文件代表一個區(qū)域),然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域再利用bitmap(https://www.jianshu.com/p/a0294f9a321e)就可直接解決也就是說只要有足夠的磁盤空間，就可以很方便的解決。5億個int找它們的中位數(shù)思路一將int劃分為2^16個區(qū)域讀取數(shù)據(jù),統(tǒng)計落到各個區(qū)域里的數(shù)的個數(shù)根據(jù)統(tǒng)計結(jié)果判斷中位數(shù)落到哪個區(qū)域,同時知道這個區(qū)域中的第幾大數(shù)剛好是中位數(shù)第二次掃描,只統(tǒng)計落在這個區(qū)域中的那些數(shù)即可

實際上，如果是long，我們可以經(jīng)過3次這樣的劃分即可降低到可以接受的程度即可以先將long分成2^24個區(qū)域，然后確定區(qū)域的第幾大數(shù)，在將該區(qū)域分成2^20個子區(qū)域，然后確定是子區(qū)域的第幾大數(shù)，然后子區(qū)域里的數(shù)的個數(shù)只有2^20，就可以直接利用direct addr table進(jìn)行統(tǒng)計了。

思路二

同樣需要做兩遍統(tǒng)計，如果數(shù)據(jù)存在硬盤上，就需要讀取2次方法同基排，開一個大小為65536的Int數(shù)組，第一遍讀取，統(tǒng)計Int的高16位，也就是

0-65535，都算作065536 - 131071都算作1就相當(dāng)于用該數(shù)除以65536Int除以 65536的結(jié)果不會超過65536種情況，因此開一個長度為65536的數(shù)組計數(shù)即可每讀取一個數(shù)，數(shù)組中對應(yīng)計數(shù)+1，考慮有負(fù)數(shù)的情況，需要將結(jié)果加32768(因為只用一半)后，記錄在相應(yīng)的數(shù)組內(nèi)。

第一遍統(tǒng)計之后，遍歷數(shù)組累加，看中位數(shù)處于哪個區(qū)間比如處于區(qū)間k，那么0~k-1內(nèi)數(shù)字的數(shù)量sum應(yīng)該<n/2（2.5億）而k+1 ~ 65535的計數(shù)和也<n/2第二遍統(tǒng)計同上面方法，但這次只統(tǒng)計處于區(qū)間k的情況，也就是說(x / 65536) + 32768 = k。統(tǒng)計只統(tǒng)計低16位的情況。并且利用剛才統(tǒng)計的sum，比如sum = 2.49億，那么現(xiàn)在就是要在低16位里面找100萬個數(shù)(2.5億-2.49億)。這次計數(shù)之后，再統(tǒng)計一下，看中位數(shù)所處的區(qū)間，最后將高位和低位組合一下就是結(jié)果

秘技三：Bloom filter/Bitmap

Bloom filter

適用范圍可以用來實現(xiàn)數(shù)據(jù)字典，數(shù)據(jù)判重，集合求交集基本原理及要點(diǎn)對于原理來說很簡單，位數(shù)組+k個獨(dú)立hash函數(shù)。將Hash函數(shù)對應(yīng)的值的位數(shù)組置1，查找時如果發(fā)現(xiàn)所有Hash函數(shù)對應(yīng)位都是1說明存在很明顯這個過程并不保證查找的結(jié)果100%正確的。同時也不支持刪除一個已經(jīng)插入的關(guān)鍵字，因為該關(guān)鍵字對應(yīng)的位會牽動到其他的關(guān)鍵字。所以一個簡單的改進(jìn)就是 counting Bloom filter，用一個counter數(shù)組代替位數(shù)組，就可以支持刪除了Bloom filter將集合中的元素映射到位數(shù)組中，用k(哈希函數(shù)個數(shù))個映射位是否全1表元素是否在該集合Counting bloom filter（CBF）將位數(shù)組中的每一位擴(kuò)展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)。SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。A,B兩個文件，各存放50億條URL，每條URL占用64B，內(nèi)存限制4G，求A,B文件URL交集。如果是三個乃至n個文件呢先計算下內(nèi)存占用，大概大概，若按出錯率0.01算需要大概現(xiàn)在可用340億，相差不多，可能會使出錯率上升另外如果這些url與ip是一一對應(yīng)的，就可以轉(zhuǎn)換成ip，則大大簡單了

同時本題若允許有一定的錯誤率，可使用Bloom filter將其中一個文件中的url使用Bloom filter映射為340億bit，然后挨個讀取另外一個文件的url，檢查是否在Bloom filter，如果是，那么該url應(yīng)該是共同的url（注意會有一定的錯誤率）

BitMap

用一個bit位標(biāo)記某個元素對應(yīng)的Value， 而Key即是該元素由于采用了bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，相對于 HashMap大大節(jié)省

看一個具體的例子，假設(shè)我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（假設(shè)這些元素沒有重復(fù)）。要表示8個數(shù),我們就只需要8個Bit(1Byte),首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0

然后遍歷這5個元素，首先第一個元素是4，那么就把4對應(yīng)的位置為1,因為是從0開始的，所以要把第5位置1

然后遍歷一遍bit區(qū)域，將是1的位的編號輸出（2，3，4，5，7），就達(dá)到了排序的目的。下面的代碼給出了一個BitMap的用法：排序

適用范圍可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下基本原理及要點(diǎn)使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼擴(kuò)展Bloom filter可以看做是對BitMap的擴(kuò)展已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)8位最多99 999 999，大概需要99m個bit，大概十幾M字節(jié)的內(nèi)存即可(可理解為從0~99 999 999的數(shù)字,每個數(shù)字對應(yīng)一個bit位,所以只需要99M個bit約12.4M的Bytes,這樣就用了小小的12.4M左右的內(nèi)存表示了所有的8位數(shù)的電話)在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個整數(shù)方案1采用2-BitMap,每個數(shù)分配2bit00表示不存在01表示出現(xiàn)一次10表示多次11無意義

共需內(nèi)存,尚可接受然后掃描這2.5億個整數(shù)，查看BitMap中相應(yīng)位，如果是00變01，01變10，10保持不變。掃蕩完畢后,查看BitMap,把對應(yīng)位是01的整數(shù)輸出即可

方案2

也可采用與第1題類似的方法，進(jìn)行劃分小文件的方法。然后在小文件中找出不重復(fù)的整數(shù)，并排序。然后再進(jìn)行歸并，注意去除重復(fù)的元素

40億個不重復(fù)的非負(fù)int的整數(shù)，沒排過序，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中

申請512M內(nèi)存，一個bit位代表一個int非負(fù)值。讀入40億個數(shù)，設(shè)置相應(yīng)的bit位，讀入要查詢的數(shù)，查看相應(yīng)bit位是否為1，為1表示存在，為0表示不存在。

秘技四 Trie樹/數(shù)據(jù)庫/倒排索引

Trie樹

適用范圍數(shù)據(jù)量大，重復(fù)多，但數(shù)據(jù)種類少可放入內(nèi)存基本原理及要點(diǎn)實現(xiàn)方式，節(jié)點(diǎn)孩子的表示方式擴(kuò)展壓縮實現(xiàn)一個文本文件，大約一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞用trie樹統(tǒng)計每個詞出現(xiàn)的次數(shù)，時間復(fù)雜度是O(n*le)（le表示單詞的平準(zhǔn)長度），然后找出出現(xiàn)最頻繁的10個數(shù)據(jù)庫索引適用范圍大數(shù)據(jù)量的增刪改查基本原理及要點(diǎn)利用數(shù)據(jù)的設(shè)計實現(xiàn)方法，對海量數(shù)據(jù)的增刪改查倒排索引(Inverted index)適用范圍搜索引擎，關(guān)鍵字查詢基本原理及要點(diǎn)為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。以英文為例，下面是要被索引的文本：T0 = "it is what it is" T1 = "what is it" T2 = "it is a banana"我們就能得到下面的反向文件索引"a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0, 1}檢索的條件"what","is"和"it"將對應(yīng)集合的交集。

　　正向索引開發(fā)出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據(jù)了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關(guān)系?！　U(kuò)展：　　問題實例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索。

秘技五 外排序

適用范圍大數(shù)據(jù)的排序，去重基本原理及要點(diǎn)外排序的歸并方法，置換選擇敗者樹原理，最優(yōu)歸并樹1G大小的一個文件，每一行一個詞，詞大小不超過16B，內(nèi)存限制大小是1M。返回頻數(shù)最高的100詞這個數(shù)據(jù)具有很明顯的特點(diǎn)，詞的大小為16B，但內(nèi)存只有1M,做hash明顯不夠，所以可以用來排序。內(nèi)存可以當(dāng)輸入緩沖區(qū)使用。秘技六 MapReduce計算模型，簡單的說就是將大批量的工作（數(shù)據(jù)）分解（MAP）執(zhí)行，然后再將結(jié)果合并成最終結(jié)果（REDUCE）。這樣做的好處是可以在任務(wù)被分解后，可以通過大量機(jī)器進(jìn)行并行計算，減少整個操作的時間原理就是一個歸并排序。適用范圍數(shù)據(jù)量大，但是數(shù)據(jù)種類小可以放入內(nèi)存基本原理及要點(diǎn)將數(shù)據(jù)交給不同的機(jī)器去處理，數(shù)據(jù)劃分，結(jié)果歸約給讀者看最后一道題，如下：

非常大的文件，裝不進(jìn)內(nèi)存。每行一個int類型數(shù)據(jù)，現(xiàn)在要你隨機(jī)取100個數(shù)。

發(fā)現(xiàn)上述這道題，無論是以上任何一種模式/方法都不好做，那有什么好的別的方法呢？我們可以看看：操作系統(tǒng)內(nèi)存分頁系統(tǒng)設(shè)計(說白了，就是映射+建索引)。

Windows 2000使用基于分頁機(jī)制的虛擬內(nèi)存。每個進(jìn)程有4GB的虛擬地址空間?；诜猪摍C(jī)制，這4GB地址空間的一些部分被映射了物理內(nèi)存，一些部分映射硬盤上的交換文 件，一些部分什么也沒有映射。程序中使用的都是4GB地址空間中的虛擬地址。而訪問物理內(nèi)存，需要使用物理地址。 關(guān)于什么是物理地址和虛擬地址，請看：

物理地址 (physical address): 放在尋址總線上的地址。放在尋址總線上，如果是讀，電路根據(jù)這個地址每位的值就將相應(yīng)地址的物理內(nèi)存中的數(shù)據(jù)放到數(shù)據(jù)總線中傳輸。如果是寫，電路根據(jù)這個 地址每位的值就將相應(yīng)地址的物理內(nèi)存中放入數(shù)據(jù)總線上的內(nèi)容。物理內(nèi)存是以字節(jié)(8位)為單位編址的。虛擬地址 (virtual address): 4G虛擬地址空間中的地址，程序中使用的都是虛擬地址。 使用了分頁機(jī)制之后，4G的地址空間被分成了固定大小的頁，每一頁或者被映射到物理內(nèi)存，或者被映射到硬盤上的交換文件中，或者沒有映射任何東西。對于一 般程序來說，4G的地址空間，只有一小部分映射了物理內(nèi)存，大片大片的部分是沒有映射任何東西。物理內(nèi)存也被分頁，來映射地址空間。對于32bit的 Win2k，頁的大小是4K。CPU用來把虛擬地址轉(zhuǎn)換成物理地址的信息存放在叫做頁目錄和頁表的結(jié)構(gòu)里。

物理內(nèi)存分頁，一個物理頁的大小為4K字節(jié)，第0個物理頁從物理地址 0x00000000 處開始。由于頁的大小為4KB，就是0x1000字節(jié)，所以第1頁從物理地址 0x00001000 處開始。第2頁從物理地址 0x00002000 處開始?？梢钥吹接捎陧摰拇笮∈?KB，所以只需要32bit的地址中高20bit來尋址物理頁。

返回上面我們的題目：非常大的文件，裝不進(jìn)內(nèi)存。每行一個int類型數(shù)據(jù)，現(xiàn)在要你隨機(jī)取100個數(shù)。針對此題，我們可以借鑒上述操作系統(tǒng)中內(nèi)存分頁的設(shè)計方法，做出如下解決方案：

OS中的方法，先生成4G的地址表，在把這個表劃分為小的4M的小文件做個索引，二級索引。30位前十位表示第幾個4M文件，后20位表示在這個4M文件的第幾個，等等，基于key value來設(shè)計存儲，用key來建索引。

程序員學(xué)習(xí)交流請?zhí)砑幽秸n網(wǎng)官方客服微信：mukewang666回復(fù)暗號“前端面試”可進(jìn)前端交流群回復(fù)暗號“Java”可進(jìn)Java交流群回復(fù)暗號“專欄”可進(jìn)程序員交流群作者：芥末無疆鏈接：http://www.imooc.com/article/70235來源：慕課網(wǎng)