面试中常问的 List 去重问题，你都答对了吗？

一道被问烂的面试题如果你去面试 Java 开发岗位尤其是初级到中级岗位十有八九会被问到「如何对一个 List 进行去重」很多候选人会脱口而出「用 HashSet 啊把 List 丢进去再拿出来不就好了。」但老练的面试官会继续追问用 HashSet 去重之后顺序还和原来一样吗如果 List 里装的是自定义对象HashSet 还能正确去重吗如果既要保证顺序又要高效去重应该怎么选Java 8 的stream().distinct()底层是怎么实现的如果数据量上百万哪种方式性能最好重写equals的同时为什么必须重写hashCodeList 去重本身只是一行代码的事但它背后牵扯到集合框架、哈希原理、对象相等性、算法复杂度、Java 8 Stream 机制等知识点。一、为什么面试官偏爱「List 去重」这道题题面简单人人都能答上几句但不同层次的候选人回答深度可以天差地别。这道题可以考察集合框架的掌握程度List、Set、Map 的特性HashSet、LinkedHashSet、TreeSet 的区别。对「相等性」的理解equals 和 hashCode 的契约。算法与复杂度的敏感度O(n²) 和 O(n) 的差距空间换时间的取舍。对 JDK 新特性的了解Stream API 和distinct()实现原理。工程实践意识结合数据量、是否要求顺序、是否要求排序等业务场景选型。二、准备工作构造一个带重复元素的 ListjavaListString list new ArrayList(); list.add(Java); list.add(Python); list.add(Java); list.add(Go); list.add(Python); list.add(C); list.add(Java); // 去重前[Java, Python, Java, Go, Python, C, Java]期望结果[Java, Python, Go, C]即去重的同时尽量保留原有顺序。三、方案一双重 for 循环暴力去重javafor (int i 0; i list.size() - 1; i) { for (int j list.size() - 1; j i; j--) { if (list.get(j).equals(list.get(i))) { list.remove(j); } } }为什么内层循环要倒着遍历ArrayList的remove会触发元素搬移删除后后续元素下标前移。如果从前往后遍历会出现「漏删」或「下标越界」。从后往前遍历时删除元素只影响下标更大的元素而这些位置已经处理过不会漏删。复杂度分析时间复杂度O(n²)空间复杂度O(1)原地操作只适合数据量很小、不希望占用额外内存的场景。四、方案二单层 for 循环 contains 判断javaListString result new ArrayList(); for (String item : list) { if (!result.contains(item)) { result.add(item); } }问题List.contains底层是indexOf本质仍是线性扫描时间复杂度依然是O(n²)。优势代码简洁易读能保持顺序。劣势无法应对大数据量场景。五、方案三HashSet 去重最经典的答案javaSetString set new HashSet(list); ListString result new ArrayList(set);原理HashSet 底层基于 HashMap依赖元素的hashCode和equals判断重复add、contains平均时间复杂度O(1)。整体去重时间复杂度从 O(n²) 降到O(n)。致命缺陷HashSet 不保证元素的迭代顺序。输出可能是[Java, C, Go, Python]而且每次运行结果可能不同。本质空间换时间——额外申请哈希表辅助判重。六、方案四LinkedHashSet 保持顺序去重javaSetString set new LinkedHashSet(list); ListString result new ArrayList(set); // 输出[Java, Python, Go, C]原理LinkedHashSet 继承自 HashSet内部维护一个双向链表记录插入顺序。遍历时按链表顺序返回实现「按插入顺序去重」。注意保持的是插入顺序不是排序顺序。时间复杂度仍为O(n)只是比 HashSet 略多一点内存开销。选型对顺序无要求用HashSet。要求保持第一次出现顺序用LinkedHashSet。要求去重后排序用TreeSet。七、方案五Java 8 Stream 的 distinct()javaListString result list.stream() .distinct() .collect(Collectors.toList());底层实现JDK 源码DistinctOps中串行流去重实质是使用LinkedHashSet所以有序串行流中distinct()能保持元素第一次出现的顺序。关键点distinct()是一个有状态中间操作必须保留所有已见过的元素才能判断后续元素是否重复因此会占用O(n)级别的临时内存。依据的同样是对象的equals和hashCode。对大多数「去重并保持原顺序」场景这是语义最清晰、代码最简洁的写法。八、方案六TreeSet 去重顺便排序javaSetString set new TreeSet(list); ListString result new ArrayList(set); // 输出[C, Go, Java, Python]原理TreeSet 底层基于 TreeMap红黑树插入、删除、查找稳定在O(log n)整体去重O(n log n)。自定义排序javaSetString set new TreeSet( Comparator.comparingInt(String::length) .thenComparing(String::compareTo)); set.addAll(list);必须注意的坑TreeSet 判断重复不是通过equals而是通过compareTo或Comparator.compare返回值是否为 0。javaSetUser set new TreeSet(Comparator.comparingInt(u - u.id)); set.add(new User(1, Alice)); set.add(new User(1, Bob)); System.out.println(set.size()); // 输出 1Bob 被丢弃虽然 Alice 和 Bob 是两个不同对象equals返回 false但 Comparator 认为二者「相等」Bob 被丢弃。应尽量保证排序字段与业务上的重复判定字段一致。九、方案七BitSet 对整数去重进阶加分项适用于取值范围可控的非负整数如用户 ID、状态码。javaBitSet bitSet new BitSet(max 1); for (Integer number : numbers) { bitSet.set(number); } ListInteger result new ArrayList(); for (int i 0; i max; i) { if (bitSet.get(i)) { result.add(i); } } // 输出[1, 3, 5, 8, 9]优点时间复杂度接近 O(n)去重后天然升序位图占用内存小。缺点只适用于非负整数取值上限不能太大。十、自定义对象去重equals 和 hashCode 必须一起重写javastatic class User { private int id; private String name; // 只重写 equals不重写 hashCode —— 错误示范 Override public boolean equals(Object obj) { if (this obj) return true; if (!(obj instanceof User)) return false; User other (User) obj; return id other.id name.equals(other.name); } }为什么去重失败HashSet 先根据hashCode定位桶再在同一桶内用equals判断相等。如果不重写hashCode两个业务上相等的对象仍然使用Object.hashCode根据内存地址计算会落到不同的哈希桶中即使equals返回 trueHashSet 也不会拿它们比较最终去重失败。正确做法javaOverride public boolean equals(Object obj) { if (this obj) return true; if (!(obj instanceof User)) return false; User other (User) obj; return id other.id Objects.equals(name, other.name); } Override public int hashCode() { return Objects.hash(id, name); }equals 的契约自反性、对称性、传递性、一致性、非空性。hashCode 的契约两个对象 equals 返回 truehashCode 必须相等。两个对象 equals 返回 falsehashCode 不一定要不同但不同可提升哈希表性能。面试标准回答重写 equals 必须重写 hashCode是为了保证 equals 契约和 hashCode 契约的一致性否则对象在 HashMap、HashSet 等哈希集合中会表现出不可预期的行为。十一、性能实测对比javapublic class DeduplicateBenchmark { public static void main(String[] args) { int size 200_000; ListInteger list new ArrayList(size); Random random new Random(42); for (int i 0; i size; i) { list.add(random.nextInt(size / 2)); } // 分别测试双重 for 循环、contains、HashSet、LinkedHashSet、Stream.distinct() } }典型性能对比数据量 20 万方案时间复杂度是否保序相对性能双重 for 循环O(n²)是极慢contains 判断O(n²)是极慢HashSetO(n)否快LinkedHashSetO(n)是快略慢于 HashSetStream.distinct()O(n)是快TreeSetO(n log n)排序中等BitSetO(n)升序极快限整数十二、面试答题思路总结面试被问到 List 去重时可以按下面的层次回答先给最经典答案用 HashSet 去重时间复杂度 O(n)但不保证顺序。补充顺序要求如果要求保持原顺序用LinkedHashSet或Stream.distinct()。补充排序要求如果要求去重后排序用TreeSet。补充小数据量场景双重 for 循环或 contains 判断虽然 O(n²) 但代码简单、不占额外空间。补充特殊场景非负整数范围可控时用BitSet极致高效。补充关键坑点自定义对象必须同时重写equals和hashCodeTreeSet 判断重复依赖Comparator而不是equals。总结选型需求推荐方案只要去重不关心顺序HashSet去重 保持原顺序LinkedHashSet / Stream.distinct()去重 排序TreeSet数据量小、不想占额外空间双重 for 循环非负整数、范围可控BitSet一句话总结List 去重看似简单但背后涉及的集合框架、哈希原理、equals/hashCode 契约、算法复杂度和 Stream 机制正是面试官用来区分「背答案型」和「理解原理型」候选人的绝佳素材。