40亿QQ号去重：1GB内存下的工程解法

作者：梅琳marlin2026.11.07 02:17浏览量：0

简介：面对40亿条账号去重、内存仅1GB的约束，单机哈希表无法承载。本文从基数估算、位图与哈希分片两条路线出发，给出可落地的内存预算、分片策略、冲突处理与多轮合并流程，并附伪代码与参数推导，帮助读者在面试与生产环境中快速判断方案边界与取舍。

40亿QQ号去重：1GB内存下的工程解法

一、问题本质：不是“去重”，而是“受限内存下的集合判定”

“40亿个QQ号，1GB内存如何去重”是一道典型的分布式/大数据处理入门题。它的核心矛盾在于：

  • 数据规模：40亿条，若按8字节整数存储，原始数据约32GB；
  • 内存上限：1GB，无法一次性加载；
  • 目标：输出不重复的账号集合，或至少完成“存在性判定+去重计数”。

因此，任何试图用普通哈希表（HashSet）直接存放全部数据的方案，都会因内存溢出而失败。必须借助外部排序、位图、哈希分片或概率数据结构等思路，将“大集合”拆解为“可分批处理的小集合”。

二、先做基数估算：QQ号的实际取值范围

QQ号通常为5~12位数字，实际业务中并非所有数字都被占用。若按最大值约10^12估算，直接使用位图需要：

  1. 10^12 bit = 125 GB

远超1GB。因此，不能直接对全量QQ号做位图。但如果能确认QQ号的最大值在40亿左右（例如实际有效账号集中在某个区间），则位图大小可压缩到：

  1. 40亿 bit = 500 MB

加上控制开销，1GB内存可以容纳。所以第一步应是：确认QQ号的数值范围。若范围可控，位图是极优方案；若范围不可控，则走哈希分片。

三、方案一：位图法（范围可控时）

3.1 基本思路

用一个比特位表示一个QQ号是否存在。若QQ号最大值为N，则需N+1个比特。40亿个账号若最大号约为40亿，则需约500MB。

3.2 处理流程

  1. 申请一个长度为 (maxQQ + 1) / 8 字节的字节数组；
  2. 遍历每个QQ号，计算其位索引；
  3. 若该位为0，置1并输出该QQ号；若为1，跳过。

伪代码：

  1. byte[] bitmap = new byte[(MAX_QQ + 1) / 8 + 1];
  3. for (long qq : allQQ) {
  4.     int byteIndex = (int)(qq / 8);
  5.     int bitIndex = (int)(qq % 8);
  6.     byte mask = (byte)(1 << bitIndex);
  7.     if ((bitmap[byteIndex] & mask) == 0) {
  8.         bitmap[byteIndex] |= mask;
  9.         // 输出 qq 作为不重复项
  10.         output(qq);
  11.     }
  12. }

3.3 优缺点

  • 优点：内存紧凑、查询O(1)、可同时完成去重与计数；
  • 缺点：受QQ号最大值限制。若最大值远大于40亿，内存会迅速膨胀。

四、方案二：哈希分片 + 多轮处理（范围不可控时）

当QQ号范围不确定或最大值极大时，位图不可行。此时采用哈希分片：将40亿条数据按哈希值分成若干小文件，保证每个小文件都能在内存中独立去重。

4.1 分片策略

假设内存1GB，单个哈希表最多容纳约5000万条（考虑对象开销，实际可能更少）。将40亿条分成100片，每片约4000万条，内存可控。

分片规则：

  1. fileIndex = hash(qq) % 100

遍历原始数据，将每个QQ号写入对应的小文件。每个小文件约4000万条，远小于1GB。

4.2 单文件去重

对每个小文件，加载到内存HashSet中，去重后输出。由于分片保证相同QQ号一定在同一文件，因此不会跨文件重复。

4.3 多轮合并

若单个小文件仍超过内存，可继续二次分片，直到每个子文件都能装入内存。最终将所有去重结果合并。

伪代码：

  1. // 第一轮：分片
  2. for (long qq : allQQ) {
  3.     int shard = (int)(hash(qq) % SHARD_COUNT);
  4.     writeToFile(shard, qq);
  5. }
  7. // 第二轮：逐片去重
  8. for (int i = 0; i < SHARD_COUNT; i++) {
  9.     Set<Long> set = new HashSet<>();
  10.     for (long qq : readFile(i)) {
  11.         if (set.add(qq)) {
  12.             // 首次出现
  13.         }
  14.     }
  15.     output(set);
  16. }

4.4 关键点

  • 哈希函数：需均匀分布，避免数据倾斜；
  • 分片数：根据内存和单条记录大小动态计算；
  • 磁盘IO：分片会引入额外读写，但这是内存受限下的必要代价。

五、方案三：外部排序 + 相邻去重

另一种经典思路是外部排序：

  1. 将40亿条数据分成若干块，每块在内存中排序后写回磁盘；
  2. 对多个有序块进行归并排序，生成全局有序序列；
  3. 遍历有序序列，相邻元素比较，跳过重复项。

该方案优点是不依赖哈希分片，缺点是排序开销大，且需要磁盘空间至少为原始数据的两倍。

六、方案四：概率数据结构（近似去重）

若业务允许近似去重（例如仅需估算不重复数量，或允许极低误判率），可使用布隆过滤器（Bloom Filter）：

  • 用多个哈希函数将QQ号映射到位数组；
  • 查询时若所有位均为1，则可能存在；若有一位为0，则一定不存在；
  • 布隆过滤器无法删除元素，且存在误判率，但内存占用极低。

例如，1GB内存可支持约80亿个元素的布隆过滤器（误判率约1%）。但注意：布隆过滤器只能判断“可能存在”，不能直接输出精确去重结果。若需精确去重，仍需结合分片或排序。

七、方案对比与选型建议

方案 内存需求 精确性 磁盘IO 适用场景
位图 取决于最大值 精确 无 QQ号范围可控
哈希分片 可控 精确 高 通用，范围不可控
外部排序 可控 精确 高 可接受排序开销
布隆过滤器 极低 近似 无 仅需估算或允许误判

面试回答建议：先确认QQ号范围。若范围在40亿以内，直接位图，500MB即可；若范围未知，采用哈希分片，分100片，每片4000万，逐片HashSet去重。若允许近似，可提布隆过滤器作为补充。

八、工程落地中的细节与坑

  1. 内存估算：Java中HashSet<Long>每个元素约48字节，5000万条即2.4GB，远超1GB。因此分片数应更大，或使用原始long[]+排序去重。
  2. 哈希函数选择：避免使用hashCode()直接取模，应使用MurmurHash或FNV等均匀哈希。
  3. 磁盘空间：分片会生成大量小文件，需确保磁盘IOPS和空间充足。
  4. 并发处理：可分片后多线程并行去重，但需控制总内存。
  5. 数据倾斜：若某些QQ号段分布密集，需二次分片或动态调整分片数。

九、总结

40亿QQ号去重、1GB内存的核心是分而治之：要么用位图压缩表示，要么用哈希分片将大集合拆小，要么用外部排序化随机为有序。实际选型取决于QQ号范围、精确性要求和磁盘IO成本。掌握这套分析框架，不仅能应对面试，也能在日志去重、用户画像、风控名单等场景中快速落地。

最热文章