前言

大家好,我是田螺.

分享一道網(wǎng)上很火的騰訊面試題:40億的QQ號(hào),如何去重,不超過(guò)1G的內(nèi)存. 不過(guò),有騰訊上班的朋友說(shuō),我們沒(méi)出過(guò)這種面試題~ 哈哈~

哈哈,anyway,這道題還是很有意思的. 它是一個(gè)非常經(jīng)典的海量數(shù)據(jù)去重問(wèn)題,并且做了內(nèi)存限制,最多只能1GB.本文田螺哥跟大家探討一下~~

1. 常規(guī)思路

我們?nèi)粘ｉ_(kāi)發(fā)中,如果談到去重,最容易想到的就是放到HashSet,直接放到HashSet就好:

Set<Long> qqSet = new HashSet<>();
qqSet.add(qqNumber); // 自動(dòng)去重

但是呢,是有個(gè)1G的內(nèi)存限制的! 如果放到HashSet,那40億的QQ數(shù)據(jù),都是在內(nèi)存中的話,我們來(lái)算一下,40億的QQ,要多大的內(nèi)存:

如果每個(gè)QQ號(hào)是64位整數(shù)（8字節(jié)），那么40億個(gè)QQ號(hào)的總存儲(chǔ)量為：

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左右,如果每個(gè)QQ號(hào)碼是32位整數(shù)(4字節(jié)),則是15GB左右. 顯然,都遠(yuǎn)超1GB的內(nèi)存.

因此,直接放到HashSet并不可行.

因此,這道題我們需要換個(gè)思路,就是在內(nèi)存有限的情況下,如何實(shí)現(xiàn)去重? 我們可以考慮一種更高效的數(shù)據(jù)結(jié)構(gòu)來(lái)處理這個(gè)問(wèn)題。

我們可以考慮BitMap（位圖)來(lái)解決這個(gè)問(wèn)題.

2. BitMap

2.1 BitMap 到底是什么

BitMap（位圖）是一種非常高效的數(shù)據(jù)結(jié)構(gòu)，特別適合處理大規(guī)模數(shù)據(jù)的去重和查詢問(wèn)題。它的基本思想是使用一個(gè)bit位來(lái)表示一個(gè)數(shù)字是否存在。

例如，如果我們有一個(gè)長(zhǎng)度為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號(hào)碼分別是9、5、2、7, 那么BitMap表示為:

圖片

顯然只需要一個(gè)10位就可以表示,如果用傳統(tǒng)方法來(lái)記錄,一個(gè)整型4字節(jié),4個(gè)QQ號(hào)碼就是,4*4=16字節(jié),然后一個(gè)字節(jié)8位,那就是 16*8=128位啦~. 可以發(fā)現(xiàn)用BitMap 可以大大節(jié)省存儲(chǔ)空間.

2.2 用BitMap給40億QQ去重

2.2.1 使用BitMap,40億的QQ是否超過(guò)1GB內(nèi)存

既然BitMap 可以大大節(jié)省存儲(chǔ)空間,我們用BitMap來(lái)給40億QQ去重,看看會(huì)不會(huì)超1G的內(nèi)存.

我們來(lái)一起估算一下, 因?yàn)橐?0億的QQ,那我們申請(qǐng)一個(gè)足夠大的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)存這方面,是符合不超過(guò)1GB的限制的~

2.2.2 使用BitMap,給40億QQ 去重流程

• 首先,初始化好40億位的BitMap
• 其次,遍歷這40億的QQ,把每個(gè)QQ號(hào)碼映射到BitMap中,給對(duì)應(yīng)位置的bit,設(shè)置為1

比如,假設(shè)有個(gè)QQ號(hào)碼為326443281,那么就在BitMap的對(duì)應(yīng)位置,設(shè)置為1

• 遍歷BitMap，收集所有設(shè)置為1的位對(duì)應(yīng)的QQ號(hào)碼,即為去重后的QQ號(hào)碼。

2.3 BitMap去重的簡(jiǎn)單代碼實(shí)現(xiàn)

給大家來(lái)個(gè)簡(jiǎ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; // 每個(gè)字節(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) {
                // 計(jì)算字節(jié)索引和位索引
                int index = (int) (qqNumber / BYTE_SIZE);
                int bitPosition = (int) (qqNumber % BYTE_SIZE);
                // 設(shè)置對(duì)應(yīng)的位
                bitmap[index] |= (1 << bitPosition);
            }
        }

        // 收集去重后的QQ號(hào)碼
        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)缺點(diǎn)

我們使用一種數(shù)據(jù)結(jié)構(gòu)去解決問(wèn)題,那肯定要知道它的優(yōu)缺點(diǎn)對(duì)吧.

Bitmap的優(yōu)點(diǎn)

• 空間效率高

相比哈希表存儲(chǔ)原始數(shù)據(jù)，Bitmap僅用1位/元素。對(duì)于密集數(shù)據(jù)（如連續(xù)QQ號(hào)），空間利用率極高。

• 操作非常高效

插入和查詢均為O(1)復(fù)雜度，位運(yùn)算速度快，適合海量數(shù)據(jù)實(shí)時(shí)處理。

• 去重邏輯簡(jiǎn)單

只需遍歷數(shù)據(jù)，置位存在標(biāo)記，無(wú)需復(fù)雜結(jié)構(gòu)。

Bitmap的缺點(diǎn)

• 存儲(chǔ)空間依賴值域范圍

若值域范圍大但稀疏（如QQ號(hào)上限遠(yuǎn)大于實(shí)際數(shù)量），空間浪費(fèi)嚴(yán)重。例如，若QQ號(hào)上限為1萬(wàn)億，需125GB內(nèi)存，難以承受。

• 無(wú)法存儲(chǔ)額外信息,只能記錄有還是沒(méi)有

僅記錄是否存在，無(wú)法保存出現(xiàn)次數(shù)等元數(shù)據(jù)。

最后

有些伙伴認(rèn)為,使用布隆過(guò)濾器也可以實(shí)現(xiàn),40億的QQ號(hào),不超過(guò)1G的內(nèi)存,進(jìn)行去重.大家覺(jué)得呢?