ReaderMX.
ITPUB

腾讯面试官问：如何用 1GB 内存去重 40亿 QQ号？答案竟然是...

Ixiaokang1998约 12 分钟

前段时间，一位读者朋友分享了他去腾讯面试的经历。面试官给了他一道挺有挑战性的题目：假设你有40亿个QQ号，要求把这些QQ号去重，只保留一个，且内存限制只有1GB。朋友一时没想明白，最后面试挂了。其实，这个题目乍一看挺简单，但一旦细想就会发现，背后隐藏了不少技巧和知识点。

今天我们就来聊聊这个经典的面试题，看看怎么在有限的内存下，优雅地解决40亿QQ号去重的问题。

问题背景：QQ号和内存限制

首先，让我们分析一下题目中给出的条件：

40亿个QQ号：假设QQ号使用四字节（32位）的无符号整数来存储。也就是说，它的最大值是接近43亿（2^32 - 1）。这就意味着，QQ号实际上是一个范围在0到43亿之间的数字。 而我们需要存储的QQ号数量(40亿)比这个还少一些，所以使用 32 位的无符号整数 unsigned int 来存储就够了。

内存限制1GB：这个限制看似不大，但如果你用传统的方式存储每个QQ号，单纯保存40亿个32位整数的内存就需要：

  • 40亿×4字节=160亿字节=16GB

也就是说，如果按每个QQ号用4字节存储，直接存40亿个QQ号，光是数据就已经超出了1GB的内存限制。所以，这个问题的关键在于如何通过巧妙的方式使用有限的内存来完成去重操作。

解决方案一：位图（Bitmap）方法

位图（Bitmap）是什么？

首先，我们来理解一下什么是 位图（Bitmap）。位图是一种非常节省空间的数据结构，它通过使用一个很大的数组，每个数组元素代表一个二进制位（bit）。每个二进制位只有两个值：0 或 1，也就是“开”或“关”。通过这种方式，我们能够快速存储和判断某些值是否存在，并且节省大量的内存空间。

举个简单的例子：传统方法 vs 位图

假设我们有一组数字：1, 3, 5, 7，要存储这些数字。

传统方法

如果我们用传统方法，每个数字占用一个整型（4字节），那存储4个数字就需要16字节（4个整型，每个4字节）。

传统存储：1, 3, 5, 7  ==> 需要16字节

位图方法

位图是用二进制位（0或1）来表示每个数字是否出现过。对于1, 3, 5, 7，我们可以用8个二进制位来表示：

位图：[0, 1, 0, 1, 0, 1, 0, 1]
下标： 0  1  2  3  4  5  6  7

这表示数字1, 3, 5, 7出现过，其他数字没有。

位图只需要1字节来表示这4个数字，节省了大量空间。

那我们怎么用位图来去重40亿个QQ号呢？

好了，现在让我们回到 去重 的问题。我们现在的任务是：给你40亿个QQ号，内存限制是1GB，怎么去重？

我们可以使用位图来高效地标记这些QQ号是否重复。下面我们来看看具体的步骤。

使用位图存储40亿QQ号，占用多少空间？

每个QQ号是一个32位的整数，可以从0到40亿。我们要做的是，判断每个QQ号是否重复，每个QQ号都需要在位图中占一个位置。

  • 位图的每个“位置”用一个二进制位（0或1）来表示。0 代表未出现过， 1 代表出现过。
  • 所以，40亿个QQ号就需要40亿个二进制位(bit)，大约需要500M的内存（ 1GB = 10亿字节 = 80 亿bit）。

步骤1：创建位图

我们首先需要创建一个位图，这个位图会有40亿个bit的位置，所有bit一开始都被初始化为0，表示所有QQ号都没有出现过。

步骤2：遍历QQ号并标记

接着，我们开始遍历40亿个QQ号，每遇到一个QQ号，就通过以下步骤来更新位图：

2.1 计算位图位置：我们把QQ号做一个简单的取余运算来确定它在位图中的位置：

位图位置 = QQ号 % 位图大小

比如，QQ号3456789，假设位图的大小是40亿，我们通过取余来找到它的位置：

3456789 % 40亿 = 3456789

2.2 标记位置：通过计算出来的位图位置，我们将这个位置的bit值设置为1，表示这个QQ号出现过了。

2.3 判断重复：如果这个位置已经是1了，说明这个QQ号之前已经出现过，就是重复的，跳过它；如果是0，说明这个QQ号是新的，我们把它标记为1，表示它已经出现过。

