摘要：這幾天小秋去面試了，不過最近小秋學(xué)習(xí)了不少和位算法相關(guān)文章，例如面試現(xiàn)場(chǎng)如何判斷一個(gè)數(shù)是否在億個(gè)整數(shù)中算法技巧位運(yùn)算裝逼指南對(duì)于算法題還是有點(diǎn)信心的，，，，于是，發(fā)現(xiàn)了如下對(duì)話。

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

【面試現(xiàn)場(chǎng)】如何判斷一個(gè)數(shù)是否在40億個(gè)整數(shù)中？

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

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

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

小秋：（嗯？怎么感覺和之前的那道判斷一個(gè)數(shù)是否出現(xiàn)在這 40 億個(gè)整數(shù)中有點(diǎn)一樣？可是，如果還是采用 bitmap 算法的話，好像無法統(tǒng)計(jì)一個(gè)數(shù)出現(xiàn)的次數(shù)，只能判斷一個(gè)數(shù)是否存在），我可以采用哈希表來統(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)存。

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

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

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

面試題：可以具體說說嗎？

小秋：剛才你說，我的那個(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ò)，不過，如果我給的這 20 億個(gè)數(shù)數(shù)值比較集中的話，例如都處于 1~20000000 之間，那么你都會(huì)把他們?nèi)坑成涞酵粋€(gè)文件中，你有優(yōu)化思路嗎？

小秋：那我可以先把每個(gè)數(shù)先做哈希函數(shù)映射，根據(jù)哈希函數(shù)得到的哈希值，再把他們存放到對(duì)應(yīng)的文件中，如果哈希函數(shù)設(shè)計(jì)到好的話，那么這些數(shù)就會(huì)分布的比較平均。（關(guān)于哈希函數(shù)的設(shè)計(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)存，那我可以把文件分多幾份唄，不過，這應(yīng)該不是面試官想要的答案），我可以把 value 初始值賦值為 負(fù)21億，這樣，如果 value 的數(shù)值是 21 億的話，就代表某個(gè) key 出現(xiàn)了 42 億次了。

這里說明下，文件還是 21 個(gè)就夠了，因?yàn)?21 個(gè)文件就可以把每個(gè)文件的數(shù)值種類控制在 2億種了，也就是說，哈希表存放的記錄還是不會(huì)超過 2 億中。

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

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

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

今天這篇文章主要講了大數(shù)據(jù)處理相關(guān)的一些問題，后面可能還會(huì)給大家找一些類似，但處理方式不同的題勒，大家如果覺得不錯(cuò)，不妨：

1、點(diǎn)贊，讓更多的人也能看到這篇內(nèi)容（收藏不點(diǎn)贊，都是耍流氓 -_-）

2、關(guān)注我，讓我們成為長(zhǎng)期關(guān)系

3、關(guān)注公眾號(hào)「苦逼的碼農(nóng)」，主要寫算法、計(jì)算機(jī)基礎(chǔ)之類的文章，里面已有100多篇原創(chuàng)文章，我也分享了很多視頻、書籍的資源，以及開發(fā)工具，歡迎各位的關(guān)注，第一時(shí)間閱讀我的文章。。