前言

大家好,我是田螺.

分享一道網上很火的騰訊面試題:40億的QQ號,如何去重,不超過1G的內存. 不過,有騰訊上班的朋友說,我們沒出過這種面試題~ 哈哈~

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

1. 常規思路

我們日常開發中,如果談到去重,最容易想到的就是放到HashSet,直接放到HashSet就好:

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

但是呢,是有個1G的內存限制的! 如果放到HashSet,那40億的QQ數據,都是在內存中的話,我們來算一下,40億的QQ,要多大的內存:

如果每個QQ號是64位整數（8字節），那么40億個QQ號的總存儲量為：

40億 * 8字節 = 320億字節
轉化位KB 32,000,000,000 字節/1024 = 31,250,000 KB
KB轉化為MB 31,250,000 KB/ 1024 ≈ 30,517.578125 MB
MB轉化為GB  30,517.578125 MB/ 1024 ≈ 29.8023223876953125 GB

那就是30GB左右,如果每個QQ號碼是32位整數(4字節),則是15GB左右. 顯然,都遠超1GB的內存.

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

因此,這道題我們需要換個思路,就是在內存有限的情況下,如何實現去重? 我們可以考慮一種更高效的數據結構來處理這個問題。

我們可以考慮BitMap（位圖)來解決這個問題.

2. BitMap

2.1 BitMap 到底是什么

BitMap（位圖）是一種非常高效的數據結構，特別適合處理大規模數據的去重和查詢問題。它的基本思想是使用一個bit位來表示一個數字是否存在。

例如，如果我們有一個長度為10的BitMap，那么它可以表示數字0到9是否存在：

• 如果BitMap的第0位是1，表示數字0存在；
• 如果BitMap的第1位是1，表示數字1存在；
• 如果BitMap的第2位是1，表示數字2存在；

以此類推~

數字9表示的BitMap如下:

圖片

如果用BitMap,比如我要記錄的QQ號碼分別是9、5、2、7, 那么BitMap表示為:

圖片

顯然只需要一個10位就可以表示,如果用傳統方法來記錄,一個整型4字節,4個QQ號碼就是,4*4=16字節,然后一個字節8位,那就是 16*8=128位啦~. 可以發現用BitMap 可以大大節省存儲空間.

2.2 用BitMap給40億QQ去重

2.2.1 使用BitMap,40億的QQ是否超過1GB內存

既然BitMap 可以大大節省存儲空間,我們用BitMap來給40億QQ去重,看看會不會超1G的內存.

我們來一起估算一下, 因為要40億的QQ,那我們申請一個足夠大的BitMap,假設就是40億的位,那內存大概就是:

4,000,000,000/8 = 500,000,000 
500,000,000/1024/1024/1024 ≈ 0.466GB

可以發現,只需要0.466GB的內存就足夠啦~ 在內存這方面,是符合不超過1GB的限制的~

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

• 首先,初始化好40億位的BitMap
• 其次,遍歷這40億的QQ,把每個QQ號碼映射到BitMap中,給對應位置的bit,設置為1

比如,假設有個QQ號碼為326443281,那么就在BitMap的對應位置,設置為1

• 遍歷BitMap，收集所有設置為1的位對應的QQ號碼,即為去重后的QQ號碼。

2.3 BitMap去重的簡單代碼實現

給大家來個簡單的代碼模擬吧:

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; // 每個字節有8位

    private static List<Long> deduplicateQQNumbers(long[] qqNumbers) {
        // 創建位圖，使用字節數組
        byte[] bitmap = new byte[(int) (BITMAP_SIZE / BYTE_SIZE)];

        // 更新位圖
        for (long qqNumber : qqNumbers) {
            if (qqNumber >= 0 && qqNumber < BITMAP_SIZE) {
                // 計算字節索引和位索引
                int index = (int) (qqNumber / BYTE_SIZE);
                int bitPosition = (int) (qqNumber % BYTE_SIZE);
                // 設置對應的位
                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的優缺點

我們使用一種數據結構去解決問題,那肯定要知道它的優缺點對吧.

Bitmap的優點

• 空間效率高

相比哈希表存儲原始數據，Bitmap僅用1位/元素。對于密集數據（如連續QQ號），空間利用率極高。

• 操作非常高效

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

• 去重邏輯簡單

只需遍歷數據，置位存在標記，無需復雜結構。

Bitmap的缺點

• 存儲空間依賴值域范圍

若值域范圍大但稀疏（如QQ號上限遠大于實際數量），空間浪費嚴重。例如，若QQ號上限為1萬億，需125GB內存，難以承受。

• 無法存儲額外信息,只能記錄有還是沒有

僅記錄是否存在，無法保存出現次數等元數據。

最后

有些伙伴認為,使用布隆過濾器也可以實現,40億的QQ號,不超過1G的內存,進行去重.大家覺得呢?