面经策

ArrayList 里有 1 亿条数据，要怎么去重？ ​

  • 标签：后端、场景题

🏛 业务架构师 ​

ArrayList 一亿条数据去重——这题难度低，我会快速给出正解，然后讲清内存现实和工程决策，体现量级意识。

标准答案：HashSet 一遍过

java
Set<T> set = new HashSet<>(list);       // O(n) 去重
List<T> distinct = new ArrayList<>(set);

或流式写法 list.stream().distinct().collect(toList())（底层 LinkedHashSet 保序）。原理：哈希 O(1) 判存，一遍扫描完成，复杂度 O(n)——比双循环 O(n²) 快一亿倍量级。

但一亿条的内存现实（必须主动讲）

  • 一亿个对象在 JVM 堆里本身就要几十 GB：ArrayList 的引用数组约 800MB（4 字节压缩指针 ×1e8），加上对象本体和 HashSet 的复制，单机 JVM 默认配置直接 OOM
  • 所以前提是堆足够大（-Xmx 调到容纳 2~3 倍数据）或换思路

数据量大到单机吃不下时的分档

  1. 并行流 / 分片多线程：list.parallelStream().distinct()——利用多核，但内存总量不变，只是快
  2. 外排去重：分片排序（有序后相邻比较去重）——内存不够时
  3. 分布式：Spark distinct()、或按 hash 分桶后各桶独立去重再合并——TB 级数据的正确姿势
  4. 数值型且值域可控：Bitmap/RoaringBitmap，内存再砍一个数量级

业务收尾（架构师视角）：真实工程里我会先问三个问题：数据从哪来（能不能在源头去重，如数据库 DISTINCT）、去重键是什么（对象 equals 还是业务主键）、去重之后干嘛（如果只要 count，根本不用物化结果）。多数"一亿条去重"问题的最优解在数据管道上游解决，而不是在 Java 集合里硬扛——面试考算法，工程考问对问题。

🏗 系统架构师 ​

一亿条 ArrayList 去重，我按数据特征与资源约束分路线，先把量级算清楚。

路线一：HashSet（有足够内存，最快）

java
Set<Integer> set = new HashSet<>(list.size() / 2 + 1); // 预分配防rehash
List<Integer> result = new ArrayList<>();
for (Integer x : list) { if (set.add(x)) result.add(x); }

一亿个 Integer：HashSet 开销约 40~60 字节/元素，要 4~6GB 堆。预分配容量很关键，否则扩容时瞬时双倍内存。复杂度 O(n)，秒级完成。若元素是 int，用原始类型（int[] + 自己控制或第三方库如 HPPC/Eclipse Collections 的 IntSet），内存减半以上。

路线二：排序后去重（内存紧张时）Collections.sort(list)（TimSort 对几乎有序数据友好）后一次遍历，相邻比较去重。int[] 一亿个占 400MB，排序 + 去重都不用额外大内存，是空间受限的标准解。排序 O(n log n)，几十秒内。

路线三：量化的 Bitmap（元素值域可控） 若元素是数字且值域已知（如用户 ID < 10 亿），BitSet 每元素 1 bit，一亿去重只占值域/8 字节，遍历置位再输出——最快且最省。值域稀疏就换 RoaringBitmap。

路线四：外部分布式去重（单机放不下） 数据本身超内存（字符串对象等）：写文件按 hash 分片（如 128 片），每片单独 HashSet 去重（分治后单片必然可单机处理），最后合并；或直接 Spark distinct() / Flink 去重，本质相同。

面试要点：先问清楚元素类型（Integer 还是业务对象）、内存预算、是否需要保序、重复率——HashSet 保序 O(n)、排序法不保序但省内存、Bitmap 要值域、海量上分布式。给出选型决策而非单一代码，才是架构视角。

💻 全栈开发专家 ​

一亿条 Integer 去重，我先问一句：要结果列表还是只要种类数？内存给多少？ 不同答案方案完全不同。

常规答案：HashSet

java
Set<Integer> set = new HashSet<>((int) (list.size() / 0.75f) + 1); // 预设容量防扩容
set.addAll(list);

坑：一亿个 Integer 装箱后对象头 + 引用约 20+ 字节/个，HashSet 结构再加开销，没有 8G+ 堆基本会 OOM。预设初始容量很重要，否则扩容期间旧表新表并存，内存翻倍直接炸。

省内存首选：排序后去重

java
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
Arrays.sort(arr);                 // 双轴快排，原语类型无装箱
int w = 1;
for (int i = 1; i < arr.length; i++) {
    if (arr[i] != arr[w - 1]) arr[w++] = arr[i];  // 原地去重
}
// 结果：arr[0..w)

int 数组一亿条约 400MB，排序 O(NlogN)，比 HashSet 省数倍内存，GC 压力几乎为零。这是我实际会写的版本。

并行加速

list.parallelStream().distinct().collect(toList()) 底层也是 reduce 去重，多核机器可行，但装箱开销仍在，只适合内存宽裕的场景。

再大：分片 + 外排

单机放不下就走"hash 分片到多文件 → 各自去重 → 归并"，或者干脆 bitmap（值域受限时，如 ID 范围已知，一个 bitset 几十 MB 搞定）。

面试要点：能主动对比时间（都是 O(N) 或 O(NlogN)）与空间（装箱 vs 原语 vs bitmap）的取舍，比背 API 高一个档次。