Java 集合框架源码解析与并发容器实战

// 扩容核心逻辑（JDK17 简化）
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 倍
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

// 已知容量时务必预分配，避免反复扩容拷贝
List<String> list = new ArrayList<>(10_000);

// 何时用 LinkedList？
// 1. 大量头尾操作（它同时是 Deque）
// 2. 需要高效从两端增删的队列场景
// 实际工程：ArrayList 占据 95% 场景，链表应用面其实很窄

HashMap 底层：
  数组 table[]（桶）
  每个桶可以是：链表（冲突少时）→ 红黑树（冲突≥8 时）
  默认容量 16、负载因子 0.75
  实际使用 hash 的高低位混合：(h ^ (h >>> 16))，减少碰撞

// 扰动函数：让高位参与低位计算，降低碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// put 流程（伪代码）
final V putVal(int hash, K key, V value, ...) {
    if (table 为空) resize();
    int i = (n - 1) & hash;                 // 定位桶：容量-1 与 hash
    if (桶为空) 直接放入新节点;
    else {
        if (桶头 key 相同) 覆盖;
        else if (桶头是树节点) 走红黑树插入;
        else 遍历链表，尾部插入，若长度 ≥ 8 且容量够则树化;
    }
    if (++size > threshold) resize();
}

// JDK8 put：桶空 → CAS 直接放入；桶非空 → synchronized 锁桶头再操作
final V putVal(K key, V value, boolean onlyIfAbsent) {
    ...
    for (Node<K,V>[] tab = table;;) {
        if (桶为空 && casTabAt(tab, i, null, node))  // CAS 成功即插入
            break;
        else if (tab[i] == MOVED)  // 扩容中，帮助迁移
            helpTransfer(tab, node);
        else {
            synchronized (tab[i]) {  // 锁桶头
                ... 链表/树插入
            }
        }
    }
}

// 并发累加正确用法：用 LongAdder 而不是并发加计数
ConcurrentHashMap<String, LongAdder> counts = new ConcurrentHashMap<>();
counts.computeIfAbsent("key", k -> new LongAdder()).increment();

CopyOnWriteArrayList：
  读：直接读 volatile 数组引用，无锁
  写：复制整个数组 → 修改 → 替换引用
  适用：读多写极少的场景（如监听器列表、缓存黑名单）
  代价：每次写 O(n) 拷贝；弱一致迭代器

// 经典使用：缓存订阅者列表
private final CopyOnWriteArrayList<Listener> listeners = new CopyOnWriteArrayList<>();

public void addListener(Listener l) { listeners.add(l); }   // 写时复制
public void notifyAll(Event e) {
    for (Listener l : listeners) l.onEvent(e);              // 无锁遍历
}

// 阻塞队列四组 API：失败策略不同
// add/remove/element    → 抛异常
// offer/poll/peek       → 返回 false/null
// put/take              → 永久阻塞
// offer/poll(timeout)   → 限时阻塞
ArrayBlockingQueue<String> q = new ArrayBlockingQueue<>(100);
boolean ok = q.offer("item", 2, TimeUnit.SECONDS);  // 限时入队
String v = q.poll(2, TimeUnit.SECONDS);             // 限时出队

fail-fast：迭代过程中检测到集合被结构性修改（add/remove/clear），
立即抛 ConcurrentModificationException。
实现：每个集合维护 modCount，迭代器比较 expectedModCount。

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
Iterator<String> it = list.iterator();
it.next();
list.add("d");          // 结构性修改
it.next();              // 抛 ConcurrentModificationException

// 正确删除：用迭代器自己的 remove，而不是集合的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("a")) it.remove();   // 更新 expectedModCount
}