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

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

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

那解決辦法呢?

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

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

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

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

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

本文第一部分、從談到，簡要介紹下，及之區(qū)別(萬丈高樓平地起，基礎(chǔ)最重要)，而本文第二部分，則針對(duì)上述那6種方法模式結(jié)合對(duì)應(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ù)或每個(gè)元素都有一個(gè)鍵值(key)和一個(gè)實(shí)值(value)，即所謂的Key-Value(鍵-值對(duì))set/mapset，同map一樣，所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序，值得注意的是，兩者都不允許兩個(gè)元素有相同的鍵值。不同的是：set的元素不像map那樣可以同時(shí)擁有實(shí)值(value)和鍵值(key)，set元素的鍵值就是實(shí)值，實(shí)值就是鍵值，而map的所有元素同時(shí)擁有實(shí)值(value)和鍵值(key)，pair的第一個(gè)元素被視為鍵值，第二個(gè)元素被視為實(shí)值。hash_set/hash_maphash_set/hash_map，兩者的一切操作都是基于hashtable之上。不同的是，hash_set同set一樣，同時(shí)擁有實(shí)值和鍵值，且實(shí)質(zhì)就是鍵值，鍵值就是實(shí)值，而hash_map同map一樣，每一個(gè)元素同時(shí)擁有一個(gè)實(shí)值(value)和一個(gè)鍵值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具備自動(dòng)排序功能。為什么?因?yàn)閔ashtable沒有自動(dòng)排序功能。

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

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

Hash，就是把任意長度的輸入（又叫做預(yù)映射，pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的函數(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)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”

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

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

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

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

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

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

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

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

還有幾個(gè)問題

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

堆

概念

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

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

這樣就定義了一個(gè)最大堆

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

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

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

那如何出隊(duì)呢

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

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

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

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

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

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

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

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

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

• 分而治之/hash映射遍歷文件a，對(duì)每個(gè)url求取

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

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

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

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

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

此即第一個(gè)秘技再看最后4道題

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

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

10.1000萬字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。請(qǐng)?jiān)趺丛O(shè)計(jì)和實(shí)現(xiàn)？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

思路二

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

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

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

秘技三：Bloomfilter/Bitmap

Bloomfilter

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

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

BitMap

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

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

然后遍歷這5個(gè)元素，首先第一個(gè)元素是4，那么就把4對(duì)應(yīng)的位置為1,因?yàn)槭菑?開始的，所以要把第5位置1

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

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

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

方案2

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

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

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

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

秘技五外排序

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

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

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

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

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

物理內(nèi)存分頁，一個(gè)物理頁的大小為4K字節(jié)，第0個(gè)物理頁從物理地址0x00000000處開始。由于頁的大小為4KB，就是0x1000字節(jié)，所以第1頁從物理地址0x00001000處開始。第2頁從物理地址0x00002000處開始。可以看到由于頁的大小是4KB，所以只需要32bit的地址中高20bit來尋址物理頁。

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

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

程序員學(xué)習(xí)交流請(qǐng)?zhí)砑幽秸n網(wǎng)官方客服微信：mukewang666

回復(fù)暗號(hào)“前端面試”可進(jìn)前端交流群

回復(fù)暗號(hào)“Java”可進(jìn)Java交流群

回復(fù)暗號(hào)“專欄”可進(jìn)程序員交流群

作者：芥末無疆鏈接：http://www.imooc.com/article/70235來源：慕課網(wǎng)