騰訊一面：40億QQ號，不超過1G內(nèi)存，如何去重?
前言
大家好,我是田螺.
分享一道網(wǎng)上很火的騰訊面試題:40億的QQ號,如何去重,不超過1G的內(nèi)存. 不過,有騰訊上班的朋友說,我們沒出過這種面試題~ 哈哈~
哈哈,anyway,這道題還是很有意思的. 它是一個非常經(jīng)典的海量數(shù)據(jù)去重問題,并且做了內(nèi)存限制,最多只能1GB.本文田螺哥跟大家探討一下~~
1. 常規(guī)思路
我們?nèi)粘ｉ_發(fā)中,如果談到去重,最容易想到的就是放到HashSet,直接放到HashSet就好:
Set<Long> qqSet = new HashSet<>();
qqSet.add(qqNumber); // 自動去重但是呢,是有個1G的內(nèi)存限制的! 如果放到HashSet,那40億的QQ數(shù)據(jù),都是在內(nèi)存中的話,我們來算一下,40億的QQ,要多大的內(nèi)存:
如果每個QQ號是64位整數(shù)（8字節(jié)），那么40億個QQ號的總存儲量為：
40億 * 8字節(jié) = 320億字節(jié)
轉(zhuǎn)化位KB 32,000,000,000 字節(jié)/1024 = 31,250,000 KB
KB轉(zhuǎn)化為MB 31,250,000 KB/ 1024 ≈ 30,517.578125 MB
MB轉(zhuǎn)化為GB 30,517.578125 MB/ 1024 ≈ 29.8023223876953125 GB那就是30GB左右,如果每個QQ號碼是32位整數(shù)(4字節(jié)),則是15GB左右. 顯然,都遠(yuǎn)超1GB的內(nèi)存.
因此,直接放到HashSet并不可行.
因此,這道題我們需要換個思路,就是在內(nèi)存有限的情況下,如何實現(xiàn)去重? 我們可以考慮一種更高效的數(shù)據(jù)結(jié)構(gòu)來處理這個問題。
我們可以考慮BitMap（位圖)來解決這個問題.
2. BitMap
2.1 BitMap 到底是什么
BitMap（位圖）是一種非常高效的數(shù)據(jù)結(jié)構(gòu)，特別適合處理大規(guī)模數(shù)據(jù)的去重和查詢問題。它的基本思想是使用一個bit位來表示一個數(shù)字是否存在。
例如，如果我們有一個長度為10的BitMap，那么它可以表示數(shù)字0到9是否存在：
- 如果BitMap的第0位是1，表示數(shù)字0存在；
- 如果BitMap的第1位是1，表示數(shù)字1存在；
- 如果BitMap的第2位是1，表示數(shù)字2存在；
以此類推~
數(shù)字9表示的BitMap如下:
圖片
如果用BitMap,比如我要記錄的QQ號碼分別是9、5、2、7, 那么BitMap表示為:
圖片
顯然只需要一個10位就可以表示,如果用傳統(tǒng)方法來記錄,一個整型4字節(jié),4個QQ號碼就是,4*4=16字節(jié),然后一個字節(jié)8位,那就是 16*8=128位啦~. 可以發(fā)現(xiàn)用BitMap 可以大大節(jié)省存儲空間.
2.2 用BitMap給40億QQ去重
2.2.1 使用BitMap,40億的QQ是否超過1GB內(nèi)存
既然BitMap 可以大大節(jié)省存儲空間,我們用BitMap來給40億QQ去重,看看會不會超1G的內(nèi)存.
我們來一起估算一下, 因為要40億的QQ,那我們申請一個足夠大的BitMap,假設(shè)就是40億的位,那內(nèi)存大概就是:
4,000,000,000/8 = 500,000,000
500,000,000/1024/1024/1024 ≈ 0.466GB可以發(fā)現(xiàn),只需要0.466GB的內(nèi)存就足夠啦~ 在內(nèi)存這方面,是符合不超過1GB的限制的~
2.2.2 使用BitMap,給40億QQ 去重流程
- 首先,初始化好40億位的BitMap
- 其次,遍歷這40億的QQ,把每個QQ號碼映射到BitMap中,給對應(yīng)位置的bit,設(shè)置為1
比如,假設(shè)有個QQ號碼為326443281,那么就在BitMap的對應(yīng)位置,設(shè)置為1
- 遍歷BitMap，收集所有設(shè)置為1的位對應(yīng)的QQ號碼,即為去重后的QQ號碼。
2.3 BitMap去重的簡單代碼實現(xiàn)
給大家來個簡單的代碼模擬吧:
import java.util.*;
public class QQDeduplication {
// 位圖的大小為 4,294,967,296 bits，即 0.5 GB
private static final long BITMAP_SIZE = 1L << 32; // 2^32
private static final int BYTE_SIZE = 8; // 每個字節(jié)有8位
private static List<Long> deduplicateQQNumbers(long[] qqNumbers) {
// 創(chuàng)建位圖，使用字節(jié)數(shù)組
byte[] bitmap = new byte[(int) (BITMAP_SIZE / BYTE_SIZE)];
// 更新位圖
for (long qqNumber : qqNumbers) {
if (qqNumber >= 0 && qqNumber < BITMAP_SIZE) {
// 計算字節(jié)索引和位索引
int index = (int) (qqNumber / BYTE_SIZE);
int bitPosition = (int) (qqNumber % BYTE_SIZE);
// 設(shè)置對應(yīng)的位
bitmap[index] |= (1 << bitPosition);
}
}
// 收集去重后的QQ號碼
List<Long> uniqueQQNumbers = new ArrayList<>();
for (int i = 0; i < bitmap.length; i++) {
for (int j = 0; j < BYTE_SIZE; j++) {
if ((bitmap[i] & (1 << j)) != 0) {
long qqNumber = (long) i * BYTE_SIZE + j;
uniqueQQNumbers.add(qqNumber);
}
}
}
return uniqueQQNumbers;
}
}2.4 BitMap的優(yōu)缺點
我們使用一種數(shù)據(jù)結(jié)構(gòu)去解決問題,那肯定要知道它的優(yōu)缺點對吧.
Bitmap的優(yōu)點
- 空間效率高
相比哈希表存儲原始數(shù)據(jù)，Bitmap僅用1位/元素。對于密集數(shù)據(jù)（如連續(xù)QQ號），空間利用率極高。
- 操作非常高效
插入和查詢均為O(1)復(fù)雜度，位運算速度快，適合海量數(shù)據(jù)實時處理。
- 去重邏輯簡單
只需遍歷數(shù)據(jù)，置位存在標(biāo)記，無需復(fù)雜結(jié)構(gòu)。
Bitmap的缺點
- 存儲空間依賴值域范圍
若值域范圍大但稀疏（如QQ號上限遠(yuǎn)大于實際數(shù)量），空間浪費嚴(yán)重。例如，若QQ號上限為1萬億，需125GB內(nèi)存，難以承受。
- 無法存儲額外信息,只能記錄有還是沒有
僅記錄是否存在，無法保存出現(xiàn)次數(shù)等元數(shù)據(jù)。
最后
有些伙伴認(rèn)為,使用布隆過濾器也可以實現(xiàn),40億的QQ號,不超過1G的內(nèi)存,進(jìn)行去重.大家覺得呢?
