億萬級資料處理的高效解決方案

摘要： 簡介 全文行文是基於面試題的分析基礎之上的，具體實踐過程中，還是得具體情況具體分析，且各個場景下需要考慮的細節也遠比本文所描述的任何一種解決方法複雜得多。 何謂海量資料處理？ 基於海量資料上的儲存、處理、操作。 何謂海量，就是資料量太大，導致要麼是...

簡介

全文行文是基於面試題的分析基礎之上的，具體實踐過程中，還是得具體情況具體分析，且各個場景下需要考慮的細節也遠比本文所描述的任何一種解決方法複雜得多。

何謂海量資料處理？

基於海量資料上的儲存、處理、操作。

何謂海量，就是資料量太大，導致要麼是無法在較短時間內迅速解決，要麼是資料太大，導致無法一次性裝入記憶體。

那解決辦法呢?

• 針對時間，我們可以採用巧妙的演算法搭配合適的資料結構，如Bloom filter/Hash/bit-map/堆/資料庫或倒排索引/trie樹
• 針對空間，無非就一個辦法：大而化小，分而治之（hash對映），把規模大化為規模小的，各個擊破

至於單機及叢集問題，通俗點來講

• 單機就是處理裝載資料的機器有限(只需考慮CPU，記憶體，硬碟的資料互動)
• 叢集，機器有多臺，適合分散式處理，平行計算(更多考慮節點和節點間的資料互動)。

處理海量資料，不外乎

1. 分而治之/hash對映 + hash統計 + 堆/快速/歸併排序
2. 雙層桶劃分
3. Bloom filter/Bitmap；
4. Trie樹/資料庫/倒排索引；
5. 外排序；
6. 分散式處理之Hadoop/Mapreduce。

本文第一部分、從set/map 談到hashtable/hash_map/hash_set ，簡要介紹下set/map/multiset/multimap ，及hash_set/hash_map/hash_multiset/hash_multimap 之區別(萬丈高樓平地起，基礎最重要)，而本文第二部分，則針對上述那6種方法模式結合對應的海量資料處理面試題分別具體闡述。

從set/map到hashtable/hashmap/hashset

• 序列式容器
  vector/list/deque/stack/queue/heap
• 關聯式容器。關聯式容器又分為set(集合)和map(對映表)兩大類，還有第3類關聯式容器，如hashtable(散列表)
  類似關聯式資料庫，每筆資料或每個元素都有一個鍵值(key)和一個實值(value)，即所謂的Key-Value(鍵-值對)

set/map

set，同map一樣，所有元素都會根據元素的鍵值自動被排序，值得注意的是，兩者都不允許兩個元素有相同的鍵值。

不同的是：set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，而map的所有元素同時擁有實值(value)和鍵值(key)，pair的第一個元素被視為鍵值，第二個元素被視為實值。

hash_set/hash_map

hash_set/hash_map，兩者的一切操作都是基於hashtable之上。不同的是，hash_set同set一樣，同時擁有實值和鍵值，且實質就是鍵值，鍵值就是實值，而hash_map同map一樣，每一個元素同時擁有一個實值(value)和一個鍵值(key)，所以其使用方式，和上面的map基本相同。

但由於hash_set/hash_map都是基於hashtable之上，所以不具備自動排序功能。為什麼?因為hashtable沒有自動排序功能。

所以，綜上什麼樣的結構決定其什麼樣的性質，因為set/map都是基於RB-tree之上，所以有自動排序功能，而hash_set/hash_map都是基於hashtable之上，所以不含有自動排序功能，至於加個字首multi_無非就是允許鍵值重複而已。

祕技一:分而治之/Hash對映 + HashMap統計 + 堆/快速/歸併排序

Hash，就是把任意長度的輸入（又叫做預對映， pre-image），通過雜湊演算法，變換成固定長度的輸出，該輸出就是雜湊值。這種轉換是一種壓縮對映，也就是，雜湊值的空間通常遠小於輸入的空間，不同的輸入可能會雜湊成相同的輸出，而不可能從雜湊值來唯一的確定輸入值。簡單的說就是一種將任意長度的訊息壓縮到某一固定長度的函式。

Hash主要用於資訊保安領域中加密演算法，它把一些不同長度的資訊轉化成雜亂的128位的編碼,這些編碼值叫做Hash值. 也可以說，hash就是找到一種資料內容和資料存放地址之間的對映關係。

