來(lái)源：公眾號(hào)【苦逼的碼農(nóng)】

這幾天小秋去面試了，不過(guò)最近小秋學(xué)習(xí)了不少和位算法相關(guān)文章，例如：

【算法技巧】位運(yùn)算裝逼指南

對(duì)于算法題還是有點(diǎn)信心的，，，，于是，發(fā)現(xiàn)了如下對(duì)話(huà)。

20億級(jí)別

面試官：如果我給你 2GB 的內(nèi)存，并且給你 20 億個(gè) int 型整數(shù)，讓你來(lái)找出次數(shù)出現(xiàn)最多的數(shù)，你會(huì)怎么做？

小秋：（嗯？怎么感覺(jué)和之前的那道判斷一個(gè)數(shù)是否出現(xiàn)在這 40 億個(gè)整數(shù)中有點(diǎn)一樣？可是，如果還是采用 bitmap 算法的話(huà)，好像無(wú)法統(tǒng)計(jì)一個(gè)數(shù)出現(xiàn)的次數(shù)，只能判斷一個(gè)數(shù)是否存在），我可以采用哈希表來(lái)統(tǒng)計(jì)，把這個(gè)數(shù)作為 key，把這個(gè)數(shù)出現(xiàn)的次數(shù)作為 value，之后我再遍歷哈希表哪個(gè)數(shù)出現(xiàn)最多的次數(shù)最多就可以了。

面試官：你可以算下你這個(gè)方法需要花費(fèi)多少內(nèi)存嗎？

小秋：key 和 value 都是 int 型整數(shù)，一個(gè) int 型占用 4B 的內(nèi)存，所以哈希表的一條記錄需要占用 8B，最壞的情況下，這 20 億個(gè)數(shù)都是不同的數(shù)，大概會(huì)占用 16GB 的內(nèi)存。

面試官:你的分析是對(duì)的，然而我給你的只有 2GB 內(nèi)存。

小秋：（感覺(jué)這道題有點(diǎn)相似，不過(guò)不知為啥，沒(méi)啥思路，這下涼涼），目前沒(méi)有更好的方法。

面試官：按照你那個(gè)方法的話(huà)，最多只能記錄大概 2 億多條不同的記錄，2 億多條不同的記錄，大概是 1.6GB 的內(nèi)存。

小秋：（嗯？面試官說(shuō)這話(huà)是在提示我？）我有點(diǎn)思路了，我可以把這 20 億個(gè)數(shù)存放在不同的文件，然后再來(lái)篩選。

面試題：可以具體說(shuō)說(shuō)嗎？

小秋：剛才你說(shuō)，我的那個(gè)方法，最多只能記錄大概 2 億多條的不同記錄，那么我可以把這 20 億個(gè)數(shù)映射到不同的文件中去，例如，數(shù)值在 0 至 2億之間的存放在文件1中，數(shù)值在2億至4億之間的存放在文件2中….，由于 int 型整數(shù)大概有 42 億個(gè)不同的數(shù)，所以我可以把他們映射到 21 個(gè)文件中去，如圖

顯然，相同的數(shù)一定會(huì)在同一個(gè)文件中，我們這個(gè)時(shí)候就可以用我的那個(gè)方法，統(tǒng)計(jì)每個(gè)文件中出現(xiàn)次數(shù)最多的數(shù)，然后再?gòu)倪@些數(shù)中再次選出最多的數(shù)，就可以了。

面試官：嗯，這個(gè)方法確實(shí)不錯(cuò)，不過(guò)，如果我給的這 20 億個(gè)數(shù)數(shù)值比較集中的話(huà)，例如都處于 1~20000000 之間，那么你都會(huì)把他們?nèi)坑成涞酵粋€(gè)文件中，你有優(yōu)化思路嗎？

小秋：那我可以先把每個(gè)數(shù)先做哈希函數(shù)映射，根據(jù)哈希函數(shù)得到的哈希值，再把他們存放到對(duì)應(yīng)的文件中，如果哈希函數(shù)設(shè)計(jì)到好的話(huà)，那么這些數(shù)就會(huì)分布的比較平均。（關(guān)于哈希函數(shù)的設(shè)計(jì)，我就不說(shuō)了，我這只是提供一種思路）

40億級(jí)別

面試官：那如果我把 20 億個(gè)數(shù)加到 40 億個(gè)數(shù)呢？

小秋：（這還不簡(jiǎn)單，映射到42個(gè)文件唄）那我可以加大文件的數(shù)量啊。

面試官：那如果我給的這 40 億個(gè)數(shù)中數(shù)值都是一樣的，那么你的哈希表中，某個(gè) key 的 value 存放的數(shù)值就會(huì)是 40 億，然而 int 的最大數(shù)值是 21 億左右，那么就會(huì)出現(xiàn)溢出，你該怎么辦？

小秋：（那我把 int 改為 long 不就得了，雖然會(huì)占用更多的內(nèi)存，那我可以把文件分多幾份唄，不過(guò)，這應(yīng)該不是面試官想要的答案），我可以把 value 初始值賦值為?負(fù)21億，這樣，如果 value 的數(shù)值是 21 億的話(huà)，就代表某個(gè) key 出現(xiàn)了 42 億次了。

80億級(jí)別

面試官：反應(yīng)挺快哈，那我如果把 40 億增加到 80 億呢？

小秋：（我靠，這變本加厲啊）………我知道了，我可以一邊遍歷一遍判斷啊，如果我在統(tǒng)計(jì)的過(guò)程中，發(fā)現(xiàn)某個(gè) key 出現(xiàn)的次數(shù)超過(guò)了 40 億次，那么，就不可能再有另外一個(gè) key 出現(xiàn)的次數(shù)比它多了，那我直接把這個(gè) key 返回就搞定了。

面試官：行，此次面試到此結(jié)束，回去等通知吧。

總結(jié)

今天這篇文章主要講了大數(shù)據(jù)處理相關(guān)的一些問(wèn)題，后面可能還會(huì)給大家找一些類(lèi)似，但處理方式不同的題勒，當(dāng)然，閱讀量很差的話(huà)，就會(huì)沒(méi)動(dòng)力寫(xiě)了，所以，如果覺(jué)得不錯(cuò)，或許可以轉(zhuǎn)發(fā)一波，，，閱讀量一好，熬夜也要擼，嘿嘿。對(duì)了，后面的那些拓展問(wèn)題是我自己想的，我也不知道我對(duì)應(yīng)的思路是否是最優(yōu)解，大家有更好思路的可以底部留言提供哈。

總結(jié)

以上是生活随笔為你收集整理的如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。