集合

Java 集合框架详解：从基础到实践

Java 集合框架（Java Collections Framework）是处理对象集合的核心工具，位于 java.util 包下，提供了一套统一的接口和实现类，用于存储、操作和管理一组对象。与数组相比，集合能自动调整大小，支持泛型（编译期类型检查），并提供了丰富的操作方法（如添加、删除、查找等）。本文将系统讲解集合框架的体系结构、核心实现类及常见问题解决方案。

集合框架体系概览

Java 集合框架主要分为两大体系：Collection（单列集合） 和 Map（双列集合）。

1. Collection 接口：独立元素的序列

Collection 是所有单列集合的根接口，存储一组独立元素，主要子接口包括：

• List：有序、可重复（如动态数组）；
• Set：无序、不可重复（如数学中的 “集合”）；
• Queue：按特定规则排序（如先进先出的队列）。

2. Map 接口：键值对的映射

Map 存储 “键值对”（key-value），通过键（key）查找值（value），键不可重复，值可重复。主要实现类包括 HashMap、TreeMap、LinkedHashMap 等。

Collection 子接口及实现类

List：有序可重复的动态数组

List 以插入顺序保存元素，允许重复，支持通过索引访问（类似数组）。核心实现类：ArrayList、LinkedList、Vector。

（1）ArrayList：基于数组的动态列表

• 底层结构：数组（Object[]），默认初始容量为 10，当元素满时自动扩容（默认扩容为原容量的 1.5 倍）。
• 特性：
  • 优势：随机访问效率高（通过索引直接访问，时间复杂度 O(1)）；
  • 劣势：中间插入 / 删除元素效率低（需移动后续元素，时间复杂度 O(n)）；
  • 非线程安全（多线程环境需手动同步，或使用 CopyOnWriteArrayList）。

（2）LinkedList：基于双向链表的列表

• 底层结构：双向链表（每个节点包含 prev、next 指针和元素值）。
• 特性：
  • 优势：中间插入 / 删除元素效率高（只需修改指针，时间复杂度 O(1)）；
  • 劣势：随机访问效率低（需从表头 / 表尾遍历，时间复杂度 O(n)）；
  • 非线程安全，可作为栈、队列、双向队列使用（提供 addFirst()、removeLast() 等方法）。

（3）Vector：线程安全的动态数组（已过时）

• 底层结构：数组，与 ArrayList 类似，但所有方法均被 synchronized 修饰（线程安全）。
• 问题：同步导致性能低下，推荐用 CopyOnWriteArrayList（并发包中的线程安全列表）替代。

List 实现类对比

特性	ArrayList	LinkedList	Vector（过时）
底层结构	数组	双向链表	数组
随机访问	快（O(1)）	慢（O(n)）	快（O(1)）
插入 / 删除（中间）	慢（O(n)）	快（O(1)）	慢（O(n)+ 同步开销）
线程安全	否	否	是（低效）
适用场景	频繁查询，少量增删	频繁增删，少量查询	无（推荐 CopyOnWriteArrayList）

Set：无序不可重复的集合

Set 不允许存储重复元素（通过 equals() 和 hashCode() 判断重复），无序（元素存储位置与插入顺序无关）。核心实现类：HashSet、LinkedHashSet、TreeSet。

（1）HashSet：基于哈希表的无序集合

• 底层结构：哈希表（数组 + 链表 / 红黑树，依赖 HashMap 实现，元素作为 HashMap 的 key）。
• 特性：
  • 无序：元素存储位置由哈希值决定，与插入顺序无关；
  • 去重规则：先通过 hashCode() 比较哈希值，若相同再通过 equals() 比较内容；
  • 高效：添加、删除、查找的时间复杂度平均为 O(1)；
  • 非线程安全，允许存储 null（仅一个）。

（2）LinkedHashSet：维持插入顺序的哈希集合

• 底层结构：哈希表 + 双向链表（继承 HashSet，内部使用 LinkedHashMap 实现）。
• 特性：
  • 有序：通过链表维持元素插入顺序，遍历顺序与插入顺序一致；
  • 性能：略低于 HashSet（维护链表额外开销），但遍历效率更高；
  • 其他特性与 HashSet 一致（去重、非线程安全等）。