步骤3：遍历BitMap

找出 BitMap 所有bit值为1的下标，这些就是所有的去重后的QQ号。

下面给出核心代码逻辑：

// 创建一个bitset
std::bitset<BITSET_SIZE> bitset;

// 遍历QQ号并更新bitset
voidprocessQQNumbers(conststd::vector<int>& qqNumbers){
for (int qq : qqNumbers) {
// 计算QQ号在位图中的位置
int index = qq % BITSET_SIZE;

// 判断当前位置的bit值
if (bitset[index] == 0) {
// 如果该位置是0，说明这个QQ号第一次出现，标记为1
bitset[index] = 1;
std::cout << "QQ号 " << qq << " 是新出现的，已标记" << std::endl;
            } else {
// 如果该位置已经是1，说明这个QQ号重复了
std::cout << "QQ号 " << qq << " 是重复的，已跳过" << std::endl;
            }
        }
    }

// 遍历位图，输出去重后的QQ号
voidprintUniqueQQs(){
std::cout << "\n去重后的QQ号：" << std::endl;
for (int i = 0; i < BITSET_SIZE; i++) {
if (bitset[i]) {
std::cout << i << " ";
            }
        }
std::cout << std::endl;
    }

为了让大家更清楚地理解，我们通过几个具体的QQ号来演示整个去重的过程：

1.QQ号3456789，计算出它的位置是3456789。位图[3456789]原本是0，表示这个QQ号没有出现过。所以我们将它设置为1。

QQ号：3456789  ==>  位图位置：3456789
位图： [0, 0, 0, ..., 0, ..., 0]  ==> 将位图[3456789]置为1

2.QQ号1234567，计算出它的位置是1234567。位图[1234567]原本是0，表示这个QQ号没有出现过。所以我们将它设置为1。

QQ号：1234567  ==>  位图位置：1234567
位图： [0, 0, 0, ..., 1, ..., 0]  ==> 将位图[1234567]置为1

3.QQ号3456789（重复的），计算出它的位置是3456789。位图[3456789]现在已经是1了，表示这个QQ号已经出现过了。我们就跳过这个QQ号，不再进行标记。

QQ号：3456789  ==>  位图位置：3456789
位图： [0, 0, 0, ..., 1, ..., 0]  ==> 位图[3456789]已经是1了，说明这个QQ号重复了！

4.继续处理剩余的QQ号

  • 接下来，我们依次处理剩下的QQ号，按照同样的步骤：计算出对应的位置，如果该位置是0，就将其标记为1；如果是1，就说明该QQ号已经出现过，直接跳过。

遍历完所有QQ号后，位图中值为1的下标对应的就是去重后的QQ号。

解决方案二：使用布隆过滤器

布隆过滤器是什么？

布隆过滤器也是一个省内存的数据结构，用来判断「某个元素可能存在」或者「一定不存在」，但它有 误判率。

举个现实世界的例子：夜店盖章

想象你去了一家夜店，进门时保安会在你的手背上盖几个章（不同颜色的章代表不同的哈希函数）。

规则：

1.每个进店的人，保安都会在手背的几个固定位置盖章（对应哈希函数计算出的位置）。

2.如果有人回头再来，保安就检查这些位置是否有章：

  • 如果所有位置都有章，保安认为「你可能来过」。
  • 如果有任意一个位置没有章，保安确定「你一定没来过」。

3.但章是永久性的，不会擦掉（对应布隆过滤器无法删除数据）。

布隆过滤器就是这么个东西！
它用 位数组（Bit Array）+ 多个哈希函数 来存数据，能 节省超多空间！ 🎯

布隆过滤器的核心原理

1.位数组（Bit Array）：

  • 设想一个很长的二进制数组，例如：
00000000000000000000000000  （初始时，全是 0）
  • 我们不会存具体的 QQ 号，而是把某些位置改成 1。

2.多个哈希函数（Hash Functions）：

  • 对每个 QQ 号，计算多个哈希值，映射到 位数组的不同位置，并把这些位置设为 1。

3.查询某个 QQ 号是否存在：

  • 计算它的 哈希值，看看这些位置是不是全是 1：
    • 如果全是 1，可能已经存在（但有误判）。
    • 如果有 0，那一定没出现过！

位数组大小怎么确定？

布隆过滤器的大小需要权衡 内存使用 和 误判率。

