ArrayList如何去重

ArrayList 本身 不去重，但借助 Set 可以 一行代码 搞定，同时保序/不保序任选。

最简洁：保插入顺序（推荐）

List<String> noDup = new ArrayList<>(new LinkedHashSet<>(oldList));

• 利用 LinkedHashSet 既去重又保序

• 时间复杂度 O(n)，空间额外一份 Set

不关注顺序：用 HashSet（再打乱）

List<String> noDup = new ArrayList<>(new HashSet<>(oldList));

结果顺序与 oldList 无关（哈希打散）

Java 8 Stream 链式（保序）

import static java.util.stream.Collectors.*;

List<String> noDup = oldList.stream()
                            .distinct()     // 去重
                            .collect(toList());

• 部用 LinkedHashSet 实现 distinct()，顺序不变

• 可读性高，可再叠加 filter/sorted

手写去重（教学/面试写思路）

List<String> list = new ArrayList<>();
Set<String> seen = new HashSet<>();
for (String s : oldList) {
    if (seen.add(s)) list.add(s);   // add 返回 false 表示已存在
}

同样 O(n)，同样保序，不引入第三方集合构造器

线程安全列表去重

List<String> syncList = Collections.synchronizedList(oldList);
synchronized (syncList) {                       // 必须手动同步
    List<String> noDup = new ArrayList<>(new LinkedHashSet<>(syncList));
}

“保序 new LinkedHashSet，无序 new HashSet，Stream 一行 distinct”。

相同数据下，ArrayList.contains和set.contains谁的速度快

相同数据量下，Set.contains 远比 ArrayList.contains 快，差距是 O(1) vs O(n) 的量级。

源码级复杂度

实测数据（OpenJDK 17，10 万元素，key 为 String）

什么时候会接近？

• 数据量极小（< 10）且哈希函数质量差、冲突严重，链表退化到 O(k)（k 为冲突长度），但仍远小于 O(n)。

• 若使用 TreeSet（红黑树），复杂度是 O(log n)，也比 ArrayList 快得多。

结论口诀
“查存在，先转 Set；List 顺序找，慢到哭”。