List 与 Set 详解
深入 ArrayList、LinkedList、HashSet、TreeSet 原理
List 与 Set 详解
List 有序可重复，Set 无序不重复。选对集合对性能影响巨大。
学完本章你将： 掌握 ArrayList/LinkedList 区别、HashSet/TreeSet 原理。
ArrayList vs LinkedList —— 底层结构决定性能
java
// ArrayList：底层是数组 → 按索引访问 O(1)，中间插入/删除 O(n)
List<String> array = new ArrayList<>();
array.add("A"); // 末尾加 O(1)
System.out.println(array.get(0)); // 随机访问 O(1) 闪电般快
// LinkedList：底层是双向链表 → 按索引访问 O(n)，头尾操作 O(1)
List<String> linked = new LinkedList<>();
linked.addFirst("First"); // 头部插 O(1) 很快
linked.addLast("Last"); // 尾部插 O(1) 也很快
// 选择策略
// 经常 get(index) → ArrayList（95% 场景）
// 经常在头部增删 → LinkedListHashSet —— 不重复的奥秘
HashSet 底层就是个 HashMap（值固定为 dummy 对象）。判断重复靠的是 hashCode() + equals()——所以作为 Set 元素的类必须正确重写这两个方法。
java
class Person {
String name;
int age;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person p)) return false;
return age == p.age && Objects.equals(name, p.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age); // 不重写这个，HashSet 会出 bug！
}
}
Set<Person> set = new HashSet<>();
set.add(new Person("Alice", 25));
set.add(new Person("Bob", 30));
set.add(new Person("Alice", 25)); // equals 相等 → 添加失败
System.out.println(set.size()); // 2TreeSet —— 自动排序的 Set
TreeSet 基于红黑树，元素自动排序。元素必须实现 Comparable 或提供 Comparator。
java
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.add(3);
System.out.println(treeSet); // [1, 3, 5] —— 自动有序
// 自定义排序：降序
Set<String> reverseOrder = new TreeSet<>((a, b) -> b.compareTo(a));
reverseOrder.add("Java");
reverseOrder.add("Python");
reverseOrder.add("C");
System.out.println(reverseOrder); // [Python, Java, C]性能速查
| 集合 | add | remove | contains | get(index) |
|---|---|---|---|---|
| ArrayList | O(1)* | O(n) | O(n) | O(1) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
| HashSet | O(1) | O(1) | O(1) | — |
| TreeSet | O(log n) | O(log n) | O(log n) | — |
---
## TreeSet
```java
// 基于红黑树，自动排序
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.add(3);
System.out.println(treeSet); // [1, 3, 5]（有序）
// 自定义排序
Set<String> custom = new TreeSet<>((a, b) -> b.compareTo(a));
custom.add("Java");
custom.add("Python");
custom.add("C");
System.out.println(custom); // [Python, Java, C]（降序）性能对比
| 集合 | 添加 | 删除 | 包含 |
|---|---|---|---|
| ArrayList | O(1) 末尾 | O(n) | O(n) |
| LinkedList | O(1) | O(1) | O(n) |
| HashSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |