題目描述
給定 a、b 兩個檔案，各存放 50 億個 URL，每個 URL 各佔 64B，記憶體限制是 4G。請找出 a、b兩個檔案共同的 URL。
解答思路
每個 URL 佔 64B，那麼 50 億個 URL佔用的空間大小約為 320GB。5， 000， 000， 000 * 64B ≈ 5GB * 64 = 320GB
由於記憶體大小隻有 4G，因此，我們不可能一次性把所有 URL 載入到記憶體中處理。對於這種型別的題目，一般採用分治策略，即：把一個檔案中的 URL 按照某個特徵劃分為多個小檔案，使得每個小檔案大小不超過 4G，這樣就可以把這個小檔案讀到記憶體中進行處理了。
思路如下：
首先遍歷檔案 a，對遍歷到的 URL 求 hash（URL） % 1000 ，根據計算結果把遍歷到的 URL 儲存到 a 0 ， a 1 ， a 2 ， 。。。， a 999 ，這樣每個大小約為 300MB。使用同樣的方法遍歷檔案 b，把檔案 b 中的URL 分別儲存到檔案 b 0 ， b 1 ， b 2 ， 。。。， b 999 中。這樣處理過後，所有可能相同的 URL 都在對應的小檔案中，即 a 0 對應 b 0 ， 。。。， a 999 對應 b 999 ，不對應的小檔案不可能有相同的 URL。那麼接下來，我們只需要求出這 1000 對小檔案中相同的 URL 就好了。接著遍歷 a i （ i∈［0，999］ ），把 URL 儲存到一個 HashSet 集合中。然後遍歷 b i 中每個 URL，看在 HashSet 集合中是否存在，若存在，說明這就是共同的 URL，可以把這個 URL 儲存到一個單獨的檔案中。
方法總結
1。 分而治之，進行雜湊取餘；
2。 對每個子檔案進行 HashSet 統計。
