十道海量數據處理面試題與十個方法總結

一、十道海量數據處理面試題

??1、海量日志數據，提取出某日訪問百度次數最多的那個IP。`(分治思想 + 哈希表)`

首先，從日志中提取出所有訪問百度的IP地址，將它們逐個寫入一個大文件中，便于后續處理。
考慮到IP地址是32位的，最多有 2^23 個不同IP。為了減少單個文件的處理壓力，可以采用哈希或者取模的方式，將這些IP均勻分散到 1000個小文件 中。這樣每個小文件的規模大幅縮小，更便于處理。
對于每個小文件，使用 HashMap 統計每個IP的出現次數。HashMap的插入和查找操作都是 O(1) 的復雜度，能夠高效地完成頻率統計。然后從中找出出現頻率最高的IP和對應的頻率。
最后，將這 1000個小文件 中統計出的最高頻率IP和頻率值匯總。再在這1000個IP中執行一次線性掃描，找到頻率最高的IP，得到最終結果。

??2、在1千萬個查詢記錄中，去重后不超過300萬個，要求在內存不超過1G的情況下，統計出最熱門的10個查詢串。`(典型的 Top K 問題)`

該問題是典型的 Top K 問題，可以通過以下兩種方法解決：

1. Hash + 小根堆方法：
首先，使用 Hash表 在 O(N) 的時間復雜度下統計所有查詢串的出現次數。然后，使用一個大小為 K（10） 的 小根堆 來維護出現頻率最高的查詢串。在遍歷300萬個查詢串的統計結果時，每次與堆頂元素比較，如果出現次數更高，則替換堆頂元素并重新調整堆。最終得到Top 10的查詢串。總體時間復雜度為 O(N)+O(N′log?K)。

2. Trie樹 + 小根堆方法：
構建一個 Trie樹，將所有查詢串插入其中，同時在Trie樹的節點中記錄每個查詢串的出現次數。這樣可以有效地管理和存儲大量查詢串。最后，再使用一個大小為 10 的小根堆，對Trie樹中存儲的查詢串進行排序，找出出現次數最多的Top 10。該方法在查詢串較長時，空間效率較高。

??3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。`(分治思想 + 哈希表)`

順序讀取數據，對每個詞 x 進行哈希操作 hash(x) % 5000，將詞分配到5000個小文件中，每個文件約200KB。
如果某個文件超過1MB，可繼續使用類似的方法將其劃分為更小的文件，直到所有小文件的大小都不超過1MB。
對每個小文件，使用 Trie樹 或 HashMap 統計詞頻，并通過維護一個100個節點的小根堆，選出出現頻率最高的100個詞，將結果存入文件。
最終，對這5000個文件進行類似于 歸并排序 的過程，整合并找到全局出現頻率最高的詞。

??4、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序。`(典型的 Top K 問題)`

該問題是典型的 Top K 問題，可以通過以下三種方案解決：

1. 分割+歸并排序方案：
首先，將數據順序讀取，并根據 hash(query) % 10 將查詢串分配到另外10個小文件中，每個文件約1G。然后在一臺 內存2G 的機器上，使用 HashMap 統計每個查詢串的出現次數，再通過 快速排序、堆排序 或 歸并排序 進行排序。最終，將這10個排好序的文件進行歸并排序，得到最終的結果。

2. 直接內存統計方案：
如果所有的查詢串總量有限，可以直接將它們加載到內存中，使用 Trie樹 或 HashMap 統計每個查詢串的出現次數。之后，通過排序算法快速獲取出現次數最多的查詢串。

3. 分布式處理方案：
與方案1類似，數據分割后分配到多個小文件中，但進一步采用 分布式架構（如 MapReduce）進行并行處理。各節點分別統計和排序后，將結果合并，進一步提升處理效率。

??5、給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？`(分治法/布隆過濾器)`

該問題涉及 大規模數據去重和求交集，可通過以下兩種方案解決：

1. 分治法方案：
由于數據量過大無法直接加載到內存中，采用 分治法。

第一步：對兩個文件分別按 hash(url) % 1000 進行劃分，生成1000對小文件。這樣每個小文件的大約為300M，同一哈希值的URL存儲在對應的小文件中。
第二步：對于每對小文件（如a0和b0），使用 HashSet 存儲其中一個小文件的URL，再遍歷另一個小文件，對比URL是否存在于HashSet中，找出共同的URL。

