Java 集合框架深度剖析

容器的本质是数据结构在内存中的组织方式。如果你只是机械地记住 List、Set、Map 这三个名字，那你根本不懂容器——你只是在背诵 API。这篇文章从最底层的数组讲起，一路深入到 HashMap 的扰动函数、ArrayList 的扩容源码、ConcurrentHashMap 的并发设计，把整个 Java Collections Framework（JCF）拆到骨头。

数组：被低估的基石

很多人觉得数组是“低级”的东西，学完集合就再也不碰了。但 Java 的集合框架大量地方都建立在数组之上 ArrayList、HashMap、ArrayDeque、PriorityQueue 的底层全是数组。不理解数组，就无法真正理解这些容器的性能特征。

数组的本质

数组在 JVM 层面是一段连续的内存区域，通过起始地址 + 偏移量直接寻址。这意味着：

• 随机访问 O(1)：arr[i] 的寻址公式是 base_address + i * element_size，CPU 一条指令就能算出来。
• CPU 缓存友好：连续内存让硬件预取（prefetcher）能准确预测下一次访问的地址，缓存命中率极高。这一点是链表永远无法企及的。
• 长度固定：数组一旦创建，长度不可改变。这是数组的“基因缺陷”，也是动态数组（ArrayList）存在的根本理由。

数组协变：一个设计错误

Java 的数组是协变（covariant） 的：如果 B 是 A 的子类型，那么 B[] 也是 A[] 的子类型。看这段代码：

Integer[] ints = new Integer[10];
Object[] objs = ints;   // 合法！数组协变
objs[0] = "string";     // 编译通过，运行时抛 ArrayStoreException

数组的协变在编译期放行，在运行期用 ArrayStoreException 来兜底——因为数组是具化的（reified），它在运行时确切知道自己的元素类型。

这被普遍认为是一个设计错误。Java 5 引入泛型时吸取了教训：泛型是不变的（invariant），List<Object> 不是 List<Integer> 的父类型。

List<Integer> intList = new ArrayList<>();
// List<Object> objList = intList;  // 编译错误！泛型不变

那为什么泛型不也做成协变？因为泛型通过类型擦除（type erasure） 实现，运行时 List<Integer> 和 List<String> 都是同一个 List，根本无法在运行期做 ArrayStoreException 那样的检查。所以只能从编译期挡住。协变 vs 不变，本质是“具化 vs 擦除”这一历史包袱的直接后果。

多维数组：数组的数组

Java 没有真正的多维数组，所谓二维数组其实是“数组的数组”。每行可以不等长（锯齿数组）：

int[][] jagged = {
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};

// 行可以独立分配，甚至指向不同对象
int[][] matrix = new int[3][];
matrix[0] = new int[5];
matrix[1] = new int[10];

正因为是“数组的数组”，二维数组的两次寻址都会经过一次指针解引用，缓存局部性比 C 的连续二维数组差。对性能敏感的数值计算应考虑一维数组 + 手动计算下标。

Arrays 工具类：被忽视的瑞士军刀

java.util.Arrays 提供了大量静态工具方法，是操作数组的核心。

int[] arr = {5, 3, 1, 4, 2};

// 排序：双轴快速排序（Dual-Pivot Quicksort）
Arrays.sort(arr);

// 并行排序（Java 8+），利用 ForkJoinPool
Arrays.parallelSort(arr);

// 二分查找（必须先排序），返回下标，不存在返回负数
int idx = Arrays.binarySearch(arr, 4);

// 拷贝：内部调用 System.arraycopy
int[] copy = Arrays.copyOf(arr, 10);       // 新长度 10，超出补 0
int[] range = Arrays.copyOfRange(arr, 1, 4); // [1, 4)

// 填充
Arrays.fill(arr, 0);

// 转换为可读字符串，调试利器
System.out.println(Arrays.toString(arr));

// 多维数组用 deepToString
int[][] m = {{1, 2}, {3, 4}};
System.out.println(Arrays.deepToString(m));

Arrays.asList 的三个陷阱

这是面试和实战中踩坑率最高的 API 之一：

// 陷阱一：返回的不是 java.util.ArrayList，而是 Arrays 的内部类
List<Integer> list = Arrays.asList(1, 2, 3);
// list.add(4);  // UnsupportedOperationException！不支持结构性修改
list.set(0, 99);  // 但 set 可以，因为它不改变数组长度