陣列的特點是：定址容易，插入和刪除困難

連結串列的特點是：定址困難，插入和刪除容易。

那麼我們能不能綜合兩者的特性，做出一種定址容易，插入刪除也容易的資料結構？答案是肯定的，這就是我們要提起的雜湊表，雜湊表有多種不同的實現方法，我接下來解釋的是最常用的一種方法——拉鍊法，我們可以理解為“連結串列的陣列”

左邊很明顯是個陣列，陣列的每個成員包括一個指標，指向一個連結串列的頭，當然這個連結串列可能為空，也可能元素很多。我們根據元素的一些特徵把元素分配到不同的連結串列中去，也是根據這些特徵，找到正確的連結串列，再從連結串列中找出這個元素。

元素特徵轉變為陣列下標的方法就是雜湊法

• 除法雜湊法

  最直觀的一種，上圖使用的就是這種雜湊法，公式：

  index = value % 16
  

  學過彙編的都知道，求模數其實是通過一個除法運算得到的，所以叫“除法雜湊法”。

• 平方雜湊法

  求index是非常頻繁的操作，而乘法的運算要比除法來得省時，所以我們考慮把除法換成乘法和一個位移操作。公式：

  index = (value * value) >> 28
  

  如果數值分配比較均勻的話這種方法能得到不錯的結果，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題，value如果很大，value * value不會溢位嗎？答案是會的，但我們這個乘法不關心溢位，因為我們根本不是為了獲取相乘結果，而是為了獲取index。

• 斐波那契（Fibonacci）雜湊法

  平方雜湊法的缺點是顯而易見的，所以我們能不能找出一個理想的乘數，而不是拿value本身當作乘數呢？答案是肯定的。

  1，對於16位整數而言，這個乘數是40503

  2，對於32位整數而言，這個乘數是2654435769

  3，對於64位整數而言，這個乘數是11400714819323198485

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

對我們常見的32位整數而言，公式：

index = (value * 2654435769) >> 28

如果用這種斐波那契雜湊法的話，那我上面的圖就變成這樣了：

很明顯，用斐波那契雜湊法調整之後要比原來的取模雜湊法好很多。

• 適用範圍
  快速查詢，刪除的基本資料結構，通常需要總資料量可以放入記憶體。
• 基本原理及要點
  Hash函式選擇，針對字串，整數，排列，具體相應的hash方法
  碰撞處理，一種是開放雜湊法，亦拉鍊法；另一種就是closed hashing，也稱開地址法，opened addressing。
• 擴充套件
  d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個雜湊表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個雜湊函式，h1和h2。在儲存一個新的key時，同 時用兩個雜湊函式進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經儲存的（有碰撞的）key比較多，然後將新key儲存在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都儲存了一個key，就把新key 儲存在左邊的T1子表中，2-left也由此而來。在查詢一個key時，必須進行兩次hash，同時查詢兩個位置。

海量日誌資料，提取出某日訪問百度次數最多的那個IP

無非分而治之/hash對映 + hash統計 + 堆/快速/歸併排序，說白了，就是先對映，後統計，最後排序

• 分而治之/hash對映
  針對資料太大，記憶體受限，只能把大檔案化成(取模對映)小檔案
• HashMap統計：當大檔案轉化了小檔案，便可以採用常規的HashMap(ip，value)進行頻率統計
• 堆/快速排序
  統計完了之後，進行排序(可採取堆排序)，得到次數最多的IP

首先是這一天，並且是訪問百度的日誌中的IP取出來，逐個寫入到一個大檔案中。

注意到IP是32位的，最多有個2^32個IP。同樣可以採用對映的方法，比如%1000，把整個大檔案對映為1000個小檔案，再找出每個小文中出現頻率最大的IP（可以採用HashMap對那1000個檔案中的所有IP進行頻率統計，然後依次找出各個檔案中頻率最大的那個IP）及相應的頻率。然後再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

還有幾個問題

• Hash取模是一種等價對映，不會存在同一個元素分散到不同小檔案中的情況，即這裡採用的是mod 1000演算法，那麼相同的IP在hash取模後，只可能落在同一個檔案中，不可能被分散
• 那到底什麼是hash對映呢？
  簡單來說，就是為了便於計算機在有限的記憶體中處理大資料，從而通過一種對映雜湊的方式讓資料均勻分佈在對應的記憶體位置(如大資料通過取餘的方式對映成小樹存放在記憶體中，或大檔案對映成多個小檔案)，而這個對映雜湊方式便是我們通常所說的hash函式，好的hash函式能讓資料均勻分佈而減少衝突。儘管資料對映到了另外一些不同的位置，但資料還是原來的資料，只是代替和表示這些原始資料的形式發生了變化而已

