并发集合

BlockingQueue 设计解析 🤔 道格·李为什么需要一个阻塞队列接口 生产者-消费者模式是多线程编程里最常见的协作模型——一个（或多个）线程生产数据，另一个（或多个）线程消费数据。在 JUC 出现之前，Java 开发者只能用 wait() / notify() 手写这个模型。 手写版本的典型代码如下： public synchronized void put(E e) throws InterruptedException { while (list.size() == capacity) { wait(); } list.addLast(e); notifyAll(); } 这段代码表面正确，但道格·李在分析并发程序的常见错误时发现了几个根深蒂固的问题： 生产者唤醒生产者：notifyAll() 唤醒等待队列里的所有线程——包括生产者和消费者。当队列满时，多个生产者同时被唤醒，只有第一个能成功插入，其余又回到 wait。这些"无效唤醒"不是 Bug，但大量浪费 CPU 无法区分等待原因：所有线程在同一个条件队列上等待，生产者因为"队列满"而等，消费者因为"队列空"而等。notifyAll() 叫醒所有人，但被叫醒的线程可能发现条件仍不满足，继续睡——这就是为什么 wait() 必须放在 while 循环里 没有标准接口：每个项目都在重新发明这个轮子，而且各自的行为语义不一致——有的用 null 表示失败，有的抛异常，有的阻塞等待 道格·李的解决方案是两层的：接口层——BlockingQueue 接口定义了四组标准方法（抛异常、返回特殊值、阻塞、超时），统一了所有阻塞队列的行为契约。实现层——用 ReentrantLock 的两个 Condition（notFull 和 notEmpty）精确分离生产者与消费者的等待条件，让"队列满"只唤醒消费者，“队列空"只唤醒生产者，消除无效唤醒。 🚧 BlockingQueue 接口设计：四组方法的语义定义 BlockingQueue 接口最核心的设计决策在于： 同一操作提供四种不同的线程协作策略 ，以方法名区分行为，以返回类型区分语义。 行为模式 插入 移除 检查 语义 抛异常 add(e) remove() element() 操作无法立即执行时抛出 IllegalStateException ，调用方需自行处理 返回特殊值 offer(e) poll() peek() 操作无法立即执行时返回 false 或 null ，调用方通过返回值判断是否成功 阻塞 put(e) take() — 操作无法立即执行时阻塞当前线程，直到条件满足，调用方被挂起 超时 offer(e, t, u) poll(t, u) — 操作无法立即执行时阻塞最多指定时长，超时返回 false 或 null 四组方法的核心设计哲学是"让调用方选择等待策略而非被动接受”。 同一个"放入元素"的需求，调用方可以根据业务场景选择： ...

ConcurrentLinkedQueue：无锁并发队列、Michael-Scott 算法与 HOPS 延迟更新机制全解析 🚀 道格·李为什么需要一个无锁队列 生产环境中大量使用多生产者-多消费者的队列模型：多个线程投递任务，多个线程取出执行。传统的做法是用 LinkedList 加 synchronized——任意时刻只有一个线程能操作队列，其他线程排队等锁。在高并发下，锁争用（Lock Contention）迅速成为吞吐量瓶颈：CPU 时间大量消耗在线程的阻塞-唤醒切换上，而非实际的消息处理。 道格·李在设计 JSR 166 时为这个场景引入了一个完全不同的方案：无锁并发队列。ConcurrentLinkedQueue 使用 CAS（Compare-And-Swap，比较并交换）原子操作替代锁，基于 Michael-Scott 算法（1996 年由 Maged Michael 和 Michael Scott 提出的无锁队列算法）实现多线程并发入队和出队。 核心设计思想： 入队和出队操作各自独立——生产者在队尾 CAS 插入，消费者在队头 CAS 移除，彼此不阻塞 没有锁，就不会有线程被操作系统挂起——CAS 失败意味着有其他线程抢先了一步，重试即可，没有上下文切换开销 HOPS 延迟更新策略——tail 指针不必每次都更新到最后一个节点，允许滞后 1 ~ 2 个位置，用额外的 CAS 判断换来更少的 volatile 写操作 ConcurrentLinkedQueue 是 JUC 无锁数据结构的基础模型——理解了它的 CAS 操作模式和 HOPS 策略，再看 ConcurrentHashMap、LinkedTransferQueue 等无锁结构会轻松很多。 🏗️ 核心数据结构 整体架构：基于 Node 的单向链表 ConcurrentLinkedQueue 的底层是一个 单向链表，由 head 和 tail 两个 volatile 指针维护： ...

