查找兩個大文件共同的URL

給定 a、b 兩個文件，各存放 50 億個 URL，每個 URL 各占 64B，找出 a、b 兩個文件共同的 URL。內存限制是 4G。

• 操作邏輯：

  • 使用哈希函數 hash(URL) % 1000? 將每個URL映射到0-999的編號

    • 文件A切割為a0, a1, ..., a999?，每個約300MB；文件B同理切割為b0, b1, ..., b999?

  • 關鍵保證：
    相同URL必被哈希到同一編號的小文件。例如，URL "http://example.com"在文件A中分配到a42?，則在文件B中也必分配到b42?

    匹配規則：
    僅需比較同一編號的ai?與bi?，無需跨文件比較（如a3?只與b3?對比）

  • ?

    

    `

1. 為什么必須用哈希分治？直接排序再歸并行嗎？

   排序歸并的瓶頸：
   直接排序需將320GB文件全部排序，歸并時仍需多次I/O，總耗時比分治法更高

   • 哈希分治的優勢：
     通過哈希值直接定位對應文件對，減少無效比較次數

1. 哈希沖突會導致錯誤嗎？

   不影響正確性：
   哈希沖突僅影響不同URL被分到同一文件，但匹配時通過精確比對HashSet中的原始URL可避免誤判