并发容器与工具类

ℹ️本篇定位

"synchronized 前辈容器为什么不行 + 现代并发容器怎么设计"是本篇主线：ConcurrentHashMap（并发面试双料冠军，与 HashMap、HashMap 源码对照读）、CopyOnWriteArrayList、BlockingQueue、ThreadLocal（内存泄漏必考）、CAS 与原子类（ABA 问题）。JUC 工具类（Latch/Barrier/Semaphore）已在 04-Lock与AQS 讲过，不重复。

为什么 Hashtable 不行了

Hashtable/Vector：方法级 synchronized，读读也互斥，吞吐极差；
ConcurrentHashMap：锁的粒度更细，读完全无锁——这是它替代前两者的根本原因（容器淘汰机理同 Vector 篇的分析）。

ConcurrentHashMap：1.7 分段锁 → 1.8 CAS+synchronized

JDK 1.7：Segment 分段锁（默认 16 段），并发度=段数，两把锁锁不到一起。

JDK 1.8：抛弃分段，改 Node 数组 + 链表/红黑树（结构与 HashMap 1.8 对齐，见 HashMap 篇）：

空槽插入：CAS 直接写，无锁；
非空槽：synchronized 锁住该槽的头节点——锁粒度从"段"细化到"桶"，冲突概率极低；
size() 用 CounterCell 数组 + baseCount 分散计数（LongAdder 思路），避免单点 CAS 热点；
size() 是近似值（并发下统计瞬间可能已过期）——面试常问"为什么 size 不精确"。

不允许 null：key/value 都不许 null（HashMap 允许）。原因：并发下 get(key) 返回 null 时无法区分"不存在"还是"值就是 null"，containsKey 两次调用之间状态可能已变——歧义不可容忍。

ConcurrentHashMap 源码深读：put 与 get 的两条主链

ℹ️本节定位

上一节是"设计演进"，这节落到源码：put 怎么做到"能无锁就无锁、该上锁锁最小粒度"？get 为什么能完全无锁？配合 HashMap 源码对照读，差异点就是考点。

一、三个关键字段与 Unsafe 定位

transient volatile Node<K,V>[] table;              // 桶数组，volatile
private transient volatile int sizeCtl;            // 多义：初始化 / 扩容阈值 / 扩容中（负数表正在扩容）
private transient volatile int cellsBusy;          // CounterCell 扩容的标记位

容器用 Unsafe 的 tabAt(tab, i) / casTabAt(tab, i, c, v) 按内存偏移直接读写数组槽——数组元素本身没有 volatile，靠 Unsafe 提供 volatile 读写语义，这是能 CAS 空槽的前提。

二、put 主链：能无锁就无锁

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();  // ① 双 null 校验
    int hash = spread(key.hashCode());                              // ② 扰动：高 16 位参与
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {                               // ③ for 循环 = 无界重试
        Node<K,V> f; int n, i;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();                                      // ④ 初始化（sizeCtl CAS 抢）
        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);                             // ⑥ 槽是 ForwardingNode → 帮扩容
        else {
            synchronized (f) {                                      // ⑦ 锁头节点（最小粒度）
                // 链表尾插 / 红黑树插入 / 计数 +1 / 超阈值 treeifyBin
            }
        }
    }
    addCount(1L, binCount);                                         // ⑧ 计数（CounterCell 分散）
    return null;
}

对照 HashMap 的答案：

spread() 就是 h ^ (h >>> 16) & HASH_BITS——比 HashMap 多一步 & HASH_BITS 抹掉符号位，让负数 hash 也能当非负槽下标；
为什么 for 死循环：CAS 失败（别的线程抢先占了空槽）就重来，自旋比阻塞便宜；
helpTransfer：读到 MOVED（hash=-1 的 ForwardingNode）说明桶正在扩容迁移，当前线程加入帮忙搬数据——这就是"多线程一起扩容"，比 HashMap 单线程扩容快。

