Java 基础体系 · 第 5/100 篇。示例统一以 Java 25 LTS 为语言和 JVM 基线；框架示例使用与其兼容的现代稳定版本。

Java 集合框架：List、Set、Map、Queue、迭代器和复杂度

Java 集合框架解决的是“如何组织一组对象，以及如何按某种规则访问、查找、插入和删除它们”。它不仅包含若干容器类，还包含一组接口契约、迭代协议、比较规则、泛型约束和并发语义。

在 Java 25 标准库中，最重要的抽象关系可以概括为：

classDiagram
    Iterable <|-- Collection
    Collection <|-- List
    Collection <|-- Set
    Collection <|-- Queue
    Queue <|-- Deque

    Map <|-- SortedMap
    SortedMap <|-- NavigableMap

    Set <|-- SortedSet
    SortedSet <|-- NavigableSet

    List <|.. ArrayList
    List <|.. LinkedList
    Set <|.. HashSet
    Set <|.. LinkedHashSet
    Set <|.. TreeSet
    Queue <|.. ArrayDeque
    Queue <|.. PriorityQueue
    Map <|.. HashMap
    Map <|.. LinkedHashMap
    Map <|.. TreeMap

Map 不继承 Collection，因为它保存的是“键到值”的映射，而不是单独的一组元素。Map 可以通过 keySet()、values() 和 entrySet() 暴露集合视图，但这不改变它与 Collection 的层次关系。

一、先区分接口语义和实现类

接口决定调用者可以依赖什么；实现类决定通常如何实现这些语义，以及具有什么性能特征。

例如：

List<String> names = new ArrayList<>();

变量的静态类型是 List，因此代码依赖的是列表语义：有序、允许重复、可以按整数下标访问。具体使用的是 ArrayList，所以还可以依赖其常见的随机访问性能。

应优先根据行为声明类型：

List<String> names = new ArrayList<>();
Set<String> uniqueNames = new HashSet<>();
Map<Long, String> users = new HashMap<>();
Queue<String> tasks = new ArrayDeque<>();

这样做不是为了“面向接口”这一句口号，而是为了把调用方依赖限制在真正需要的契约上。如果代码需要按下标访问，应该声明 List；如果只需要去重，应声明 Set；如果需要键值查找，应声明 Map。

集合接口大致承担以下职责：

  • Iterable<E>：允许通过迭代器遍历元素。
  • Collection<E>：描述一组元素的添加、删除、包含判断和大小等通用操作。
  • List<E>：元素有顺序、有整数位置，并允许重复。
  • Set<E>：不允许按照集合契约出现重复元素。
  • Queue<E>：表示等待处理的元素，通常具有先进先出或优先级顺序。
  • Deque<E>：双端队列，可以从头尾两端插入和删除。
  • Map<K, V>：把键映射到值，每个键至多对应一个值。

二、泛型：集合保存的是哪一种对象

Java 集合通常使用泛型参数描述元素类型：

List<String> words = new ArrayList<>();
words.add("java");
// words.add(42);  // 编译错误

List<String> 表示这个列表的元素类型是 String。泛型检查主要发生在编译期，运行时通常会发生类型擦除，因此不能写：

// 错误：不能直接创建泛型数组
// List<String>[] array = new ArrayList<String>[10];

集合中的泛型参数也决定了方法签名：

void addNumbers(List<? extends Number> source) {
    Number n = source.get(0);
}

? extends Number 表示“某一种未知的、继承自 Number 的类型”。调用方可以传入 List<Integer> 或 List<Double>，但方法不能安全地向其中加入任意 Number，因为实际列表可能是 List<Integer>。

相反：

void addIntegers(List<? super Integer> target) {
    target.add(1);
}

? super Integer 表示某一种 Integer 的父类型，因此向其中写入 Integer 是安全的。读取时只能可靠地当作 Object 处理。

这就是 PECS：

  • Producer Extends：只读生产者使用 ? extends T。
  • Consumer Super：只写消费者使用 ? super T。

例如复制集合的通用方法可以写成：

static <T> void copy(
        List<? super T> destination,
        List<? extends T> source) {

    for (T value : source) {
        destination.add(value);
    }
}

这里的安全性来自类型关系，而不是来自具体集合实现。ArrayList、LinkedList 和不可变列表都必须先满足泛型类型约束，之后才讨论它们的运行时行为。

三、List：有位置的有序序列

3.1 List 的契约