（3）TreeSet：可排序的集合

• 底层结构：红黑树（一种自平衡二叉查找树，依赖 TreeMap 实现）。
• 特性：
  • 有序：元素按指定规则排序（自然排序或定制排序）；
  • 排序规则：
    • 自然排序：元素类实现 Comparable 接口，重写 compareTo() 方法；
    • 定制排序：创建 TreeSet 时传入 Comparator 接口实现类；
  • 查找效率高（O(log n)），但添加 / 删除效率低于 HashSet；
  • 非线程安全，不允许 null（排序时会抛出异常）。

Set 实现类对比

特性	HashSet	LinkedHashSet	TreeSet
底层结构	哈希表	哈希表 + 链表	红黑树
顺序	无序	插入顺序	排序顺序（自然 / 定制）
去重依据	hashCode() + equals()	hashCode() + equals()	compareTo()/compare()
时间复杂度	增删查 O(1)	增删查 O(1)（略低）	增删查 O(log n)
适用场景	快速去重，无需顺序	去重 + 需插入顺序遍历	去重 + 需排序

Queue：按规则排序的队列

Queue 用于存储 “等待处理的元素”，通常按 FIFO（先进先出） 规则排序，核心实现类：LinkedList、PriorityQueue、ArrayBlockingQueue。

（1）LinkedList：双向队列

LinkedList 实现了 Queue 接口，可作为队列使用，核心方法：

• offer(e)：尾部添加元素（成功返回 true）；
• poll()：移除并返回头部元素（空队列返回 null）；
• peek()：返回头部元素（空队列返回 null）。

（2）PriorityQueue：优先级队列

• 特性：元素按优先级排序（默认自然排序，或通过 Comparator 定制），每次出队的是 “优先级最高” 的元素（非 FIFO）。
• 适用场景：任务调度（优先执行高优先级任务）。

（3）BlockingQueue：阻塞队列（并发场景）

位于 java.util.concurrent 包，支持阻塞操作：

• 当队列满时，put(e) 阻塞直到有空间；
• 当队列空时，take() 阻塞直到有元素。
• 适用场景：生产者 - 消费者模式（如线程池任务队列）。

Map 接口及实现类

Map 存储键值对（key-value），键唯一（重复添加会覆盖值），值可重复。核心实现类：HashMap、LinkedHashMap、TreeMap、HashTable。

HashMap：基于哈希表的键值对映射

• 底层结构：哈希表（JDK 8+ 为数组 + 链表 / 红黑树，当链表长度 > 8 时转为红黑树）。
• 特性：
  • 无序：键的存储位置由哈希值决定；
  • 键值规则：键可为 null（仅一个），值可为 null；
  • 高效：增删查时间复杂度平均 O(1)；
  • 非线程安全，初始容量 16，负载因子 0.75（当元素数 > 容量 × 负载因子时扩容为 2 倍）。

LinkedHashMap：维持插入顺序的哈希映射

• 底层结构：哈希表 + 双向链表（继承 HashMap，通过链表维持键的插入顺序）。
• 特性：
  • 有序：遍历顺序与键的插入顺序一致；
  • 性能：略低于 HashMap（维护链表开销），但遍历效率更高；
  • 其他特性与 HashMap 一致（非线程安全、允许 null 等）。

TreeMap：可排序的键值对映射

• 底层结构：红黑树（键按排序规则存储）。
• 特性：
  • 有序：键按自然排序或定制排序（同 TreeSet）；
  • 支持范围查询（如 subMap(fromKey, toKey) 获取子映射）；
  • 非线程安全，键不允许 null（排序时会抛出异常）。

HashTable：线程安全的哈希映射（已过时）

• 底层结构：哈希表，与 HashMap 类似，但所有方法均被 synchronized 修饰（线程安全）。
• 问题：同步导致性能低下，键和值均不允许为 null，推荐用 ConcurrentHashMap（并发包中的高效线程安全 Map）替代。

Map 实现类对比

