面試經(jīng)歷：如何從 100 億 URL 中找出相同的 URL？
點擊上方?藍(lán)字?關(guān)注我們！
題目描述
解答思路
方法總結(jié)
題目描述
給定 a、b 兩個文件，各存放 50 億個 URL，每個 URL 各占 64B，內(nèi)存限制是 4G。請找出 a、b 兩個文件共同的 URL。
解答思路
每個 URL 占 64B，那么 50 億個 URL占用的空間大小約為 320GB。
5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB
由于內(nèi)存大小只有 4G，因此，我們不可能一次性把所有 URL 加載到內(nèi)存中處理。對于這種類型的題目，一般采用分治策略?，即：把一個文件中的 URL 按照某個特征劃分為多個小文件，使得每個小文件大小不超過 4G，這樣就可以把這個小文件讀到內(nèi)存中進(jìn)行處理了。
思路如下?：
首先遍歷文件 a，對遍歷到的 URL 求?hash(URL) % 1000?，根據(jù)計算結(jié)果把遍歷到的 URL 存儲到 a0, a1, a2, ..., a999，這樣每個大小約為 300MB。使用同樣的方法遍歷文件 b，把文件 b 中的 URL 分別存儲到文件 b0, b1, b2, ..., b999 中。這樣處理過后，所有可能相同的 URL 都在對應(yīng)的小文件中，即 a0 對應(yīng) b0, ..., a999 對應(yīng) b999，不對應(yīng)的小文件不可能有相同的 URL。那么接下來，我們只需要求出這 1000 對小文件中相同的 URL 就好了。
接著遍歷 ai(?i∈[0,999]?)，把 URL 存儲到一個 HashSet 集合中。然后遍歷 bi 中每個 URL，看在 HashSet 集合中是否存在，若存在，說明這就是共同的 URL，可以把這個 URL 保存到一個單獨的文件中。
方法總結(jié)
分而治之，進(jìn)行哈希取余；
對每個子文件進(jìn)行 HashSet 統(tǒng)計。
往期推薦
END
若覺得文章對你有幫助，隨手轉(zhuǎn)發(fā)分享，也是我們繼續(xù)更新的動力。
長按二維碼，掃掃關(guān)注哦
?「C語言中文網(wǎng)」官方公眾號，關(guān)注手機(jī)閱讀教程??
目前收集的資料包括：?Java，Python，C/C++，Linux，PHP，go，C#，QT，git/svn，人工智能，大數(shù)據(jù)，單片機(jī)，算法，小程序，易語言，安卓，ios，PPT，軟件教程，前端，軟件測試，簡歷，畢業(yè)設(shè)計，公開課?等分類，資源在不斷更新中...