Java 集合体系 — 知识详解

更新: 5/15/2026 字数: 0 字时长: 0 分钟

1. ArrayList 源码分析

1.1 底层结构

ArrayList 底层使用 Object[] 数组存储元素：

java

transient Object[] elementData; // 存储元素的数组
private int size;               // 实际元素个数

elementData 被标记为 transient，这是序列化优化——ArrayList 自定义了 writeObject/readObject，只序列化 size 个有效元素，而非整个数组（数组末尾可能有空位）。

1.2 扩容机制（1.5 倍）

当 add() 发现容量不足时触发 grow()：

java

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 旧容量 + 旧容量/2，即 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容流程：

新容量 = 旧容量 × 1.5（位运算 >> 1）
若 1.5 倍仍不够，直接用所需最小容量
Arrays.copyOf 创建新数组并复制数据（O(n) 操作）

性能提示：预知元素数量时用 new ArrayList<>(initialCapacity) 避免多次扩容拷贝。

1.3 modCount 快速失败

modCount 记录结构性修改次数。迭代器创建时快照 expectedModCount = modCount，每次 next() 前检查：

java

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

常见坑：

java

// ❌ 错误：foreach 中直接 remove 触发 ConcurrentModificationException
for (String s : list) {
    if (s.equals("target")) list.remove(s);
}

// ✅ 正确：使用迭代器的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("target")) it.remove();
}

// ✅ 正确：Java 8+ removeIf
list.removeIf(s -> s.equals("target"));

1.4 ArrayList vs LinkedList

特性	ArrayList	LinkedList
底层	Object[] 数组	双向链表 Node
随机访问	O(1)	O(n)
头部插入	O(n)（需移动元素）	O(1)
尾部插入	均摊 O(1)	O(1)
内存	紧凑，缓存友好	每个节点额外 prev/next 指针

结论：绝大多数场景用 ArrayList，LinkedList 只在频繁头部插入/删除且不需要随机访问时考虑。

2. LinkedList 源码分析

2.1 Node 结构

java

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

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

维护 first 和 last 两个指针，头尾操作 O(1)。

2.2 实现的接口

LinkedList 同时实现了 List 和 Deque 接口：

作为 List：支持索引访问（但 O(n)，内部会判断 index 靠前还是靠后来决定从头还是尾遍历）
作为 Deque：addFirst/addLast/pollFirst/pollLast，可当队列或栈使用

3. HashMap 源码分析（JDK 1.8）

3.1 数据结构

数组 + 链表 + 红黑树：

table[0] → null
table[1] → Node → Node → Node（链表）
table[2] → TreeNode（红黑树根）
table[3] → null
...

java

// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

3.2 hash() 扰动函数

java

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么要扰动？ 桶定位用 (n-1) & hash，当 n 较小时只有低位参与运算。将高 16 位异或到低 16 位，让高位信息也参与桶定位，减少碰撞。

3.3 put 流程（核心）

java

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. 数组为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 桶为空，直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 桶的第一个节点 key 相同，直接覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5. 链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度 >= 8 则尝试树化
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 6. key 已存在，更新 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    // 7. 超过阈值则扩容
    if (++size > threshold)
        resize();
    return null;
}

put 流程总结：

数组为空 → resize() 初始化（默认容量 16，负载因子 0.75，阈值 12）
计算桶位置 (n-1) & hash
桶为空 → 直接放入新节点
桶非空 → 判断第一个节点 key 是否相同
不同 → 遍历链表/红黑树查找
链表尾插，长度 ≥ 8 则 treeifyBin
treeifyBin 内部还会检查数组长度 < 64 时优先扩容而非树化
++size > threshold 则扩容

3.4 resize 扩容

java

// 核心逻辑：容量翻倍，重新分配节点
Node<K,V> loHead = null, loTail = null; // 低位链表（留在原位）
Node<K,V> hiHead = null, hiTail = null; // 高位链表（移到 原位+oldCap）

// 判断依据：hash & oldCap
if ((e.hash & oldCap) == 0) {
    // 低位：留在原索引 i
} else {
    // 高位：移到索引 i + oldCap
}

