Java集合
Java集合框架（Java Collections Framework）是Java最核心的基础设施之一，几乎所有Java应用都离不开它。本文档深入讲解List、Set、Map的底层原理、源码细节、线程安全方案及面试高频考点。
一、集合框架全景
1.1 两大接口体系
Collection（单列集合）：List（有序可重复）、Set（无序不可重复）、Queue（队列）。Map（双列集合）：键值对存储，key不能重复，每个key映射一个value。
1.2 类图总览
|
接口 |
实现类 |
|---|---|
|
List |
ArrayList、LinkedList、Vector（已淘汰）、CopyOnWriteArrayList（并发） |
|
Set |
HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipListSet |
|
Queue/Deque |
LinkedList、ArrayDeque、PriorityQueue、BlockingQueue系列 |
|
Map |
HashMap、LinkedHashMap、TreeMap、Hashtable（已淘汰）、ConcurrentHashMap、ConcurrentSkipListMap |
二、List 详解
2.1 ArrayList
底层：Object[] elementData（transient修饰，自定义序列化避免序列化空槽位）。默认容量：JDK7+ 无参构造初始化为空数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)，首次add时才扩容至10。
扩容机制
- 扩容倍数：oldCapacity + (oldCapacity >> 1) = 1.5倍。JDK6及之前是(oldCapacity*3)/2+1
- 扩容过程：计算新容量 → ensureExplicitCapacity检查是否溢出 → Arrays.copyOf(elementData, newCapacity)，底层调System.arraycopy()（native）
- 大容量优化：addAll时扩容取min(原1.5倍, 所需最小容量)中的较大值
- 最大容量：Integer.MAX_VALUE - 8（部分VM在数组中保留header）
关键源码
常见问题
- modCount：结构性修改计数器，用于fail-fast机制。迭代中结构性修改(非迭代器自身)抛ConcurrentModificationException
- 遍历删除：必须用Iterator.remove()；增强for和forEach中删除会抛异常
- 线程安全：ArrayList非线程安全 → Collections.synchronizedList() 或 CopyOnWriteArrayList
2.2 LinkedList
底层：双向链表（Node有prev/next/item三个字段），同时实现List和Deque接口。first/last指针指向头尾节点。
核心特性
- 查询：O(n)，根据index距离头尾远近决定从头还是从尾遍历（折半优化）
- 插入/删除：O(1)（已知节点位置），但如果需要先定位（按index）则O(n)
- Deque操作：addFirst/addLast/getFirst/getLast/removeFirst/removeLast；可作栈(push/pop)和队列(offer/poll)
2.3 ArrayList vs LinkedList
|
ArrayList |
LinkedList |
|---|---|
|
底层动态数组，内存连续 |
底层双向链表，内存不连续 |
|
随机访问 O(1) |
随机访问 O(n) |
|
尾部插入 O(1)摊销，中间O(n) |
头尾插入 O(1)，中间O(n)（需先定位） |
|
内存占用少（仅存数据） |
内存占用多（每个节点存prev/next指针） |
|
无法当作队列高效使用 |
实现Deque，可作队列/双端队列/栈 |
三、HashMap 深度解析
HashMap是面试最高频考点。JDK8+底层：数组(Node[]) + 链表 + 红黑树。以下逐层深入解析。
3.1 数据结构与参数
|
参数 |
默认值 |
说明 |
|---|---|---|
|
DEFAULT_INITIAL_CAPACITY |
16 |
初始容量（必须为2的幂） |
|
DEFAULT_LOAD_FACTOR |
0.75 |
负载因子（时间空间折中） |
|
TREEIFY_THRESHOLD |
8 |
链表树化阈值 |
|
UNTREEIFY_THRESHOLD |
6 |
树退化为链表阈值 |
|
MIN_TREEIFY_CAPACITY |
64 |
最小树化数组容量（容量<64时优先扩容而非树化） |
|
MAXIMUM_CAPACITY |
1<<30 |
最大容量 |
3.2 put() 完整流程
- 计算hash： (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)。高位参与异或运算，减少低位相同的碰撞
- 定位桶位： (n - 1) & hash，等价于 hash % n（n为2的幂时位运算更高效）
- 桶为空：直接newNode放入
- 桶非空：判断首节点key是否相等 → 是则替换value；否则判断是否TreeNode → 是则走putTreeVal；否则遍历链表 → 找到相同key替换，未找到尾插新节点 → 检查链表长度≥8则treeifyBin（若数组长度<64则resize扩容）
- 最后：判断size > threshold(容量×负载因子) → resize()扩容
3.3 resize() 扩容机制
- 2倍扩容：newCap = oldCap << 1，newThr = oldThr << 1
- rehash优化（JDK8）：旧索引为i的元素，在新表中要么仍为i，要么为i+oldCap。判断条件：(e.hash & oldCap) == 0 → 仍为i；!= 0 → i+oldCap。避免JDK7中全部重新hash的消耗
- 链表拆分：维护loHead/loTail（低位链）和hiHead/hiTail（高位链）两条链表，一次性迁移
- 红黑树拆分：拆分为lo和hi两棵树 → 节点数≤6退化为链表
- 红黑树插入数据后需要维护树平衡、旋转和变色
3.4 为何容量必须是2的幂？
- (n - 1) & hash 等价于 hash % n，位运算效率远高于取模
- 扩容后rehash时只需判断新增参与运算的1bit（即e.hash & oldCap），简化迁移逻辑
- 若非2的幂，(n-1)低位为0的概率增大，hash碰撞变多
3.5 hash() 扰动函数
设计目的：当数组长度较小时（如16），(n-1)&hash 只用到hash的低几位。通过高16位异或低16位，让高位特征也影响最终索引，减少碰撞。
3.6 JDK7 vs JDK8 对比
|
对比项 |
JDK7 |
JDK8 |
|---|---|---|
|
数据结构 |
数组 + 链表 |
数组 + 链表 + 红黑树 |
|
插入方式 |
头插法 |
尾插法 |
|
并发扩容 |
死循环（环形链表） |
尾插法不会出现环形链表，但仍有数据丢失问题 |
|
rehash |
全部重新hash |
e.hash & oldCap 判断高位 |
|
空参构造 |
直接初始化16 |
空数组，首次put扩容到16（延迟初始化） |
3.7 红黑树在HashMap中的条件
树化条件（两个同时满足）：(1) 链表长度 ≥ 8（即插入第9个节点时触发）(2) 数组长度 ≥ 64。若数组长度不足64，只扩容不树化。原因：短数组上即使链表长也是因为数组太小导致的，扩容分散即可。
- 退化条件：resize拆分或remove后树节点 ≤ 6，转为链表
- 为何阈值是8：泊松分布，负载因子0.75下，桶中节点数达到8的概率约0.00000006，极低。正常情况几乎不会树化
四、其他 Map 实现
4.1 LinkedHashMap
继承HashMap，额外维护双向链表记录插入顺序（默认）或访问顺序（accessOrder=true时，get过的移到链表末尾）。
- Entry：继承HashMap.Node，增加before/after指针
- LRU实现：accessOrder=true + removeEldestEntry()重写返回true → 最老元素自动移除。天然适合LRU缓存
4.2 TreeMap
- 底层：红黑树（自平衡二叉搜索树），Entry有left/right/parent/color
- 顺序：key自然排序(Comparable) 或 构造时传入Comparator。key不能为null（Comparator比较时NPE）
- 复杂度：get/put/remove均为O(log n)
- 核心方法：firstEntry/lastEntry/lowerEntry/higherEntry/subMap/tailMap/headMap
4.3 Hashtable（已淘汰）
- 线程安全：所有方法synchronized修饰（全表锁），并发性能极差
- 遗留差异：key/value不能为null；默认容量11，扩容2n+1
- 替代：ConcurrentHashMap（推荐）或 Collections.synchronizedMap()
五、Set 详解
5.1 HashSet
底层：基于HashMap实现，元素作为key存入HashMap，value为统一的PRESENT(Object常量)。所有操作委托给HashMap，时间复杂度同HashMap。
- 无序性：存取顺序不一致（底层数组+链表+红黑树）
- 去重：equals()返回true 且 hashCode()相同认为重复，HashMap.put返回旧值非null判断重复
- 重写equals必须重写hashCode：否则两个equals为true的对象可能hashCode不同，存入不同桶，Set无法去重
5.2 LinkedHashSet
- 继承HashSet，构造调用LinkedHashMap。保持插入顺序
5.3 TreeSet
- 基于TreeMap（红黑树），元素自动排序。add/remove/contains均为O(log n)
六、并发集合
6.1 ConcurrentHashMap
JDK7：分段锁（Segment）
- Segment extends ReentrantLock，默认16段，并发度16
- 每个Segment内部是一个小HashEntry数组（类似小HashMap）
- put：先hash找到Segment → tryLock() → 失败自旋等待 → 获取锁后插入
- get：不加锁（HashEntry.value是volatile，保证可见性）
JDK8：CAS + synchronized
彻底抛弃分段锁，锁粒度细化到每个桶的头节点。并发度更高，代码更简洁。
- put：key/value不能为null → spread计算hash → 桶空：CAS自旋newNode放入(finishing CAS: casTabAt) → 桶非空且hash==MOVED(-1)：协助扩容 → 桶非空：synchronized锁头节点(f = tabAt(tab, i)) → 遍历链表/树 → 更新或插入 → 节点计数(addCount)触发扩容检查
- get：完全无锁，利用volatile读（Node.val和Node.next均为volatile）
- size：不维护全局size，通过baseCount + CounterCell分散计数，避免竞争。sumCount()汇总
- 扩容：多线程协助扩容（helpTransfer）。每个线程领取一个步长(stride)迁移，通过transferIndex(CAS)分配。扩容中桶头hash=MOVED做标记
JDK7 vs JDK8 ConcurrentHashMap
|
对比项 |
JDK7 |
JDK8 |
|---|---|---|
|
锁粒度 |
Segment(16段) |
桶头节点 |
|
锁类型 |
ReentrantLock |
CAS + synchronized |
|
get |
无锁volatile读 |
无锁volatile读 |
|
size计算 |
Segment三次数+锁 |
baseCount + CounterCell |
|
数据结构 |
数组+链表 |
数组+链表+红黑树 |
|
并发度 |
固定16(仅Segment) |
动态(每个桶) |
|
扩容 |
Segment内部独立扩容 |
全局协同扩容（多线程协助） |
6.2 CopyOnWriteArrayList
写时复制：写操作(add/set/remove)加ReentrantLock + Arrays.copyOf创建新数组 + 将引用指向新数组。读操作无锁直接读，读写分离。
- 适用场景：读多写极少（监听器列表、配置信息）。写操作开销大（全量复制），不适合频繁写入
- 数据一致性：读的是写之前快照，弱一致性（最终一致）
- 迭代器：COWIterator，遍历快照数组，不支持remove/set/add
6.3 ConcurrentLinkedQueue
- 底层：无界非阻塞队列，CAS + 自旋实现offer/poll，无锁高效
- Michael-Scott算法：单向链表 + head/tail指针（tail是延时更新）
七、Queue 和 BlockingQueue
|
队列 |
特点 |
使用场景 |
|---|---|---|
|
ArrayBlockingQueue |
有界，数组+一把ReentrantLock+两个Condition |
固定容量生产者消费者 |
|
LinkedBlockingQueue |
有界(默认Integer.MAX_VALUE)，链表+两把锁(putLock/takeLock) |
Executors.newFixedThreadPool默认队列 |
|
SynchronousQueue |
无容量，生产与消费必须同时匹配 |
Executors.newCachedThreadPool默认队列 |
|
PriorityBlockingQueue |
无界，二叉堆(最小堆)，元素须Comparable |
优先级任务调度 |
|
DelayQueue |
延迟队列，元素实现Delayed接口，到期才能取出 |
定时任务(如订单超时取消) |
|
LinkedTransferQueue |
无锁(?), transfer()等待消费者直接交付 |
高性能传输场景 |
八、Collections 工具类
|
方法 |
说明 |
|---|---|
|
synchronizedXxx() |
包装为线程安全集合（全方法synchronized，性能差） |
|
unmodifiableXxx() |
不可修改视图(只读，修改抛UnsupportedOperationException) |
|
sort() / binarySearch() |
排序 / 二分查找 |
|
reverse() / shuffle() |
反转 / 随机打乱 |
|
emptyList() / emptyMap() |
返回空不可变集合（避免null，节省内存） |
|
singletonList()/singletonMap() |
单元素不可变集合 |
|
frequency() / disjoint() |
出现频率 / 是否无交集 |
面试核心梳理：
- 必问：HashMap put流程、扩容机制、为何容量2的幂、JDK7/8差异、头插/尾插并发问题
- 高频：ConcurrentHashMap JDK7/8实现差异、ArrayList扩容、HashSet去重原理
- 进阶：CopyOnWriteArrayList写时复制、LinkedHashMap实现LRU、TreeMap红黑树
- 实用：BlockingQueue选型、Collections工具方法、fail-fast机制