2. Bloom Filter方案：
如果允許一定的錯誤率，可以使用 Bloom Filter。

第一步：使用 4G內存（約340億bit）將一個文件的URL映射到Bloom Filter中。
第二步：讀取另一個文件的URL，逐個檢查是否在Bloom Filter中，若存在則認為是可能的共同URL。由于Bloom Filter存在誤判的可能性，結果需要進一步驗證。

??6、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。`(Bitmap、分治法)`

該問題涉及 大規模數據去重和查找唯一整數，可通過以下兩種方案解決：

1. Bitmap方案：

原理：使用 Bitmap 為每個整數分配 2bit 來表示狀態：
- 00：不存在
- 01：出現一次
- 10：出現多次
- 11：無意義
步驟：掃描整數文件，更新Bitmap狀態。掃描完成后，再遍歷Bitmap，輸出所有狀態為 01 的整數，即為不重復的整數。由于Bitmap占用內存較小，適用于數據量較大的場景。

2. 分治法方案：

原理：如果數據量過大，可以采用 分治法。
步驟：將數據按 hash(num) % N 進行劃分，存入 N個小文件 中，確保同一整數存入同一個文件。對每個小文件使用HashMap或Bitmap統計整數出現次數。然后再排序和歸并這些小文件，同時去重，最終輸出不重復的整數。
此方法在內存受限時非常有效。

??7、騰訊面試題：給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？

該問題涉及 大規模數據查找和去重，可通過以下兩種方案解決：

1. 位圖法（Bitmap）方案：
申請 512M內存，使用 1bit 表示一個無符號整數的存在狀態。讀取40億個數時，將對應位置的bit置為1。查詢時，只需檢查該位置的bit是否為1，即可判斷數是否存在。此方法內存占用小，查詢效率高。

2. 分治法（二分查找）方案：
根據數的 最高位 將數據劃分為兩個文件，一個存儲最高位為0的數，另一個存儲最高位為1的數。根據查詢數的最高位，選擇對應的文件繼續查找。重復這一過程，每次根據下一位劃分數據，類似 二分查找，最終以 O(log?n) 的時間復雜度定位查詢數。此方法適用于超大數據集的查找。

??8、怎么在海量數據中找出重復次數最多的一個？

先做hash，然后求模映射為小文件，求出每個小文件中重復次數最多的一個，并記錄重復次數。然后找出上一步求出的數據中重復次數最多的一個就是所求（具體參考前面的題）。

??9、上千萬或上億數據（有重復），統計其中出現次數最多的前N個數據。

上千萬或上億的數據，現在的機器的內存應該能存下。所以考慮采用hashmap/搜索二叉樹/紅黑樹等來進行統計次數。然后就是取出前N個出現次數最多的數據了，可以用第2題提到的堆機制完成。

??10、一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。

這題是考慮時間效率。用trie樹統計每個詞出現的次數，時間復雜度是O(nle)（le表示單詞的平準長度）。然后是找出出現最頻繁的前10個詞，可以用堆來實現，前面的題中已經講到了，時間復雜度是O(nlg10)。所以總的時間復雜度，是O(nle)與O(nlg10)中較大的那一個。

二、海量數據處理的十大方法總結

在面對超大數據時，無法一次性加載到內存中處理。這時就需要一些高效的算法和數據結構。以下是10個常用方法的詳細總結，包含原理、適用場景和典型問題示例。

📌 1. Bloom Filter（布隆過濾器）

用途

判斷某個數據是否存在于集合中。
適合快速去重、檢測數據是否存在。

原理

使用一個位數組和多個哈希函數。
插入數據時，將數據用哈希函數計算多個位置，將這些位置的位設為1。
判斷數據是否存在時，檢查所有對應的位是否為1。
注意：布隆過濾器會有假陽性（誤判為存在），但不會有假陰性。

優化

Counting Bloom Filter：用計數器代替位數組，支持刪除操作。
Spectral Bloom Filter：支持統計元素的頻次。

典型場景

URL去重：檢測某個網頁是否已被爬取。
垃圾郵件檢測：判斷是否是已知垃圾郵件。
廣告反欺詐：檢測是否重復點擊廣告。

📌 2. Hashing（哈希）

用途

數據快速查找、統計和去重。

原理

使用哈希函數將數據映射到固定大小的哈希表中。
通過哈希表存儲鍵值對，O(1)的時間復雜度完成查找和插入。
解決哈希沖突的方式：鏈地址法、開放地址法。

