海量 URL 去重問題：50 億 URL 找共同項（4G 記憶體限制）

海量 URL 去重問題：50 億 URL 找共同項（4G 記憶體限制）

經典大數據面試題：兩個檔案各 50 億 URL，每 URL 64 字節，記憶體限制 4GB，找出共同 URL。單檔約 320GB，遠超記憶體，需採用分治策略。

問題分析

• 檔案大小：50億 × 64 bytes ≈ 320 GB
• 記憶體：4 GB（無法一次載入）
• 目標：找出檔案 A 和 B 都存在的 URL

分治法解決方案

步驟 1：哈希分桶

# 對檔案 A 分桶
for each url in file_A:
    bucket = hash(url) % 1000
    write url to bucket_A[bucket]

# 對檔案 B 分桶（相同哈希函數）
for each url in file_B:
    bucket = hash(url) % 1000
    write url to bucket_B[bucket]

• 產生 1000 對小檔案：a0 vs b0, a1 vs b1 ... a999 vs b999
• 相同 URL 必落入同一對桶（哈希函數確定性）
• 單桶大小：320GB / 1000 ≈ 320 MB（符合 4GB 記憶體）

步驟 2：逐對處理

for i in 0..999:
    # 載入較小桶建立 HashSet
    hashset = new HashSet()
    for url in bucket_A[i]:
        hashset.add(url)
    
    # 掃描另一桶查找共同項
    for url in bucket_B[i]:
        if hashset.contains(url):
            output url to result_file
    
    # 釋放記憶體
    hashset.clear()

步驟 3：合併結果

將 1000 個結果檔合併為最終答案。

關鍵優化點

替代方案：外部排序 + 歸併

# 1. 將兩檔分別外部排序（歸併排序，利用磁碟）
sort file_A -o sorted_A
sort file_B -o sorted_B

# 2. 雙指標歸併找交集
i = j = 0
while i < len(sorted_A) and j < len(sorted_B):
    if sorted_A[i] == sorted_B[j]:
        output sorted_A[i]
        i++; j++
    elif sorted_A[i] < sorted_B[j]:
        i++
    else:
        j++

• 優點：無哈希碰撞風險、順序 IO 效率高
• 缺點：排序階段耗時較長（O(N log N)）

工程落地建議

1. 語言選擇：Go/Java/C++ 高效能；Python 需用 mmap、array 優化記憶體
2. 分桶數：根據記憶體動態計算 buckets = ceil(file_size / (memory * 0.7))
3. 並行處理：不同桶對可並行處理（多進程/分散式）
4. 斷點續傳：記錄已處理桶索引，支援中斷恢復
5. 進度監控：統計處理行數、耗時、輸出量

擴展場景

• Top K 問題：哈希分桶 + 堆/快選
• 唯一值計數：HyperLogLog、Bitmap
• 多檔交集：擴展為 N 檔，用計數器或 Bitmap
• 近似去重：Bloom Filter、MinHash（允許誤差）

複雜度分析

分桶法是工程上最常用的方案，結合 Bloom Filter 預過濾與遞歸分桶處理傾斜，能穩健解決 TB 級別的大數據去重/交集問題。