Java 集合框架概览

Java 集合框架（Java Collections Framework, JCF）是 java.util 包下的一套统一的数据结构与算法接口体系。它分为两大分支：Collection（单列集合）和 Map（键值对集合）。

整体继承结构

Iterable
└── Collection
    ├── List（有序、可重复）
    │   ├── ArrayList        ← 动态数组，随机访问快
    │   ├── LinkedList       ← 双向链表，实现了 List + Deque
    │   ├── Vector           ← 线程安全的动态数组（已过时）
    │   │   └── Stack        ← 栈（已过时，推荐用 ArrayDeque）
    │   └── CopyOnWriteArrayList ← 写时复制，读多写少的线程安全 List
    │
    ├── Set（不重复）
    │   ├── HashSet          ← 基于 HashMap，无序
    │   │   └── LinkedHashSet ← 基于 LinkedHashMap，保持插入顺序
    │   ├── TreeSet          ← 基于 TreeMap（红黑树），有序
    │   ├── EnumSet          ← 枚举专用 Set，性能极高
    │   └── CopyOnWriteArraySet ← 线程安全的 Set
    │
    └── Queue（队列）
        ├── LinkedList       ← 同时实现了 Deque
        ├── ArrayDeque       ← 基于循环数组的双端队列（推荐替代 Stack）
        ├── PriorityQueue    ← 基于堆的优先队列
        └── 并发队列
            ├── ConcurrentLinkedQueue   ← 无界非阻塞队列
            ├── ArrayBlockingQueue      ← 有界阻塞队列
            ├── LinkedBlockingQueue     ← 可选有界阻塞队列
            ├── PriorityBlockingQueue   ← 优先级阻塞队列
            ├── DelayQueue              ← 延迟队列
            └── SynchronousQueue        ← 无容量的同步队列

Map（键值对，独立体系，不继承 Collection）
├── HashMap              ← 数组+链表+红黑树，无序
│   └── LinkedHashMap    ← HashMap + 双向链表，保持插入/访问顺序
├── TreeMap              ← 红黑树，按 key 排序
├── Hashtable            ← 线程安全（已过时）
│   └── Properties       ← 配置文件专用
├── ConcurrentHashMap    ← 高性能线程安全 Map
├── ConcurrentSkipListMap ← 跳表实现的有序并发 Map
├── WeakHashMap          ← 弱引用 key，可被 GC 回收
├── IdentityHashMap      ← 用 == 而非 equals 比较 key
└── EnumMap              ← 枚举专用 Map，性能极高

核心接口职责

各实现类速查

List 实现

*LinkedList 的 O(1) 插入/删除仅限已定位到节点的情况

Set 实现

Map 实现

Queue 实现

Collection 与 Collections 的区别

// Collections 常用方法
Collections.sort(list);                    // 排序
Collections.reverse(list);                 // 反转
Collections.shuffle(list);                 // 随机打乱
Collections.unmodifiableList(list);        // 不可修改包装
Collections.synchronizedMap(map);          // 线程安全包装
Collections.singletonList("only");         // 单元素不可变 List
Collections.emptyList();                   // 空不可变 List

线程安全集合

集合选型决策树

存储数据的需求？
│
├─ 键值对 → Map
│   ├─ 不需要排序 → HashMap
│   ├─ 需要保持顺序 → LinkedHashMap
│   ├─ 需要按 key 排序 → TreeMap
│   └─ 需要线程安全 → ConcurrentHashMap
│
├─ 不需要键值对
│   ├─ 允许重复 → List
│   │   ├─ 随机访问多 → ArrayList
│   │   ├─ 队列/栈操作多 → ArrayDeque
│   │   └─ 需要线程安全 → CopyOnWriteArrayList
│   │
│   ├─ 不允许重复 → Set
│   │   ├─ 不关心顺序 → HashSet
│   │   ├─ 保持插入顺序 → LinkedHashSet
│   │   └─ 需要排序 → TreeSet
│   │
│   └─ 先进先出 → Queue
│       ├─ 优先级 → PriorityQueue
│       ├─ 阻塞 → ArrayBlockingQueue / LinkedBlockingQueue
│       └─ 非阻塞并发 → ConcurrentLinkedQueue

迭代器机制

集合与迭代器的关系

迭代器（Iterator）是集合提供的一个"遍历游标"，它不存储数据，而是持有集合的内部引用，按顺序逐个访问元素。

从接口设计看，Java 集合框架的遍历能力是这样串联起来的：

Iterable 接口           ← 所有集合的祖先接口
  └── iterator()        ← 返回一个 Iterator 对象

Iterator 接口           ← 遍历的统一抽象
  ├── hasNext()         ← 是否还有下一个元素
  ├── next()            ← 获取下一个元素
  └── remove()          ← 删除当前元素（可选操作）

