過(guò)濾100億黑名單
題目
假設(shè)有100億個(gè)URL的黑名單，每個(gè)URL最多占用64B拓哺，設(shè)計(jì)一個(gè)過(guò)濾系統(tǒng)跟狱，判斷某條URL是否在黑名單里。
要求
不高于萬(wàn)分之一的判斷失誤率世吨；額外內(nèi)存不超過(guò)30GB
答案
100億個(gè)64B的URL需要640GB的內(nèi)存澡刹，顯然直接存哈希表不合理≡呕椋考慮布隆過(guò)濾器罢浇，假設(shè)有一個(gè)長(zhǎng)度為m的bit類型數(shù)組，如圖所示：
[圖片上傳失敗...(image-ebc667-1536497961910)]
輸入階段：
有k個(gè)哈希函數(shù)，函數(shù)的輸出域S大于或等于m嚷闭，假設(shè)哈希函數(shù)彼此獨(dú)立攒岛，對(duì)于同一個(gè)輸入(以字符串表示的URL)，經(jīng)過(guò)k個(gè)哈希函數(shù)的計(jì)算結(jié)果也是相互獨(dú)立凌受。對(duì)計(jì)算的每一個(gè)結(jié)果Mod m阵子，將bit array上對(duì)應(yīng)的位置置1，如下：
一個(gè)輸入對(duì)象會(huì)將bitmap某些位置涂黑胜蛉，處理完所有輸入對(duì)象挠进，會(huì)將bitmap相當(dāng)多位置涂黑，至此誊册，布隆過(guò)濾器生成完畢领突，代表之前所有輸入對(duì)象的集合。
[圖片上傳失敗...(image-e8a7b1-1536497961910)]
20億個(gè)數(shù)中出現(xiàn)最多的數(shù)
問(wèn)題
包含20億個(gè)全是32位整數(shù)的大文件案怯，在其中找出出現(xiàn)次數(shù)最多的數(shù)君旦。
要求
內(nèi)存限制：2GB
答案
將20億個(gè)數(shù)用hash函數(shù)分成16個(gè)文件。然后統(tǒng)計(jì)每個(gè)小文件中嘲碱，哪個(gè)數(shù)字出現(xiàn)次數(shù)最多金砍。最后再比較每個(gè)小文件的次數(shù)最多的數(shù)。（本題分成16個(gè)也是根據(jù)題目來(lái)的麦锯∷〕恚考慮最極端情況。20億個(gè)數(shù)都不同）32位的整數(shù)要占4b,key占4b扶欣，value占4b鹅巍。共8b。內(nèi)存只有2G料祠。所以大概每個(gè)小文件存2億條骆捧。就需要10個(gè)小文件。但是hash函數(shù)必須2的n次方髓绽。所以2的4次方敛苇。16個(gè)
40億個(gè)數(shù)找沒(méi)出現(xiàn)的數(shù)
問(wèn)題
有一個(gè)包含40億個(gè)無(wú)符號(hào)整數(shù)的文件，最多使用1GB內(nèi)存顺呕，找到所有沒(méi)出現(xiàn)的數(shù)
分析
最差情況枫攀，40億個(gè)數(shù)都不同，哈希表保存出現(xiàn)過(guò)的數(shù)塘匣，需要內(nèi)存4B*40億脓豪，大約16GB內(nèi)存。
答案
使用bitmap忌卤，申請(qǐng)一個(gè)長(zhǎng)度為4294967295bit類型的bitArray扫夜，每個(gè)位置只表示0或1，該數(shù)組占用空間約500MB。遍歷這20億個(gè)數(shù)笤闯，例如遇到7000堕阔，就將bitArray[7000]置1。遍歷完成后颗味，再依次遍歷bitArray超陆，哪個(gè)位置沒(méi)有置1，哪個(gè)數(shù)就不在40億個(gè)數(shù)中浦马。
40億個(gè)數(shù)找第一個(gè)沒(méi)出現(xiàn)的數(shù) 时呀。內(nèi)存只有10M
答案
具體的，第一次遍歷晶默，申請(qǐng)長(zhǎng)度64的整形數(shù)組countArr[0...63]谨娜，統(tǒng)計(jì)每個(gè)區(qū)間計(jì)數(shù)增加。例如磺陡，當(dāng)前數(shù)是34225522090趴梢，34225522090/67108864=51，countArr[51]++币他。遍歷完之后坞靶，必定有一個(gè)countArr[i]小于67108864，表示i區(qū)間內(nèi)至少有一個(gè)數(shù)沒(méi)出現(xiàn)過(guò)蝴悉。此時(shí)countArr[]使用的內(nèi)存是64*4B彰阴。
假設(shè)在37區(qū)間有一個(gè)數(shù)沒(méi)出現(xiàn)，申請(qǐng)一個(gè)長(zhǎng)度為67108864的bitmap辫封，內(nèi)存大約8MB硝枉，記為bitArr[0~67108863]廉丽。再一次遍歷40億個(gè)數(shù)倦微，只關(guān)心37區(qū)間的數(shù)，記為num正压。將bitAry[num-6710886437]的值置位1欣福。遍歷完之后，bitArr必然有沒(méi)有置1的位置焦履，記為i拓劝，則6710886437+i就是沒(méi)出現(xiàn)過(guò)的數(shù)。
找出100億個(gè)重復(fù)URL以及搜索詞匯topK問(wèn)題
問(wèn)題
有一個(gè)包含100億URL的大文件嘉裤，每個(gè)URL占64B郑临，找出重復(fù)URL；補(bǔ)充屑宠，找出top100搜索詞匯
常規(guī)答案
- 大文件通過(guò)哈希函數(shù)分配到不同機(jī)器
- 哈希函數(shù)將大文件拆分成小文件厢洞。
對(duì)于每一個(gè)小文件，利用哈希表遍歷，找出重復(fù)的URL躺翻，或者分給機(jī)器或拆分文件完之后丧叽，進(jìn)行排序，看是否有重復(fù)的URL公你。
補(bǔ)充問(wèn)題的思路也是通過(guò)哈希函數(shù)分流踊淳，對(duì)于每個(gè)小文件，簡(jiǎn)歷詞頻哈希表陕靠，建一個(gè)大小為100的小根堆迂尝，選出每個(gè)小文件的top100.每個(gè)小文件的top100進(jìn)行外排序或者接著使用小根堆，就能得到100億數(shù)據(jù)的top100.
出現(xiàn)兩次的數(shù)以及中位數(shù)問(wèn)題
問(wèn)題
有40億個(gè)無(wú)符號(hào)32位整數(shù)剪芥，最多可以使用1GB內(nèi)存雹舀，找出所有出現(xiàn)了兩次的數(shù)；補(bǔ)充問(wèn)題粗俱，最多使用10MB內(nèi)存说榆，找到40億個(gè)數(shù)的中位數(shù)
答案
第一個(gè)問(wèn)題可以用bitmap做，申請(qǐng)長(zhǎng)度為2?232bit的bitArr寸认，2個(gè)bit表示一個(gè)數(shù)出現(xiàn)的詞頻签财。遍歷40億個(gè)數(shù)，假設(shè)出現(xiàn)num偏塞，將bitArr[2num]和bitArr[2num+1]設(shè)置為01唱蒸，第二次出現(xiàn)，設(shè)置為10灸叼，第三次神汹，設(shè)置為11。以后再遇到11的古今，就不做處理屁魏。遍歷完成后，再遍歷一次捉腥，若發(fā)現(xiàn)bitArr[2num]和bitArr[2num+1]是10氓拼，則num是出現(xiàn)了兩次的數(shù)。
第二個(gè)問(wèn)題抵碟，分區(qū)間討論桃漾。長(zhǎng)度為2MB的unsigned int數(shù)組占用8MB，將區(qū)間數(shù)目定位232/2M拟逮，取整為2148個(gè)區(qū)間撬统，第0區(qū)間02M-1，第i區(qū)間2M*i2M*（i+1）-1
申請(qǐng)一個(gè)長(zhǎng)度為2148的unsigned int整數(shù)數(shù)組arr[0..2147],arr[i]表示i區(qū)間有多少個(gè)數(shù)敦迄，arr占用內(nèi)存小于10MB恋追。遍歷40億個(gè)數(shù)粒竖，當(dāng)前數(shù)num為num，落在區(qū)間(num/2M)几于，對(duì)應(yīng)arr[num/2M]++蕊苗。累加統(tǒng)計(jì)每個(gè)區(qū)間的累計(jì)數(shù)目，就能找到40億個(gè)數(shù)的中位數(shù)沿彭。例如0~K-1區(qū)間數(shù)目個(gè)數(shù)為19.998億朽砰，加上第K個(gè)區(qū)間就超過(guò)了20億，說(shuō)要中位數(shù)一定在K區(qū)間中喉刘，并且一定是第K區(qū)間的第0.002億個(gè)數(shù)瞧柔。
接著申請(qǐng)長(zhǎng)度2M的unsigned int數(shù)組countArr[0..2M-1]，占用8MB睦裳。遍歷40億個(gè)數(shù)造锅，只關(guān)心第K區(qū)間的數(shù)numi，countArr[numi-K*2M]++廉邑。統(tǒng)計(jì)完之后在第K區(qū)間找地0.002億個(gè)數(shù)字即可哥蔚。
一致性哈希
分布式數(shù)據(jù)庫(kù)集群緩存，例如memcached蛛蒙，將數(shù)據(jù)的id通過(guò)哈希函數(shù)轉(zhuǎn)換為key糙箍，假設(shè)有N個(gè)機(jī)器，計(jì)算key%N牵祟，得到及其所屬編號(hào)深夯，增刪改查都在這臺(tái)機(jī)器上。一致性哈希能在機(jī)器擴(kuò)容（N發(fā)生變化）诺苹，使得不用重新計(jì)算一遍key%N
三臺(tái)機(jī)器處于哈希環(huán)咕晋，id通過(guò)哈希映射為key，在哈希環(huán)中順時(shí)針找距離最近的機(jī)器收奔。
機(jī)器較少的時(shí)候可能會(huì)出現(xiàn)負(fù)載不均衡掌呜，如圖所示：
答案
引入虛擬節(jié)點(diǎn)，增加結(jié)點(diǎn)數(shù)