计算公式：

  • 设 n = 40亿（QQ号数量）
  • 设 p = 误判率（误判率设置范围通常在 0.1% 到 1% 之间。误判率越低，空间需求越高。  ）
  • k（哈希函数个数）：通常取最优值 k = ln(2) * (m/n)

需要的位数组大小m（单位：比特）：

m=−(n×lnp)/ln2^2

当 p = 0.01，n = 40亿，算下来 m=4.8G > 1G , 这个时候你可以调大 p 值，减小m。

布隆过滤器如何去重 40 亿 QQ 号？

我们假设有一个 16 位的位数组（真实会更大）：

索引:      0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
BitArray: [0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0]

步骤 1：插入 QQ 号 12345

假设 12345 经过 3 个哈希函数，得到 3 个哈希值：

  • H1(12345) = 3
  • H2(12345) = 7
  • H3(12345) = 12

于是，我们把这些位置的 bit 设为 1：

索引:      0   1   2   3   4   5   6   7   8   9  10   11  12  13  14  15
BitArray: [0][0][0][1][0][0][0][1][0][0][0][0][1][0][0][0]

步骤 2：插入 QQ 号 67890

假设 67890 经过 3 个哈希函数，得到 3 个哈希值：

  • H1(67890) = 3
  • H2(67890) = 5
  • H3(67890) = 9

于是，我们把位置5，9 的 bit 设为 1，哈希值 3 和上面的有重复，不用管。

索引:      0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
BitArray: [0][0][0][1][0][1][0][1][0][1][0][0][1][0][0][0]

步骤 3： 插入剩余数据......

接下来，我们执行查询：

1、查询 QQ 号 12345 是否出现过

计算 12345 的 3 个哈希值：

  • H1(12345) = 3
  • H2(12345) = 7
  • H3(12345) = 12

发现这些位置 全是 1：

索引:      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
BitArray: [0][1][0][1][0][1][0][1][0][1][0][0][1][0][0][0]

✅ 说明 可能存在。

2、查询一个新的 QQ 号 99999

计算 99999 的 3 个哈希值：

  • H1(99999) = 2
  • H2(99999) = 6
  • H3(99999) = 14

发现 索引 2、6 和 索引 14 还是 0：

索引:      0   1   2   3   4   5   6   7   8   9  10   11  12  13  14  15
BitArray: [0][1][0][1][0][1][0][1][0][1][0][0][1][0][0][0]

❌ 说明 一定没出现过。

解决方案三：外部排序（External Sorting）——适用于超大规模数据排序和去重

当数据规模 远超内存大小（如几十亿个 QQ 号，而内存只有 1GB），普通的内存排序（如快排、归并排序）无法一次性完成任务。这时候，我们就需要用到外部排序（External Sorting）。

外部排序的核心思路

外部排序的基本思路是 「分而治之」：

  1. 将大数据拆成多个小块，每个小块可以装入内存并完成排序。
  2. 对每个小块进行独立排序，然后保存到磁盘上。
  3. 使用多路归并排序合并所有小块，最终得到一个完整的有序数据集。

这种方法在内存受限的情况下，仍然可以高效处理超大数据集。

具体步骤

📌步骤 1：分批加载数据

由于内存只有 1GB，而 40 亿个 QQ 号占用约 160GB（每个 QQ 号 4 字节），我们不能一次性加载所有数据。

怎么拆分？

  1. 一次读取 2.5亿个 QQ 号，能完全装入内存(1G)。
  2. 每批数据进行排序（快排 / 归并排序），并去重。
  3. 把排序后的数据写入磁盘，形成多个已排序的中间文件（如 sorted_chunk_1.txt, sorted_chunk_2.txt …）。

示意图：

原始数据（40亿个QQ号）
↓分批加载（每批2.5亿个）
批次1:读取+内存排序+去重→sorted_chunk_1.txt
批次2:读取+内存排序+去重→sorted_chunk_2.txt
...
批次N:读取+内存排序+去重→sorted_chunk_N.txt

✅ 这样，我们把 40 亿个 QQ 号拆分成多个已排序的小文件(16个)，每个小文件大约1G。

📌 步骤2：归并排序 & 去重

当 步骤 1 生成了 16 个已排序的小文件（每个 1GB） 后，我们需要合并这些小文件，并去重，得到最终的排序结果。

在这个过程中，我们使用 最小堆（Min Heap） 来管理多个文件的数据，确保数据全局有序，并在归并的同时进行去重。

如何归并 16 个有序小文件？

