集合框架 - Java

01. 集合框架概览

Java 的集合框架就像一套收纳工具，List 是有序可重复的列表，Set 是无序不可重复的集合，Map 是键值对。主要接口是 Collection 和 Map，下面各有不同的实现类。ArrayList 和 LinkedList、HashSet 和 TreeSet、HashMap 和 TreeMap，不同的实现适用于不同的场景。

java

import java.util.*;

List<String> list = new ArrayList<>();    // 可重复有序
Set<String> set = new HashSet<>();         // 不可重复无序
Map<String, Integer> map = new HashMap<>(); // 键值对
Queue<String> queue = new LinkedList<>();  // 队列

声明变量用接口类型，new 的时候用具体实现类，方便后期切换。

02. ArrayList vs LinkedList

ArrayList 底层是数组，查询快 O(1)，增删慢 O(n)因为要挪动元素。LinkedList 底层是双向链表，查询慢 O(n)要遍历，增删快 O(1)改指针就行。大部分场景用 ArrayList，因为实际开发中查的多改的少。LinkedList 实现了 Deque 接口，可以当队列和栈用。

java

ArrayList<Integer> arr = new ArrayList<>();
arr.add(1); arr.get(0); arr.remove(0);

LinkedList<Integer> linked = new LinkedList<>();
linked.addFirst(1);  // 头部插入
linked.addLast(2);   // 尾部插入
linked.pollFirst();  // 弹出头部，可以当队列用

默认用 ArrayList，只有频繁在头部增删时才用 LinkedList。

03. HashSet 和 TreeSet

HashSet 基于哈希表，无序，增删查都是 O(1)。TreeSet 基于红黑树，有序（自然排序或自定义比较器），增删查 O(log n)。HashSet 快但没顺序，TreeSet 有顺序但慢一些。去重场景首选 HashSet，需要排序输出用 TreeSet。

java

Set<Integer> hashSet = new HashSet<>();
hashSet.add(3); hashSet.add(1); hashSet.add(2);
// 输出顺序不确定：可能是 1,2,3 也可能不是

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3); treeSet.add(1); treeSet.add(2);
// 输出一定是有序的：1, 2, 3

// 自定义排序
Set<String> sorted = new TreeSet<>((a, b) -> b.compareTo(a));

04. HashMap 原理和遍历

HashMap 底层是数组加链表（JDK8 加入了红黑树），通过 key 的 hashCode 找到桶的位置。冲突少的时候是链表，冲突多了转成红黑树提高效率。遍历 Map 有三种方式：keySet 遍历键，values 遍历值，entrySet 遍历键值对（最推荐因为一次拿俩）。

java

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 5);

// 推荐：遍历键值对
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// JDK8 流式写法
map.forEach((k, v) -> System.out.println(k + ": " + v));

entrySet 遍历效率最高，因为一次就能拿到 key 和 value，不用先拿 key 再 get。

05. Collections 工具类

Collections 是集合的工具类，全是静态方法。排序 sort、翻转 reverse、打乱 shuffle、最大值 max、最小值 min、线程安全包装 synchronizedXXX、不可变包装 unmodifiableXXX。Arrays 工具类处理数组，asList 可以把数组转 List 但注意是固定大小的。

java

List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list);           // 升序
Collections.reverse(list);        // 翻转
Collections.shuffle(list);        // 洗牌
int max = Collections.max(list);  // 最大值
Collections.frequency(list, 1);   // 计数

// 线程安全包装
List<Integer> syncList = Collections.synchronizedList(list);

Arrays.asList 返回的 List 是固定大小的，不能 add 或 remove。

知识测验

第 1/4 题正确 0

ArrayList 的底层数据结构是什么？

异常处理