如果 ArrayList 中存储了 1 亿条记录，你会采用什么方案来去除其中的重复数据？
考察说明
考查在大数据量场景下对去重方案的选择、复杂度分析及内存与性能的权衡。
回答思路
- 【回答框架 1】先明确去重目标：保留首次出现还是最后一次出现，以及是否需要保持原有顺序，这决定了方案选择。
- 【回答框架 2】若内存允许，使用 HashSet 或 LinkedHashSet 遍历一次，时间复杂度 O(n)，空间复杂度 O(n)，可保持顺序且实现简单，但 1 亿条数据可能占用数 GB 内存，需评估 JVM 堆大小。
- 【回答框架 3】若内存受限，可采用外部排序后相邻比较去重，或使用数据库临时表加唯一索引，或利用布隆过滤器先过滤大部分重复，再对可能重复的做精确校验，但布隆过滤器有误判率，需权衡。
- 【回答框架 4】对于 1 亿级别数据，还可考虑分治：将数据分片，每片分别用 HashSet 去重，再合并结果或使用位图、基数排序等特殊数据结构，需根据数据类型（如整数、字符串）选择最合适方案。
- 【回答框架 5】最终方案需结合数据特征、可用内存、允许的耗时和是否允许漏重或错判来决定，并给出具体空间估算和性能预期。
- 【关键点 1】HashSet 去重最简单，时间复杂度 O(n)，空间 O(n)，但内存消耗大。
- 【关键点 2】保持顺序用 LinkedHashSet，否则可用 HashSet。
- 【关键点 3】内存不足时考虑外部排序、数据库唯一索引或布隆过滤器加精确校验。
- 【关键点 4】1 亿数据内存占用需估算，如 Integer 约 4 字节但对象头导致实际更大，需谨慎。
- 【关键点 5】分片去重结合合并，可降低单机内存压力，但需处理跨片重复。
- 【易错点 1】直接使用 HashSet 可能引发内存溢出，需先评估堆内存。
- 【易错点 2】布隆过滤器有误判，可能漏掉重复，不适合要求精确去重的场景。
- 【易错点 3】使用数据库去重时，考虑导入导出耗时和索引维护成本，可能性能低下。