// 陷阱二：int[] 装箱的灾难
int[] nums = {1, 2, 3};
List<int[]> weird = Arrays.asList(nums); // List<int[]>，长度为 1！
// 基本类型数组被当成单个元素。要装箱成 Integer 必须用流：
List<Integer> boxed = Arrays.stream(nums).boxed().toList();

// 陷阱三：返回的列表是原数组的视图
Integer[] arr = {1, 2, 3};
List<Integer> view = Arrays.asList(arr);
arr[0] = 999;
System.out.println(view.get(0)); // 999，两边同步！

想要一个真正可变的 ArrayList：

List<Integer> mutable = new ArrayList<>(Arrays.asList(1, 2, 3));

数组与集合的互转

// 集合 -> 数组
List<String> list = List.of("a", "b", "c");

// 推荐写法：传入长度为 0 的数组，让实现自己决定分配
String[] arr = list.toArray(String[]::new);   // 方法引用（Java 11+）
String[] arr2 = list.toArray(new String[0]);  // 传统写法

// 数组 -> 集合
String[] src = {"a", "b", "c"};

// Java 9+：不可变列表，推荐
List<String> immutable = List.of(src);

// 经典：可变但受限（见 1.5）
List<String> view = Arrays.asList(src);

// 流式：灵活处理
List<String> filtered = Arrays.stream(src).filter(s -> !s.isEmpty()).toList();

数组 vs 集合：如何取舍

维度	数组	集合
长度	固定	动态
类型安全	协变，运行期检查	不变，编译期检查（泛型擦除但有编译保障）
性能	最高，无装箱/无对象开销	略有开销（对象头、扩容拷贝）
元素类型	支持基本类型	只能存对象（基本类型需装箱）
API	贫乏，靠 Arrays	丰富，迭代、流、排序、并发
适用场景	长度已知、基本类型密集计算、性能极致	绝大多数业务场景

结论：能用集合就用集合，只有在长度确定 + 性能敏感 + 基本类型这三者叠加时，才回退到数组。

集合框架全景

核心架构

Java 集合框架分为两大支系：Collection（单值）和 Map（键值对）。下图展示核心接口与实现的关系：

graph TD
    Iterable["Iterable<E>"]
    Collection["Collection<E>"]
    List["List<E>"]
    Set["Set<E>"]
    Queue["Queue<E>"]
    Deque["Deque<E>"]
    Map["Map<K,V>"]

    Iterable --> Collection
    Collection --> List
    Collection --> Set
    Collection --> Queue
    Queue --> Deque
    Deque -.继承.-> List

    ArrayList["ArrayList"]
    LinkedList["LinkedList"]
    Vector["Vector"]

    List --> ArrayList
    List --> LinkedList
    List --> Vector

    HashSet["HashSet"]
    LinkedHashSet["LinkedHashSet"]
    TreeSet["TreeSet"]

    Set --> HashSet
    Set --> LinkedHashSet
    Set --> TreeSet
    LinkedHashSet -.底层.-> HashSet

    HashMap["HashMap"]
    LinkedHashMap["LinkedHashMap"]
    TreeMap["TreeMap"]

    Map --> HashMap
    Map --> LinkedHashMap
    Map --> TreeMap
    LinkedHashMap -.底层.-> HashMap
    HashSet -.底层.-> HashMap
    TreeSet -.底层.-> TreeMap

    classDef impl fill:#e8f5e9,stroke:#388e3c;
    classDef iface fill:#e3f2fd,stroke:#1976d2;
    class ArrayList,LinkedList,Vector,HashSet,LinkedHashSet,TreeSet,HashMap,LinkedHashMap,TreeMap impl;
    class Iterable,Collection,List,Set,Queue,Deque,Map iface;

读这张图的关键：

1. Collection 继承 Iterable——这意味着所有集合都可迭代，这是 for-each 语法和 Stream 的根基。
2. Set 的实现底层几乎全是 Map——HashSet 内部是一个 HashMap，TreeSet 内部是一个 TreeMap。Set 只是 Map 的 Value 被塞了一个常量占位符。
3. Deque 继承 Queue，而 LinkedList 同时实现了 List 和 Deque——这也是 LinkedList 定位模糊、常常被滥用的根源。

Sequenced Collections：Java 21 迟来的统一

Java 21 之前，有序集合的 API 设计堪称一塌糊涂。你想访问第一个元素：

• List 用 get(0)
• Deque 用 getFirst()
• SortedSet 用 first()

三种接口三种风格，毫无一致性。Java 21 引入 SequencedCollection、SequencedSet、SequencedMap 三个接口，终于统一了：

