腾讯面试：40亿QQ号，给你1G内存，怎么去重？

前段时间，有个小伙伴给我分享了他去腾讯面试的经历。他说被问到了一道去重的面试题：

给你40亿个QQ号，要求相同的QQ号码仅保留一个，内存限制为1个G，你会怎么实现？

小伙伴由于没有回答好，导致面试挂了。

这其实就是个经典的海量数据去重问题，而且还附带一个让人头疼的条件：内存限制只有1G！

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

我们先来分析一下问题本身。

QQ号其实是一串数字，范围是4字节的无符号正整数，也就是32位，理论上最大值接近43亿。所以，如果单纯存储这40亿个QQ号，需要耗费多少内存呢？

简单计算一下：

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

总共需要15GB的内存，显然远远超过了题目给的1GB限制。这就需要我们换个思路，不能“硬塞”，要想办法巧妙地存储和处理这些QQ号。

所以问题的本质就是“在内存非常有限的情况下，高效实现重复数据的去重”。

解决方案有很多，但是主流的方案有两种：

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

两者各有千秋，但在本题中，我们使用BitMap更加合适。

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

2.1 什么是BitMap？

所谓位图（BitMap）其实就是一个bit数组，即每一个位置都是一个bit，其中的取值可以是0或者1。

通俗点说，BitMap就像一个超级节省空间的“登记簿”。

• 如果某个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号，限制1G内存，如何用BitMap去重？

步骤如下：

1）申请一个足够大的BitMap，大小为40亿个bit，也就是：

4000000000 * 1 /8/1024/1024 = 476M

只需要不到500MB的空间就可以搞定！

2）遍历这40亿QQ号，把每个号码映射到BitMap中，把对应位置的bit设置为1。

比如，QQ号“12345678”会直接映射到BitMap的第“12345678”个位置，然后置为1，表示它已经出现过。

3）通过遍历BitMap，找出所有bit值为1的位置，这些就是所有的去重后的QQ号。

通过这样的方式，我们用BitMap成功实现了40亿QQ号去重，最大内存消耗也不到500MB，不会有内存不足的问题。

2.3 BitMap的优缺点

优点：

• 超极节省内存

相比直接存储数据，BitMap的内存消耗大约只有八分之一甚至更少，非常高效。

• 操作快

插入、查询、去重的时间复杂度都是O(1)，十分适合处理海量数据。

• 易于实现

算法简单，只需要依赖一个数组，理解成本低。

缺点：

• 只能表示“有或没有”

BitMap只能用0和1表示是否存在，无法存储更复杂的数据（如具体值或出现次数）。

• 需要确定值域范围

BitMap只能操作固定范围的数据，超出范围将导致无法标记。

3.总结

通过这道题我们看到了BitMap的优雅之处，它让我们用不到500MB的内存，成功完成了40亿QQ号的去重操作。更重要的是，这种思路在很多场景中都有广泛应用，比如：

• 大规模数据去重

• 数据快速排序

• 集合运算（交集、并集、差集）

• 布隆过滤器的底层实现

所以，掌握BitMap不仅能帮你顺利通过面试，在实际的大数据场景中也非常实用！

你还有其他更好的思路吗？欢迎留言讨论~

https://mp.weixin.qq.com/s/82P8d8HECMelgQc0Cd_UIA