點(diǎn)擊上方?泥瓦匠 關(guān)注我！

• 題目描述

• 解答思路

• 方法總結(jié)

---

題目描述

給定 a、b 兩個(gè)文件，各存放 50 億個(gè) URL，每個(gè) URL 各占 64B，內(nèi)存限制是 4G。請(qǐng)找出 a、b 兩個(gè)文件共同的 URL。

解答思路

每個(gè) URL 占 64B，那么 50 億個(gè) URL占用的空間大小約為 320GB。

5, 000, 000, 000 * 64B ≈ 5GB * 64 = 320GB

由于內(nèi)存大小只有 4G，因此，我們不可能一次性把所有 URL 加載到內(nèi)存中處理。對(duì)于這種類型的題目，一般采用分治策略?，即：把一個(gè)文件中的 URL 按照某個(gè)特征劃分為多個(gè)小文件，使得每個(gè)小文件大小不超過(guò) 4G，這樣就可以把這個(gè)小文件讀到內(nèi)存中進(jìn)行處理了。

思路如下?：

首先遍歷文件 a，對(duì)遍歷到的 URL 求?hash(URL) % 1000?，根據(jù)計(jì)算結(jié)果把遍歷到的 URL 存儲(chǔ)到 a0, a1, a2, ..., a999，這樣每個(gè)大小約為 300MB。使用同樣的方法遍歷文件 b，把文件 b 中的 URL 分別存儲(chǔ)到文件 b0, b1, b2, ..., b999 中。這樣處理過(guò)后，所有可能相同的 URL 都在對(duì)應(yīng)的小文件中，即 a0 對(duì)應(yīng) b0, ..., a999 對(duì)應(yīng) b999，不對(duì)應(yīng)的小文件不可能有相同的 URL。那么接下來(lái)，我們只需要求出這 1000 對(duì)小文件中相同的 URL 就好了。

接著遍歷 ai(?i∈[0,999]?)，把 URL 存儲(chǔ)到一個(gè) HashSet 集合中。然后遍歷 bi 中每個(gè) URL，看在 HashSet 集合中是否存在，若存在，說(shuō)明這就是共同的 URL，可以把這個(gè) URL 保存到一個(gè)單獨(dú)的文件中。

方法總結(jié)

1. 分而治之，進(jìn)行哈希取余；

2. 對(duì)每個(gè)子文件進(jìn)行 HashSet 統(tǒng)計(jì)。

往期推薦

如何在 SpringBoot 中用注解實(shí)現(xiàn) Redis 分布式鎖？

Java 中 bean mapper 的性能分析以及深入分析底層原理

Java日志體系整理，必看權(quán)威總結(jié)

知乎高贊：為何 Java 開(kāi)源項(xiàng)目都試圖用 go 進(jìn)行重寫(xiě)？

下方二維碼關(guān)注我

技術(shù)草根，堅(jiān)持分享?編程，算法，架構(gòu)

朋友助力下！點(diǎn)個(gè)贊和在看！