graph LR
    SC["SequencedCollection<E>"] --> Coll["Collection<E>"]
    Coll --> List["List<E>"]
    Coll --> Q["Queue<E>"]
    Q --> DQ["Deque<E>"]
    SS["SequencedSet<E>"] --> Set["Set<E>"]
    SM["SequencedMap<K,V>"] --> Map["Map<K,V>"]

统一方法族：addFirst / addLast / getFirst / getLast / removeFirst / removeLast / reversed()。reversed() 返回一个逆序视图（不拷贝），这在回文判断、反向遍历场景非常优雅。

迭代器：集合的通用语言

Iterable 与 Iterator

Iterable 只有一个抽象方法 iterator()，配合 Java 8 的默认方法 forEach 和 spliterator：

public interface Iterable<E> {
    Iterator<E> iterator();
    default void forEach(Consumer<? super E> action) { ... }
    default Spliterator<E> spliterator() { ... }
}

Iterator 的核心是 hasNext / next，Java 8 又加了 forEachRemaining 和 remove（默认抛异常）。

fail-fast vs fail-safe

这是迭代器最容易被问到、也最容易被误解的概念。

fail-fast（快速失败）：ArrayList、HashMap 等非并发集合的迭代器。它们在创建时记录容器的 modCount，每次 next() 都会检查 modCount 是否变化，若被结构性修改（add/remove）就抛 ConcurrentModificationException。

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
for (Integer i : list) {
    if (i == 2) list.remove(i); // ConcurrentModificationException！
}

注意：fail-fast 是“尽力而为”的机制，不能作为并发正确性的保证——它依赖 modCount 的非原子读，多线程下可能检测不到修改。它的设计目的是尽早暴露程序 bug，而不是处理并发。

fail-safe（安全失败）：java.util.concurrent 包下的并发容器（CopyOnWriteArrayList、ConcurrentHashMap）的迭代器。它们遍历的是创建时的快照或弱一致视图，不抛异常，但可能看不到迭代过程中新增的元素。

正确删除：Iterator.remove 与 removeIf

要边遍历边删除，正确做法是用迭代器的 remove：

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 2) it.remove(); // 安全：删除的是最近返回的元素
}

更简洁的是 Java 8 的 removeIf：

list.removeIf(i -> i == 2);

List：有序的真相

ArrayList：动态数组源码剖析

ArrayList 是 JCF 中最重要的实现，本质就是“会自动扩容的数组”。

字段与延迟初始化：

// JDK 8+：延迟初始化，首次 add 才分配
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // 存储，transient 见 4.1.3
private int size;

// 空数组常量，用于 new ArrayList() 时
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

JDK 7 的 new ArrayList() 会立刻分配 10 长度的数组——这在大量空列表场景下浪费内存。JDK 8 改为延迟到首次 add 才分配，是个很务实的优化。

扩容逻辑：

flowchart TD
    A["add(e)"] --> B{size == elementData.length?}
    B -- 否 --> C["elementData[size] = e; size++"]
    B -- 是 --> D["grow(minCapacity)"]
    D --> E["newCap = oldCap + oldCap >> 1\n(1.5 倍)"]
    E --> F{newCap 够吗?}
    F -- 否 --> G["newCap = minCapacity"]
    F -- 是 --> H["用 newCap"]
    G --> I["Arrays.copyOf 拷贝"]
    H --> I
    I --> C

核心源码（简化）：

private void grow(int minCapacity) {
    int oldCap = elementData.length;
    int newCap = oldCap + (oldCap >> 1);  // 1.5 倍
    if (newCap < minCapacity) newCap = minCapacity;
    if (newCap > MAX_ARRAY_SIZE) newCap = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCap); // 底层 System.arraycopy
}

为什么是 1.5 倍而不是 2 倍？ HashMap 是 2 倍，ArrayList 是 1.5 倍，Vector 是 2 倍。1.5 倍是个平衡：扩容次数不至于太频繁（相比 1.2 倍），同时内存利用率更高（相比 2 倍，平均浪费更少）。更关键的是，1.5 倍能复用之前释放的内存块——多次扩容后，旧的数组总长度之和恰好能凑出下一个新数组的开头（内存复用理论，Growth Factor ≈ φ 的工程近似）。

插入/删除的真相：add(index, e) 和 remove(index) 需要用 System.arraycopy 移动后续元素，O(n)。但注意——移动是内存连续的批量拷贝，对 CPU 而言这是高度优化的操作（SIMD、prefetch），常数极小。实践中，即使是 O(n) 的中间插入，ArrayList 在数据量不大时往往比 LinkedList 的 O(1)（理论）更快，因为后者每次 new Node() 的开销和缓存不命中率远超一次批量数组拷贝。

