大數(shù)據(jù)介紹

面試中關于大數(shù)據(jù)的題目有些是和采樣結合的題目，其實更適合放在概率的章節(jié)弹渔，但值得注意的是越來越大的題更注重對map-reduce的理解和掌握拨匆，Map-reduce和Hadoop逐漸成為面試的熱門。

介紹哈希函數(shù)

哈希函數(shù)又叫散列函數(shù)告丢，哈希函數(shù)的輸入域可以是非常大的范圍韩玩，但是輸出域是固定范圍垒玲。假設為s。
哈希函數(shù)的性質(zhì)：
1啸如、典型的哈希函數(shù)都擁有無限的輸入值域侍匙。
2氮惯、輸入值相同時叮雳，返回值一樣。
3妇汗、輸入值不同時帘不，返回值可能一樣，也可能不一樣杨箭。
4寞焙、不同輸入值得到的哈希值，整體均勻的分布在輸出域s上。（重要）
MD5與SHA1算法都是經(jīng)典的哈希函數(shù)算法，了解即可压真，面試時不要求掌握苦掘。

map-reduce

1、Map階段→把大任務分成子任務鞍恢。
2、Reduce階段→子任務并發(fā)處理，然后合并結果娘扩。
注意點：
1、備份的考慮壮锻，分布式存儲的設計細節(jié)琐旁，以及容災策略。
2猜绣、任務分配策略與任務進度跟蹤的細節(jié)設計灰殴，節(jié)點狀態(tài)的呈現(xiàn)。
3掰邢、多用戶權限的控制牺陶。

常見的海量數(shù)據(jù)處理技巧

1擅羞、分而治之。通過哈希函數(shù)將大任務分流到機器义图，或分流成小文件减俏。
2、常用的hashMap或bitmap碱工。
難點：通訊娃承、時間和空間的估算。

經(jīng)典題

• 用map-reduce方法統(tǒng)計一篇文章中每個單詞出現(xiàn)的個數(shù)
  1怕篷、預處理历筝，生成只包含單詞的文本
  2、map階段：1）對每個單詞生成詞頻為1的記錄如：（dog廊谓，1）梳猪、（pig，1）蒸痹，一個單詞可能有多個詞頻為1的記錄此時還未進行合并春弥；2）通過哈希函數(shù)得到每個單詞的哈希值，并根據(jù)該值分成若干組任務叠荠，每個子任務中包含若干種單詞匿沛，但同一種單詞不會分配進不同的子任務中。
  3榛鼎、reduce階段：1）單個子任務中同一種單詞的詞頻進行合并逃呼；2）所有記錄統(tǒng)一合并
• 排序：請對10億個ipv4的地址進行排序，每個ip只出現(xiàn)一次
  ipv4的ip數(shù)量有42億多一點
  普通方法：將10億ip轉化為對應的用4個字節(jié)32位表示的整數(shù)者娱，對這些數(shù)排序后再轉換為ip地址
  更好的方法：申請長度為2³²的bit類型的數(shù)組抡笼，其大小約為500m，記為bitmap黄鳍，將10一個ip轉化為相應的整數(shù)后推姻，在bitmap中會有對應的位置，將其描黑际起，表示其出現(xiàn)拾碌，最后按順序遍歷bitmap即可，遍歷過程中再轉回ip地址街望。
• 請對10億人的年齡進行排序
  年齡的范圍可以認為是0~200間校翔，這樣可以用200個桶，采用計數(shù)排序就行
• 有一個包含20億個全是32位整數(shù)的大文件灾前，在其中找到出現(xiàn)次數(shù)最多的數(shù)防症。但是內(nèi)存限制只有2G
  通常做法：用hash表做詞頻統(tǒng)計，但此題需要以每個數(shù)作為鍵，以該數(shù)出現(xiàn)的次數(shù)作為值創(chuàng)建hash表蔫敲，所以一條記錄需要8個字節(jié)存儲饲嗽，一共20億數(shù)據(jù)就需要大約16G的內(nèi)存空間，顯然不合適奈嘿。
  推薦做法：用hash函數(shù)對不同的數(shù)進行分流貌虾，此處假設分流為16個小文件，再利用hash表進行詞頻統(tǒng)計裙犹，找出各自的詞頻最高的數(shù)尽狠，再進行比較。