关键设计：迭代器是集合的内部类，共享集合的内部状态。

public class ArrayList<E> {
    Object[] elementData;   // 底层数组
    int size;               // 元素个数
    int modCount;           // 修改计数器

    // 迭代器是 ArrayList 的内部类
    private class Itr implements Iterator<E> {
        int cursor;             // 下一个要读取的位置
        int expectedModCount = modCount;  // 创建时快照

        // 因为是内部类，可以直接访问外部类的 elementData、size、modCount
    }

    public Iterator<E> iterator() {
        return new Itr();   // 每次调用都创建一个新的游标
    }
}

迭代器和集合的关系好比书和书签：

• 集合 = 书（存储内容）
• 迭代器 = 书签（记录读到哪了）
• 你可以同时插多个书签（创建多个迭代器），互不影响
• 但如果有人偷偷撕掉了几页（修改了集合），书签的页码就对不上了

for-each 和 Iterator 的关系：for-each 就是 Iterator 的语法糖，编译器会自动展开：

// 你写的
for (String item : list) { ... }

// 编译器生成的
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    ...
}

理解了这个关系，就能明白为什么 list.remove() 和 it.remove() 的行为不同——因为迭代器是集合的内部类，it.remove() 能同时维护双方的状态，而 list.remove() 只改了集合，迭代器完全不知道。

遍历时修改集合的问题

遍历时可以修改集合，但结果取决于集合类型和修改方式：

对于常用的 fail-fast 集合，根本原因是：for-each 中调用 list.remove() 只修改了集合的状态，没有同步更新迭代器的内部状态（索引、指针），导致迭代器后续操作时数据结构已经变了：

以 ArrayList 为例（底层是数组）：

初始: ["A", "B", "C", "D"]   size=4
迭代器: cursor=0, 准备读 index=0

假设遍历到 "B"（cursor=2）时删除了 "B"：

删除前: ["A", "B", "C", "D"]   size=4, cursor=2
                 ↑ 删除这个

删除后: ["A", "C", "D"]        size=3, cursor=2
                  ↑ cursor 指向这里

→ 迭代器下一步读 index=2 得到 "D"，跳过了 "C"！

以 HashMap 为例（底层是数组+链表）更严重：

删除/新增元素 → 可能触发 rehash（重新散列）
→ 所有元素在桶数组中的位置可能全部改变
→ 迭代器正在按桶序号遍历，可能重复访问或遗漏元素

以 LinkedList 为例（底层是双向链表）：

A ↔ B ↔ C ↔ D
        ↑ 迭代器当前指向 C

如果此时删除了 C 的 next 指针指向的 D：
→ 迭代器调用 next() 时，可能访问到已断开的节点
→ 导致 NullPointerException 或死循环

问题的本质是：迭代器和集合共享内部状态（索引、指针、桶位置），修改集合会破坏迭代器对这些状态的假设，可能导致跳过元素、重复访问、数组越界、空指针或死循环。

fail-fast 与 fail-safe 机制

fail-fast（快速失败）

设计思想：尽早暴露问题，防止在错误状态下继续运行导致更难排查的隐蔽 bug。

实现原理：通过 modCount（修改计数器）检测并发修改。

public class ArrayList<E> {
    // ① 集合内部维护一个修改计数器
    protected transient int modCount = 0;

    // ② 集合的 add() —— modCount++
    public boolean add(E e) {
        modCount++;
        // ... 添加元素到数组
    }

    // ③ 集合的 remove() —— modCount++
    //    遍历中调用 list.remove() 就是调的这个方法！
    public E remove(int index) {
        modCount++;       // 只改了集合的计数器
        // ... 从数组中移除元素，后面的元素前移
        return oldValue;
        // ⚠️ 注意：这里完全没有通知迭代器！
    }

    // ④ 迭代器是 ArrayList 的内部类
    private class Itr implements Iterator<E> {
        int cursor;
        int expectedModCount = modCount;  // 创建时拍个快照

        public E next() {
            // ⑤ 每次 next() 都先检查：集合有没有背着我偷偷改过？
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();  // 💥
            // ... 返回元素
        }
    }
}

// 所以整个因果链是：
// list.remove() → modCount++ → 迭代器不知道
// → it.next() 检查 modCount ≠ expectedModCount → 抛异常

关键细节：

• 异常不是在修改的瞬间抛出的。调用 list.remove() 本身可以正常执行，元素也确实被删除了。异常发生在下一次调用 it.next() 时——迭代器在 next() 开头检查 modCount，发现和自己记录的 expectedModCount 不一致，才抛出 ConcurrentModificationException。
• set() 替换元素不会触发异常。因为 set() 是原地替换，不改变集合的结构（元素个数不变、数组不扩缩），所以 modCount 不递增。只要 modCount 没变，迭代器就检测不到任何"异常修改"：