1.每个文件读取 100 万个数，填充读取缓冲区（减少磁盘 read() 调用）。

2.从每个文件的缓冲区取出 1 个数，放入最小堆（存储 (数值, 文件索引)，确保知道数据来自哪个文件）。

3.最小堆维护当前 16 个文件的最小值，堆顶是当前全局最小值。

4.取出最小值 num，然后进行去重：

  • 如果 num == last_written，跳过（去重）。
  • 否则，写入写缓冲区，并更新 last_written。

5.从对应文件的缓冲区取下一个数，继续放入堆中。

6.写缓冲区满 1000 万 个数时，一次性写入磁盘，减少 write() 频率。

7.重复以上步骤，直到所有文件归并完毕。

✅ 最终，数据全局有序，且去重完成！

📌 归并 & 去重示例（最小堆图解）

输入文件：

chunk_1.txt:[1,2,5,7,10]
chunk_2.txt:[2,3,6,10,15]
chunk_3.txt:[1,4,7,8,12]

我们希望使用最小堆（Min Heap）归并这 3 个有序文件，并去重，得到最终的去重有序数据。

以下是归并 & 去重具体步骤：

1️⃣ 初始化最小堆

从每个文件缓冲区读取首个数，并存入最小堆：

(数值, 文件索引)

最小堆：
      (1, 1)
    /       \
 (2, 2)    (1, 3)
  • (1,1): 1 来自 chunk_1.txt
  • (2,2): 2 来自 chunk_2.txt
  • (1,3): 1 来自 chunk_3.txt

2️⃣ 取出最小值 1，存入写缓冲区

堆顶 1 来自 chunk_1.txt，写入写缓冲区：

写缓冲区：[1]

从 chunk_1.txt 读取下一个数 2，插入堆：

最小堆：
      (1, 3)
    /       \
 (2, 2)    (2, 1)

3️⃣ 取出最小值 1，跳过去重

堆顶 1 来自 chunk_3.txt，但 1 == last_written，跳过不写入。

从 chunk_3.txt 读取下一个数 4，插入堆：

最小堆：
      (2, 1)
    /       \
 (2, 2)    (4, 3)

4️⃣ 取出最小值 2，存入写缓冲区

堆顶 2 来自 chunk_1.txt，写入写缓冲区：

写缓冲区：[1, 2]

从 chunk_1.txt 读取下一个数 5，插入堆：

最小堆：
      (2, 2)
    /       \
 (4, 3)    (5, 1)

5️⃣ 取出最小值2，跳过去重

堆顶 2 来自 chunk_2.txt，但 2 == last_written，跳过不写入。

从 chunk_2.txt 读取下一个数 3，插入堆：

最小堆：
      (3, 2)
    /       \
 (4, 3)    (5, 1)

6️⃣取出最小值 3，存入写缓冲区

写缓冲区：[1, 2, 3]

从 chunk_2.txt 读取下一个数 6，插入堆：

最小堆：
      (4, 3)
    /       \
 (6, 2)    (5, 1)

7️⃣ 取出最小值4，存入写缓冲区

写缓冲区：[1, 2, 3, 4]

从 chunk_3.txt 读取下一个数 7，插入堆：

最小堆：
      (5, 1)
    /       \
 (6, 2)    (7, 3)

持续归并，最终输出文件

最终所有数据归并 & 去重完成，得到：

最终结果文件: [1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15]

✅ 所有数据有序，且去重完成！

🚀 最小堆保证数据全局有序，last_written 变量实现去重，最终所有数据排序 & 去重完成！

🔥 方案对比

方案内存占用查询速度去重精准度磁盘 I/O适用场景
位图（Bitmap）500MBO(1)
✅ 完全精准
无磁盘 I/O
适用于 整型数据（如 QQ 号、IP 地址）且 数据范围已知 的场景。
布隆过滤器（Bloom Filter）大于1GO(1)
❌ 有误判
无磁盘 I/O
适用于 内存有限但可接受误判的场景，支持 整型和字符串 数据。
外部排序（External Sorting）<=1GBO(logN)
✅ 完全精准
依赖磁盘 I/O
适用于 超大数据规模，可以处理 整型和字符串 数据，适合内存不足时处理大规模数据。

所以，最优方案是位图！

在40亿QQ号这样的场景下，位图（Bitmap）既能精确去重，又能保证查询效率，并且内存占用较少，对于 已知范围的整数数据去重而言，是最直接且最简单的解决方案。

KEEP THE THREAD GOING

更多来源文章