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

日期：2026-07-12
标签：#面试 #八股 #后端 #Java集合 #大数据 #场景题

一句话答案

先确认元素类型、内存和是否保序：内存充足用 HashSet，需节省内存可排序后双指针原地去重，放不下内存则哈希分桶或外部排序。

面试口语版

一亿条不能直接默认 stream().distinct()，对象和 HashSet 节点开销可能导致 OOM。如果内存足够且只需判断重复，用预估容量的 HashSet 单遍处理，平均 O(n)，需要保持首次出现顺序可按原列表扫描输出。若允许改变顺序，对 ArrayList 排序后用双指针把不同元素压到前面，额外空间小但 O(n log n)。内存不足时按稳定 hash 把数据分到多个文件，同值必在同桶，再逐桶内存去重；或做外部排序后线性去重。整数可用 primitive 集合、Bitmap 或 RoaringBitmap 降低对象开销。

关键细节

HashSet 预分配需按元素数/负载因子估算，并留 JVM 其他空间。
distinct() 的有状态去重仍需保存已见集合。
分桶数量根据单桶最大数据和倾斜情况计算。
自定义对象必须正确实现稳定的 equals/hashCode。

面试官追问

如何保证分桶去重不漏数据？
需要保持原始顺序怎么办？
为什么 HashSet 实际内存远大于原数据？

面试官追问参考答案

1. 如何保证分桶去重不漏数据？

使用确定性函数 hash(value) mod N，相同值一定进入同一桶，每条输入只写一个桶。每桶独立去重后合并；任务记录分片、条数和校验和，失败只重跑对应输入分片。

2. 需要保持原始顺序怎么办？

内存够时按原列表扫描，用 Set 判断首次出现并写入结果。外存场景可先分桶计算“值的最早位置”，再按最早位置做外部排序输出，代价比无序去重更高。

3. 为什么 HashSet 实际内存远大于原数据？

除元素对象外还有桶数组、节点对象、引用、hash 字段、对象头、对齐和空槽；装载因子还预留容量。应使用 JOL/实测估算，primitive 集合可显著减少装箱开销。

学习清单

能按内存、顺序和类型选择算法。
掌握外部哈希分桶和外部排序。