給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url?

兩種方法：

一、采用Bloom filter，假設布隆過濾器的錯誤率為0.01，則位數組大小m約為輸入元素個數n的13倍，此時需要的哈希函數k約為8個。

元素個數：n = 5G

位數組大小：m = 5G * 13 = 65G = 650億 即需要650億個bit位才能達到錯誤率0.01

而我們擁有的內存可容納bit位個數：4G * 8bit = 32G bit = 320億，按此實現錯誤率大于0.01。

布隆過濾器：https://blog.csdn.net/qq_41946557/article/details/102593912

二、采用分治的思想

假如每個url大小為10bytes，那么可以估計每個文件的大小為50G×64=320G，遠遠大于內存限制的4G，所以不可能將其完全加載到內存中處理，可以采用分治的思想來解決。

　　Step1：遍歷文件a，對每個url求取hash(url)%1000，然后根據所取得的值將url分別存儲到1000個小文件(記為a0,a1,...,a999，每個小文件約300M);

　　Step2:遍歷文件b，采取和a相同的方式將url分別存儲到1000個小文件(記為b0,b1,...,b999);

　　巧妙之處：這樣處理后，所有可能相同的url都被保存在對應的小文件(a0vsb0,a1vsb1,...,a999vsb999)中，不對應的小文件不可能有相同的url。然后我們只要求出這個1000對小文件中相同的url即可。

　　Step3：求每對小文件ai和bi中相同的url時，可以把ai的url存儲到hash_set/hash_map中。然后遍歷bi的每個url，看其是否在剛才構建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

【補充】

1、為什么使用hash？是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

也就是說將url通過hash函數變成一個固定長度的值，（url有的挺長的！）然后假如有一部分數值%1000后，等于0，那么放入到a0中，等于1的放入到a1中，以此類推。。。

【注】：

• 1、Hash取模是一種等價映射，不會存在同一個元素分散到不同小文件中的情況，即這里采用的是mod1000算法，那么相同的url在hash取模后，只可能落在同一個文件中，不可能被分散的。因為如果兩個url相等，那么經過Hash(url)之后的哈希值是相同的，將此哈希值取模（如模1000），必定仍然相等。

• 2、那到底什么是hash映射呢？簡單來說，就是為了便于計算機在有限的內存中處理big數據，從而通過一種映射散列的方式讓數據均勻分布在對應的內存位置(如大數據通過取余的方式映射成小樹存放在內存中，或大文件映射成多個小文件)，而這個映射散列方式便是我們通常所說的hash函數，設計的好的hash函數能讓數據均勻分布而減少沖突。盡管數據映射到了另外一些不同的位置，但數據還是原來的數據，只是代替和表示這些原始數據的形式發生了變化而已。

mini版代碼實現：https://blog.csdn.net/qq_41946557/article/details/102711573?

?

總結

以上是生活随笔為你收集整理的给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。