序列化：elementData 被 transient 修饰，但 ArrayList 重写了 writeObject/readObject，只序列化 [0, size) 范围内的元素。因为数组通常有空余容量，直接序列化整个数组会浪费空间。

LinkedList：被高估的选项

LinkedList 是双向链表，同时实现 List 和 Deque：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

它的致命缺陷是缓存：每个 Node 都是堆上独立分配的对象，内存地址分散。遍历时 CPU 几乎每次都 cache miss，要回主存取数据——这比一次数组拷贝慢一两个数量级。

“插入快”是个伪命题：很多人记着“链表插入 O(1)”。但前提是你已经拿到了目标节点的引用。在 LinkedList 上做 add(index, e)，首先要花 O(n) 找到位置，然后才 O(1) 修改指针。而 ArrayList 是 O(n) 找位置（实际上是 O(1) 寻址）+ O(n) 批量拷贝。在多数实际场景下，ArrayList 的常数更优。

唯一合理用途：作为 Deque/Queue 使用。但即便如此，ArrayDeque 在绝大多数场景下也优于 LinkedList。结论是：现代 Java 开发中，LinkedList 几乎没有不可替代的场景。

Vector：请忘记它

Vector 的每个方法都加了 synchronized，是一把粗粒度的全局锁，并发性能极差。它在 Collections.synchronizedList 出现后就已过时，在 ConcurrentHashMap、CopyOnWriteArrayList 出现后更是毫无存在意义。需要线程安全时去 java.util.concurrent 找，永远别碰 Vector（以及 Stack——它继承自 Vector，同样是历史包袱）。

List 性能对比

操作	ArrayList	LinkedList	Vector
随机访问 get(i)	O(1)	O(n)	O(1) (锁开销)
头部插入 add(0,e)	O(n)	O(1)	O(n)
尾部插入 add(e)	均摊 O(1)	O(1)	均摊 O(1)
中间插入	O(n) 但常数小	O(n) 寻址 + O(1)	O(n)
遍历	极快（缓存友好）	慢（缓存不友好）	同 ArrayList
线程安全	否	否	是（粗锁）
内存开销	小（数组）	大（每节点一对象）	小

Set：去重的艺术

Set 的大多数实现本质上是 Map 的包装：把 Value 设为一个常量占位符，复用 Map 的存储和去重逻辑。

• HashSet：底层是 HashMap。无序，查找/插入/删除均摊 O(1)。
• LinkedHashSet：维护插入顺序的 HashSet（底层 LinkedHashMap），遍历顺序与插入顺序一致。
• TreeSet：底层是 TreeMap（红黑树）。元素有序，操作 O(log n)。
• EnumSet：专为枚举设计的位向量实现，极致紧凑高效，枚举集合的首选。

HashSet 的 equals/hashCode 契约

HashSet 判重依赖 equals 和 hashCode。这两个方法必须满足契约：

1. 一致性：a.equals(b) 为 true，则 a.hashCode() == b.hashCode()。
2. 一致性逆否：a.hashCode() != b.hashCode()，则 a.equals(b) 必为 false。

破坏契约的后果是元素“丢失”——明明加进去了，却 contains 不到。更隐蔽的陷阱是用可变对象作为 key 并在放入后修改其参与 hashCode 计算的字段，会导致该元素在 Set 中“失踪”，且无法移除（因为定位不到原来的桶）。

TreeSet 与比较器

TreeSet 要求元素要么实现 Comparable，要么构造时传入 Comparator。注意它用比较而非 equals 判等——如果两个对象 compareTo 返回 0，TreeSet 认为它们相等，会拒绝后者。这常常导致“明明 equals 不同却加不进去”的困惑。

Map：性能的心脏

Map 是 JCF 的性能核心，也是面试和源码考察的重灾区。

HashMap 数据结构

JDK 8 的 HashMap 是数组 + 链表 + 红黑树的混合结构：

graph TD
    subgraph Table["Node[] table（哈希桶数组，长度始终为 2 的幂）"]
        T0["table[0]"]
        T1["table[1]"]
        T2["table[2]"]
        T3["table[3]"]
        TDOTS["..."]
    end

    T0 --> N0a["Node(k0,v0,h0)"]
    N0a --> N0b["Node(k1,v1,h1)"]
    N0b --> N0c["Node(k2,v2,h2)\n链表长度 ≥8 且 table ≥64\n→ 转红黑树"]

    T2 --> N2a["Node(k3,v3,h3)"]
    N2a --> N2b["Node(k4,v4,h4)"]

    T3 --> TN3["TreeNode（红黑树根）\nTreeBin 封装"]
    TN3 --> TN3L["左子树"]
    TN3 --> TN3R["右子树"]