特性	HashMap	LinkedHashMap	TreeMap	HashTable（过时）
底层结构	哈希表	哈希表 + 链表	红黑树	哈希表
顺序	无序	插入顺序	键排序顺序	无序
线程安全	否	否	否	是（低效）
允许 null	键值均可（键仅 1 个）	键值均可（键仅 1 个）	均不允许	均不允许
时间复杂度	增删查 O(1)	增删查 O(1)（略低）	增删查 O(log n)	增删查 O(1)（低效）
适用场景	快速键值查询	键值查询 + 需插入顺序	键值查询 + 需排序	无（推荐 ConcurrentHashMap）

迭代器（Iterator）：集合遍历的统一方式

迭代器是遍历集合的标准方式，定义在 java.util.Iterator 接口中，替代了早期的 Enumeration，支持在遍历中安全删除元素。

Iterator 核心方法

• boolean hasNext()：判断是否有下一个元素；
• E next()：获取下一个元素（需先调用 hasNext() 避免 NoSuchElementException）；
• void remove()：删除 next() 返回的元素（需在 next() 之后调用）。

ListIterator：List 专属的双向迭代器

ListIterator 是 Iterator 的子接口，仅用于 List，支持双向遍历和修改元素：

• boolean hasPrevious()：判断是否有上一个元素；
• E previous()：获取上一个元素；
• void add(E e)：在当前位置插入元素；
• void set(E e)：修改 next() 或 previous() 返回的元素。

迭代器与增强 for 循环的关系

增强 for 循环（for-each）是迭代器的语法糖，编译后会被转换为 Iterator 遍历：

// 增强 for 循环
for (String s : list) { ... }

// 编译后等价于
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    ...
}

Collections 工具类：集合操作的辅助工具

java.util.Collections 提供了大量静态方法，用于操作集合（如排序、同步、不可修改等）。

不可修改集合

通过 unmodifiableXXX() 方法创建只读集合，禁止添加 / 删除元素（否则抛出 UnsupportedOperationException）：

List<String> list = new ArrayList<>();
List<String> readOnlyList = Collections.unmodifiableList(list);
readOnlyList.add("a"); // 抛出异常

同步集合

通过 synchronizedXXX() 方法创建线程安全集合（对所有方法加锁）：

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// 适用于多线程环境，但性能低于并发包中的集合（如 CopyOnWriteArrayList）

其他常用方法

• sort(list)：对 List 排序（元素需实现 Comparable）；
• shuffle(list)：随机打乱 List 元素顺序；
• binarySearch(list, key)：二分查找元素（需先排序）；
• max(collection)/min(collection)：获取最大 / 小元素。

常见问题与解决方案

1. 遍历时删除元素导致 ConcurrentModificationException

原因：使用集合的 remove() 方法删除元素时，会修改 modCount（修改次数），而迭代器依赖 expectedModCount（初始修改次数）判断是否并发修改，不一致时抛出异常。

解决方案：

• 用迭代器的 remove() 方法（会同步 expectedModCount 和 modCount）；
• 倒序遍历（普通 for 循环，避免索引偏移）。

// 正确方式1：迭代器 remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("a")) {
        it.remove(); // 安全删除
    }
}

// 正确方式2：倒序 for 循环
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("a")) {
        list.remove(i); // 无索引偏移
    }
}

2. Arrays.asList() 返回的 List 无法修改

原因：Arrays.asList() 返回的是 Arrays 的内部类 ArrayList，仅实现了部分 List 方法，add()/remove() 会直接抛出 UnsupportedOperationException。

解决方案：转为真正的 ArrayList：

List<String> list = new ArrayList<>(Arrays.asList("a", "b")); // 可修改

3. fail-fast 与 fail-safe 机制

• fail-fast（快速失败）：迭代时若集合被修改（如其他线程添加元素），立即抛出 ConcurrentModificationException（如 ArrayList、HashMap 的迭代器）；
• fail-safe（安全失败）：迭代时遍历集合的副本，不影响原集合，不会抛出异常（如 CopyOnWriteArrayList、ConcurrentHashMap）。

4. 集合与泛型的配合

泛型确保集合只能存储指定类型的元素，避免运行时类型转换异常：

List<String> strList = new ArrayList<>();
strList.add(123); // 编译报错（不允许添加 Integer）