引言
學(xué)習(xí)完布隆過(guò)濾器,相當(dāng)于是入門了海量數(shù)據(jù)處理.然后我們?cè)賮?lái)看看這一道題.
有一個(gè)包含20億全是32位整數(shù)的大文件,在其中找到出現(xiàn)次數(shù)最多的數(shù)
內(nèi)存大小為2GB
分析
如果不是海量處理的話,我們會(huì)使用一個(gè)哈希函數(shù),來(lái)記錄詞(key)和它出現(xiàn)的頻率(value),因?yàn)檫@是32位的數(shù),所以key的大小是4B,value的大小也設(shè)置為4B這樣的話一條hash記錄就是8B,所以當(dāng)哈希表的記錄數(shù)為2億個(gè)時(shí),這個(gè)時(shí)候就需要1.6GB的內(nèi)存大小.
但是如果是20億個(gè)不同的數(shù)那,一條記錄時(shí)8GB,那么20億條記錄就是16GB.這樣使用一個(gè)hash是可能的,那么這個(gè)時(shí)候該如何處理那?
我們把包含20億個(gè)數(shù)分解成小文件,那分解成幾個(gè)那,我們想象以下,一塊2GB的內(nèi)存,存著key和value,那么其中能存的記錄就是1GB(1GB存key,1GB存value)key那就是文件中的數(shù),所以一次能夠查1GB的記錄,20億條數(shù)據(jù),20億條數(shù)據(jù)對(duì)應(yīng)著16GB的存儲(chǔ)空間,一次能查1GB,所有要分成16分小文件,一份小文件就是1GB,裝入到2GB中1GB是key,1GB是value,具體操作我們截取書中的內(nèi)容
圖片.png
注意到我們分成16個(gè)小文件是通過(guò)hash函數(shù)分的,因?yàn)閔ash函數(shù)的性質(zhì),同一種數(shù)就絕對(duì)不可能分在同一個(gè)文件上.
這樣就完成了.....
