[面试题] 40亿QQ号去重实战：1G内存限制下BitMap解决方案详解

在技术面试中，海量数据处理是一个常见考点。例如，腾讯面试中曾出现这样一道题：给定40亿个QQ号，要求去重，但内存限制仅为1GB。如何高效实现？这正是一个经典的海量数据去重问题，在有限内存下挑战巨大。

1. 理解题目：从QQ号和内存限制说起

我们先来分析问题本身。QQ号是一串数字，范围是4字节的无符号正整数（32位），理论最大值接近43亿。如果直接存储40亿个QQ号，需要多少内存？

简单计算一下：

4000000000 * 4 / 1024 / 1024 / 1024 ≈ 15GB

这需要约15GB内存，远超题目给出的1GB限制。因此，不能硬存储，必须寻找更巧妙的处理方法。

问题的本质是：在内存非常有限的情况下，高效实现重复数据的去重。主流解决方案有两种：

• 方案1：使用BitMap
• 方案2：使用布隆过滤器

两者各有优势，但针对本题，使用BitMap更为合适。

2. 解决方案：用BitMap的精妙之处化繁为简

2.1 什么是BitMap？

位图（BitMap）本质上是一个bit数组，每个位置存储一个bit（0或1）。你可以把它想象成一个超级节省空间的“登记簿”：如果某个QQ号存在，就在对应位置标记为1；否则标记为0。

例如，要记录QQ号1、4、6。传统方法可能需要3个整型变量（每个4字节），共12字节。但BitMap只需一个字节（8位），将第1、4、6位置为1即可，节省了12倍空间。

BitMap的最大优势在于能用极小空间表示巨大数值范围，并支持快速查询、去重等操作。它特别适合这种“存在与否”的问题，无需存储原始数据。

2.2 如何使用BitMap进行40亿个QQ号去重？

回到问题：40亿个QQ号，1GB内存限制，如何用BitMap去重？步骤如下：

1. 申请足够大的BitMap：大小为40亿个bit。计算内存占用：

4000000000 * 1 / 8 / 1024 / 1024 ≈ 476MB

仅需不到500MB空间，完全满足内存限制。

2. 遍历QQ号并映射到BitMap：逐个处理40亿个QQ号，将每个号码对应的bit位置设为1。例如，QQ号“12345678”映射到BitMap的第12345678位，置1表示已出现。

3. 提取去重结果：遍历BitMap，找出所有值为1的bit位置，这些就是去重后的唯一QQ号。

通过这种方式，我们用BitMap成功实现去重，内存消耗控制在500MB以内，完美解决内存不足问题。这种算法与数据结构的思路在实际应用中非常高效。

2.3 BitMap的优缺点

优点：

• 极致节省内存：相比直接存储，内存消耗可减少至八分之一或更少。
• 操作速度快：插入、查询、去重的时间复杂度均为O(1)，适合海量数据处理。
• 实现简单：仅依赖数组结构，理解成本低。

缺点：

• 只能表示存在性：仅用0/1标记是否存在，无法存储更复杂数据（如具体值或出现次数）。
• 需要固定值域：只能操作预定范围的数据，超出范围则无法处理。

3. 总结

通过BitMap，我们用不到500MB内存完成了40亿QQ号的去重，展示了其在资源受限场景下的强大能力。这种思路在实际开发中广泛应用，例如：

• 大规模数据去重
• 数据快速排序
• 集合运算（交集、并集、差集）
• 布隆过滤器的底层实现

掌握BitMap不仅能帮助你在面试求职中脱颖而出，还能在大数据和高并发场景中游刃有余。如果你想深入探讨更多技术话题，欢迎访问云栈社区获取更多资源。