• 32位無符號整數(shù)的范圍是0~4294967295∫镀裕現(xiàn)在有一個正好包含40億個無符號整數(shù)的文件袄膏，所以在整個范圍中必然有沒出現(xiàn)過的數(shù)〔艄冢可以使用最多10M的內(nèi)存沉馆，只用找到一個沒出現(xiàn)過的數(shù)即可，該如何找德崭？
  如果供hash表做：因為只記錄是否出現(xiàn)斥黑，不需要記錄詞頻，所以每條記錄需要4個字節(jié)接癌，一共40億記錄的話需要大約16G心赶，遠超題目給的10m
  如果用bitmap做：這里長度為2³²的bit類型數(shù)組可以表示42億多的數(shù)，所以此處申請長度為2³²的bit類型數(shù)組缺猛，該數(shù)組的大小大約為500m，也不滿足題意
  此題推薦做法：用hash函數(shù)對每個整數(shù)進行分流椭符，此處需要分流64份荔燎，則每份數(shù)據(jù)用bitmap的話僅僅需512 / 64 = 8m空間。
  對每個區(qū)間做詞數(shù)統(tǒng)計销钝，假設a區(qū)間詞數(shù)小于區(qū)間長度有咨，則遍歷一次40個數(shù)，此時只關注區(qū)間a上的數(shù)蒸健，并用bitmap統(tǒng)計區(qū)間a上的數(shù)的出現(xiàn)情況座享，在a區(qū)間必定至少有一個數(shù)不存在。
• 某搜索公司一天的用戶搜索詞匯是海量的似忧，假設有百億的數(shù)據(jù)量渣叛，請設計一種求出每天最熱100詞的可行辦法
  還是用hash函數(shù)分流，然后在用hash表做詞頻統(tǒng)計盯捌，如果機器數(shù)有限淳衙，則需要分流每臺機器上的文件，再用hash表做詞頻統(tǒng)計。
  創(chuàng)建hash表后箫攀，可以利用小根堆來進行top100篩選肠牲，得到每個小文件排序后的top100，然后再將同一臺機器上所有文件的top100通過小根堆或外排得到每臺機器上的排序后的top100靴跛，最后再通過小根堆或外排得到所有機器也就是所有數(shù)據(jù)桶的排序后的top100缀雳，返回即可。
• 工程師常使用服務器集群來設計和實現(xiàn)數(shù)據(jù)緩存梢睛，以下是常見的策略俏险。1，無論是添加扬绪、查詢還是刪除數(shù)據(jù)竖独，都先將數(shù)據(jù)的id通過哈希函數(shù)轉換成一個哈希值，記為key挤牛。2莹痢，如果目前機器有N臺，則計算key%N的值墓赴，這個值就是該數(shù)據(jù)所屬的機器編號竞膳，無論是添加、刪除還是查詢操作诫硕，都只在這臺機器上進行坦辟。請分析這種緩存策略可能帶來的問題，并提出改進的方案
  帶來的問題：如果增加或刪除機器的話章办，數(shù)據(jù)遷移的代價太高
  推薦的一致性hash的算法：
  1锉走、將所有的數(shù)據(jù)id的hash結果看成一個環(huán)形。
  2藕届、將所有的機器工具其id計算hash結果挪蹭，并將其插入到數(shù)據(jù)hash結果組成的環(huán)中
  3、數(shù)據(jù)處理時休偶，計算某條數(shù)據(jù)的hash值后梁厉，在環(huán)中找從這個hash值開始順時針方向最近的機器即可，那么數(shù)據(jù)的增刪改查都在此機器上進行