Java集合框架深度剖析：从设计理念到源码实现
2025年2月27日大约 27 分钟
Java集合框架深度剖析：从设计理念到源码实现
一、集合框架概述
1.1 整体架构设计
Java集合框架的设计充分体现了面向对象的设计思想和软件工程的最佳实践。整体架构如下：
架构设计要点总结：
- 接口与实现分离，提高了扩展性
- 继承体系清晰，易于理解和使用
- 提供了丰富的实现类，满足不同场景需求
1.2 核心接口分析
public interface Collection<E> extends Iterable<E> {
// 核心方法
boolean add(E e); // 添加元素，成功返回true
boolean remove(Object o); // 移除元素，成功返回true
boolean contains(Object o); // 检查是否包含元素
int size(); // 返回集合大小
boolean isEmpty(); // 检查集合是否为空
void clear(); // 清空集合
// 批量操作
boolean addAll(Collection<? extends E> c); // 添加所有元素
boolean removeAll(Collection<?> c); // 移除所有指定元素
boolean retainAll(Collection<?> c); // 仅保留指定元素
// 转换操作
Object[] toArray(); // 转换为数组
<T> T[] toArray(T[] a); // 转换为指定类型数组
}接口设计特点：
- 方法命名直观，符合直觉
- 返回值类型合理，便于判断操作结果
- 支持泛型，提供类型安全
二、ArrayList深度解析
2.1 整体设计
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 实际存储元素的数组
// transient修饰防止序列化，因为可能包含未使用的空间
transient Object[] elementData;
// 实际元素数量
private int size;
// 修改次数，用于快速失败机制
protected transient int modCount = 0;
}核心设计要点总结：
- 使用数组实现，随机访问性能好
- 支持动态扩容，内存利用灵活
- 实现多个接口，功能丰富
2.2 关键方法源码分析
2.2.1 动态扩容机制
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. 1.5倍的扩容比例是经过优化的结果：
* - 小于1.5会导致频繁扩容
* - 大于1.5会导致空间浪费
* - 1.5是一个比较好的平衡点
*
* 2. 使用位运算 oldCapacity >> 1 而不是 oldCapacity * 0.5：
* - 位运算性能更好
* - 避免浮点运算
*
* 3. 数组复制使用Arrays.copyOf：
* - 底层使用System.arraycopy，性能好
* - 实现简单，代码清晰
*/2.2.2 添加元素分析
public boolean add(E e) {
// 确保容量足够
ensureCapacityInternal(size + 1);
// 在数组末尾添加元素
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// 检查索引是否合法
rangeCheckForAdd(index);
// 确保容量足够
ensureCapacityInternal(size + 1);
// 将index及其之后的元素后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 在index位置插入新元素
elementData[index] = element;
size++;
}
/**
* add操作的性能分析：
* 1. add(E)：
* - 平均时间复杂度O(1)
* - 最坏情况O(n)，需要扩容
*
* 2. add(int, E)：
* - 时间复杂度O(n)
* - 主要开销在数组元素移动
*/2.3 性能特征总结
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| add(E) | O(1) | 平均情况，扩容时O(n) |
| add(int, E) | O(n) | 需要移动元素 |
| remove(Object) | O(n) | 需要遍历查找 |
| remove(int) | O(n) | 需要移动元素 |
| get(int) | O(1) | 直接数组访问 |
| contains(Object) | O(n) | 需要遍历查找 |
使用建议：
- 已知元素数量时，指定初始容量
- 查询操作频繁的场景优先使用
- 避免频繁在中间位置插入/删除
三、HashMap深度剖析
3.1 数据结构设计
HashMap在Java 8中采用了复合数据结构：
关键设计点说明：
- 数组提供了O(1)的访问性能
- 链表解决了哈希冲突
- 红黑树优化了长链表的查询性能
3.2 源码解析
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/* 默认初始容量 - 必须是2的幂 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
/* 最大容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/* 默认负载因子 */
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;
/* 存储数据的数组 */
transient Node<K,V>[] table;
/* 实际元素数量 */
transient int size;
/* 扩容阈值 */
int threshold;
/* 负载因子 */
final float loadFactor;
}
/**
* 重要参数说明：
* 1. 初始容量16：
* - 2的幂，便于计算索引
* - 较小的初始值，避免空间浪费
*
* 2. 负载因子0.75：
* - 空间和时间的折中值
* - 大于0.75容易产生碰撞
* - 小于0.75浪费空间
*
* 3. 树化阈值8：
* - 根据泊松分布统计得出
* - 链表长度达到8的概率很小
*/3.3 HashMap核心方法分析
3.3.1 put方法详解
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果table为空或长度为0，进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算索引位置，如果为空直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果key已存在，准备更新值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是红黑树节点，使用树的put方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 链表情况
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 检查是否需要树化
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;
}
}
// 如果key已存在，更新值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 检查是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* put方法的关键设计点：
* 1. 哈希计算：
* - 使用(n-1)&hash计算索引
* - 要求数组长度必须是2的幂
*
* 2. 冲突处理：
* - 先判断key是否相同
* - 再判断是否是树节点
* - 最后遍历链表
*
* 3. 树化条件：
* - 链表长度达到8
* - 数组长度达到64
*/3.3.2 resize方法详解
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 计算新容量和新阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 重新分配节点
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历旧表，重新分配节点
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
/**
* resize方法的精妙之处：
* 1. 扩容策略：
* - 每次扩容为原来的2倍
* - 保持2的幂特性
*
* 2. 节点重分配：
* - 利用hash&oldCap判断节点新位置
* - 新位置要么在原位置，要么在原位置+oldCap
*
* 3. 优化：
* - 使用两个链表分别存储不同位置的节点
* - 避免了rehash
*/3.4 红黑树转换机制详解
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 需要在删除时取消链接
boolean red; // 节点颜色
// 树化方法
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 设置根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 从根节点开始查找插入位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
// 确保root是第一个节点
moveRootToFront(tab, root);
}
}
/**
* 树化过程的关键点：
* 1. 转换条件：
* - 链表长度超过TREEIFY_THRESHOLD (8)
* - 数组长度超过MIN_TREEIFY_CAPACITY (64)
*
* 2. 树的平衡：
* - 使用红黑树自平衡特性
* - 插入后进行颜色调整和旋转
*
* 3. 性能考虑：
* - 复杂度从O(n)降为O(logn)
* - 但是维护成本更高
*/四、ConcurrentHashMap深度解析
4.1 并发设计核心思想
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
/* 最大数组容量 */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/* 默认初始容量 */
private static final int DEFAULT_CAPACITY = 16;
/* 并发级别，实际不使用，保留为了兼容性 */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/* 负载因子 */
private static final float LOAD_FACTOR = 0.75f;
/* Node数组 */
transient volatile Node<K,V>[] table;
/* 扩容过程中的新数组 */
private transient volatile Node<K,V>[] nextTable;
/* 扩容标志位 */
private transient volatile int sizeCtl;
/**
* 并发控制主要思路：
* 1. CAS + synchronized实现并发控制
* 2. 细粒度锁定，只锁定当前桶
* 3. 支持多线程扩容
*/
}4.2 并发操作实现
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
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) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// 正在扩容，帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 锁定当前桶
synchronized (f) {
if (tabAt(tab, i) == f) {
// 链表操作
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 红黑树操作
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 检查是否需要树化
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
/**
* 并发控制的精髓：
* 1. 分段锁设计：
* - 只锁定当前操作的桶
* - 降低锁竞争
*
* 2. CAS操作：
* - 无锁操作提高并发性
* - 确保原子性
*
* 3. 帮助扩容：
* - 多线程协同扩容
* - 提高扩容效率
*/4.3 多线程扩容机制
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 计算每个线程处理的桶区间
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
// 初始化新表
if (nextTab == null) {
try {
// 创建新表，大小是原来的2倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) {
// 处理内存不足情况
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
// 转发节点，标识该桶已经被处理
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false;
// 多线程协同迁移数据
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 确定当前线程负责的桶区间
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt(this, TRANSFERINDEX,
nextIndex, nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 处理当前桶
if (i < 0 || i >= n || i + n >= nextn) {
// 完成扩容
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 继续处理其他桶
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true;
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
// 链表节点的重哈希分配
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 放入新表
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
// 红黑树节点的重哈希分配
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 根据节点数决定是否需要取消树化
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
/**
* 多线程扩容的精髓：
* 1. 任务分配：
* - 使用stride确定每个线程处理的桶数量
* - 通过CAS分配任务区间
*
* 2. 数据迁移：
* - 使用ForwardingNode标记已处理的桶
* - 分别处理链表和红黑树节点
*
* 3. 并发控制：
* - 桶级别的锁定
* - CAS确保原子性
* - 多线程协同工作
*/五、LinkedHashMap的LRU实现原理
5.1 数据结构
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V> {
// 双向链表的头节点
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;
// 是否按访问顺序排序
final boolean accessOrder;
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // 双向链表指针
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
}
/**
* 关键设计特点：
* 1. 继承HashMap：
* - 复用HashMap的存储结构
* - 保持HashMap的性能特性
*
* 2. 额外的双向链表：
* - 维护节点的插入顺序
* - 支持按访问顺序排序
*
* 3. accessOrder字段：
* - true：访问顺序（LRU）
* - false：插入顺序
*/5.2 LRU缓存实现
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// 初始容量、负载因子、访问顺序
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当大小超过容量时删除最老的元素
return size() > capacity;
}
/**
* 使用示例：
*/
public static void main(String[] args) {
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("A", 1); // 缓存: [A=1]
cache.put("B", 2); // 缓存: [A=1, B=2]
cache.put("C", 3); // 缓存: [A=1, B=2, C=3]
cache.get("A"); // 缓存: [B=2, C=3, A=1]
cache.put("D", 4); // 缓存: [C=3, A=1, D=4]，B被删除
}
}
/**
* LRU实现的关键点：
* 1. 继承LinkedHashMap：
* - 利用访问顺序特性
* - 自动维护双向链表
*
* 2. 控制缓存大小：
* - 重写removeEldestEntry方法
* - 在put操作时自动触发
*
* 3. 性能特性：
* - get/put操作 O(1)
* - 自动维护顺序
*/六、TreeSet和TreeMap的红黑树实现
6.1 TreeMap的核心实现
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
// 比较器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 元素数量
private transient int size = 0;
// 结构修改计数
private transient int modCount = 0;
// 节点定义
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left; // 左子节点
Entry<K,V> right; // 右子节点
Entry<K,V> parent; // 父节点
boolean color = BLACK; // 节点颜色
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
/**
* TreeMap的设计特点：
* 1. 有序性：
* - 基于红黑树实现
* - 可以指定比较器
*
* 2. 性能特性：
* - 查找/插入/删除都是O(log n)
* - 空间占用相对较大
*
* 3. 应用场景：
* - 需要有序性的场合
* - 需要范围查询的场合
*/6.2 红黑树平衡操作
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; // 新插入节点为红色
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
// 情况1：叔叔节点为红色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
// 情况2：叔叔节点为黑色，当前节点为右子节点
x = parentOf(x);
rotateLeft(x);
}
// 情况3：叔叔节点为黑色，当前节点为左子节点
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
// 对称情况
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK; // 根节点始终为黑色
}
/**
* 红黑树平衡的关键点：
* 1. 插入规则：
* - 新节点总是红色
* - 通过重新着色和旋转维持平衡
*
* 2. 平衡条件：
* - 根节点是黑色
* - 红节点的子节点必须是黑色
* - 每条路径包含相同数量的黑节点
*
* 3. 旋转操作：
* - 左旋：用于调整右边过重的情况
* - 右旋：用于调整左边过重的情况
*/6.3 TreeSet的委托实现
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
// 内部使用TreeMap存储数据
private transient NavigableMap<E,Object> m;
// 虚拟值，用于Map的value
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E,Object>());
}
// 添加元素
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}
// 查找元素
public boolean contains(Object o) {
return m.containsKey(o);
}
}
/**
* TreeSet的设计特点：
* 1. 委托模式：
* - 所有操作都委托给TreeMap
* - 复用TreeMap的实现
*
* 2. 简化接口：
* - 只暴露Set相关的操作
* - 隐藏Map的复杂性
*
* 3. 性能特性：
* - 与TreeMap相同
* - 额外的空间开销很小
*/七、PriorityQueue的堆实现
7.1 基本结构
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
// 存储元素的数组
transient Object[] queue;
// 元素数量
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;
// 结构修改计数
transient int modCount = 0;
}
/**
* 设计特点：
* 1. 堆结构：
* - 使用数组实现的二叉堆
* - 可以指定比较器
*
* 2. 性能特性：
* - 插入：O(log n)
* - 删除最小元素：O(log n)
* - 查看最小元素：O(1)
*
* 3. 应用场景：
* - 需要维护最大/最小值的场合
* - 优先级调度
*/7.2 核心操作实现
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; // 计算父节点位置
Object e = queue[parent];
if (key.compareTo((E) e) >= 0) // 比较与父节点的大小
break;
queue[k] = e; // 父节点下移
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1; // 左子节点
Object c = queue[child];
int right = child + 1;
// 选择较小的子节点
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c; // 子节点上移
k = child;
}
queue[k] = key;
}
/**
* 堆操作的关键点：
* 1. 上浮操作(siftUp)：
* - 新插入节点时使用
* - 与父节点比较并交换
*
* 2. 下沉操作(siftDown)：
* - 删除节点时使用
* - 与较小的子节点比较并交换
*
* 3. 实现细节：
* - 使用位运算优化父子节点计算
* - 支持比较器和自然顺序
*/八、ArrayDeque的循环数组实现
8.1 基本结构及设计思想
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
// 存储元素的数组
transient Object[] elements;
// 头部元素的索引
transient int head;
// 尾部元素的下一个位置的索引
transient int tail;
// 最小初始容量，必须是2的幂
private static final int MIN_INITIAL_CAPACITY = 8;
}
/**
* 设计特点分析：
* 1. 循环数组结构：
* - 头尾指针循环移动
* - 数组容量始终是2的幂
* - 通过位运算优化索引计算
*
* 2. 性能特点：
* - 头尾操作均为O(1)
* - 随机访问O(1)
* - 内存利用率高
*
* 3. 应用场景：
* - 双端队列场景
* - 需要栈或队列功能
* - 需要高性能的头尾操作
*/8.2 关键方法实现
// 添加元素到队列尾部
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
// 使用位运算计算下一个位置，等价于 (tail + 1) % elements.length
if ((tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity(); // 队列已满，扩容
}
// 添加元素到队列头部
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
// 计算前一个位置
head = (head - 1) & (elements.length - 1);
elements[head] = e;
if (head == tail)
doubleCapacity(); // 队列已满，扩容
}
// 扩容操作
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边的元素个数
int newCapacity = n << 1; // 容量翻倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
// 复制head右边的元素到新数组开头
System.arraycopy(elements, p, a, 0, r);
// 复制head左边的元素到新数组后面
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
/**
* 实现要点分析：
* 1. 索引计算优化：
* - 使用位运算代替取模运算
* - 要求数组长度必须是2的幂
*
* 2. 扩容策略：
* - 容量翻倍
* - 重新排列元素，使其连续
*
* 3. 空间管理：
* - head == tail 表示队列为空或满
* - 通过额外的size字段区分空和满
*/8.3 迭代器实现
private class DeqIterator implements Iterator<E> {
private int cursor = head;
private int fence = tail;
private int lastRet = -1;
private int expectedModCount = modCount;
public boolean hasNext() {
return cursor != fence;
}
@SuppressWarnings("unchecked")
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (cursor == fence)
throw new NoSuchElementException();
E result = (E) elements[cursor];
lastRet = cursor;
cursor = (cursor + 1) & (elements.length - 1);
return result;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (lastRet >= head) {
// 删除lastRet位置的元素
System.arraycopy(elements, lastRet + 1,
elements, lastRet,
tail - lastRet - 1);
tail--;
} else {
// 处理循环情况
System.arraycopy(elements, head,
elements, head + 1,
lastRet - head + 1);
head++;
}
lastRet = -1;
expectedModCount = modCount;
}
}
/**
* 迭代器设计要点：
* 1. 快速失败机制：
* - 通过modCount检测并发修改
* - 及时抛出ConcurrentModificationException
*
* 2. 遍历策略：
* - 按照逻辑顺序遍历元素
* - 处理数组循环的特殊情况
*
* 3. 删除操作：
* - 支持迭代过程中的元素删除
* - 维护数组的连续性
*/九、WeakHashMap的弱引用实现
9.1 基本原理
public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V> {
// 实际存储Entry的数组
private Entry<K,V>[] table;
// 引用队列，用于存放已被GC的Entry
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
// Entry继承自WeakReference
private static class Entry<K,V> extends WeakReference<Object>
implements Map.Entry<K,V> {
V value;
final int hash;
Entry<K,V> next;
Entry(Object key, V value, ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
}
}
/**
* 核心设计特点：
* 1. 弱引用特性：
* - key使用WeakReference包装
* - 当key不再被强引用时，Entry会被GC
*
* 2. 引用队列：
* - 用于管理已被GC的Entry
* - 在操作时清理失效的Entry
*
* 3. 应用场景：
* - 缓存实现
* - 避免内存泄漏
*/9.2 关键操作实现
private void expungeStaleEntries() {
Entry<K,V> e;
while ((e = (Entry<K,V>) queue.poll()) != null) {
int h = e.hash;
int i = indexFor(h, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
if (p == e) {
if (prev == p)
table[i] = next;
else
prev.next = next;
e.value = null; // 帮助GC
size--;
break;
}
prev = p;
p = next;
}
}
}
public V get(Object key) {
Object k = maskNull(key);
int h = hash(k);
Entry<K,V>[] tab = getTable();
int index = indexFor(h, tab.length);
Entry<K,V> e = tab[index];
while (e != null) {
if (e.hash == h && eq(k, e.get()))
return e.value;
e = e.next;
}
return null;
}
/**
* 实现要点：
* 1. 垃圾回收处理：
* - 定期清理已失效的Entry
* - 在主要操作前执行清理
*
* 2. 性能考虑：
* - 清理操作可能影响性能
* - 需要平衡清理频率
*
* 3. 并发安全：
* - 非线程安全
* - 需要外部同步
*/十、Collections同步包装器的实现机制
10.1 同步包装器基本原理
public class Collections {
// 同步List包装器
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
static class SynchronizedCollection<E> implements Collection<E> {
private final Collection<E> c; // 被包装的集合
private final Object mutex; // 同步锁对象
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
public boolean add(E e) {
synchronized (mutex) { return c.add(e); }
}
public boolean remove(Object o) {
synchronized (mutex) { return c.remove(o); }
}
// 其他方法类似，都使用synchronized保护
}
}
/**
* 同步包装器的设计要点：
* 1. 装饰器模式：
* - 不改变原有集合的代码
* - 动态添加同步功能
*
* 2. 同步策略：
* - 所有方法都使用同一个锁
* - 保证操作的原子性
*
* 3. 使用限制：
* - 迭代器不是线程安全的
* - 需要外部同步迭代操作
*/10.2 不可修改集合实现
public static <T> List<T> unmodifiableList(List<? extends T> list) {
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList<>(list) :
new UnmodifiableList<>(list));
}
static class UnmodifiableCollection<E> implements Collection<E> {
private final Collection<? extends E> c;
UnmodifiableCollection(Collection<? extends E> c) {
this.c = Objects.requireNonNull(c);
}
public boolean add(E e) {
throw new UnsupportedOperationException();
}
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}
public boolean contains(Object o) {
return c.contains(o);
}
// 只读操作直接委托给原集合
}
/**
* 不可修改集合的设计特点：
* 1. 安全保护：
* - 禁止所有修改操作
* - 运行时检查而非编译时
*
* 2. 实现策略：
* - 修改操作抛出异常
* - 读取操作委托给原集合
*
* 3. 应用场景：
* - 创建只读视图
* - 防止集合被修改
*/十一、集合工具类分析
11.1 Collections工具类
public class Collections {
// 二分查找实现
public static <T> int binarySearch(List<? extends T> list, T key,
Comparator<? super T> c) {
if (c == null)
return binarySearch((List<? extends Comparable<? super T>>) list, key);
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = list.get(mid);
int cmp = c.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid;
}
return -(low + 1);
}
// 混排算法
@SuppressWarnings("unchecked")
public static void shuffle(List<?> list, Random rnd) {
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i = size; i > 1; i--) {
swap(list, i - 1, rnd.nextInt(i));
}
} else {
Object[] arr = list.toArray();
for (int i = size; i > 1; i--) {
swap(arr, i - 1, rnd.nextInt(i));
}
ListIterator it = list.listIterator();
for (Object e : arr) {
it.next();
it.set(e);
}
}
}
}
/**
* 工具类设计要点：
* 1. 算法实现：
* - 通用性好
* - 性能优化
*
* 2. 接口设计：
* - 静态方法
* - 类型安全
*
* 3. 性能考虑：
* - 区分RandomAccess
* - 针对不同情况优化
*/11.2 Arrays工具类
public class Arrays {
// 并行排序实现
public static void parallelSort(int[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
// ArrayList转换
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable {
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
public E get(int index) {
return a[index];
}
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
public int size() {
return a.length;
}
}
}
/**
* Arrays工具类特点：
* 1. 并行算法支持：
* - 利用ForkJoin框架
* - 自动选择串行或并行
*
* 2. 视图实现：
* - 数组与List转换
* - 固定大小的List视图
*
* 3. 性能优化：
* - 针对不同数据规模优化
* - 利用现代CPU特性
*/十二、最佳实践与性能优化
12.1 集合选择指南
12.2 性能优化技巧
public class CollectionBestPractices {
// 1. 合理指定初始容量
public void capacityExample() {
// 好的实践
List<Integer> list = new ArrayList<>(10000);
Map<String, Object> map = new HashMap<>(16, 0.75f);
// 避免频繁扩容
for (int i = 0; i < 10000; i++) {
list.add(i);
}
}
// 2. 批量操作优化
public void batchOperationExample() {
List<Integer> list = new ArrayList<>();
// 不好的实践
for (int i = 0; i < 10000; i++) {
list.add(0, i); // 频繁移动元素
}
// 好的实践
List<Integer> temp = new ArrayList<>(10000);
for (int i = 0; i < 10000; i++) {
temp.add(i);
}
Collections.reverse(temp);
list.addAll(temp);
}
// 3. 遍历优化
public void iterationExample(List<String> list) {
// 不好的实践
for (int i = 0; i < list.size(); i++) {
// size()方法被重复调用
process(list.get(i));
}
// 好的实践
int size = list.size();
for (int i = 0; i < size; i++) {
process(list.get(i));
}
// 更好的实践（如果不需要索引）
for (String item : list) {
process(item);
}
}
private void process(String item) {
// 处理逻辑
}
}
/**
* 性能优化要点：
* 1. 容量管理：
* - 预估容量
* - 避免扩容
*
* 2. 算法选择：
* - 选择合适的数据结构
* - 使用批量操作
*
* 3. 遍历方式：
* - 缓存size
* - 使用增强for循环
*/12.3 常见陷阱和解决方案
public class CollectionPitfalls {
// 1. 并发修改问题
public void concurrentModificationExample() {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
// 错误方式：可能抛出ConcurrentModificationException
for (String item : list) {
if ("B".equals(item)) {
list.remove(item);
}
}
// 正确方式：使用迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if ("B".equals(it.next())) {
it.remove();
}
}
}
// 2. 内存泄漏预防
public class Cache {
private Map<String, Object> map = new WeakHashMap<>();
public void put(String key, Object value) {
map.put(key, value);
}
public void clear() {
map.clear(); // 及时清理不用的引用
}
}
// 3. 线程安全处理
public class ThreadSafeCollection {
private final List<String> list =
Collections.synchronizedList(new ArrayList<>());
public void addItem(String item) {
synchronized (list) { // 同步整个复合操作
if (!list.contains(item)) {
list.add(item);
}
}
}
public void iterateItems() {
synchronized (list) { // 同步迭代操作
for (String item : list) {
process(item);
}
}
}
}
}
/**
* 关键注意点：
* 1. 并发修改：
* - 使用正确的迭代方式
* - 注意并发场景
*
* 2. 内存管理：
* - 及时清理引用
* - 使用合适的集合类型
*
* 3. 线程安全：
* - 选择合适的同步策略
* - 注意锁的粒度
*/十三、写在最后
核心设计理念
说实话，用了这么多年的Java集合，最让我印象深刻的是它的几个核心设计理念：
首先是接口设计。Java集合框架把接口定义和具体实现分得很干净，这一点在实际开发中帮了大忙。比如我们经常用List接口定义，但在不同场景下可以随意切换ArrayList或LinkedList的实现，代码完全不用改。
性能取舍
每种集合的实现都有自己的特点：
- ArrayList用空间换时间，查询快但插入慢
- LinkedList用时间换空间，插入快但查询慢
- HashMap在时间和空间上做了很好的平衡，但要消耗额外内存来保存hash值
重要变化
这些年Java集合的一些变化也很有意思：
- JDK 8引入Stream API，大大简化了集合操作
- 并发集合越来越重要，尤其是ConcurrentHashMap的优化
- 红黑树在HashMap中的应用，解决了hash冲突的性能问题
基于这些年的开发经验，我总结了几点实用建议：
选对集合很重要
- 数据量大的时候，ArrayList比LinkedList省心
- 需要频繁增删，LinkedList更合适
- 并发场景就直接用ConcurrentHashMap，别想着自己加锁
关于性能
- 能预估容量就预估一下，避免扩容
- HashMap的loadFactor不用改，0.75是经过精心计算的
- 数据量特别大时，留意一下内存
代码习惯
- 接口编程是好习惯，但也不用什么都用接口
- 异常处理要当回事，特别是ConcurrentModificationException
- 文档注释要写，主要是给自己看的