List<E> 是一个有序集合。这里的“有序”指元素具有位置，遍历顺序与列表顺序相关，不等同于“按大小排序”。

List<String> list = new ArrayList<>();
list.add("B");
list.add("A");
list.add("B");

System.out.println(list);       // [B, A, B]
System.out.println(list.get(1)); // A

List 的基本特征是：

  1. 元素有位置，位置从 0 到 size() - 1。
  2. 通常允许重复元素。
  3. 可以通过 get(index) 访问元素。
  4. add(index, value) 会在指定位置插入，并移动后续元素。
  5. remove(index) 删除指定位置元素，并移动后续元素。

List 的相等性具有顺序语义。两个列表相等，需要元素数量相同，并且对应位置的元素依次相等：

List<Integer> a = List.of(1, 2);
List<Integer> b = List.of(1, 2);
List<Integer> c = List.of(2, 1);

System.out.println(a.equals(b)); // true
System.out.println(a.equals(c)); // false

3.2 ArrayList：连续数组上的动态列表

ArrayList 以数组保存元素。数组长度固定，但 ArrayList 会在容量不足时创建更大的数组并复制元素。

因此：

  • get(index)：通常为 O(1)。
  • set(index, value)：通常为 O(1)。
  • 末尾添加：摊销 O(1)。
  • 中间插入：O(n)。
  • 中间删除：O(n)。
  • contains：O(n)。

“摊销 O(1)”需要特别理解。单次扩容可能需要复制当前所有元素，是 O(n)；但扩容后会获得一段新的空余容量。若连续执行 n 次尾部插入，总复制成本通常与 n 同阶，因此平均到每次操作是 O(1)。

设第 i 次扩容复制 c_i 个元素。如果容量按一定比例增长，则：

c1+c2+⋯+ck=O(n)c_1 + c_2 + \cdots + c_k = O(n)

其中 n 是最终插入的元素总数，所以总插入成本为 O(n)，平均每次为摊销 O(1)。这不是说每一次 add 都严格只执行常数步。

ArrayList 的容量增长策略属于实现细节，不能把某个具体增长比例当作 Java API 契约。

3.3 LinkedList：链表和双端队列的结合

LinkedList 由链式节点组成。每个节点保存元素以及前后节点引用。

它适合的操作是：

  • 在已知节点附近插入或删除。
  • 从头部或尾部操作。
  • 同时使用 List 和 Deque 的接口能力。

但 get(index) 不是常数时间。实现必须从头部或尾部沿节点逐个寻找目标位置，因此复杂度为 O(min(index, n-index))，通常记作 O(n)。

下面两段代码的复杂度不同：

List<Integer> list = new LinkedList<>();

list.add(0, 10);       // 找到头部，通常为 O(1)
list.add(list.size(), 20); // 尾部，通常为 O(1)

list.add(500_000, 30); // 需要先定位位置，整体为 O(n)

常见误解是“链表插入永远是 O(1)”。只有在已经拥有目标节点或迭代器位置时，节点链接操作才是 O(1)；如果必须先通过下标查找位置，查找成本仍然是 O(n)。

在只需要双端队列时，通常使用 ArrayDeque，而不是因为“链表插入快”就选择 LinkedList。

四、Set：按相等性去重

4.1 Set 的契约

Set<E> 不允许存在两个按照集合相等性判断为相等的元素：

Set<String> set = new HashSet<>();
System.out.println(set.add("java")); // true
System.out.println(set.add("java")); // false
System.out.println(set.size());      // 1

add 返回 false，表示集合中已经存在相等元素，集合没有发生变化。

集合是否有顺序，取决于实现：

  • HashSet：不承诺遍历顺序。
  • LinkedHashSet：通常保持插入顺序。
  • TreeSet：按照自然顺序或提供的比较器排序。

“无序”不代表每次都随机，也不代表顺序一定变化；它表示调用方不能依赖某种顺序。某次运行中看到的顺序可能来自哈希表布局、容量和哈希值，修改元素或升级 JDK 后都可能变化。

4.2 equals 与 hashCode

哈希集合依赖 equals 和 hashCode。对象相等时，必须满足：

a.equals(b) == true  =>  a.hashCode() == b.hashCode()

反过来不成立：哈希值相同的两个对象仍然可能不相等，这称为哈希冲突。