三、get 主链：为什么能完全无锁

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e; int n, eh;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {                 // ① 头节点 hash 对上（或正节点）
            if (e.key == key || (e.key != null && e.key.equals(key)))
                return e.val;                     // 头节点直接命中
        }
        else if (eh < 0)                          // ② 负 hash：树 / 迁移中 / 保留节点
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {            // ③ 顺着链表 equals
            if (e.hash == h && (e.key == key || (e.key != null && e.key.equals(key))))
                return e.val;
        }
    }
    return null;                                  // ④ 找不到返回 null（值不许 null → 语义明确）
}

贯穿 get 全程没有一把锁、没有一次 CAS——全靠 table 是 volatile（新建数组的可见性）+ tabAt 的 volatile 读。这解释了三个考点：

get 不需要加锁，读读、读写都不互斥——吞吐远高于 Hashtable；
Node 的 val 是 volatile，值改了别的线程立刻可见；
黑科技：JDK 8 迁移时 ForwardingNode 指向新表，get 读到它会自动跳到新表找——迁移全程 get 不阻塞。

四、与"hashtable 为什么慢"呼应的总结

环节	Hashtable	ConcurrentHashMap 1.8
读	加同一把大锁	无锁，volatile 读
空槽写	加锁	CAS
非空槽写	加锁	锁桶头节点
扩容	单线程搬全部	多线程 helpTransfer 一起搬
size	锁内累加	CounterCell 分散，近似值

四个维度全从"串行化"改成了"分摊 + 无锁 + 最小锁"——这个故事就是 Java 并发容器演进的缩影。

CopyOnWriteArrayList：写时复制

List<String> list = new CopyOnWriteArrayList<>();
// 读：无锁，直接读当前数组
// 写：加锁 → 复制整个新数组 → 改副本 → 原子替换引用

读多写极少场景（监听器列表、配置缓存）性能极好；
写的代价 O(n) 且占双倍内存；读到的是快照，遍历时不会抛 ConcurrentModificationException，但也看不见刚写入的数据（最终一致）。

BlockingQueue：生产者消费者的标准解

实现	特点
ArrayBlockingQueue	数组 + 一把锁，有界
LinkedBlockingQueue	链表 + 两把锁（put/take 分离），默认看似"有界"容量 Integer.MAX_VALUE（近无界，慎用）
SynchronousQueue	零容量，必须一手交一手（CachedThreadPool 用它）
PriorityBlockingQueue	优先级排序，无界

两套方法（同 Queue 总览）：add/offer/put（抛异常/返回 false/阻塞等待）、remove/poll/take。

ThreadLocal：线程私有变量（内存泄漏必考）

static ThreadLocal<SimpleDateFormat> sdf =
        ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd"));
// 每个线程拿到的是自己的 SimpleDateFormat 实例，互不干扰（SimpleDateFormat 非线程安全，这是经典用法）

结构：每个 Thread 内部有 ThreadLocalMap，key 是 ThreadLocal 的弱引用，value 是强引用。

内存泄漏链：线程长期存活（如线程池）→ 外部对 ThreadLocal 的强引用没了 → key 被回收变 null → 但 Entry(value) 被线程的 map 强引用着 → value 永远够不着又清不掉。

正确姿势：用完必须 remove()（finally 里），尤其是线程池场景——线程不死，value 就一直被踩着。

CAS 与原子类

AtomicInteger n = new AtomicInteger(0);
n.incrementAndGet();          // 内部 CAS：期望 0 → 加 1 → CAS 写回，失败自旋重试
n.compareAndSet(1, 5);        // 期望值 1，改成 5

CAS 是 CPU 级原子指令（cmpxchg），无锁实现安全更新；
三大问题：① 自旋失败白白耗 CPU；② 只能保证单变量；③ ABA（值从 A→B→A，CAS 察觉不到）——AtomicStampedReference 加版本号解决；
LongAdder：高并发计数热点优化——分段 Cell 累加，sum 时汇总，比 AtomicLong 的单点自旋强（ConcurrentHashMap 的 size 计数同思路）。

⬅️ 04-Lock与AQS 🏠 00-Java ➡️ 06-CompletableFuture异步编程

05-并发容器与工具类