面经策

现在有 40 亿个 QQ 号，给你 1G 的内存，如何实现去重？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

先算账：40 亿个 QQ 号去重，1G 内存。这题的关键是先问一句：要精确结果还是允许近似？ 业务用途决定方案和成本。

方案一：Bitmap（精确去重，首选）

QQ 号是数值型且范围有限（10 位以内，约 43 亿空间），一个 bit 标记一个号码是否存在：

  • 40 亿 bit ≈ 477MB，完全放得下 1G 内存
  • 初始化全 0，遍历数据把对应位置 1，最后统计 1 的个数即去重结果
java
BitSet bits = new BitSet(4300000000); // 约500MB
for (long qq : data) bits.set((int) qq);
long distinct = bits.cardinality();

时间 O(N)、一次遍历，简单可靠。

方案二：分片 Bitmap（内存再紧时）

1G 里要放程序、IO 缓冲，可以按 QQ 号高位分 8 个片，每片约 60MB，分批处理两遍（先按片过滤再装载），空间换时间变成时间换空间。

方案三：布隆过滤器（允许误判时）

如果业务只要"估计有多少独立用户"（比如 UV 粗估、垃圾名单预判），布隆过滤器用几十 MB 就够，误判率 1% 量级——存储成本砍掉一个数量级，代价是少量误判。用户画像精确计费就不行，广告 UV 估算完全可以。

架构师收尾：这道题的本质是"用业务容忍度换资源成本"。精确、近似、分批离线，三档方案成本差 10 倍以上，先问清用途再选——这也是我评审类似需求时问的第一个问题：这个数错 1% 会有人发现吗？

🏗 系统架构师 ​

这题本质是大整数域上的去重，直接上位图（Bitmap），先算空间可行性。

方案一：直接位图（QQ 号是 32 位正整数）

  • 40 亿个 QQ 号，数值空间最多约 2^32 ≈ 42.9 亿。
  • 一个 bit 标记一个号，总内存 = 2^32 / 8 = 512MB，小于 1G，单机可行。
java
BitSet bits = new BitSet(1 << 30);   // 约 512MB
bits.set(qq);                        // 出现即置位
// 遍历 bits 中为 1 的下标即为去重结果

顺序读入每个 QQ 号 set 对应位，一遍扫描完成去重，时间 O(n)，这就是经典的海量数据处理思路：用 bit 级空间换掉 hash 结构的指针和对象头开销。

方案二：稀疏场景用 RoaringBitmap 如果 ID 分布稀疏（比如只有几百万个号但散布在 0~100 亿区间），原始位图会浪费严重（100 亿 bit ≈ 1.25GB 超预算）。RoaringBitmap 按 2^16 分容器：稠密块用位图、稀疏块用有序数组，典型可压缩 50~100 倍，也是 1G 内稳稳放下。

方案三：数据量远超内存时 分治：按 QQ 号高位（比如前 8 位）切分成 256 个文件，每个文件内的号码必然落在同一位图区间，逐文件用小位图处理再合并。原则是先按模/范围散列，让同一元素必然落进同一个分片，分片内部就能独立去重。

工程取舍：能预估值域就用原始位图，值域稀疏或不可预估用 RoaringBitmap，两者都是我可以直接给出内存上界判断的方案——先算空间再写代码。

💻 全栈开发专家 ​

40 亿 QQ 号上限约 2^32，直接上 Bitmap：一个 bit 标记一个号是否存在，2^32 bit = 512MB，1G 内存完全放得下，这是标准答案。

实现要点

  • Java 堆内用 BitSet，或直接分配堆外内存避免 GC 压力：
java
long[] bits = new long[1 << 27]; // 2^32 bit
void add(long qq) { bits[(int)(qq >> 6)] |= 1L << (qq & 63); }
boolean exists(long qq) { return (bits[(int)(qq >> 6)] & (1L << (qq & 63))) != 0; }
  • 分布式/离线场景用 Redis：SETBIT qq_set <qq> 1，判重 GETBIT，统计 BITCOUNT。40 亿 bit 约 512MB，单节点可扛，也可以按 QQ 号段拆多个 key。

如果内存再紧（比如只给 100MB） 换 布隆过滤器：误判率 1% 时 40 亿条约需 4.8GB… 依然不够，那就得允许更高误判率或上磁盘。面试时说清 trade-off：Bitmap 零误判但吃精确内存，布隆省内存但有误判（只会误判"存在"，不会漏）。

踩过的坑

  • JVM 堆内 512MB 数组要注意给足 -Xmx，否则直接 OOM；我更倾向堆外 ByteBuffer.allocateDirect 或直接 Redis。
  • QQ 号是数值才这么玩；如果是任意字符串，得先 hash 到 long 再入 bitmap，会有极小概率冲突。