插入哈希集合时，概念上的过程是：

  1. 根据元素的哈希值定位候选桶。
  2. 在桶中寻找哈希值相同且 equals 为 true 的元素。
  3. 找到则不插入，找不到则插入新元素。

因此，以下类如果重写了 equals，通常也必须重写 hashCode：

final class UserKey {
    private final long id;

    UserKey(long id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object other) {
        return other instanceof UserKey key && id == key.id;
    }

    @Override
    public int hashCode() {
        return Long.hashCode(id);
    }
}

如果对象进入 HashSet 后，其参与 equals 或 hashCode 的字段被修改，集合可能无法再正确定位它：

Set<UserKey> keys = new HashSet<>();
// 如果 UserKey 的 id 可变，插入后修改 id 会破坏哈希定位

这不是集合“丢失”了对象，而是对象所在的桶由旧哈希值决定，之后用新哈希值查找自然可能失败。因此哈希集合中的键或元素最好具有稳定的相等性属性。

4.3 HashSet、LinkedHashSet 和 TreeSet

HashSet 的添加、删除和包含判断在正常哈希分布下通常是期望 O(1)。这是复杂度分析中的平均或期望结论，不是所有输入下的严格上界。最坏情况取决于实现和哈希冲突分布。

现代 JDK 的哈希表实现可能对严重冲突进行树化等优化，但具体阈值和节点结构属于实现细节，不能据此编写依赖特定常数的业务逻辑。

LinkedHashSet 在哈希集合基础上维护链式顺序，因此通常仍有期望 O(1) 的查找，并额外保持插入顺序。

TreeSet 基于有序树结构：

  • add：O(log n)。
  • remove：O(log n)。
  • contains：O(log n)。
  • 可执行范围查询，例如 subSet、headSet 和 tailSet。

TreeSet 的“重复”由比较结果决定。如果两个对象的比较结果为 0，TreeSet 会把它们视为同一个集合元素，即使它们的 equals 返回 false。因此，排序规则最好与 equals 保持一致，否则可能出现：

Comparator<String> byLength = Comparator.comparingInt(String::length);
Set<String> set = new TreeSet<>(byLength);

set.add("aa");
set.add("bb");

System.out.println(set.size()); // 1

这里 "aa" 和 "bb" 长度相同，比较器返回 0，所以第二个字符串不会作为独立元素加入。

五、Map：从键到值的映射

5.1 Map 的基本模型

Map<K, V> 维护键和值之间的关系：

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 20);
ages.put("Alice", 21);

System.out.println(ages.size());      // 1
System.out.println(ages.get("Alice")); // 21

同一个键再次调用 put 会替换旧值。键不能重复，但不同键可以映射到相同的值。

Map 常用方法包括：

ages.get("Alice");
ages.containsKey("Alice");
ages.remove("Alice");
ages.putIfAbsent("Bob", 18);
ages.getOrDefault("Unknown", -1);
ages.merge("Alice", 1, Integer::sum);

get 返回 null 时存在歧义：

  1. 键不存在。
  2. 键存在，但对应值就是 null。

需要区分时使用：

if (ages.containsKey("Alice")) {
    Integer value = ages.get("Alice");
}

HashMap 允许一个 null 键和多个 null 值；其他实现是否允许 null，要看具体接口和实现契约，不能从 Map 接口推断所有实现都接受 null。

5.2 三种常用遍历方式

如果同时需要键和值，应优先遍历 entrySet()：

for (Map.Entry<String, Integer> entry : ages.entrySet()) {
    System.out.println(entry.getKey() + " -> " + entry.getValue());
}

只需要键时使用 keySet()：

for (String name : ages.keySet()) {
    System.out.println(name);
}

只需要值时使用 values()：

for (Integer age : ages.values()) {
    System.out.println(age);
}

这些返回值是集合视图，而不是必然复制出的新集合。对视图进行允许的删除操作，可能会影响原始 Map：

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);

map.keySet().remove("a");

System.out.println(map.isEmpty()); // true

5.3 HashMap、LinkedHashMap 和 TreeMap

HashMap 在哈希分布正常时，get、put、remove 通常是期望 O(1)。

LinkedHashMap 额外维护遍历顺序，通常可以保持：

  • 插入顺序；
  • 或访问顺序。

访问顺序模式常用于实现近似 LRU 的缓存骨架，但生产级缓存还需要考虑并发、容量、过期、统计和淘汰竞态，不能仅凭 LinkedHashMap 自动获得完整缓存语义。

