1.題目描述
給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url?

2.思考過程
（1）首先我們最常想到的方法是讀取文件a，建立哈希表（為什么要建立hash表？因?yàn)榉奖愫竺娴牟檎?#xff09;，然后再讀取文件b，遍歷文件b中每個(gè)url，對(duì)于每個(gè)遍歷，我們都執(zhí)行查找hash表的操作，若hash表中搜索到了，則說明兩文件共有，存入一個(gè)集合。

（2）但上述方法有一個(gè)明顯問題，加載一個(gè)文件的數(shù)據(jù)需要50億*64bytes = 320G遠(yuǎn)遠(yuǎn)大于4G內(nèi)存，何況我們還需要分配哈希表數(shù)據(jù)結(jié)構(gòu)所使用的空間，所以不可能一次性把文件中所有數(shù)據(jù)構(gòu)建一個(gè)整體的hash表。

---

（3）針對(duì)上述問題，我們分治算法的思想。

step1：遍歷文件a，對(duì)每個(gè)url求取hash(url)%1000，然后根據(jù)所取得的值將url分別存儲(chǔ)到1000個(gè)小文件(記為a0,a1,...,a999，每個(gè)小文件約300M)，為什么是1000？主要根據(jù)內(nèi)存大小和要分治的文件大小來計(jì)算，我們就大致可以把320G大小分為1000份，每份大約300M（當(dāng)然，到底能不能分布盡量均勻，得看hash函數(shù)的設(shè)計(jì)）

step2：遍歷文件b，采取和a相同的方式將url分別存儲(chǔ)到1000個(gè)小文件(記為b0,b1,...,b999)（為什么要這樣做? 文件a的hash映射和文件b的hash映射函數(shù)要保持一致，這樣的話相同的url就會(huì)保存在對(duì)應(yīng)的小文件中，比如，如果a中有一個(gè)url記錄data1被hash到了a99文件中，那么如果b中也有相同url，則一定被hash到了b99中）

所以現(xiàn)在問題轉(zhuǎn)換成了：找出1000對(duì)小文件中每一對(duì)相同的url（不對(duì)應(yīng)的小文件不可能有相同的url）

step3：因?yàn)槊總€(gè)hash大約300M，所以我們再可以采用（1）中的想法

---

所以海量數(shù)據(jù)面前要多采用分治算法，化整為零 各個(gè)擊破！
?

總結(jié)

以上是生活随笔為你收集整理的海量数据处理：两个大文件中的相同记录的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。