为什么这样拆分？ 扩容后容量翻倍，(newCap-1) & hash 比 (oldCap-1) & hash 多了一个高位 bit。这个 bit 就是 oldCap 的位置。如果 hash & oldCap == 0，说明这个高位是 0，索引不变；否则索引 = 原索引 + oldCap。

3.5 树化条件

两个条件同时满足才会树化：

链表长度 ≥ 8（TREEIFY_THRESHOLD）
数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）

数组长度 < 64 时，优先扩容而非树化，因为扩容能更有效地分散节点。

3.6 线程不安全分析

JDK 1.7：头插法 + 并发扩容 → 链表成环 → 死循环
JDK 1.8：尾插法解决了成环问题，但并发 put 仍可能丢数据（两个线程同时写同一个桶）

4. ConcurrentHashMap 源码分析

4.1 JDK 1.7：分段锁

Segment[] → 每个 Segment 内部是一个小 HashMap
Segment extends ReentrantLock

默认 16 个 Segment，并发度 = 16
读不加锁（volatile 保证可见性），写锁 Segment
缺点：Segment 数量固定，无法动态调整并发度

4.2 JDK 1.8：CAS + synchronized

抛弃 Segment，锁粒度细化到桶（数组的每个槽位）：

java

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ...
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // CAS 初始化
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶为空：CAS 插入，无需加锁
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        } else {
            // 桶非空：synchronized 锁住头节点
            synchronized (f) {
                // 链表或红黑树操作
            }
        }
    }
}

关键设计：

空桶用 CAS 无锁插入
非空桶用 synchronized 锁头节点（比 ReentrantLock 更轻量，JVM 有锁升级优化）
扩容时多线程协助 transfer（每个线程负责一段桶）

4.3 size() 计算

java

// 类似 LongAdder 的思路
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

// size = baseCount + Σ counterCells[i].value

无竞争时 CAS 更新 baseCount
有竞争时分散到 CounterCell[]
size() 汇总所有 cell 的值

4.4 ConcurrentHashMap 常见坑

java

// ❌ 非原子操作：check-then-act
if (!map.containsKey(key)) {
    map.put(key, value); // 两步之间可能被其他线程插入
}

// ✅ 原子操作
map.putIfAbsent(key, value);
map.computeIfAbsent(key, k -> createValue());

5. 红黑树基本原理

HashMap 链表长度 ≥ 8 时转为红黑树，理解红黑树是面试高频考点。

5.1 红黑树的五个性质

每个节点是红色或黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的两个子节点都是黑色（不能有连续红节点）
从任一节点到其所有叶子节点的路径上，黑色节点数量相同（黑高相同）

这些性质保证了红黑树的关键特性：最长路径不超过最短路径的 2 倍，因此查找/插入/删除都是 O(log n)。

5.2 红黑树 vs AVL 树

特性	红黑树	AVL 树
平衡条件	黑高相同	左右子树高度差 ≤ 1
平衡程度	近似平衡	严格平衡
查找性能	O(log n)，略慢	O(log n)，略快
插入/删除	旋转次数少（最多 3 次）	旋转次数多
适用场景	插入删除频繁（HashMap、TreeMap）	查找频繁（数据库索引）

HashMap 选择红黑树而非 AVL 树，是因为 HashMap 的插入删除操作频繁，红黑树的旋转次数更少，综合性能更好。

5.3 插入和旋转

插入新节点默认为红色（不破坏黑高），然后通过变色和旋转修复：

叔叔节点是红色 → 变色（父和叔变黑，祖父变红，向上递归）
叔叔节点是黑色 → 旋转 + 变色（左旋/右旋，最多 2 次旋转）

6. 其他重要集合

6.1 ArrayDeque

双端队列，基于循环数组实现：

java

// 比 LinkedList 更适合做栈和队列
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);    // 栈操作
stack.pop();

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);   // 队列操作
queue.poll();

优势：

数组连续内存，缓存友好
无 Node 对象开销
大多数操作 O(1)
比 LinkedList 做栈/队列性能好 3-5 倍