TreeMap 按键排序，基本操作通常为 O(log n)。排序依据可以是键的自然顺序，也可以是构造时传入的 Comparator：

Map<String, Integer> scores = new TreeMap<>();
scores.put("Bob", 80);
scores.put("Alice", 90);

System.out.println(scores); // {Alice=90, Bob=80}

TreeMap 中的键必须能够被比较器处理。若自然顺序无法比较不同键，运行时会抛出 ClassCastException。

5.4 修改 Map 中的键是危险的

哈希映射要求键的哈希值和相等性在映射期间保持稳定；有序映射要求键的排序关系保持稳定。

错误示意：

class MutableKey {
    int value;

    MutableKey(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return value;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof MutableKey k && value == k.value;
    }
}

如果对象作为 HashMap 的键插入后修改 value，随后用同一个对象调用 get，可能查不到原来的值。原因是查找使用了新的哈希值，而元素仍然位于根据旧哈希值确定的位置。

六、Queue 和 Deque：按规则取出元素

6.1 Queue 的两组方法

Queue<E> 的头部元素是下一步通常要处理的元素。它提供两组语义相近但失败行为不同的方法：

操作 失败时返回特殊值 失败时抛出异常
插入 offer(e) 返回 false add(e) 抛出异常
查看头部 peek() 返回 null element() 抛出异常
删除头部 poll() 返回 null remove() 抛出异常

对有容量限制的队列，offer 能让调用者显式处理“暂时放不进去”；对不应失败的无界队列，add 可以让异常暴露出来。

null 通常不能作为队列元素，因为 poll() 用 null 表示“队列为空”。ArrayDeque 和 PriorityQueue 都不允许 null。

6.2 ArrayDeque：高效的双端队列

ArrayDeque 使用循环数组，支持两端操作：

Deque<String> deque = new ArrayDeque<>();

deque.addLast("task-1");
deque.addLast("task-2");
deque.addFirst("urgent");

System.out.println(deque.removeFirst()); // urgent
System.out.println(deque.removeLast());  // task-2

两端插入和删除通常为摊销 O(1)，按值查找为 O(n)。它不支持按下标访问，也不允许 null。

可以把它用作栈：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);

System.out.println(stack.pop()); // 2

也可以把它用作普通 FIFO 队列：

Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(1);
queue.offerLast(2);

System.out.println(queue.pollFirst()); // 1

6.3 PriorityQueue：优先级队列不是 FIFO

PriorityQueue 的头部是最小元素，或者是比较器定义的最高优先级元素：

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(5);
queue.offer(1);
queue.offer(3);

while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

输出为：

1
3
5

其典型复杂度是：

  • peek()：O(1)。
  • offer()：O(log n)。
  • poll()：O(log n)。
  • remove(Object)：通常 O(n)，因为需要先查找对象。
  • 遍历：不保证按优先级排序。

因此不能这样理解：

for (Integer value : queue) {
    // 不保证按 1、3、5 的顺序输出
}

只有反复调用 poll()，才能按照队列规则取出元素。PriorityQueue 不是线程安全的；并发场景应使用并发队列或外部同步。

七、迭代器：集合遍历的统一协议

7.1 Iterator 的状态模型

Iterable<E> 提供：

Iterator<E> iterator();

Iterator<E> 主要有：

boolean hasNext();
E next();
default void remove();

标准遍历过程是：

  1. 创建迭代器。
  2. 用 hasNext() 判断是否还有元素。
  3. 用 next() 获取下一个元素。
  4. 如果需要，调用 remove() 删除最近一次 next() 返回的元素。
List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4));

Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
    int value = iterator.next();
    if (value % 2 == 0) {
        iterator.remove();
    }
}

System.out.println(numbers); // [1, 3]

Iterator.remove() 删除的是最近一次 next() 返回的元素，而不是任意指定元素。以下调用顺序非法：

// iterator.remove(); // 在 next() 前调用，抛出 IllegalStateException

连续调用两次 remove()，中间没有新的 next()，同样会违反迭代器状态规则。

7.2 为什么不能在增强 for 中直接修改集合

增强 for 本质上使用迭代器：

for (Integer value : numbers) {
    // ...
}

如果遍历过程中直接执行结构性修改：

List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3));

for (Integer value : numbers) {
    if (value == 2) {
        numbers.remove(value);
    }
}

通常会抛出 ConcurrentModificationException。正确做法是使用迭代器删除：