关键参数：

static final int DEFAULT_INITIAL_CAPACITY = 16;   // 默认容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;   // 负载因子
static final int TREEIFY_THRESHOLD = 8;           // 链表树化阈值
static final int UNTREEIFY_THRESHOLD = 6;         // 树退化阈值
static final int MIN_TREEIFY_CAPACITY = 64;       // 树化最小表容量

扰动函数与桶定位

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 桶定位
int index = (n - 1) & hash;

为什么要扰动？ 桶定位用的是 (n-1) & hash（位与，等价于 hash % n，但位运算更快，前提是 n 是 2 的幂）。当 n=16 时，n-1 = 0b1111，只有 hash 的低 4 位参与运算。如果某些 key 的 hashCode 在低位高度集中（碰撞），就会退化成链表。扰动函数把高 16 位与低 16 位异或，让高位的影响也参与到低位计算，降低碰撞概率。

为什么容量必须是 2 的幂？ 为了让 (n-1) & hash 等价于取模。扩容时翻倍（n×2），n-1 只是最高位多了一个 1，这让 rehash 有极优雅的优化（见 6.4）。

put 流程

flowchart TD
    A["put(key, value)"] --> B["hash =扰动(key.hashCode())"]
    B --> C["index = (n-1) & hash"]
    C --> D{table[index] 为空?}
    D -- 是 --> E["新建 Node 放入，break"]
    D -- 否 --> F{是 TreeNode?}
    F -- 是 --> G["红黑树插入/覆盖"]
    F -- 否 --> H["遍历链表"]
    H --> I{key 相等?}
    I -- 是 --> J["覆盖 value，break"]
    I -- 否 --> K{链表末尾?}
    K -- 否 --> H
    K -- 是 --> L["尾插新 Node\n链表长度 ≥8?"]
    L --> M{≥8 且 table ≥64?}
    M -- 是 --> N["treeifyBin 链表转红黑树"]
    M -- 否 --> O["保持链表"]
    N --> P["size++ > threshold?\n扩容 resize()"]
    O --> P
    E --> P
    G --> P
    J --> R["返回 oldValue"]
    P --> R

扩容：JDK 8 的优雅优化

当 size > threshold（threshold = capacity × loadFactor）时触发扩容：容量翻倍，并 rehash 所有元素。

JDK 7 是逐个重新计算 index = hash % newCap。JDK 8 利用了一个数学性质——扩容后元素的新位置只有两种可能：原位置，或原位置 + oldCap。

为什么？设扩容前 n=16，n-1 = 0b01111；扩容后 n=32，n-1 = 0b11111。差别只在多出来的**第 5 位（bit 4）**参与运算。所以：

• 若 hash 的 bit 4 为 0：新 index = 旧 index（不变）。
• 若 hash 的 bit 4 为 1：新 index = 旧 index + 16（= oldCap）。

只需检查 hash 的这一位，就能判断元素去留，无需重新取模。JDK 8 把原链表拆成两条（lo 链和 hi 链），分别挂到新旧位置。这比 JDK 7 快得多，且是尾插法，避免了 JDK 7 的死循环问题。

JDK 7 的死循环：为什么被废弃

JDK 7 的 HashMap 扩容用头插法。多线程并发扩容时，两个线程各自搬移节点，头插法会让链表形成环形引用。此后任何 get 命中这个环，CPU 就会在环上 100% 自旋——经典的线上事故。

JDK 8 改为尾插法 + 拆分双链表，从结构上消除了成环可能。但**HashMap 仍然不是线程安全的**——尾插法避免了死循环，但多线程下仍会丢数据、size 不准。并发场景必须用 ConcurrentHashMap。

LinkedHashMap 与 LRU

LinkedHashMap 在 HashMap 基础上维护了一条双向链表记录插入顺序（或访问顺序）。它的 Entry 比 HashMap.Node 多了 before/after：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

开启访问顺序（accessOrder=true）后，每次 get/put 命中的节点会被移到链表尾部。配合重写 removeEldestEntry，可以轻松实现 LRU 缓存：

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LruCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // 超容量时淘汰链表头部（最久未访问）
    }
}

TreeMap：红黑树