6.2 TreeMap

红黑树实现，key 有序
时间复杂度 O(log n)
需要 key 实现 Comparable 或传入 Comparator
提供 firstKey/lastKey/subMap/headMap/tailMap 等范围操作

6.3 LinkedHashMap

HashMap + 双向链表维护插入顺序（或访问顺序）
accessOrder=true 时每次 get 会将节点移到链表尾部 → 可实现 LRU 缓存

java

// 简单 LRU 缓存
class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

6.4 HashSet

内部就是一个 HashMap，value 是固定的 PRESENT 对象
add(e) 实际调用 map.put(e, PRESENT)

6.5 PriorityQueue

基于小顶堆（数组实现的完全二叉树）
offer/poll 时间复杂度 O(log n)，peek O(1)
常用于 Top K 问题、任务调度

java

// 大顶堆（取最大的 K 个元素）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 自定义比较器
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

6.6 Collections 工具类常用方法

java

Collections.unmodifiableList(list);     // 不可变包装
Collections.synchronizedMap(map);       // 线程安全包装（全局锁，性能差）
Collections.singletonList(item);        // 单元素不可变列表
Collections.emptyList();                // 空不可变列表

关联知识

HashMap 的红黑树 → TreeMap 也是红黑树
ConcurrentHashMap 的 CAS → 参见并发篇 CAS 原理
LinkedHashMap 的 LRU → Android 中 LruCache 就是基于 LinkedHashMap
集合的线程安全 → Collections.synchronizedMap vs ConcurrentHashMap：前者全局锁，后者分段/桶级锁

Java 集合体系 — 知识详解 ​

1. ArrayList 源码分析 ​

1.1 底层结构 ​

1.2 扩容机制（1.5 倍） ​

1.3 modCount 快速失败 ​

1.4 ArrayList vs LinkedList ​

2. LinkedList 源码分析 ​

2.1 Node 结构 ​

2.2 实现的接口 ​

3. HashMap 源码分析（JDK 1.8） ​

3.1 数据结构 ​

3.2 hash() 扰动函数 ​

3.3 put 流程（核心） ​

3.4 resize 扩容 ​

3.5 树化条件 ​

3.6 线程不安全分析 ​

4. ConcurrentHashMap 源码分析 ​

4.1 JDK 1.7：分段锁 ​

4.2 JDK 1.8：CAS + synchronized ​

4.3 size() 计算 ​

4.4 ConcurrentHashMap 常见坑 ​

5. 红黑树基本原理 ​

5.1 红黑树的五个性质 ​

5.2 红黑树 vs AVL 树 ​

5.3 插入和旋转 ​

6. 其他重要集合 ​

6.1 ArrayDeque ​

6.2 TreeMap ​

6.3 LinkedHashMap ​

6.4 HashSet ​

6.5 PriorityQueue ​

6.6 Collections 工具类常用方法 ​

关联知识 ​

Java 集合体系 — 知识详解

1. ArrayList 源码分析

1.1 底层结构

1.2 扩容机制（1.5 倍）

1.3 modCount 快速失败

1.4 ArrayList vs LinkedList

2. LinkedList 源码分析

2.1 Node 结构

2.2 实现的接口

3. HashMap 源码分析（JDK 1.8）

3.1 数据结构

3.2 hash() 扰动函数

3.3 put 流程（核心）

3.4 resize 扩容

3.5 树化条件

3.6 线程不安全分析

4. ConcurrentHashMap 源码分析

4.1 JDK 1.7：分段锁

4.2 JDK 1.8：CAS + synchronized

4.3 size() 计算

4.4 ConcurrentHashMap 常见坑

5. 红黑树基本原理

5.1 红黑树的五个性质

5.2 红黑树 vs AVL 树

5.3 插入和旋转

6. 其他重要集合

6.1 ArrayDeque

6.2 TreeMap

6.3 LinkedHashMap

6.4 HashSet

6.5 PriorityQueue

6.6 Collections 工具类常用方法

关联知识