Collection体系

Java

集合框架全景图

Java集合就像是各种容器，数组是固定大小的箱子，集合是能自动伸缩的魔法口袋

顶层接口是 Collection，下面分三大家族：

List：有序、可重复（像排队，每个人有编号，允许同名）

Set：无序、不重复（像一堆弹珠，不关心顺序，不允许重复）

Queue：先进先出（像排队买奶茶，先来先服务）

文字版层次结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Iterable
└── Collection
├── List（有序可重复）
│   ├── ArrayList      ← 最常用，底层数组
│   ├── LinkedList     ← 底层链表，也实现了Queue
│   └── Vector         ← 线程安全但过时，别用
├── Set（无序不重复）
│   ├── HashSet        ← 最常用，底层HashMap
│   ├── TreeSet        ← 有序，底层红黑树
│   └── LinkedHashSet  ← 保留插入顺序
└── Queue（先进先出）
    ├── LinkedList     ← 同时实现List和Queue
    ├── PriorityQueue  ← 优先级队列
    └── ArrayDeque     ← 双端队列，比LinkedList快

另外还有个独立门派 Map体系，不属于Collection，但也是集合框架的一部分

List：有序可重复

像一个有编号的清单，每个元素都有下标（从0开始），可以有重复元素

ArrayList —— 最常用的集合，没有之一

底层是数组，查询快（通过下标直接定位），增删慢（要移动后面的元素）

默认初始容量10，扩容时变成原来的1.5倍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@Test
public void testArrayList() {
// 创建ArrayList
List<String> names = new ArrayList<>();

// 添加元素
names.add("张三");
names.add("李四");
names.add("王五");
names.add("张三");  // 可以重复！
System.out.println(names);  // [张三, 李四, 王五, 张三]

// 按下标访问，O(1) 超快
System.out.println(names.get(1));  // 李四

// 修改元素
names.set(0, "赵六");
System.out.println(names);  // [赵六, 李四, 王五, 张三]

// 删除元素（后面的元素要往前挪，O(n)）
names.remove("李四");
System.out.println(names);  // [赵六, 王五, 张三]

// 按下标删除
names.remove(0);
System.out.println(names);  // [王五, 张三]
}

LinkedList —— 链表实现

底层是双向链表，增删快（改指针就行），查询慢（要从头一个一个找）

同时实现了 List 和 Deque（双端队列）接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Test
public void testLinkedList() {
LinkedList<String> list = new LinkedList<>();

list.add("A");
list.add("B");
list.add("C");

// 头部和尾部操作很快，O(1)
list.addFirst("HEAD");
list.addLast("TAIL");
System.out.println(list);  // [HEAD, A, B, C, TAIL]

// 当队列用
System.out.println(list.getFirst());  // HEAD
System.out.println(list.getLast());    // TAIL

// 按下标访问就很慢了，O(n)
System.out.println(list.get(2));  // B（要从头数过去）
}

ArrayList vs LinkedList 性能对比

操作 ArrayList LinkedList 谁赢？
按下标查询 get(i) O(1) 直接算地址 O(n) 从头遍历 ArrayList
尾部添加 add(e) O(1) 均摊 O(1) 平手
中间插入 add(i, e) O(n) 要移动元素 O(n) 要先找到位置 看情况
中间删除 remove(i) O(n) 要移动元素 O(n) 要先找到位置 看情况
头部插入/删除 O(n) 所有元素后移 O(1) 改指针 LinkedList
内存占用 较少（连续数组） 较多（每个节点多两个指针） ArrayList

实战建议：99%的场景用 ArrayList 就对了。LinkedList 只在频繁头部插入删除时才有优势，而且现代CPU的缓存机制让数组的实际表现往往更好

Set：无序不重复

就像数学里的集合概念：元素不能重复，无所谓顺序

HashSet —— 最常用的Set

底层是 Map体系 中的 HashMap（value全放一个固定值），所以性能取决于hash函数

增删查都是 O(1)，非常快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@Test
public void testHashSet() {
Set<String> fruits = new HashSet<>();

fruits.add("苹果");
fruits.add("香蕉");
fruits.add("苹果");  // 重复！不会加进去
fruits.add("橙子");

System.out.println(fruits);        // 顺序不确定，可能是 [香蕉, 苹果, 橙子]
System.out.println(fruits.size());  // 3，不是4！重复的不算

System.out.println(fruits.contains("苹果"));  // true，O(1)

fruits.remove("香蕉");
System.out.println(fruits);  // [苹果, 橙子]
}

TreeSet —— 有序的Set

底层是红黑树，元素会自动排序（自然顺序或自定义Comparator）

增删查都是 O(log n)

1
2
3
4
5
6
7
8
9
10
@Test
public void testTreeSet() {
Set<Integer> numbers = new TreeSet<>();
numbers.add(30);
numbers.add(10);
numbers.add(20);
numbers.add(10);  // 重复，忽略

System.out.println(numbers);  // [10, 20, 30] 自动排序！
}

LinkedHashSet —— 保留插入顺序的Set

HashSet + 链表维护插入顺序，性能略低于HashSet

1
2
3
4
5
6
7
8
9
@Test
public void testLinkedHashSet() {
Set<String> set = new LinkedHashSet<>();
set.add("C");
set.add("A");
set.add("B");

System.out.println(set);  // [C, A, B] 按插入顺序输出！
}