ConcurrentHashMap 深度解析：从数据结构到线程安全的底层实现 一、道格·李为什么需要重新设计一个并发哈希表 Java 1.0 提供了 Hashtable——一个线程安全的 Map 实现。它的线程安全策略很简单：在所有 public 方法上加 synchronized。这个策略正确但不实用——任何时候只有一个线程能操作整个表，即使两个线程操作的是不同的键。在 1.0 时代并发不常见时还凑合，到了 Java 5 时代，服务器端的多线程访问同一个缓存 Map 已经是常规操作，Hashtable 的全局锁成了吞吐量的天花板。 HashMap 是 Hashtable 的非线程安全替代，性能好得多，但一旦多线程并发 put，就会出现数据丢失、size 计数错误，甚至在 JDK 7 扩容时出现链表成环导致 CPU 100%。 道格·李在设计 ConcurrentHashMap 时面临的问题是：既要保证线程安全（不能丢数据），又要提供接近 HashMap 的并发吞吐量（不能全局锁）。这是两个互相矛盾的目标，传统的 synchronized 方案只能取其一。 道格·李的解决方案是把锁的粒度从"整张表"缩小到"单个桶"。JDK 5 ~ 7 中用了 Segment 分段锁（16 个段，每段独立加锁），JDK 8 进一步细化为桶级别 CAS + synchronized——对空桶用 CAS 无锁插入，对非空桶只锁链表/红黑树的头节点。这种设计让 16 个线程同时操作 16 个不同桶时完全无竞争，并发度从 Hashtable 的 1 提升到桶的数量级。 🗺️ 二、ConcurrentHashMap 的数据结构 JDK 8 的 ConcurrentHashMap 放弃了 JDK 7 的 Segment 分段锁设计，直接采用与 HashMap 相似的结构： Node 数组 + 链表 + 红黑树 。 ...

CopyOnWriteArrayList 源码深度解析：从线程安全列表到写时复制的实现原理 一、道格·李为什么需要"写时复制"的列表 Java 1.0 的 Vector 用 synchronized 保证线程安全——所有方法加锁，读写都互斥。Collections.synchronizedList 同理。这在读多写少的场景中有一个严重的浪费：多个线程同时读取不应该互相阻塞，因为读取不修改数据。 但去掉锁也不行——ArrayList 的迭代器有 fail-fast 机制，遍历时如果有其他线程写入，直接抛 ConcurrentModificationException。而且多线程同时 add() 还会导致数据丢失（elementData 数组和 size 计数器都没有同步保护）。 道格·李在 JSR 166 中为这个场景设计了一个完全不同的策略：写时复制（Copy-On-Write）。每次写入（add、set、remove）不直接修改原数组，而是复制一份新数组，在新数组上操作，最后用 volatile 写把引用指向新数组。读操作完全无锁——直接读当前的数组引用，不需要任何同步。 这个设计的取舍非常明确：写操作很贵（要复制整个数组），但读操作极其便宜（无锁 + volatile 读）。因此 CopyOnWriteArrayList 仅适用于读多写极少（比如读:写 > 100:1）的场景——配置信息、监听器列表、白名单等写入很少但频繁遍历的数据结构。 📐 二、设计理念：Copy-On-Write 📌 2.1 什么是写时复制 写时复制（Copy-On-Write，COW）是一种并发优化策略。它的核心思想只有一句话：当容器需要被修改时，不直接在原数组上操作，而是先复制一份新数组，在新数组上修改，修改完成后用新数组替换旧数组的引用。 这就保证了：读操作永远在不变的数组上进行，完全不需要加锁；写操作虽然开销大，但只影响它自己，不会阻塞任何读线程。 📌 2.2 CopyOnWriteArrayList 的架构总览 CopyOnWriteArrayList 的并发安全由"一锁一数组"两个组件配合完成： flowchart TD %% 半暗底色 + 高亮描边：完美适配博客深色/浅色双主题 %% classDef process fill:#1e1e24,stroke:#6b7280,stroke-width:2px,color:#e5e7eb; COW[CopyOnWriteArrayList] COW --> ARRAY["array: volatile Object[]"] COW --> LOCK["lock: ReentrantLock"] ARRAY --> A0["元素0"] ARRAY --> A1["元素1"] ARRAY --> A2["元素2"] ARRAY --> AN["元素N"] LOCK --> W["写线程"] ARRAY --> R["读线程"] W --> |写操作加锁| LOCK R --> |volatile读无锁| ARRAY class A0,A1,A2,AN,ARRAY,COW,LOCK,Object,R,W process; 组件 类型 作用 array volatile Object[] 存储元素，volatile 保证写后对其他线程立即可见 lock final ReentrantLock 写操作的互斥锁，同一时刻只允许一个写线程 array 加上 volatile 是关键——写线程完成数组替换后，volatile 写语义将所有读线程看到的旧引用刷成新引用，保证最终一致性。 ...