TreeMap 基于红黑树（自平衡 BST），保证键有序。红黑树通过五条性质约束，使树高保持在 O(log n)，插入/删除/查找都是 O(log n)。适用于需要按 key 范围查询（subMap、headMap、tailMap）或有序遍历的场景。

compute 家族：别再写 check-then-act

// 反模式：两次哈希定位 + 竞态条件
if (map.get(key) == null) {
    map.put(key, value);
}

compute 家族让操作原子化，单次哈希定位完成：

方法	适用场景	键不存在	键存在	返回值
computeIfAbsent	缓存/初始化	计算并插入	不操作	关联值（新计算或已存在）
computeIfPresent	更新已有值	不操作	计算并替换	新值（键不存在返回 null）
compute	强制计算/删除	计算并插入	计算并替换	新值（返回 null 则删除键）
merge	合并/累加	用默认值	计算并替换	合并后的值

// computeIfAbsent：分组，只做一次哈希定位
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

// computeIfPresent：条件更新
map.computeIfPresent(key, (k, v) -> v + 1);

// compute：强制计算，返回 null 可删除键
map.compute(key, (k, v) -> v == null ? init : transform(v));

// merge：优雅的计数器
map.merge(key, 1, Integer::sum);

// 批量合并两个 map
other.forEach((k, v) -> map.merge(k, v, Integer::sum));

这些方法在 ConcurrentHashMap 上尤其关键——它们在桶级别保证原子性，避免了 check-then-act 的竞态。

Map.of：不可变 Map

Java 9+ 的 Map.of(k1,v1,...) 返回不可变 Map，Map.entry + Map.ofEntries 用于构造超过 10 对的情况。不可变集合天然线程安全，适合配置、常量映射。注意 Map.of 不允许 null key/value，且重复 key 直接抛异常。

Queue 与 Deque

接口方法对照

Queue/Deque 的方法分两族——抛异常 vs 返回特殊值：

操作	抛异常	返回特殊值
入队	add（满抛 IllegalStateException）	offer（满返回 false）
出队	remove（空抛 NoSuchElementException）	poll（空返回 null）
查看队首	element（空抛异常）	peek（空返回 null）

Deque 是双端队列，两端都可出入。push/pop 提供栈语义。

ArrayDeque：栈与队列的首选

ArrayDeque 基于循环数组（circular buffer），两端操作均摊 O(1)，不允许 null。它几乎在所有场景都优于 LinkedList 作为栈/队列的实现：

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

// 队列
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll(); // 1

PriorityQueue：二叉堆

PriorityQueue 基于数组实现的二叉最小堆（默认自然序，或传入 Comparator）。它不是 FIFO——出队顺序由优先级决定：

// 小顶堆：每次 poll 取最小
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(3, 1, 4, 1, 5, 9));
pq.poll(); // 1
pq.poll(); // 1
pq.poll(); // 3

// 大顶堆：传 reverseOrder
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

• offer / poll：O(log n)（上浮/下沉）
• peek：O(1)
• 遍历不保证有序（堆只保证堆序性质，不保证全局有序）。需要有序输出应一个个 poll，或直接用排序结构。

并发容器：别再用全局锁了

如果你还在用 Collections.synchronizedMap()，那你还在石器时代。它用一把全局锁锁住整个容器，并发性能极差。java.util.concurrent 提供了精细设计的并发容器。

ConcurrentHashMap：工业级杰作

ConcurrentHashMap 经历了两代设计：

JDK 7：分段锁（Segment）

graph LR
    subgraph CHM7["ConcurrentHashMap"]
        S0["Segment 0\n(ReentrantLock)"]
        S1["Segment 1"]
        SD["..."]
        S15["Segment 15"]
    end
    S0 --> E0["Entry[]"]
    S1 --> E1["Entry[]"]
    S15 --> E15["Entry[]"]

默认 16 个 Segment，每个 Segment 是一个独立的小 HashMap，带自己的 ReentrantLock。理论上支持 16 线程并发写。读用 volatile，不加锁。

JDK 8：CAS + synchronized 桶锁

graph TD
    subgraph CHM8["Node[] table"]
        B0["table[0]"]
        B1["table[1]"]
        B2["table[2]"]
    end
    B0 --> L0["Node 链表"]
    B1 --> T1["TreeBin（红黑树）"]
    B2 -.空桶.-> C0["CAS 直接插入\n无锁"]
    L0 -->|"synchronized 锁头节点"| W0["桶内更新"]

JDK 8 放弃了 Segment，直接用 Node[] 数组，锁粒度细化到每个哈希桶：

