Java 集合框架大师课：集合框架源码解剖室（五）

🔥Java 集合框架大师课：集合框架源码解剖室（五）

💣 警告：本章包含大量 裸码级硬核分析，建议搭配咖啡因饮料阅读！☕️

---

第一章 ArrayList 的扩容玄学

1.1 动态扩容核心代码大卸八块

// 祖师爷の扩容魔法 ✨
private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;// 1.5倍增长公式（暗藏数学之美）int newCapacity = oldCapacity + (oldCapacity >> 1); return elementData = Arrays.copyOf(elementData, newCapacity);
}

📌 灵魂拷问表：

现象	数学原理	性能影响
初始容量10	2的倍数+2？🤔	小数据集省内存
1.5倍增长	斐波那契数列逼近 🌊	平衡内存与扩容次数
Arrays.copyOf	内存连续分配 📏	超大数组扩容卡顿风险

1.2 扩容流程可视化

---

第二章 HashMap 的哈希战争

2.1 扰动函数の黑科技

static final int hash(Object key) {int h;// 让高位参与哈希运算，减少碰撞 💥return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

🎯 哈希碰撞处理方案对比：

方案	数据结构	时间复杂度	JDK版本
链表法	单向链表 🚂	O(n)	<8
红黑树	平衡二叉树 🌳	O(logn)	≥8
开放寻址	线性探测 🔍	O(1)~O(n)	其他实现

2.2 树化阈值背后的博弈

// 链表转红黑树的临界点
static final int TREEIFY_THRESHOLD = 8;// 为什么是8？统计学の魔法 🎲
/*
* 理想哈希下链表长度出现8的概率：0.00000006
* 此时树化的收益超过维护成本
*/

---

第三章 LinkedList 的双向暗恋

3.1 节点结构解剖图

private static class Node<E> {E item;          // 当前元素 🎁Node<E> next;    // 下个节点 👉Node<E> prev;    // 上个节点 👈
}

📊 增删操作性能真相：

操作	ArrayList	LinkedList	真相大白 😏
头部插入	O(n)	O(1)	LinkedList胜
随机删除	O(n)	O(1)	但需要先遍历找节点！😱
尾部追加	O(1)	O(1)	平手 👯

3.2 迭代器陷阱演示

LinkedList<Integer> list = new LinkedList<>();
list.addAll(Arrays.asList(1,3,5,7,9));// 错误示范：用for循环随机访问
for(int i=0; i<list.size(); i++){list.get(i); // O(n^2) 警告！💣
}// 正确姿势：迭代器访问
Iterator<Integer> it = list.iterator();
while(it.hasNext()){it.next(); // O(n) 丝滑访问 🛷
}

---

第四章 ConcurrentHashMap 的线程安全秘籍

4.1 📌 锁机制对比表：

版本	数据结构	锁粒度	吞吐量提升
JDK7	Segment 数组	16个独立分区 🔒	4~6倍
JDK8	Node+CAS	单个链表头 🔓	10倍+
JDK19	协程+无锁	无锁访问 🚀	实验阶段

4.2 size() 方法の统计学魔术

// 高并发下的size计算策略
public int size() {long n = sumCount();return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}// 分片计数减少竞争 🎯
final long sumCount() {CounterCell[] as = counterCells; long sum = baseCount;if (as != null) {for (CounterCell a : as)if (a != null)sum += a.value;}return sum;
}

4.3 putVal() 方法源码拆解

final V putVal(K key, V value, boolean onlyIfAbsent) {// 哈希扰动加强版 🌪️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(); // 延迟初始化else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null, new Node<>(hash, key, value)))break; // CAS 无锁插入成功！}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f); // 协助扩容else {// 真正的锁竞争区 💥synchronized (f) {if (tabAt(tab, i) == f) {// 链表/红黑树插入逻辑...}}}}addCount(1L, binCount);return null;
}

🎯 关键操作流程图：

---

🔥 性能调优黄金法则

// ArrayList 最佳实践
List<String> list = new ArrayList<>(100_0000); // 预分配容量 🚀// HashMap 防坑指南
Map<String,Object> map = new HashMap<>(32, 0.75f); // 控制负载因子 ⚖️// LinkedList 使用禁区
if(需要随机访问) {throw new IllegalArgumentException("别用我！"); 💣
}

---

第五章 LinkedHashMap 的时空穿梭术

5.1 双向链表结构大曝光

// 继承自 HashMap.Node 的超级节点 🦸
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);}
}// 维护访问顺序的核心代码 🔗
void afterNodeAccess(Node<K,V> e) {Entry<K,V> last;if (accessOrder && (last = tail) != e) {// 把最近访问的节点移动到链表尾部Entry<K,V> p = (Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
}

5.2 LRU 缓存实现原理

// 实现简易 LRU 缓存 🗂️
public class LRUCache<K,V> extends LinkedHashMap<K,V> {private final int maxCapacity;public LRUCache(int maxCapacity) {super(maxCapacity, 0.75f, true);this.maxCapacity = maxCapacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return size() > maxCapacity; // 自动淘汰最旧元素 🗑️}
}// 使用示例：
LRUCache<String, User> cache = new LRUCache<>(1000);
cache.put("user_9527", user); // 插入新数据
cache.get("user_1234");       // 访问数据会提升新鲜度

---

第六章 PriorityQueue 的堆排序魔法

6.1 最小堆实现原理

// 优先队列的骨架数组结构 🦴
transient Object[] queue; // 元素插入时的上浮操作 🌊
private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);
}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;
}

📊 堆操作复杂度表：

操作	时间复杂度	原理说明
插入元素	O(logn)	上浮操作调整堆结构 🌊
取出队首	O(logn)	下沉操作重建堆结构 ⚓
查看队首	O(1)	直接返回堆顶元素 🏔️
批量建堆	O(n)	Floyd 算法优化 🚀

6.2 堆结构可视化

---

🛠️ 手撕源码挑战赛

挑战一：ConcurrentHashMap 扩容触发器

// 找出触发扩容的隐藏条件
private final void addCount(long x, int check) {// 当 counterCells 不为空时...if (check >= 0) {Node<K,V>[] tab, nt; int n, sc;while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {// 神秘扩容信号 🚨int rs = resizeStamp(n);if (sc < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt);}// 尝试发起扩容的线程会走到这里 💪else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null);s = sumCount();}}
}

挑战二：PriorityQueue 堆排序缺陷

// 危险操作：直接修改队列元素
PriorityQueue<Student> queue = new PriorityQueue<>();
queue.add(new Student("Alice", 90));
queue.add(new Student("Bob", 80));// 作死修改分数导致堆结构破坏 💣
queue.peek().score = 100; 
System.out.println(queue.poll()); // 输出结果可能不符合预期！// 正确做法：删除后重新插入
Student s = queue.poll();
s.score = 100;
queue.offer(s);

---

🧘♂️ 下期预告：《集合框架的暗黑料理——弱引用与幽灵队列》👻

// 彩蛋代码：HashMap 的隐藏迭代器
final class KeyIterator extends HashIterator implements Iterator<K>, Spliterator<K> {public final K next() { return nextNode().key; }
}
// 快速失败（fail-fast）机制的实现秘密 🔍

🌟 终极领悟 ：读源码就像破案，每个设计都是权衡的艺术！下次面试被问HashMap原理时，请优雅地甩出红黑树阈值计算公式 🌈

// 彩蛋：HashMap 树化阈值计算公式
static final int TREEIFY_THRESHOLD = 8;
// 为什么是8？因为 log8 = 3, 在O(logn)和O(n)之间找到平衡点 ⚖️