堆

概念

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

• 每個節點的值都大於(或者都小於，即最小堆)其子節點的值
• 樹完全平衡的，並且最後一層的樹葉都在最左邊

這樣就定義了一個最大堆

• 二叉堆

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

最小的一個元素就是陣列第一個元素,那麼二叉堆這種有序佇列如何入隊呢

假設要在這個二叉堆裡入隊一個單元，鍵值為2，那隻需在陣列末尾加入這個元素，然後儘可能把這個元素往上挪，直到挪不動，經過了這種複雜度為Ο(logn)的操作，二叉堆還是二叉堆。

那如何出隊呢

出隊一定是出陣列的第一個元素，這麼來第一個元素以前的位置就成了空位，我們需要把這個空位挪至葉子節點，然後把陣列最後一個元素插入這個空位，把這個“空位”儘量往上挪。這種操作的複雜度也是Ο(logn)

• 適用範圍
  海量資料前n大，並且n比較小，堆可以放入記憶體
• 基本原理及要點
  最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆裡的最大元素，如果它小於最大元素，則應該替換那個最大元 素。這樣最後得到的n個元素就是最小的n個。適合大資料量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。
• 擴充套件
  雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

100w個數中找最大的前100個數

用一個100個元素大小的最小堆即可。

尋找熱門查詢，300萬個查詢字串中統計最熱門的10個查詢

搜尋引擎會通過日誌檔案把使用者每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255位元組。假設目前有一千萬個記錄（這些查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個。一個查詢串的重複度越高，說明查詢它的使用者越多，也就是越熱門），請你統計最熱門的10個查詢串，要求使用的記憶體不能超過1G。

解答：由上題，我們知道，資料大則劃為小的，如一億個IP求Top 10，可先%1000 將IP分到1000個小檔案中去，並保證一種IP只出現在一個檔案中，再對每個小檔案中的IP進行HashMap計數統計並按數量排序，最後歸併或者最小堆依次處理每個小檔案的Top10以得到最後的結果

但如果資料規模比較小，能一次性裝入記憶體呢?比如這題，雖然有一千萬個Query，但是由於重複度比較高，因此事實上只有300萬的Query，每個Query 255位元組，因此我們可以考慮把他們都放進記憶體中去（300萬個字串假設沒有重複，都是最大長度，那麼最多佔用記憶體3M*1K/4=0.75G。所以可以將所有字串都存放在記憶體中進行處理），而現在只是需要一個合適的資料結構，在這裡，HashMap絕對是我們優先的選擇。

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

• HashMap統計

  對這批海量資料預處理

  維護一個Key為Query字串，Value為該串出現次數的HashMap，即HashMap(Query，Value) ，每次讀取一個Query，如果該字串不在HashMap中，則加入該串，並將Value設1

  若該串在HashMap，則將該串的計數加一

  最終我們在O(N)的時間複雜度內用HashMap完成了統計

• 堆排序

  藉助堆這個資料結構，找出Top K，時間複雜度為N*logK ,即藉助堆結構，我們可以在log量級的時間內查詢和調整。

  因此，維護一個K(該題目中是10)大小的小根堆，然後遍歷300萬的Query，分別和根元素進行對比。

  所以，我們最終的時間複雜度是O（N） + N' * O（logK） ，（N為1000萬，N’為300萬）。

• 堆排序思路

  維護k個元素的最小堆，即用容量為k的最小堆儲存最先遍歷到的k個數，並假設它們即是最大的k個數，建堆O(k) ,調整堆O(logk) 後，有

  k1>k2>...kmin (kmin設為小頂堆中最小元素)

  繼續遍歷數列，每次遍歷一個元素x，與堆頂元素比較，若x>kmin ，則更新堆(x入堆，用時logk )，否則不更新堆。這樣下來，總費時O（k*logk+（n-k）*logk）=O（n*logk）
  此方法得益於在堆中，查詢等各項操作時間複雜度均為logk
  

  也可以採用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0

  最後用10個元素的最小堆來對出現頻率進行排序。