• 读完全无锁：Node 的 val 和 next 是 volatile，读操作直接读，保证可见性。
• 写空桶用 CAS：桶为空时，用 CAS 插入头节点，无锁。
• 写非空桶用 synchronized：桶非空时，锁住头节点（不是整个表），其他桶不受影响。
• 链表树化：长度 ≥8 转红黑树（TreeBin 封装），把最坏 O(n) 查找优化为 O(log n)。

重要差异：ConcurrentHashMap 不允许 null key 和 null value（HashMap 允许）。原因是并发场景下 get 返回 null 时无法区分“不存在”还是“值为 null”——HashMap 可以事后用 containsKey 消歧，但并发下这个消歧本身就有竞态。

CopyOnWriteArrayList：读多写少的利器

final transient Object[] array;  // volatile 引用
final transient ReentrantLock lock = new ReentrantLock();

写时复制：每次 add/remove 都在锁保护下拷贝整个数组，替换 volatile 引用。

• 读完全无锁：直接读 volatile 数组引用，性能极好。
• 写代价极高：O(n) 拷贝，频繁写会产生大量垃圾，GC 压力大。
• 弱一致性：迭代器遍历的是创建时的数组快照，看不到后续修改。

适用场景：读极多、写极少，且能容忍数据短暂不一致——典型如监听器列表、配置缓存。写频繁时务必用 ConcurrentHashMap 或加锁结构。

BlockingQueue：生产者-消费者的基石

实现	底层	特点
ArrayBlockingQueue	有界数组	单锁，FIFO，容量固定
LinkedBlockingQueue	链表	双锁（put/take 分离），默认 Integer.MAX_VALUE（危险！）
SynchronousQueue	无容量	直接传递，put 阻塞到有 take
PriorityBlockingQueue	无界堆	按优先级出队
DelayQueue	无界堆	元素到期才能出队

LinkedBlockingQueue 默认容量是 Integer.MAX_VALUE，在生产线程快于消费线程时会无限堆积，最终 OOM。永远显式指定容量：

new LinkedBlockingQueue<>(1000);

BlockingQueue 的 put/take 是阻塞的（满则阻塞 put，空则阻塞 take），offer/poll 带超时版本，是线程池（ThreadPoolExecutor）工作队列的标准实现。

跳表 vs 红黑树：并发有序的抉择

ConcurrentSkipListMap / ConcurrentSkipListSet 提供并发有序 Map/Set，基于跳表（Skip List） 而非红黑树。

为什么不用红黑树？红黑树插入/删除涉及多次旋转和重染色，并发修改时全局重平衡极难做无锁化。跳表是概率结构，插入/删除只需修改局部指针（CAS 即可），天然适合无锁/低锁并发。代价是空间换时间（多层索引）和 O(log n) 的期望（而非最坏）复杂度。在并发有序场景，跳表是更务实的选择。

Collections 工具类

java.util.Collections 提供静态工厂和算法。理解它就理解了“如何把非线程安全集合包装成线程安全”“如何制造不可变视图”。

同步包装

List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

底层是装饰器，每个方法用 synchronized 包裹。粒度粗，迭代时仍需手动加锁：

synchronized (syncList) {  // 必须手动同步！
    for (String s : syncList) { ... }
}

现代代码应优先 java.util.concurrent 的并发容器，而非这套同步包装。

不可变包装

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

返回只读视图，底层仍是原集合——原集合改了，视图也变。要真正不可变应配合拷贝，或直接用 Java 9+ 的 List.of/Map.of。

检查类型包装

// 防止通过原始类型绕过泛型，插入错误类型
List<String> checked = Collections.checkedList(new ArrayList<>(), String.class);

主要用于与遗留代码（raw type）交互时，在插入而非读取时抛 ClassCastException，便于定位问题源头。

算法

Collections.sort(list);                    // 自然序，Java 8+ List 自带 sort
Collections.sort(list, Comparator.reverseOrder());
Collections.shuffle(list);                 // 随机打乱
Collections.reverse(list);                 // 反转
Collections.binarySearch(sortedList, key); // 二分查找（需已排序）
Collections.frequency(list, elem);         // 计数
Collections.disjoint(list1, list2);        // 是否无交集

空与单元素

Collections.emptyList();      // 单例空 List
Collections.singletonList(x); // 单元素 List
Collections.emptyMap();
Collections.emptySet();

这些返回单例对象，避免重复分配，适合返回空结果的场景（优于 new ArrayList<>()）。

选型决策树