典型場景

統計某日訪問量最大的IP地址。
判斷兩個大文件中是否有重復的記錄。

📌 3. Bitmap（位圖）

用途

占用極少的空間判斷數據是否存在或進行數據去重。
適用于數據范圍大但數據量相對較小的場景。

原理

用每一位（bit）表示一個數據的存在狀態。
數據值直接映射到位數組中的索引位置，置1表示存在。

優化

使用多bit位圖可以統計數據的出現次數。

典型場景

統計某個地區的所有電話號碼。
2.5億個整數中找出不重復的整數。

📌 4. Heap（堆）

用途

快速找出前N大的數據或前N小的數據。

原理

使用最小堆或最大堆。
當需要找前N大的數據時，用一個大小為N的最小堆。
每次遇到更大的數據時替換堆頂元素。

典型場景

找出100萬個數中最大的前100個數。
實時監控系統中檢測前N個異常事件。

📌 5. 分治法（雙層桶劃分）

用途

解決無法一次性加載到內存的大數據問題。
適合找中位數、第K大元素或去重等問題。

原理

通過哈希函數或簡單取模的方式，將數據劃分到多個桶中。
每個桶的大小控制在內存可處理的范圍內。
在桶內繼續執行相關操作。

典型場景

找出5億個整數的中位數。
找出2.5億個整數中不重復的整數。

📌 6. 數據庫索引

用途

提高大規模數據的查詢效率。

原理

數據庫通過B+樹或哈希索引等結構，為表中的字段創建索引。
查詢時通過索引快速定位數據，而不是全表掃描。

典型場景

電商平臺中商品的快速查詢。
銀行系統中的賬戶查詢。

📌 7. 倒排索引（Inverted Index）

用途

用于關鍵詞搜索場景。
搜索引擎等文本數據場景。

原理

每個單詞對應一個文檔列表，記錄出現位置和頻率。
搜索時將關鍵詞對應的文檔列表取交集，快速獲取結果。

典型場景

搜索引擎中查找包含某個關鍵詞的文章。
論文數據庫中查找包含指定關鍵詞的論文。

📌 8. 外排序

用途

對無法全部加載到內存中的數據進行排序。

原理

使用歸并排序和分塊排序的思想。
將數據分割為若干小塊，每塊在內存中排序后存儲到磁盤。
最后使用多路歸并排序合并結果。

典型場景

處理1G大小的文本文件，內存僅有1M的情況。
大型日志文件的排序與分析。

📌 9. Trie樹

用途

快速查找和前綴匹配。
適用于海量字符串數據的存儲與搜索。

原理

使用樹狀結構存儲字符串，每個節點代表一個字符。
查詢時根據字符逐層匹配，時間復雜度為O(L)，L為字符串長度。

優化

壓縮Trie樹：減少節點數量。

典型場景

搜索引擎的自動補全和聯想詞推薦。
查詢重復的搜索關鍵詞。

📌 10. 分布式處理（MapReduce）

用途

處理超大規模的數據集，常用于分布式環境。

原理

Map階段：將數據分割并分發到多臺機器上進行并行計算。
Reduce階段：對Map階段的結果進行歸約，得到最終結果。

典型場景

日志分析：統計日志中不同類型的訪問次數。
計算全網用戶的行為數據。

🚀 總結與對比

方法	主要用途	優點	缺點	典型場景
Bloom Filter	數據判重	占用內存少、效率高	有誤判率，不支持刪除	URL去重、垃圾郵件檢測
Hashing	快速查找和統計	查找速度快	可能發生哈希沖突	IP訪問統計、數據去重
Bitmap	存儲和判斷數據是否存在	節省內存空間	僅適合整數等有限范圍數據	電話號碼去重、整數計數
Heap	前N大或前N小	時間復雜度低	不適合全量排序	實時監控異常數據
分治法	數據劃分處理	適合大規模數據	需要多次掃描數據	找中位數、查找不重復數據
數據庫索引	快速查詢	查詢效率高	需要額外存儲空間	電商商品查詢、用戶查詢
倒排索引	關鍵詞搜索	查詢速度快	建索引耗時較長	搜索引擎、論文檢索
外排序	數據排序	適合超大數據集	需要磁盤I/O	大型日志排序
Trie樹	字符串查找	前綴匹配高效	空間占用大	搜索聯想、詞頻統計
MapReduce	分布式數據處理	并行處理速度快	部署復雜	日志分析、用戶行為分析