對于常見的海量數據處理方法，通常為以下幾種，下面的題解也會圍繞這幾種解法展開

• 位圖 / 布隆過濾器
• 字典樹 / 倒排索引
• 外部排序
• 分治 / 哈希切割 + 堆 / 排序

---

1. 給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。

當我們看到這樣一個題目時，腦海中可能第一時間想到的就是排序 + 二分，但是要知道40億個無符號整數所占據的內存空間達到了16G，這樣的數據是無法放進內存中進行計算的，所以上面的方法無法實現。

我們需要用位圖來完成這道題，我們用一個位來表示一個整數，所以40億個數據也僅僅只占用了500M，然后將所有的數據用直接定址法放入位圖中，并將放入的對應位置1。當進行查詢時，只要位圖的對應位置為1，則說明該數據在這40億個數據中。

---

2. 給定100億個整數，設計算法找到只出現一次的整數？
這道題還是使用位圖來解決，但是由于我們需要找到只出現一次的整數，此時對于每一個整數就存在著3種狀態(出現0次， 出現1次，出現多次),由于一個位只能表示兩種，所以我們需要對位圖進行改造，此時變成用兩個位來映射一個數據。并且00代表出現0次，01代表出現1次，11代表出現多次。此時占據的空間是 1G

但是使用兩個位的位圖映射稍微有一點麻煩，所以可以考慮使用雙位圖來進行解決，一個位圖就代表著一個位，組合起來就是我們需要的結果。做法如下
當數據第一次出現時位圖1對應位置置1，如果位圖1為1后再次出現，則將位圖2對應位置也置1，此時達到最終狀態，對于后面的出現直接忽略。

---

3.給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集？
100億個整數需要40G的內存，所以我們這里還是使用位圖來解決。

方法1：將文件1的整數全部映射到位圖中，接著從文件2中讀取數據，并在位圖中查詢該數據，如果數據存在，則說明該數據是交集之一。內存消耗500M。

方法2：將文件1和文件2中的整數分別映射到位圖1，位圖2中。接著遍歷兩個位圖，對每個位置按位與，如果為1則說明該整數是交集之一，內存消耗1G。

---

4.位圖應用變形：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數
此時的狀態有四種，出現次數為0，出現次數為1，出現次數為2，出現次數超過2。需要用到兩個位表示，所以還是使用第二題的雙位圖來進行解決，00代表1次，01代表2次，10代表2次，11代表多次。消耗內存1G。

---

5.給兩個文件，分別有100億個query，我們只有1G內存，如何找到兩個文件交集？分別給出精確算法和近似算法
query一般為URL中的查詢字符串或者SQL中的查詢語句，假設每個query30個字節，那么100億個query也得300G的內存才能裝下，而我們只有1G，所以直接放棄裝入內存直接比對的做法。

近似算法：對于字符串，也可以采用位圖的思路進行對某個字符串進行標記，也就是使用布隆過濾器來進行處理。但是由于數據過多且空間不足，可能會因為映射時映射到了其他數據的比特位上，導致造成誤判。所以當一個數據不存在于布隆過濾器中，則它必定不存在，但是如果一個數據存在于布隆過濾器中，它也不一定存在，所以布隆過濾器是近似算法。

精確算法：如果要精確的進行查找，那就必須得將數據放入內存中，但是由于數據過大無法一次性放入，所以我們可以考慮對數據進行切分。切割的方式有兩種，哈希切割和平均切割

平均切割： 平均切割不是一個很好的方法，但是它確實是我們很容易就能思考到的方法，我們將兩個文件中的數據平均切分為M份(能放入內存)，分別存儲到一個set中，然后以此將數據進行比較。這種方法就需要以此對所有的數據進行比對，效率會比較低

哈希切割： 這時就可以采取哈希切割的思路，使用字符串哈希算法進行哈希映射，映射位置為i，則放入編號為i的文件中，對兩個文件都采用這樣的做法進行切分，分別為Ai和Bi。
之后，由于我們使用的是同一種字符串哈希算法，所以相同的字符串必定會被映射到同一個編號下的文件中，所以我們只需要依次進入編號相同的Ai和Bi文件中尋找交集即可。

---

6.給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現次數最多的IP地址？ 與上題條件相同，如何找到top K的IP？如何直接用Linux系統命令實現？
統計次數我們首先想到的方法就是使用鍵值對的方式，將每一個string的ip地址與出現次數相關聯，pair<string, int>，然后使用KV模型的Map進行存儲。但是由于數據超過100個G，內存中無法直接存下，所以我們需要對數據進行切割。
我們可以使用哈希切割的方式來解決文件分片的問題。相同的IP地址必定會被映射到同一個文件中，所以我們依次讀取文件，使用Map進行次數統計即可。

之后再進行排序即可

Linux的命令如下

sort log_file | uniq -c | sort -nr | head -k

首先使用sort log_file來將數據進行一個排序，使得相同的IP地址全部靠在一起。接著使用uniq - c進行去重，并將重復的次數顯示在每列的旁邊，通過這個次數來使用sort -nr進行降序排序，使得出現次數最的IP地址在前面，然后使用head -k 獲取前k個IP地址即可。

---

7.100w個數中找出最大的100個數
由于100w個數據并不算多，可以存放進內存中，所以可以考慮以下解法
方法1：采用快排中的partition劃分思想，即單趟劃分后，樞軸s前面的數據都比他大，后面的數據都比他小，此時我們選取其中較大的那一部分，繼續劃分。當劃分后前端的數據剛好等于100后劃分結束，對前端數據進行排序即可得到結果。如果前端數據不足100，則從后端數據進行排序后取出不足的那部分補上，再進行排序即可。O(100w*100)
方法2：局部淘汰法，使用一個大小為100的小堆來完成，維護一個小堆，當數據比堆頂也就是最小值大的時候，用新數據替換掉堆頂，然后調整堆的結構。遍歷完所有數據后就可以得到前100的數據。O(100w*lg100)
方法3：局部淘汰法，使用插入排序來完成，首先取出前100個數據進行排序，然后依次遍歷后面的數據，如果數據大于最小值，則將最小值刪除，然后按照插入排序的思路將數據插入進去。
O(100w*100)

---

8.海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。
解法與上一題類似，可以使用堆來完成
對于每一個電腦，都構建一個大小為10的堆(選大的構建小堆，選小的構建大堆)，選出當前電腦的TOP10。接著將所有電腦的數據匯總起來，共1000個數據，繼續用堆從其中選出TOP10

---

9.給上千個文件，每個文件大小為 1K—100M。給 n 個詞，設計算法對每個詞找到所有包含它的文件，你只有 100K 內存
這題可以使用倒排索引來解決，即建立起單詞——文件的映射。
很簡單，只需要遍歷所有文章，如果文章中出現過查詢詞，則將文件號追加在對應詞的倒排拉鏈中即可。如果100M的文件放不下內存中，就對數據進行切割后處理即可。

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的海量数据处理（二） ：常见海量数据处理方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。