有一個1G的檔案,每一行是一個詞，詞的大小不超過16位元組，記憶體限制大小是1M。返回頻數最高的100個詞

由上面那兩個例題，分而治之 + hash統計 + 堆/快速排序這個套路再多多驗證下。此題又是檔案很大，又是記憶體受限,無非還是

• 分而治之/hash對映
  順序讀檔案中，對於每個詞x，取hash(x)%5000 ,然後按照該值存到5000個小檔案（記為x0,x1,...x4999）中。這樣每個檔案大概是200k。
  如果其中的有的檔案超過了1M，還可以按照類似的方法繼續下分，直到分解得到的小檔案都不超過1M
• HashMap統計
  對每個小檔案，採用trie樹/HashMap等統計每個檔案中出現的詞以及相應的頻率
• 堆/歸併排
  取出出現頻率最大的100個詞（可以用含100個結點的最小堆）後，再把100個詞及相應的頻率存入檔案，這樣又得到了5000個檔案。最後就是把這5000個檔案進行歸併（類似於歸併排序）的過程了。

海量資料分佈在10臺電腦中,想個辦法高效統計出這批資料的TOP10,如果每個資料元素只出現一次，而且只出現在某一臺機器中，那麼可以採取以下步驟統計出現次數TOP10的資料元素：

• 堆排序
  在每臺電腦上求出TOP10，可以採用包含10個元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆，比如求TOP10大，我們首先取前10個元素調整成最小堆，如果發現，然後掃描後面的資料，並與堆頂元素比較，如果比堆頂元素大，那麼用該元素替換堆頂，然後再調整為最小堆。最後堆中的元素就是TOP10大）。
• 求出每臺電腦上的TOP10後，然後把這100臺電腦上的TOP10組合起來，共1000個數據，再利用上面類似的方法求出TOP10就可以了。

如果同一個元素重複出現在不同的電腦中呢

這個時候，你可以有兩種方法

• 遍歷所有資料，重新hash取模，使同一個元素只出現在單獨的一臺電腦中，然後採用上面所說的方法，統計每臺電腦中各個元素的出現次數找出TOP10，繼而組合100臺電腦上的TOP10，找出最終的TOP10
• 暴力求解：直接統計每臺電腦中各個元素的出現次數，然後把同一個元素在不同機器中的出現次數相加，最終從所有資料中找出TOP10

10個檔案，每個1G，每個檔案的每一行存放的都是使用者的query，每個檔案的query都可能重複。要求按照query的頻度排序

方案1

• Hash對映
  順讀10個檔案，按照hash(query)%10 將query 寫到另外10個檔案(記為a0,a1,..a9 )中
  這樣新生成的檔案每個的大小大約也1G)(假設hash函式較好)
• HashMap統計
  找一臺記憶體在2G左右機器，依次用HashMap(query, query_count) 統計每個query 頻度
  注：HashMap(query,query_count)是統計每個query的出現次數，不是儲存他們的值，出現一次，則count +1
• 堆/快速/歸併排序
  利用快速/堆/歸併排序按頻率排序，將排序好的query 和對應的query_cout 輸出到檔案，就得到了10個排好序的檔案
  
  最後，對這10個檔案進行歸併排序（內/外排相結合）

方案2

一般query的總量是有限的，只是重複的次數比較多而已，可能對於所有的query，一次性就可以加入到記憶體了。這樣，我們就可以採用trie樹/HashMap等直接統計每個query出現的次數，然後按次數做快速/堆/歸併排序

方案3

與方案1類似，但在做完hash，分成多個檔案後，可以交給多個檔案來處理，採用分散式的架構來處理（比如MapReduce），最後再進行合併

給定a、b兩個檔案，各存放50億個url，每個url各佔64位元組，記憶體限制是4G，找出a、b檔案共同的url

可估計每個檔案的大小為5G×64=320G ，遠遠大於記憶體限制。所以不可能將其完全載入到記憶體中處理。考慮採取分而治之的方法

• 分而治之/hash對映

  遍歷檔案a，對每個url求取

  

  然後根據所取得的值將url分別儲存到1000個小檔案

  

  (漏個a1)中。

  這樣每個小檔案大約300M

  遍歷檔案b，採取和a相同方式將url分別儲存到1000個小檔案

  

  這樣處理後，所有可能相同的url都在對應的小檔案

  

  不對應的小檔案不可能有相同的url。然後我們只要求出1000對小檔案中相同的url即可