Iterator<Integer> it = numbers.iterator();
while (it.hasNext()) {
    if (it.next() == 2) {
        it.remove();
    }
}

也可以使用：

numbers.removeIf(value -> value == 2);

removeIf 由集合实现参与执行，通常比在循环中反复按值删除更清晰。

7.3 Fail-fast 不是并发安全保证

许多非并发集合的迭代器具有 fail-fast 行为：如果检测到集合在迭代期间被结构性修改，尽快抛出 ConcurrentModificationException。

但这有三个边界：

  1. 它主要用于尽早发现编程错误。
  2. 它通常依赖实现内部状态，例如修改计数。
  3. Java API 不保证在所有并发竞态下都一定抛出异常。

因此不能写出依赖异常来保证线程安全的逻辑：

try {
    for (String item : list) {
        // 不能把没抛异常理解成没有并发问题
    }
} catch (ConcurrentModificationException e) {
    // 这不是并发控制方案
}

如果需要并发访问，应使用正确的并发集合、锁或消息传递机制。

7.4 ListIterator

ListIterator<E> 是 List 专用迭代器，支持双向遍历和在当前位置插入、替换：

List<String> names = new ArrayList<>(List.of("A", "C"));

ListIterator<String> it = names.listIterator();
while (it.hasNext()) {
    if (it.next().equals("A")) {
        it.add("B");
    }
}

System.out.println(names); // [A, B, C]

ListIterator 的插入位置、游标位置和 remove/set 的合法调用顺序都有明确状态约束。set 只能替换最近一次 next() 或 previous() 返回的元素；add 会在游标处插入，并使最近返回元素的替换状态失效。

八、复杂度：不要只背一个 O(1)

8.1 三种常见复杂度结论

算法复杂度描述输入规模 n 增长时，操作成本如何增长：

  • O(1)：成本与 n 无关。
  • O(log n)：每一步通常缩小问题规模，例如平衡树查找。
  • O(n)：可能需要扫描全部元素。
  • O(n log n)：常见于高效比较排序。

集合复杂度还要说明条件：

  • 是最坏情况，还是平均/期望情况？
  • 是单次操作，还是摊销成本？
  • 是按下标操作，还是按值查找？
  • 是否包含“先定位，再修改”的两阶段成本？

8.2 常见实现的典型复杂度

下表是常见实现的典型结论，不是所有接口实现的统一保证：

类型与操作 ArrayList LinkedList HashSet TreeSet HashMap TreeMap
按位置读取 O(1) O(n) 不适用 不适用 不适用 不适用
尾部添加 摊销 O(1) O(1) — — — —
插入/删除指定位置 O(n) 定位 O(n)，已有节点附近可为 O(1) — — — —
contains / get O(n) O(n) 期望 O(1) O(log n) 期望 O(1) O(log n)
按键/元素删除 O(n) O(n) 期望 O(1) O(log n) 期望 O(1) O(log n)

队列类需要单独看：

类型 典型操作复杂度
ArrayDeque 两端插入/删除 摊销 O(1)
ArrayDeque.contains O(n)
PriorityQueue.peek O(1)
PriorityQueue.offer/poll O(log n)
PriorityQueue.remove(Object) 通常 O(n)

例如，下面的代码看起来都是“删除一个元素”，但代价不同：

list.remove(0);              // ArrayList：移动后续元素，O(n)
list.remove(Integer.valueOf(0)); // 先线性查找，通常 O(n)
map.remove(key);             // HashMap：期望 O(1)
treeMap.remove(key);         // TreeMap：O(log n)

对于 List<Integer>，remove(0) 的参数是 int，表示删除下标 0；如果要删除值为 0 的元素，需要显式装箱。这是 Java 重载和基本类型转换造成的实际陷阱。

8.3 空间复杂度和常数因素

两个算法都有 O(n) 时间，并不代表性能相同。ArrayList 的连续数组具有较好的局部性；LinkedList 的节点访问涉及引用跳转，可能产生更多缓存未命中和对象分配。

另一方面，ArrayList 可能保留未使用容量，HashMap 需要桶数组和节点结构，LinkedHashMap 还需要额外的顺序链接。空间复杂度通常仍是 O(n)，但常数和内存布局会影响实际表现。

因此复杂度用于排除明显不合适的方案，而不是替代基准测试。基准测试还必须固定数据规模、操作比例、预热过程、分配行为和并发条件，否则结果容易受到 JIT 编译和垃圾回收影响。

