前言
面對海量資料處理，單一演算法往往無法滿足所有場景。本文整理 10 種常見處理策略，涵蓋記憶體優化、分治法、分散式計算等，並附上實戰案例分析。
1. Bloom Filter（布隆過濾器）
適用場景
核心原理
位元陣列 + k 個獨立雜湊函數。寫入時將 k 個雜湊位置設為 1；查詢時若所有位置皆為 1 則判定存在（有一定誤判率）。
關鍵參數計算
- 錯誤率 E 時，位元陣列大小 m ≥ n × lg(1/E) × 1.44（n 為元素數）
- 最佳雜湊函數個數 k = (ln2) × (m/n)
- 範例：n=50 億、E=0.01 → m ≈ 650 億 bits（≈8 GB），k ≈ 8
延伸變體
- Counting Bloom Filter：用計數器取代位元，支援刪除
- Spectral Bloom Filter：關聯元素出現頻率
2. Hashing（雜湊表）
適用場景
關鍵點
- 雜湊函數選擇（字串、整數、排列等）
- 衝突處理：Open Hashing（拉鏈法）vs Closed Hashing（開放定址法）
延伸：d-left Hashing
將雜湊表分成 d 個子表，寫入時選擇負載較低的子表，查詢時需檢查 d 個位置。
3. Bit-map（位圖）
適用場景
- 快速查找、去重、刪除；資料範圍在 int 的 10 倍以內
核心概念
用位元陣列標記元素是否存在。例如 8 位數電話號碼最多 99,999,999，約需 12 MB 記憶體。
擴展：2-bit Map
用 2 位元表示狀態：00=未出現、01=出現一次、10=出現多次。可用兩個 bit-map 模擬。
4. Heap（堆積）
適用場景
- 海量資料求前 N 大/小，且 N 較小可放入記憶體
核心策略
- 求前 N 小 → 使用最大堆（維護堆頂為最大值）
- 求前 N 大 → 使用最小堆（維護堆頂為最小值）
- 掃描一次即可得到結果，時間複雜度 O(n log N)
延伸：雙堆維護中位數
5. 雙層桶劃分（分而治之）
核心思想
資料範圍過大無法直接定址時，多次劃分縮小範圍，最後在可接受範圍內處理。
案例
- 2.5 億整數去重：劃分 2^8 區域 → 各區域用 bitmap 處理
- 5 億整數找中位數：先劃分 2^16 區域統計分布 → 定位中位數所在區域 → 二次掃描該區域
- int64 可三次劃分降至 2^20 直接用直接定址表
6. 資料庫索引
利用 B+ 樹等索引結構支援海量資料的增刪改查，適合持久化儲存場景。
7. 倒排索引
適用場景
核心概念
建立「詞 → 包含該詞的文件集合」映射。查詢時取多個詞對應文件集合的交集。
8. 外部排序
適用場景
關鍵技術
9. Trie 樹（字典樹）
適用場景
應用案例
- 10 個 1G 日誌檔案按 query 頻度排序
- 1000 萬字串去重
- 熱門查詢統計（去重後不超過 300 萬）
10. 分散式處理 MapReduce
核心流程
Map: (key, value) → list(key', value')
Reduce: (key', list(value')) → list(value'')
經典案例
- Word Count：Map 輸出 (word, 1)，Reduce 加總
- 100 台機器分布式 TOP10 統計
- N 台機器各 N 個數，找 N² 個數的中位數
經典問題深度分析：上千萬/億級資料求 Top N
可一次讀入記憶體（去重後）
- Trie 樹 / HashMap / 資料庫索引建立字典 → 統計頻率 → 堆維護 Top N
無法一次讀入記憶體
- 字典存硬碟（參考資料庫存儲）
- 分散式 MapReduce：依值或 hash 範圍劃分到不同機器 → 各機器輸出局部 Top N → 歸併得全域 Top N
- 單機模擬：依值範圍分割子檔案 → 逐個處理 → 歸併
- 近似計算：利用自然語言特性，只保留高頻詞字典
關鍵誤區：不可隨機均分資料到各機器，必須按 hash 範圍劃分，否則會導致統計錯誤。