// ArrayList.set() 源码（简化）
public E set(int index, E element) {
    // 注意：这里没有 modCount++
    E oldValue = elementData[index];
    elementData[index] = element;  // 原地替换
    return oldValue;
}
// 所以遍历中调 list.set(i, newValue) 是完全安全的

• 迭代器自己的 remove() 也不会触发异常，因为它在删除后会同步 expectedModCount = modCount。
• fail-fast 不是线程安全机制，只是一个"尽力而为"的检测——在多线程场景下，即使没有触发异常，数据也可能已经错了。

list.remove() 与 iterator.remove() 的区别

❌ list.remove()——只更新 modCount

// ArrayList.remove() 源码（简化）
public E remove(int index) {
    modCount++;                    // ① 集合的 modCount +1
    // 移动数组元素...
    return oldValue;
    // ⚠️ 没有更新迭代器的 expectedModCount，也没有调整 cursor
}

✅ iterator.remove()——同步更新两边

// ArrayList 内部类 Itr.remove() 源码（简化）
public void remove() {
    ArrayList.this.remove(lastRet);  // ① modCount++
    cursor = lastRet;               // ② 把 cursor 回退一位，避免跳过元素
    expectedModCount = modCount;    // ③ 重新同步，下次检查不触发异常
}

过程图解：

list = ["A", "B", "C", "D"]     modCount=0

创建迭代器 → expectedModCount=0, cursor=0

it.next() → "A"    cursor=1
it.next() → "B"    cursor=2, lastRet=1

----- 此时要删除 "B" -----

方式1: list.remove("B")
  modCount=1, expectedModCount=0, cursor=2
  数组变为 ["A", "C", "D"]
  → it.next() 先检查 1≠0 → 💥 ConcurrentModificationException

方式2: it.remove()
  modCount=1
  cursor 回退: cursor=1      ← 防止跳过 "C"
  同步: expectedModCount=1   ← 防止误报异常
  数组变为 ["A", "C", "D"]
  → it.next() 检查 1==1 ✅ → 读 index=1 → 得到 "C" ✅

一句话总结：list.remove() 只改了集合的状态，迭代器不知道发生了什么；it.remove() 同时维护了集合和迭代器双方的状态。

fail-safe（安全失败）

设计思想：在并发环境中保证迭代不会因其他线程的修改而崩溃，适合"可接受短暂不一致"的场景。

有两种实现策略：

策略 1：写时复制（CopyOnWriteArrayList）

// 每次写操作复制整个数组
public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        Object[] newElements = Arrays.copyOf(es, len + 1);
        newElements[len] = e;
        setArray(newElements);  // 替换引用
    }
}

// 迭代器基于创建时的数组快照
public Iterator<E> iterator() {
    return new COWIterator(getArray(), 0);
    // 即使之后有新元素添加，迭代器看到的仍然是旧数组
}

策略 2：弱一致性（ConcurrentHashMap）

// ConcurrentHashMap 的迭代器直接遍历当前数据
// 不复制，也不抛异常
// 反映的是迭代器创建时（或之后某一刻）的状态
// 不保证能看到迭代开始后的所有修改

两种机制对比

各集合的迭代器类型

遍历中安全删除的方法

// ✅ 方法1：使用迭代器的 remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if ("bad".equals(it.next())) {
        it.remove();  // 同步 expectedModCount
    }
}

// ✅ 方法2：JDK 8+ removeIf（最简洁，底层也是迭代器）
list.removeIf(item -> "bad".equals(item));

// ✅ 方法3：普通的 for 循环（必须倒序遍历！）
// 注意：普通 for 循环没有用到迭代器，所以即使修改集合，也【绝对不会】触发 ConcurrentModificationException！
// ❌ 错误写法（正序）：删除元素后，后续元素前移，i 递增，会导致漏删紧挨着的下一个元素；如果提前缓存了 size，还会抛出越界异常（IndexOutOfBoundsException）。
// ✅ 正确写法（倒序）：倒着遍历删除，前移的都是已经处理过的元素，完全不影响。
for (int i = list.size() - 1; i >= 0; i--) {
    if ("bad".equals(list.get(i))) {
        list.remove(i);
    }
}

// ✅ 方法4：ConcurrentHashMap 替代 HashMap（多线程）
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(originalMap);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    if (entry.getValue() < 0) {
        map.remove(entry.getKey());  // 不抛异常
    }
}

// ✅ 方法5：收集后统一删除
List<String> toRemove = new ArrayList<>();
for (String item : list) {
    if ("bad".equals(item)) toRemove.add(item);
}
list.removeAll(toRemove);