• HashSet統計
  求每對小檔案中相同的url時，可以把其中一個小檔案的url儲存到HashSet
  然後遍歷另一個小檔案的url，看其是否在剛才構建的HashSet中，如果是，那麼就是共同的url，存到檔案即可

在海量資料中找出重複次數最多的

• 先hash
• 然後求模對映為小檔案，求出每個小檔案中重複次數最多的，並記錄重複次數
• 最後找出上一步求出的資料中重複次數最多的即為所求

千萬或上億資料（有重複）,統計次數最多的前N個數據

• 上千萬或上億的資料，現在的機器的記憶體應該能存下
• 考慮採用HashMap/搜尋二叉樹/紅黑樹等來進行統計次數
• 最後利用堆取出前N個出現次數最多的資料

一個文字檔案，約一萬行，每行一個詞，統計出其中最頻繁的10個詞，給出思想及時間複雜度分析

方案1

• 如果檔案較大,無法一次性讀入記憶體，可採用hash取模，將大檔案分解為多個小檔案
• 對於單個小檔案利用HashMap統計出每個小檔案中10個最常出現的詞
• 然後歸併
• 找出最終的10個最常出現的詞

方案2

• 通過hash取模將大檔案分解為多個小檔案後

  -用trie樹統計每個詞出現的次數，時間複雜度O(n*le) (le:單詞平均長度），最終同樣找出出現最頻繁的前10個詞（可用堆來實現），時間複雜度是O(n*lg10)。

10. 1000萬字符串，其中有些是重複的，需要把重複的全部去掉，保留沒有重複的字串。請怎麼設計和實現？

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

一個文字檔案，找出前10個經常出現的詞，但這次檔案比較長，說是上億行或十億行，總之無法一次讀入記憶體，問最優解

方案1：首先根據用hash並求模，將檔案分解為多個小檔案，對於單個檔案利用上題的方法求出每個檔案件中10個最常出現的詞。然後再進行歸併處理，找出最終的10個最常出現的詞。

100w個數中找出最大的100個數

方案1:區域性淘汰法

• 取前100個元素，並排序，記為序列L
• 然後一次掃描剩餘的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那麼把這個最小的元素刪除，並把x利用插入排序的思想，插入到序列L中。依次迴圈，知道掃描了所有的元素。複雜度為O(100w*100)。

方案2

快速排序的思想，每次分割之後只考慮比軸大的部分，知道比軸大的一部分在比100多的時候，採用傳統排序演算法排序，取前100個。複雜度為O(100w*100)

方案3

在前面的題中，我們已經提到了，用一個含100個元素的最小堆完成。複雜度為O(100w*lg100)。

接下來看第二種方法，雙層桶劃分

祕技二:雙層桶劃分

一種演算法設計思想。面對大量的資料我們無法處理時，可以將其分成一個個小任務，然後根據一定的策略來處理這些小任務，從而達到目的。

• 適用場景
  第k大，中位數，不重複或重複的數字
• 基本原理及要點
  因為元素範圍很大，不能利用直接定址表，所以通過多次劃分，逐步確定範圍，然後最後在一個可以接受的範圍內進行。可以通過多次縮小，雙層只是一個例子，分治才是其根本（只是“只分不治”）。

【擴充套件】當有時候需要用一個小範圍的資料來構造一個大資料，也是可以利用這種思想，相比之下不同的，只是其中的逆過程。

【問題例項】 1).2.5億個整數中找出不重複的整數的個數，記憶體空間不足以容納這2.5億個整數。

有點像鴿巢原理，整數個數為2

32,也就是，我們可以將這2

32個數，劃分為2^8個區域(比如用單個檔案代表一個區域)，然後將資料分離到不同的區域，然後不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁碟空間，就可以很方便的解決。 當然這個題也可以用我們前面講過的BitMap方法解決，正所謂條條大道通羅馬~~~

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

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然後讀取資料統計落到各個區域裡的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然後確定區域的第幾 大數，在將該區域分成2

20個子區域，然後確定是子區域的第幾大數，然後子區域裡的數的個數只有2

20，就可以直接利用direct addr table進行統計了。

3).現在有一個0-30000的隨機數生成器。請根據這個隨機數生成器，設計一個抽獎範圍是0-350000彩票中獎號碼列表，其中要包含20000箇中獎號碼。

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

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

