40亿个qq号，如何实现去重，限制内存1g的情况下。

从QQ号和内存限制说起

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

简单计算一下：

1
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倍空间。

img

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

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

回到我们的问题：40亿个QQ号，限制1G内存，如何用BitMap去重？

步骤如下：

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

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

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

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

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

img

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不仅能帮你顺利通过面试，在实际的大数据场景中也非常实用！