flowchart TD
    Start["需要存什么？"] --> Q1{键值对?}
    Q1 -- 是 --> Q1a{需要有序/范围查询?}
    Q1a -- 是 --> Q1b{并发?}
    Q1b -- 是 --> CM["ConcurrentSkipListMap"]
    Q1b -- 否 --> TM["TreeMap"]
    Q1a -- 否 --> Q1c{需要插入顺序?}
    Q1c -- 是 --> Q1d{并发?}
    Q1d -- 是 --> CHM["ConcurrentHashMap"]
    Q1d -- 否 --> LHM["LinkedHashMap"]
    Q1c -- 否 --> Q1e{并发?}
    Q1e -- 是 --> CHM
    Q1e -- 否 --> HM["HashMap"]

    Q1 -- 否 --> Q2{需要去重?}
    Q2 -- 是 --> Q2a{需要有序?}
    Q2a -- 是 --> Q2b{并发?}
    Q2b -- 是 --> CSLS["ConcurrentSkipListSet"]
    Q2b -- 否 --> TS["TreeSet"]
    Q2a -- 否 --> Q2c{需要插入顺序?}
    Q2c -- 是 --> LHS["LinkedHashSet"]
    Q2c -- 否 --> HS["HashSet"]

    Q2 -- 否 --> Q3{栈/队列语义?}
    Q3 -- 是 --> Q3a{需要阻塞?}
    Q3a -- 是 --> Q3b{有界?}
    Q3b -- 是 --> ABQ["ArrayBlockingQueue"]
    Q3b -- 否 --> Q3c{优先级?}
    Q3c -- 是 --> PBQ["PriorityBlockingQueue"]
    Q3c -- 否 --> LBQ["LinkedBlockingQueue"]
    Q3a -- 否 --> Q3d{优先级?}
    Q3d -- 是 --> PQ["PriorityQueue"]
    Q3d -- 否 --> AD["ArrayDeque"]

    Q3 -- 否 --> Q4{需要索引随机访问?}
    Q4 -- 是 --> Q4a{并发?}
    Q4a -- 是 --> Q4b{读多写少?}
    Q4b -- 是 --> COW["CopyOnWriteArrayList"]
    Q4b -- 否 --> COW2["CopyOnWriteArrayList\n或加锁 ArrayList"]
    Q4a -- 否 --> AL["ArrayList"]
    Q4 -- 否 --> Q4a

常见陷阱与最佳实践

陷阱清单

1. Arrays.asList 不是 ArrayList：不支持 add/remove，且是原数组视图。
2. subList 是视图：修改子列表影响原列表，对原列表做结构性修改会让子列表失效（抛 ConcurrentModificationException）。
3. HashMap 容量规划：已知元素数 N 时，初始容量设为 N / 0.75 + 1（向上取 2 的幂）可避免扩容。new HashMap<>(expectedSize) 的位运算技巧（Java 8 的 tableSizeFor）已自动处理。
4. foreach 中修改：触发 fail-fast。用 Iterator.remove 或 removeIf。
5. == 比较装箱类型：Integer 在 [-128, 127] 有缓存，超出范围 == 失效。集合元素比较永远用 equals。
6. ConcurrentHashMap 不允许 null：get 返回 null 即“不存在”，简洁且无歧义。
7. LinkedBlockingQueue 默认无界：务必指定容量，否则 OOM。
8. 可变对象作 key：放入 Map/Set 后修改其 hashCode 字段，会导致元素“失踪”且无法移除。
9. PriorityQueue 遍历无序：堆只保证堆序，不保证全局有序。

最佳实践

1. 默认 ArrayList：除非有极其特殊的理由（高频头尾插入用 ArrayDeque，并发用对应并发容器），否则永远用 ArrayList。
2. HashMap 默认 Map：需要有序用 LinkedHashMap（插入/访问序）或 TreeMap（排序/范围查询），并发用 ConcurrentHashMap。
3. 预估容量：ArrayList、HashMap、StringBuilder 等可扩容结构，已知规模时预设容量，避免扩容拷贝。
4. 不可变优先：能用 List.of/Map.of/Set.of 就用，天然线程安全、语义清晰。
5. compute 替代 check-then-act：原子、单次哈希、并发安全。
6. EnumSet/EnumMap：枚举场景的专用实现，位向量/数组实现，性能碾压通用集合。
7. 并发容器看场景：读多写少 CopyOnWriteArrayList，通用并发 ConcurrentHashMap，有序并发 ConcurrentSkipListMap，生产消费 BlockingQueue。