• 適用範圍：第k大，中位數，不重複或重複的數字
• 基本原理及要點：元素範圍很大，不能利用直接定址表，所以多次劃分，逐步確定範圍，然後最後在一個可以接受的範圍內進行

2.5億個整數中找出不重複的整數的個數，記憶體空間不足以容納這2.5億個整數

整數個數為2^32, 也就是，我們可以將這2

32個數,劃分為2

8個區域(如用單個檔案代表一個區域),然後將資料分離到不同的區域，然後不同的區域再利用bitmap(ofollow,noindex">https://www.jianshu.com/p/a0294f9a321e )就可直接解決

也就是說只要有足夠的磁碟空間，就可以很方便的解決。

5億個int找它們的中位數

思路一

• 將int劃分為2^16個區域
• 讀取資料,統計落到各個區域裡的數的個數
• 根據統計結果判斷中位數落到哪個區域,同時知道這個區域中的第幾大數剛好是中位數
• 第二次掃描,只統計落在這個區域中的那些數即可

實際上，如果是long，我們可以經過3次這樣的劃分即可降低到可以接受的程度

即可以先將long分成2

24個區域，然後確定區域的第幾大數，在將該區域分成2

20個子區域，然後確定是子區域的第幾大數，然後子區域裡的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

思路二

同樣需要做兩遍統計，如果資料存在硬碟上，就需要讀取2次

方法同基排，開一個大小為65536的Int陣列，第一遍讀取，統計Int的高16位，也就是

• 0-65535，都算作0
• 65536 - 131071都算作1
  就相當於用該數除以65536
  Int除以 65536的結果不會超過65536種情況，因此開一個長度為65536的陣列計數即可
  每讀取一個數，陣列中對應計數+1，考慮有負數的情況，需要將結果加32768(因為只用一半)後，記錄在相應的陣列內。

第一遍統計之後，遍歷陣列累加，看中位數處於哪個區間

比如處於區間k，那麼0~k-1內數字的數量sum應該<n/2（2.5億）

而k+1 ~ 65535的計數和也<n/2

第二遍統計同上面方法，但這次只統計處於區間k的情況，也就是說(x / 65536) + 32768 = k。統計只統計低16位的情況。並且利用剛才統計的sum，比如sum = 2.49億，那麼現在就是要在低16位裡面找100萬個數(2.5億-2.49億)。這次計數之後，再統計一下，看中位數所處的區間，最後將高位和低位組合一下就是結果

祕技三：Bloom filter/Bitmap

Bloom filter

• 適用範圍
  可以用來實現資料字典，資料判重，集合求交集
• 基本原理及要點
  對於原理來說很簡單，位陣列+k個獨立hash函式。
  將Hash函式對應的值的位陣列置1，查詢時如果發現所有Hash函式對應位都是1說明存在
  很明顯這個過程並不保證查詢的結果100%正確的。
  同時也不支援刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。
  所以一個簡單的改進就是 counting Bloom filter，用一個counter陣列代替位陣列，就可以支援刪除了
  Bloom filter將集合中的元素對映到位陣列中，用k(雜湊函式個數)個對映位是否全1表元素是否在該集合
  Counting bloom filter（CBF）將位陣列中的每一位擴充套件為一個counter，從而支援了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF採用counter中的最小值來近似表示元素的出現頻率。

A,B兩個檔案，各存放50億條URL，每條URL佔用64B，記憶體限制4G，求A,B檔案URL交集。如果是三個乃至n個檔案呢

• 先計算下記憶體佔用，4G=2^32 大概40億*8 大概340億bit
n=50億 ，若按出錯率0.01算需要大概650億bit
  

  現在可用340億，相差不多，可能會使出錯率上升

  另外如果這些url與ip是一一對應的，就可以轉換成ip，則大大簡單了

同時本題若允許有一定的錯誤率，可使用Bloom filter

將其中一個檔案中的url使用Bloom filter對映為340億bit，然後挨個讀取另外一個檔案的url，檢查是否在Bloom filter，如果是，那麼該url應該是共同的url（注意會有一定的錯誤率）

BitMap

用一個bit位標記某個元素對應的Value， 而Key即是該元素

由於採用了bit為單位來儲存資料，因此在儲存空間方面，相對於 HashMap大大節省

看一個具體的例子，假設我們要對0-7內的5個元素(4,7,2,5,3)排序（假設這些元素沒有重複）。

要表示8個數,我們就只需要8個Bit(1Byte),首先我們開闢1Byte的空間，將這些空間的所有Bit位都置為0

然後遍歷這5個元素，首先第一個元素是4，那麼就把4對應的位置為1,因為是從0開始的，所以要把第5位置1

然後遍歷一遍bit區域，將是1的位的編號輸出（2，3，4，5，7），就達到了排序的目的。下面的程式碼給出了一個BitMap的用法：排序

//定義每個Byte中有8個Bit位
#include ＜memory.h＞
#define BYTESIZE 8
void SetBit(char *p, int posi)
{
for(int i=0; i ＜ (posi/BYTESIZE); i++)
{
p++;
}
 
*p = *p|(0x01＜＜(posi%BYTESIZE));//將該Bit位賦值1
return;
}
 
void BitMapSortDemo()
{
//為了簡單起見，我們不考慮負數
int num[] = {3,5,2,10,6,12,8,14,9};
 
//BufferLen這個值是根據待排序的資料中最大值確定的
//待排序中的最大值是14，因此只需要2個Bytes(16個Bit)
//就可以了。
const int BufferLen = 2;
char *pBuffer = new char[BufferLen];
 
//要將所有的Bit位置為0，否則結果不可預知。
memset(pBuffer,0,BufferLen);
for(int i=0;i＜9;i++)
{
//首先將相應Bit位上置為1
SetBit(pBuffer,num[i]);
}
 
//輸出排序結果
for(int i=0;i＜BufferLen;i++)//每次處理一個位元組(Byte)
{
for(int j=0;j＜BYTESIZE;j++)//處理該位元組中的每個Bit位
{
//判斷該位上是否是1，進行輸出，這裡的判斷比較笨。
//首先得到該第j位的掩碼（0x01＜＜j），將記憶體區中的
//位和此掩碼作與操作。最後判斷掩碼是否和處理後的
//結果相同
if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j))
{
printf("%d ",i*BYTESIZE + j);
}
}
pBuffer++;
}
}
 