九、可运行示例：一次使用多种集合

下面的程序可以直接保存为 CollectionsDemo.java，使用 Java 25 编译运行：

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>(
                List.of("java", "set", "java", "map"));

        Set<String> uniqueWords = new LinkedHashSet<>(words);

        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        }

        Queue<String> fifo = new ArrayDeque<>();
        fifo.offer("first");
        fifo.offer("second");

        PriorityQueue<Integer> priorities = new PriorityQueue<>();
        priorities.offer(5);
        priorities.offer(1);
        priorities.offer(3);

        Iterator<String> iterator = uniqueWords.iterator();
        while (iterator.hasNext()) {
            if (iterator.next().equals("set")) {
                iterator.remove();
            }
        }

        System.out.println(words);
        System.out.println(uniqueWords);
        System.out.println(counts);
        System.out.println(fifo.poll());
        System.out.println(fifo.poll());

        while (!priorities.isEmpty()) {
            System.out.print(priorities.poll() + " ");
        }
        System.out.println();
    }
}

预期输出为：

[java, set, java, map]
[java, map]
{java=2, set=1, map=1}
first
second
1 3 5

逐步看其数据流：

  1. ArrayList 保存原始输入，因此保留重复项和插入顺序。
  2. LinkedHashSet 根据集合相等性去重，并保留第一次出现的顺序。
  3. Map.merge 对相同键执行累加，得到词频。
  4. ArrayDeque 按加入顺序从头部取出。
  5. PriorityQueue 不按插入顺序取出，而是每次取当前最小值。
  6. 迭代器删除 "set"，修改的是 uniqueWords，不会修改 words。

这个例子也展示了容器语义不能互换：如果把 PriorityQueue 当作 FIFO 使用，程序结果就会与需求不符。

十、不可变集合、只读视图和复制

Java 提供了几种相近但不同的方式。

List.of 等工厂方法

List<String> fixed = List.of("a", "b");
// fixed.add("c"); // UnsupportedOperationException

List.of 返回不可变集合，不能添加、删除或替换元素，也不接受 null 元素。Set.of 和 Map.of 也具有相应限制；集合工厂方法创建的集合不提供可变更新接口语义。

Collections.unmodifiableList

List<String> source = new ArrayList<>();
source.add("a");

List<String> view = Collections.unmodifiableList(source);
source.add("b");

System.out.println(view); // [a, b]

这是只读视图，不是独立副本。调用者不能通过 view 修改，但仍能通过 source 修改，视图会反映变化。

如果需要快照，应显式复制：

List<String> snapshot = List.copyOf(source);

List.copyOf 创建不可变副本语义；之后修改 source 不会改变 snapshot。但这仍然是浅复制：列表中的对象本身没有被深度复制。

十一、并发集合与故障路径

普通集合通常不是线程安全的。多个线程同时修改 ArrayList、HashMap 或 HashSet，可能造成数据竞争、丢失更新或观察到不一致状态。即使某些单次操作看起来没有立即出错，也不能因此推断复合操作是原子的。

同步包装

List<String> list =
        Collections.synchronizedList(new ArrayList<>());

synchronized (list) {
    for (String item : list) {
        System.out.println(item);
    }
}

同步包装通常要求调用方在遍历时锁住包装对象。只锁住单次 add，不能自动保护“检查后再操作”这类复合流程。

ConcurrentHashMap

ConcurrentHashMap 适合多个线程并发读写映射。它提供 putIfAbsent、computeIfAbsent、merge 等原子复合操作，使用这些方法比“先 containsKey 再 put”更可靠：

ConcurrentHashMap<String, Integer> counts =
        new ConcurrentHashMap<>();

counts.merge("java", 1, Integer::sum);

并发集合的迭代器通常是弱一致的：不会像普通集合迭代器那样把 fail-fast 作为主要行为，也不保证迭代期间获得某个全局瞬时快照。具体可见性和遍历保证应查看相应实现的 API 契约。

BlockingQueue

生产者—消费者模型通常使用 BlockingQueue：

BlockingQueue<String> tasks = new ArrayBlockingQueue<>(100);

tasks.put("job-1");   // 满时等待
String task = tasks.take(); // 空时等待

其状态路径是：

生产者 put
    -> 队列未满：立即入队
    -> 队列已满：阻塞等待

消费者 take
    -> 队列非空：立即取出
    -> 队列为空：阻塞等待

