企业官网建设流程全解析

一道被问烂的面试题：如果你去面试 Java 开发岗位，尤其是初级到中级岗位，十有八九会被问到：「如何对一个 List 进行去重？」

很多候选人会脱口而出：「用 HashSet 啊，把 List 丢进去再拿出来不就好了。」但老练的面试官会继续追问：

• 用 HashSet 去重之后，顺序还和原来一样吗？

• 如果 List 里装的是自定义对象，HashSet 还能正确去重吗？

• 如果既要保证顺序，又要高效去重，应该怎么选？

• Java 8 的stream().distinct()底层是怎么实现的？

• 如果数据量上百万，哪种方式性能最好？

• 重写equals的同时，为什么必须重写hashCode？

List 去重本身只是一行代码的事，但它背后牵扯到集合框架、哈希原理、对象相等性、算法复杂度、Java 8 Stream 机制等知识点。

一、为什么面试官偏爱「List 去重」这道题

题面简单，人人都能答上几句，但不同层次的候选人回答深度可以天差地别。这道题可以考察：

• 集合框架的掌握程度：List、Set、Map 的特性，HashSet、LinkedHashSet、TreeSet 的区别。

• 对「相等性」的理解：equals 和 hashCode 的契约。

• 算法与复杂度的敏感度：O(n²) 和 O(n) 的差距，空间换时间的取舍。

• 对 JDK 新特性的了解：Stream API 和distinct()实现原理。

• 工程实践意识：结合数据量、是否要求顺序、是否要求排序等业务场景选型。

二、准备工作：构造一个带重复元素的 List

java

List<String> 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 循环暴力去重

java

for (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 判断

java

List<String> result = new ArrayList<>(); for (String item : list) { if (!result.contains(item)) { result.add(item); } }

问题：List.contains底层是indexOf，本质仍是线性扫描，时间复杂度依然是O(n²)。

优势：代码简洁易读，能保持顺序。
劣势：无法应对大数据量场景。

五、方案三：HashSet 去重（最经典的答案）

java

Set<String> set = new HashSet<>(list); List<String> result = new ArrayList<>(set);

原理：HashSet 底层基于 HashMap，依赖元素的hashCode和equals判断重复，add、contains平均时间复杂度O(1)。整体去重时间复杂度从 O(n²) 降到O(n)。

致命缺陷：HashSet 不保证元素的迭代顺序。输出可能是[Java, C++, Go, Python]，而且每次运行结果可能不同。

本质：空间换时间——额外申请哈希表辅助判重。

六、方案四：LinkedHashSet 保持顺序去重

java

Set<String> set = new LinkedHashSet<>(list); List<String> result = new ArrayList<>(set); // 输出：[Java, Python, Go, C++]

原理：LinkedHashSet 继承自 HashSet，内部维护一个双向链表记录插入顺序。遍历时按链表顺序返回，实现「按插入顺序去重」。

注意：保持的是插入顺序，不是排序顺序。

时间复杂度：仍为O(n)，只是比 HashSet 略多一点内存开销。

选型：

• 对顺序无要求：用HashSet。

• 要求保持第一次出现顺序：用LinkedHashSet。

• 要求去重后排序：用TreeSet。

七、方案五：Java 8 Stream 的 distinct()

java

List<String> result = list.stream() .distinct() .collect(Collectors.toList());

底层实现：JDK 源码DistinctOps中，串行流去重实质是使用LinkedHashSet，所以有序串行流中distinct()能保持元素第一次出现的顺序。

关键点：

• distinct()是一个有状态中间操作，必须保留所有已见过的元素才能判断后续元素是否重复，因此会占用O(n)级别的临时内存。

• 依据的同样是对象的equals和hashCode。

• 对大多数「去重并保持原顺序」场景，这是语义最清晰、代码最简洁的写法。

八、方案六：TreeSet 去重（顺便排序）

java

Set<String> set = new TreeSet<>(list); List<String> result = new ArrayList<>(set); // 输出：[C++, Go, Java, Python]

原理：TreeSet 底层基于 TreeMap（红黑树），插入、删除、查找稳定在O(log n)，整体去重O(n log n)。

自定义排序：

java

Set<String> set = new TreeSet<>( Comparator.comparingInt(String::length) .thenComparing(String::compareTo)); set.addAll(list);

必须注意的坑：TreeSet 判断重复不是通过equals，而是通过compareTo或Comparator.compare返回值是否为 0。

java

Set<User> 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()); // 输出 1，Bob 被丢弃

虽然 Alice 和 Bob 是两个不同对象，equals返回 false，但 Comparator 认为二者「相等」，Bob 被丢弃。应尽量保证排序字段与业务上的重复判定字段一致。

九、方案七：BitSet 对整数去重（进阶加分项）

适用于取值范围可控的非负整数（如用户 ID、状态码）。

java

BitSet bitSet = new BitSet(max + 1); for (Integer number : numbers) { bitSet.set(number); } List<Integer> 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 必须一起重写

java

static 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返回 true，HashSet 也不会拿它们比较，最终去重失败。

正确做法：

java

@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 && Objects.equals(name, other.name); } @Override public int hashCode() { return Objects.hash(id, name); }

equals 的契约：自反性、对称性、传递性、一致性、非空性。

hashCode 的契约：

• 两个对象 equals 返回 true，hashCode 必须相等。

• 两个对象 equals 返回 false，hashCode 不一定要不同，但不同可提升哈希表性能。

面试标准回答：重写 equals 必须重写 hashCode，是为了保证 equals 契约和 hashCode 契约的一致性，否则对象在 HashMap、HashSet 等哈希集合中会表现出不可预期的行为。

十一、性能实测对比

java

public class DeduplicateBenchmark { public static void main(String[] args) { int size = 200_000; List<Integer> 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 万）：

十二、面试答题思路总结

面试被问到 List 去重时，可以按下面的层次回答：

1. 先给最经典答案：用 HashSet 去重，时间复杂度 O(n)，但不保证顺序。

2. 补充顺序要求：如果要求保持原顺序，用LinkedHashSet或Stream.distinct()。

3. 补充排序要求：如果要求去重后排序，用TreeSet。

4. 补充小数据量场景：双重 for 循环或 contains 判断，虽然 O(n²) 但代码简单、不占额外空间。

5. 补充特殊场景：非负整数范围可控时用BitSet，极致高效。

6. 补充关键坑点：自定义对象必须同时重写equals和hashCode；TreeSet 判断重复依赖Comparator而不是equals。

7. 总结选型：

一句话总结：List 去重看似简单，但背后涉及的集合框架、哈希原理、equals/hashCode 契约、算法复杂度和 Stream 机制，正是面试官用来区分「背答案型」和「理解原理型」候选人的绝佳素材。