int _tmain(int argc, _TCHAR* argv[])
{
BitMapSortDemo();
return 0;
}

• 適用範圍
  可進行資料的快速查詢，判重，刪除，一般來說資料範圍是int的10倍以下
• 基本原理及要點
  使用bit陣列來表示某些元素是否存在，比如8位電話號碼
• 擴充套件
  Bloom filter可以看做是對BitMap的擴充套件

已知某個檔案內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數

8位最多99 999 999，大概需要99m個bit，大概十幾M位元組的記憶體即可(可理解為從0~99 999 999的數字,每個數字對應一個bit位,所以只需要99M個bit約12.4M的Bytes,這樣就用了小小的12.4M左右的記憶體表示了所有的8位數的電話)

在2.5億個整數中找出不重複的整數，注，記憶體不足以容納這2.5億個整數

方案1

採用2-BitMap,每個數分配2bit

• 00表示不存在
• 01表示出現一次
• 10表示多次
• 11無意義

共需記憶體2^32 * 2 bit=1 GB ,尚可接受

然後掃描這2.5億個整數，檢視BitMap中相應位，如果是00變01，01變10，10保持不變。

掃蕩完畢後,檢視BitMap,把對應位是01的整數輸出即可

方案2

也可採用與第1題類似的方法，進行劃分小檔案的方法。然後在小檔案中找出不重複的整數，並排序。然後再進行歸併，注意去除重複的元素

40億個不重複的非負int的整數，沒排過序，然後再給一個數，如何快速判斷這個數是否在那40億個數當中

申請512M記憶體，一個bit位代表一個int非負值。讀入40億個數，設定相應的bit位，讀入要查詢的數，檢視相應bit位是否為1，為1表示存在，為0表示不存在。

祕技四 Trie樹/資料庫/倒排索引

Trie樹

• 適用範圍
  資料量大，重複多，但資料種類少可放入記憶體
• 基本原理及要點
  實現方式，節點孩子的表示方式
• 擴充套件
  壓縮實現

一個文字檔案，大約一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞

用trie樹統計每個詞出現的次數，時間複雜度是O(n*le)（le表示單詞的平準長度），然後找出出現最頻繁的10個

資料庫索引

• 適用範圍
  大資料量的增刪改查
