What is 海量數(shù)據(jù)啊送？
數(shù)據(jù)量太大，導(dǎo)致要么是無法在較短時(shí)間內(nèi)迅速解決泄鹏，要么由于數(shù)據(jù)量太大实胸，無法一次性裝入內(nèi)存而導(dǎo)致傳統(tǒng)方法無法解決
What is 海量數(shù)據(jù)處理 他嫡？
基于海量數(shù)據(jù)的查找，統(tǒng)計(jì)童芹，運(yùn)算等操作
常見的對(duì)海量數(shù)據(jù)的處理方法
分治 —— Hash映射
在對(duì)大文件進(jìn)行處理時(shí)涮瞻，若文件過大，無法一次性讀入內(nèi)存假褪，可以考慮采用Hash映射的方法將文件中的元素映射到不同小文件中署咽，然后在依次處理各個(gè)小文件，最后合并處理結(jié)果生音，這樣就降低了問題的規(guī)模
常見問題
1. TopK問題
描述：在大規(guī)模數(shù)據(jù)處理中宁否，會(huì)經(jīng)常出現(xiàn)一類問題：如何尋找出最大的前k個(gè)數(shù)，或最小的k個(gè)數(shù)缀遍。
若這些數(shù)據(jù)能一次性裝入內(nèi)存慕匠，快排的時(shí)間復(fù)雜度為O(n)或堆排序的時(shí)間復(fù)雜O(nlogk)空間O(1)
但是在面對(duì)海量數(shù)據(jù)時(shí)，快排的一次劃分就不能再使用域醇！但堆結(jié)構(gòu)依舊可以使用
堆是海量數(shù)據(jù)處理的常用工具之一
例1：
有一個(gè)1GB文件台谊，里面一行是一個(gè)詞，詞的大小不超過16字節(jié)譬挚，內(nèi)存限制為1MB锅铅，返回頻數(shù)最高的100個(gè)詞 （2012.百度）
解析：
可以采用分治法：
順序讀文件，對(duì)于每個(gè)詞x减宣，取 hash(x) % 5000盐须，然后根據(jù)值存到5000個(gè)小文件中，記為X0漆腌，X1贼邓，……阶冈，X4999，這樣每個(gè)小文件大小為200KB左右
如果其中有文件的大小超過了1MB塑径，還可以按照類似的方法繼續(xù)往下分女坑，直到不超過。
對(duì)每個(gè)小文件晓勇，統(tǒng)計(jì)每個(gè)小文件中出現(xiàn)的詞及相應(yīng)頻率（可用樹或hash_map）堂飞，并分別取出頻率最大的100個(gè)詞（可用含100個(gè)結(jié)點(diǎn)的最小堆結(jié)構(gòu)）灌旧，將這100個(gè)詞及相應(yīng)的頻數(shù)存入文件绑咱，這樣又得到5000個(gè)有序文件（每個(gè)文件有100個(gè)詞），下一步就是把這5000個(gè)文件進(jìn)行歸并排序的過程枢泰。
例2：
海量日志數(shù)據(jù)描融，提取出某日訪問百度次數(shù)最多的那個(gè)IP，假設(shè)當(dāng)前機(jī)器可用內(nèi)存較小衡蚂，無法一次性讀入日志文件（2012.百度）
解析
- 方案1：使用分而治之的思想
為了保證海量數(shù)據(jù)分成幾個(gè)小塊后窿克，每個(gè)小塊中的元素都互不相同，也就是說毛甲，值相同的元素要被分到同一數(shù)據(jù)塊中年叮，可以使用hash的方法：
hash(value) % n，n就是要分的塊數(shù)
這樣在每個(gè)小塊中再使用hash_map的方法統(tǒng)計(jì)每個(gè)value的頻數(shù)玻募，之后再利用堆排序對(duì)每個(gè)小塊的頻數(shù)進(jìn)行排序只损，具體過程如下- IP地址最多有
2^32 = 4G種取值可能，按照IP地址的hash(IP)%1024的值七咧，將海量日志存儲(chǔ)到1024個(gè)小文件中跃惫，每個(gè)小文件最多包含4MB個(gè)IP地址 - 對(duì)于每個(gè)小文件，可以構(gòu)建一個(gè)IP作為Key艾栋，出現(xiàn)次數(shù)作為Value的Hash_map爆存，并記錄當(dāng)前出現(xiàn)次數(shù)最多的一個(gè)IP地址
- 有了1024個(gè)小文件中出現(xiàn)次數(shù)最多的IP，我么就可以輕松得到總體上出現(xiàn)次數(shù)最多的IP
- IP地址最多有
Bit_map
原理：使用位數(shù)來表示某些元素是否存在蝗砾，由于采用bit為單位來存儲(chǔ)數(shù)據(jù)先较，因此儲(chǔ)存空間方面可以大大節(jié)省，故適用于海量數(shù)據(jù)的快速查找悼粮，判重闲勺，刪除等
Bloom Filter：布隆過濾器
可視為Bit_map的拓展
