技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

Java-集合框架大师课集合框架源码解剖室五

 收录于 Java
   约 2024 字   预计阅读 5 分钟 
https://bing.ee123.net/img/rand?artid=146190962

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);
}

📌 灵魂拷问表 ：

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

1.2 扩容流程可视化

https://i-blog.csdnimg.cn/direct/14499dc8c9e64684adbfdb24d3ac9aba.png

第二章 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;    // 上个节点 👈
}

📊 增删操作性能真相 ：

操作ArrayListLinkedList真相大白 😏
头部插入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 📌 锁机制对比表 ：

版本数据结构锁粒度吞吐量提升
JDK7Segment 数组16个独立分区 🔒4~6倍
JDK8Node+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;
}

🎯 关键操作流程图 ：

https://i-blog.csdnimg.cn/direct/56b570b2c2e94df7ac79a6e2091fd6dd.png

🔥 性能调优黄金法则

// 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;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = 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;
    }
  
    @Override
    protected 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);
    else
        siftUpComparable(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 堆结构可视化

https://i-blog.csdnimg.cn/direct/395187d1a01e4c41bd567143f7465250.png

🛠️ 手撕源码挑战赛

挑战一：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)之间找到平衡点 ⚖️
更新于 2025-03-11
 开发语言, Java
返回 | 主页