三种Set对比

Set类型 底层 有序？ 性能 适用场景
HashSet HashMap 无序 O(1) 最快 去重、判断是否存在
TreeSet 红黑树 自然排序 O(log n) 需要排序的去重
LinkedHashSet HashMap+链表 插入顺序 O(1) 略慢 去重且保持顺序

Queue：先进先出

像排队买奶茶：先到的先买，后到的排后面（FIFO：First In First Out）

LinkedList 当Queue用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Test
public void testQueue() {
Queue<String> queue = new LinkedList<>();

// 入队
queue.offer("第1个顾客");
queue.offer("第2个顾客");
queue.offer("第3个顾客");

System.out.println(queue);  // [第1个顾客, 第2个顾客, 第3个顾客]

// 看看队头是谁（不出队）
System.out.println(queue.peek());  // 第1个顾客

// 出队（队头离开）
System.out.println(queue.poll());  // 第1个顾客
System.out.println(queue.poll());  // 第2个顾客
System.out.println(queue);          // [第3个顾客]
}

⚠️ add vs offer、remove vs poll、element vs peek

操作 抛异常版 返回null版（推荐）
入队 add() 队满抛异常 offer() 队满返回false
出队 remove() 队空抛异常 poll() 队空返回null
查看队头 element() 队空抛异常 peek() 队空返回null

实战建议：用右边那列，别给自己找异常的麻烦

PriorityQueue —— 优先级队列

不是先进先出，而是优先级高的先出（底层是堆）

1
2
3
4
5
6
7
8
9
10
11
12
@Test
public void testPriorityQueue() {
// 默认小顶堆，最小的先出
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll());  // 10（最小的先出）
System.out.println(pq.poll());  // 20
System.out.println(pq.poll());  // 30
}

常用方法速查

这些方法所有Collection子类都能用：

方法 作用 返回值
add(e) 添加元素 boolean
remove(e) 删除元素 boolean
contains(e) 是否包含 boolean
size() 元素个数 int
isEmpty() 是否为空 boolean
clear() 清空 void
iterator() 获取迭代器 Iterator
toArray() 转数组 Object[]

遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@Test
public void testIteration() {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

// 方式1：for-each（最常用，简洁）
for (String s : list) {
    System.out.println(s);
}

// 方式2：Iterator（可以在遍历时安全删除元素）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if ("B".equals(s)) {
        it.remove();  // 安全删除！
    }
}
System.out.println(list);  // [A, C]

// 方式3：Stream（Java8，后面专门讲）
list.stream().forEach(System.out::println);
}

⚠️ 遍历时删除的坑：用for-each遍历时直接调用 list.remove() 会抛 ConcurrentModificationException，必须用 Iterator 的 remove() 方法

集合的交集、并集、差集

对应 集合论基础 中的数学概念，Java用Collection的批量操作实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Test
public void testSetOperations() {
Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> setB = new HashSet<>(Arrays.asList(3, 4, 5, 6, 7));

// 并集：A ∪ B
Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);
System.out.println("并集：" + union);  // [1, 2, 3, 4, 5, 6, 7]

// 交集：A ∩ B
Set<Integer> intersection = new HashSet<>(setA);
intersection.retainAll(setB);
System.out.println("交集：" + intersection);  // [3, 4, 5]

// 差集：A - B
Set<Integer> difference = new HashSet<>(setA);
difference.removeAll(setB);
System.out.println("差集：" + difference);  // [1, 2]
}

常见坑

坑1：自定义对象放HashSet/HashMap，不重写hashCode和equals

HashSet判断重复靠 hashCode() + equals()，不重写的话两个”相同”的对象会被当成不同的

详见 Object类 中关于equals和hashCode的约定

坑2：遍历时修改集合

for-each里直接 list.remove() 会炸，要用Iterator

坑3：Arrays.asList() 返回的List不能增删

1
2
3
4
5
List<String> list = Arrays.asList("A", "B", "C");
// list.add("D");  // ❌ UnsupportedOperationException！
// 这个List是固定大小的，要想增删，包一层：
List<String> mutableList = new ArrayList<>(Arrays.asList("A", "B", "C"));
mutableList.add("D");  // ✅

坑4：List的remove方法重载

1
2
3
4
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
list.remove(1);           // 删除下标1的元素，结果 [1, 3]
list.remove(Integer.valueOf(1));  // 删除值为1的元素，结果 [3]
// 参数是int就按下标删，参数是Integer对象就按值删，别搞混！

练习题

题1：去重 —— 给定一个List，去掉里面的重复元素，保持原来的顺序

提示：用哪种Set可以保持插入顺序？

1
2
3
4
5
6
7
8
@Test
public void exercise1() {
List<Integer> list = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3);
// 你的代码：去重并保持顺序
Set<Integer> set = new LinkedHashSet<>(list);
List<Integer> result = new ArrayList<>(set);
System.out.println(result);  // [3, 1, 4, 5, 9, 2, 6]
}

题2：统计词频 —— 统计一个字符串数组中每个单词出现的次数

提示：用 Map体系 中的HashMap，key是单词，value是次数

题3：两个List求交集 —— 不用retainAll，自己用HashSet实现

提示：把第一个List放进HashSet，遍历第二个List检查contains

上一章 目录 下一章
Math类 java基础 Map体系