分享一道網(wǎng)上很火的面試題：40億QQ號(hào)，不超過(guò)1G的內(nèi)存，如何去重？
開頭直接上干貨：40億個(gè)QQ號(hào)塞進(jìn)電腦，內(nèi)存只給1G，這題聽著就離譜！但真有人用個(gè)小技巧搞定了——位圖，原理簡(jiǎn)單到像小學(xué)生畫格子簽到。
---
一、為啥常規(guī)方法行不通？
1. 日常去重咋做？
一般人會(huì)想到用`HashSet`，把QQ號(hào)往里一丟，重復(fù)的自動(dòng)過(guò)濾。
2. 但內(nèi)存炸了！
40億個(gè)QQ號(hào)，每個(gè)占4字節(jié)，總內(nèi)存需要約15GB；如果是8字節(jié)，直接飆到30GB。可題目只給1G內(nèi)存，硬塞肯定崩。
---
二、神操作：用位圖省空間
1. 位圖是啥？
想象一張超大的簽到表：
- 每個(gè)格子代表一個(gè)QQ號(hào)。
- 如果這個(gè)QQ號(hào)來(lái)過(guò)，就在格子里畫個(gè)勾；沒來(lái)就空著。
→ 關(guān)鍵點(diǎn)：一個(gè)格子只占1個(gè)bit，比存QQ號(hào)本身省了幾十倍空間。
2. 40億QQ號(hào)要多少內(nèi)存？
簽到表需要40億個(gè)格子：
```
40億 bit ÷ 8 = 5億字節(jié)
476MB ÷ 1024 ≈ 0.46GB
```
不到0.5GB就能搞定！ 完美滿足1G限制。
3. 操作三步走：
- 第一步：準(zhǔn)備一張40億格子的簽到表。
- 第二步：遍歷所有QQ號(hào)，每看到一個(gè)號(hào)，就在對(duì)應(yīng)格子畫勾。
- 第三步：掃一遍簽到表，把畫了勾的格子對(duì)應(yīng)的QQ號(hào)記下來(lái)——這些就是去重后的結(jié)果。
---
三、位圖的優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)：
? 省內(nèi)存：40億數(shù)據(jù)只用半G，爽！
? 速度快：找號(hào)碼、畫勾都是秒完成。
? 操作簡(jiǎn)單：像查簽到表一樣直觀。
- 缺點(diǎn)：
? 號(hào)碼不能太分散：如果QQ號(hào)最大到1萬(wàn)億，格子就得預(yù)留1萬(wàn)億個(gè)，內(nèi)存直接漲到125GB，血虧。
? 只能記“來(lái)過(guò)”：想統(tǒng)計(jì)某個(gè)號(hào)來(lái)了幾次？做不到。