• 基本原理及要點
  利用資料的設計實現方法，對海量資料的增刪改查

倒排索引(Inverted index)

• 適用範圍
  搜尋引擎，關鍵字查詢
• 基本原理及要點
  為何叫倒排索引？一種索引方法，被用來儲存在全文搜尋下某個單詞在一個文件或者一組文件中的儲存位置的對映。
  以英文為例，下面是要被索引的文字：

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"將對應集合的交集。

正向索引開發出來用來儲存每個文件的單詞的列表。正向索引的查詢往往滿足每個文件有序頻繁的全文查詢和每個單詞在校驗文件中的驗證這樣的查詢。在正向索引中，文件佔據了中心的位置，每個文件指向了一個它所包含的索引項的序列。也就是說文件指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文件，很容易看到這個反向的關係。

擴充套件：

問題例項：文件檢索系統，查詢那些檔案包含了某單詞，比如常見的學術論文的關鍵字搜尋。

祕技五 外排序

• 適用範圍
  大資料的排序，去重
• 基本原理及要點
  外排序的歸併方法，置換選擇敗者樹原理，最優歸併樹

1G大小的一個檔案，每一行一個詞，詞大小不超過16B，記憶體限制大小是1M。返回頻數最高的100詞

這個資料具有很明顯的特點，詞的大小為16B，但記憶體只有1M,做hash明顯不夠，所以可以用來排序。記憶體可以當輸入緩衝區使用。

祕技六 MapReduce

計算模型，簡單的說就是將大批量的工作（資料）分解（MAP）執行，然後再將結果合併成最終結果（REDUCE）。這樣做的好處是可以在任務被分解後，可以通過大量機器進行平行計算，減少整個操作的時間原理就是一個歸併排序。

• 適用範圍
  資料量大，但是資料種類小可以放入記憶體
• 基本原理及要點
  將資料交給不同的機器去處理，資料劃分，結果歸約給讀者看最後一道題，如下：

非常大的檔案，裝不進記憶體。每行一個int型別資料，現在要你隨機取100個數。

發現上述這道題，無論是以上任何一種模式/方法都不好做，那有什麼好的別的方法呢？我們可以看看：作業系統記憶體分頁系統設計(說白了，就是對映+建索引)。

Windows 2000使用基於分頁機制的虛擬記憶體。每個程序有4GB的虛擬地址空間。基於分頁機制，這4GB地址空間的一些部分被映射了實體記憶體，一些部分對映硬碟上的交換文 件，一些部分什麼也沒有對映。程式中使用的都是4GB地址空間中的虛擬地址。而訪問實體記憶體，需要使用實體地址。 關於什麼是實體地址和虛擬地址，請看：

• 實體地址 (physical address): 放在定址總線上的地址。放在定址總線上，如果是讀，電路根據這個地址每位的值就將相應地址的實體記憶體中的資料放到資料匯流排中傳輸。如果是寫，電路根據這個 地址每位的值就將相應地址的實體記憶體中放入資料匯流排上的內容。實體記憶體是以位元組(8位)為單位編址的。

• 虛擬地址 (virtual address): 4G虛擬地址空間中的地址，程式中使用的都是虛擬地址。 使用了分頁機制之後，4G的地址空間被分成了固定大小的頁，每一頁或者被對映到實體記憶體，或者被對映到硬碟上的交換檔案中，或者沒有對映任何東西。對於一 般程式來說，4G的地址空間，只有一小部分映射了實體記憶體，大片大片的部分是沒有對映任何東西。實體記憶體也被分頁，來對映地址空間。對於32bit的 Win2k，頁的大小是4K。CPU用來把虛擬地址轉換成實體地址的資訊存放在叫做頁目錄和頁表的結構裡。

  實體記憶體分頁，一個物理頁的大小為4K位元組，第0個物理頁從實體地址 0x00000000 處開始。由於頁的大小為4KB，就是0x1000位元組，所以第1頁從實體地址 0x00001000 處開始。第2頁從實體地址 0x00002000 處開始。可以看到由於頁的大小是4KB，所以只需要32bit的地址中高20bit來定址物理頁。

  返回上面我們的題目：非常大的檔案，裝不進記憶體。每行一個int型別資料，現在要你隨機取100個數。針對此題，我們可以借鑑上述作業系統中記憶體分頁的設計方法，做出如下解決方案：

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