如果线程在等待期间被中断，阻塞方法会抛出 InterruptedException。业务代码通常应该恢复中断标志或继续向上层传递，而不是静默吞掉中断：

try {
    String task = tasks.take();
} catch (InterruptedException e) {
    Thread.currentThread().interrupt();
    return;
}

十二、集合视图、迭代器和 Stream 的关系

集合遍历不只有 Iterator。Collection 还可以通过 spliterator() 暴露可分割遍历器，Stream API 会利用它进行惰性遍历和可能的并行拆分。

List<Integer> numbers = List.of(1, 2, 3, 4);

int sum = numbers.stream()
        .filter(n -> n % 2 == 0)
        .mapToInt(Integer::intValue)
        .sum();

System.out.println(sum); // 6

Stream 不等同于集合：

  • 集合保存数据。
  • Stream 描述数据处理流水线。
  • 中间操作通常是惰性的。
  • 终端操作才触发遍历。
  • Stream 通常不能重复消费。

在遍历集合时修改集合仍然可能违反集合的遍历规则；Stream 的存在不会自动消除结构性修改问题。若需要生成新结果，应使用收集操作，而不是在流处理中直接修改共享集合。

十三、常见误解与诊断方法

误解一：HashMap 永远是 O(1)

正确说法是：在正常哈希分布下，哈希映射的基本操作通常具有期望 O(1) 性能。异常哈希分布、扩容、对象哈希计算成本和内存压力都会影响实际表现。

诊断 Map 查找异常时，应检查：

  1. 键的 equals 和 hashCode 是否一致。
  2. 键是否在插入后被修改。
  3. 是否错误地把 null 返回当成“不存在”。
  4. 是否有大量碰撞或不合理的自定义哈希实现。

误解二：TreeSet 一定按 equals 去重

TreeSet 按比较器或自然顺序判断元素位置。比较结果为 0 时，集合会认为元素等价。若比较器只比较部分字段，可能有多个 equals 不相等的对象被合并。

误解三：迭代器抛出异常就说明发生了线程安全保护

ConcurrentModificationException 是错误检测信号，不是锁，也不是事务回滚机制。它甚至不保证在所有并发交错中出现。并发访问必须使用同步、并发集合或其他明确的协调方式。

误解四：PriorityQueue 的遍历就是有序遍历

优先队列只保证头部元素满足优先级规则。若要求完整排序，应反复 poll()，或复制数据后使用排序操作；直接迭代不能得到排序结果。

误解五：LinkedList 适合所有插入删除场景

如果每次都通过下标定位，链表仍然需要线性查找。只有调用方已经处在目标迭代器位置，链表的局部链接操作才体现出优势。很多实际场景中，ArrayList 的连续内存和较低对象开销更有利。

十四、选择集合的推导方式

选择集合不应从类名开始，而应从不变量和主要操作开始：

  1. 是否需要键值映射？
    • 需要：从 Map 开始。
  2. 是否允许重复？
    • 不允许：从 Set 开始。
  3. 是否需要按位置访问？
    • 需要：从 List 开始。
  4. 是否需要从两端处理？
    • 需要：从 Deque 开始。
  5. 是否需要按优先级取出？
    • 需要：考虑 PriorityQueue。
  6. 是否需要排序或范围查询？
    • 考虑 TreeSet 或 TreeMap。
  7. 是否只需保持插入顺序？
    • 考虑 LinkedHashSet 或 LinkedHashMap。
  8. 是否需要多线程并发访问？
    • 选择并发集合、阻塞队列或显式同步方案。

可以把常见需求压缩成如下映射：

需求 常见选择
紧凑存储、按下标访问 ArrayList
去重且不依赖顺序 HashSet
去重并保持插入顺序 LinkedHashSet
去重并保持排序 TreeSet
快速键值查找 HashMap
键值查找并保持插入顺序 LinkedHashMap
按键排序和范围查询 TreeMap
普通 FIFO/LIFO ArrayDeque
按优先级取出 PriorityQueue
有界生产者—消费者通信 BlockingQueue

最终的选择依据不是“哪个集合最快”，而是数据结构必须保持什么顺序、唯一性和比较规则，以及程序最频繁执行哪种操作。只有先明确这些语义，复杂度分析才有意义。

系列导航与关联阅读

官方资料

本文依据 Java、Spring 与相关项目官方文档重新梳理；正文、示例与生产清单由 WR BLOG 编写。