02.10.4 并发数据结构设计
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题
覆盖范围
- 阻塞队列与生产者消费者
- 无锁栈/队列(CAS)
- 多线程交替打印(ABC)
- 线程安全单例
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.10.4-001 | ArrayBlockingQueue 实现原理 | 基础 | ★★★★ |
| 02.10.4-002 | 生产者消费者模式手写 | 基础 | ★★★★★ |
| 02.10.4-003 | 无锁栈(CAS) | 高级 | ★★★★ |
| 02.10.4-004 | 无锁队列(CAS) | 高级 | ★★★ |
| 02.10.4-005 | 多线程交替打印 ABC | 进阶 | ★★★★★ |
| 02.10.4-006 | 线程安全单例(DCL/静态内部类/枚举) | 基础 | ★★★★★ |
| 02.10.4-007 | ThreadLocal 原理与内存泄漏 | 进阶 | ★★★★ |
| 02.10.4-008 | ConcurrentHashMap 分段锁演进 | 进阶 | ★★★★ |
02.10.4-001 ArrayBlockingQueue 实现原理
频率 ★★★★ | 难度 基础
一句话结论
基于数组 + 一把 ReentrantLock + 两个条件队列(notEmpty、notFull);put 时队列满则 notFull.await,take 时队列空则 notEmpty.await;put 成功 signal notEmpty,take 成功 signal notFull。
概念解释
- 数组存储:定长循环数组。
- 一把锁:put 和 take 共用同一把锁,吞吐受限。
- 条件队列:notEmpty(等待非空)、notFull(等待不满)。
原理流程
- put(e):加锁,队列满则 notFull.await;否则入队,signal notEmpty。
- take():加锁,队列空则 notEmpty.await;否则出队,signal notFull。
- 数组用 putIndex、takeIndex 维护头尾。
代码 / 示例
class MyArrayBlockingQueue<E> {
private final Object[] items;
private int takeIndex, putIndex, count;
private final Object lock = new Object();
private final java.util.concurrent.locks.Condition notEmpty;
private final java.util.concurrent.locks.Condition notFull;
private final java.util.concurrent.locks.ReentrantLock qlock = new java.util.concurrent.locks.ReentrantLock();
MyArrayBlockingQueue(int cap) {
items = new Object[cap];
notEmpty = qlock.newCondition();
notFull = qlock.newCondition();
}
void put(E e) throws InterruptedException {
qlock.lock();
try {
while (count == items.length) notFull.await();
items[putIndex] = e;
if (++putIndex == items.length) putIndex = 0;
count++;
notEmpty.signal();
} finally { qlock.unlock(); }
}
@SuppressWarnings("unchecked")
E take() throws InterruptedException {
qlock.lock();
try {
while (count == 0) notEmpty.await();
E e = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length) takeIndex = 0;
count--;
notFull.signal();
return e;
} finally { qlock.unlock(); }
}
}
常见误区
- 误区:用 if 判断队列空/满;正解:必须用 while,因为 await 被唤醒后可能其他线程已经先消费/生产。
- 误区:put 和 take 用两把锁;正解:ArrayBlockingQueue 用一把锁,LinkedBlockingQueue 才用两把锁。
追问 / 延伸
- Q:LinkedBlockingQueue 吞吐为什么更高? A:put 和 take 用两把独立锁,可并行。
- Q:ArrayBlockingQueue 为什么用条件队列而不是 wait/notify? A:条件队列可精确唤醒 notEmpty/notFull,避免唤醒所有线程。
02.10.4-002 生产者消费者模式手写
频率 ★★★★★ | 难度 基础
一句话结论
用一个有界队列作为缓冲区,生产者 put,消费者 take;队列满则生产者等待,队列空则消费者等待;用 wait/notify 或 Lock+Condition 实现。
概念解释
- 缓冲区:解耦生产和消费速度。
- 有界:防止生产者无限生产。
- 等待/通知:满时等,空时等,变化时通知。
原理流程
- 生产者:队列满则 wait,否则生产并 notify。
- 消费者:队列空则 wait,否则消费并 notify。
- 必须在 while 循环中等待,防止虚假唤醒。
代码 / 示例
class ProducerConsumer {
private final java.util.Queue<Integer> q = new java.util.LinkedList<>();
private final int cap = 10;
private final Object lock = new Object();
void produce(int item) throws InterruptedException {
synchronized (lock) {
while (q.size() == cap) lock.wait();
q.offer(item);
lock.notifyAll();
}
}
int consume() throws InterruptedException {
synchronized (lock) {
while (q.isEmpty()) lock.wait();
int v = q.poll();
lock.notifyAll();
return v;
}
}
}
常见误区
- 误区:用 if 判断队列空/满;正解:必须 while,防止虚假唤醒或多线程竞争。
- 误区:用 notify 不用 notifyAll;正解:可能唤醒同类线程(生产者唤醒生产者),导致死锁。
追问 / 延伸
- Q:为什么不用阻塞队列? A:阻塞队列就是这个模式的封装,实际生产用 ArrayBlockingQueue 或 LinkedBlockingQueue。
- Q:虚假唤醒是什么? A:线程在 wait 状态下被意外唤醒,不是由 notify 触发,所以必须 while 重新检查条件。
02.10.4-003 无锁栈(CAS)
频率 ★★★★ | 难度 高级
一句话结论
栈顶用 AtomicReference 维护;push 时新建节点指向旧栈顶,CAS 把栈顶从旧值改成新节点;pop 时读栈顶,CAS 把栈顶改成 next;失败重试。
概念解释
- CAS:Compare And Swap,原子比较并交换。
- 栈顶指针:AtomicReference
。 - 失败重试:CAS 失败说明有并发修改,重读重试。
原理流程
- push(v):new Node(v, oldTop),CAS top 从 oldTop 改成 newNode;成功返回,失败重读 oldTop 重试。
- pop():读 top,取 next;CAS top 从 top 改成 next;成功返回,失败重试。
代码 / 示例
class LockFreeStack<E> {
static class Node<E> { E val; Node<E> next; Node(E v) { val = v; } }
private final java.util.concurrent.atomic.AtomicReference<Node<E>> top = new java.util.concurrent.atomic.AtomicReference<>();
void push(E v) {
Node<E> n = new Node<>(v);
while (true) {
Node<E> old = top.get();
n.next = old;
if (top.compareAndSet(old, n)) return;
}
}
E pop() {
while (true) {
Node<E> old = top.get();
if (old == null) return null;
if (top.compareAndSet(old, old.next)) return old.val;
}
}
}
常见误区
- 误区:CAS 失败直接抛异常;正解:CAS 失败是并发竞争,重读重试即可。
- 误区:无锁栈不会 ABA 问题;正解:栈顶从 A 变成 B 再变回 A,CAS 仍成功,可能导致逻辑错误;用 AtomicStampedReference 解决。
追问 / 延伸
- Q:ABA 问题是什么? A:值从 A 变 B 再变回 A,CAS 认为没变,但实际中间被修改过。
- Q:无锁栈性能? A:低竞争时比锁快,高竞争时 CAS 重试开销大,可能比锁慢。
02.10.4-004 无锁队列(CAS)
频率 ★★★ | 难度 高级
一句话结论
Michael-Scott 队列:head 和 tail 都是 AtomicReference;入队时把新节点挂到 tail.next,再 CAS 推进 tail;出队时 CAS 推进 head;比无锁栈复杂,因为有 head 和 tail 两个指针。
概念解释
- 哑节点:head 指向一个不存数据的哑节点,简化边界。
- 入队两步:先挂 next,再推进 tail。
- 出队两步:先读 head.next,再推进 head。
原理流程
- enqueue(v):new Node(v),读 tail 和 tail.next;若 tail.next==null,CAS tail.next 从 null 改成 newNode;再 CAS tail 从 oldTail 改成 newNode。
- dequeue():读 head 和 head.next;若 head.next==null 返回 null;CAS head 从 oldHead 改成 head.next。
代码 / 示例
class LockFreeQueue<E> {
static class Node<E> { E val; final java.util.concurrent.atomic.AtomicReference<Node<E>> next = new java.util.concurrent.atomic.AtomicReference<>(); Node(E v) { val = v; } }
private final java.util.concurrent.atomic.AtomicReference<Node<E>> head;
private final java.util.concurrent.atomic.AtomicReference<Node<E>> tail;
LockFreeQueue() {
Node<E> dummy = new Node<>(null);
head = new java.util.concurrent.atomic.AtomicReference<>(dummy);
tail = new java.util.concurrent.atomic.AtomicReference<>(dummy);
}
void enqueue(E v) {
Node<E> n = new Node<>(v);
while (true) {
Node<E> t = tail.get();
Node<E> next = t.next.get();
if (t == tail.get()) {
if (next == null) {
if (t.next.compareAndSet(null, n)) {
tail.compareAndSet(t, n);
return;
}
} else {
tail.compareAndSet(t, next);
}
}
}
}
E dequeue() {
while (true) {
Node<E> h = head.get();
Node<E> t = tail.get();
Node<E> next = h.next.get();
if (h == head.get()) {
if (h == t) {
if (next == null) return null;
tail.compareAndSet(t, next);
} else {
E v = next.val;
if (head.compareAndSet(h, next)) return v;
}
}
}
}
}
常见误区
- 误区:入队一步完成;正解:入队分两步(挂 next、推进 tail),中间状态 tail 可能滞后。
- 误区:出队直接读 head.val;正解:head 是哑节点,真实数据在 head.next。
追问 / 延伸
- Q:Michael-Scott 队列难点? A:head 和 tail 两个指针都可能滞后,需要处理中间状态。
- Q:无锁队列有 ABA 问题吗? A:有,用 AtomicStampedReference 解决。
02.10.4-005 多线程交替打印 ABC
频率 ★★★★★ | 难度 进阶
一句话结论
三个线程轮流打印 A、B、C,每个线程打印后通知下一个;用 Lock + 两个 Condition(或三个 Condition),或 synchronized + wait/notify;关键是用一个共享变量标记当前该谁打印。
概念解释
- 共享状态:当前轮到哪个线程。
- 等待:不是自己则 wait。
- 通知:打印后 notifyAll 或 signal 下一个。
原理流程
- 三个线程 A、B、C,共享 state(0、1、2)。
- A 线程:state==0 则打印 A,state=1,通知;否则 wait。
- B 线程:state==1 则打印 B,state=2,通知;否则 wait。
- C 线程:state==2 则打印 C,state=0,通知;否则 wait。
代码 / 示例
class ABCPrinter {
private int state = 0;
private final Object lock = new Object();
void print(String name, int expect) throws InterruptedException {
for (int i = 0; i < 10; i++) {
synchronized (lock) {
while (state % 3 != expect) lock.wait();
System.out.print(name);
state++;
lock.notifyAll();
}
}
}
}
// 线程 A:printer.print("A", 0);
// 线程 B:printer.print("B", 1);
// 线程 C:printer.print("C", 2);
常见误区
- 误区:用 if 判断 state;正解:用 while,防止虚假唤醒。
- 误区:notify 只唤醒一个;正解:用 notifyAll 或精确 signal 下一个,否则可能唤醒同类线程。
追问 / 延伸
- Q:两个线程交替打印奇偶数? A:同理,共享一个计数器,线程 1 打奇数,线程 2 打偶数。
- Q:用 Lock 怎么写? A:用 ReentrantLock + 三个 Condition,每个线程等自己的 Condition,打印后 signal 下一个。
02.10.4-006 线程安全单例(DCL/静态内部类/枚举)
频率 ★★★★★ | 难度 基础
一句话结论
DCL(双重检查锁)用 volatile + synchronized;静态内部类利用类加载机制保证线程安全;枚举单例最简单且防反射破坏;生产推荐静态内部类或枚举。
概念解释
- DCL:两次判空,第一次无锁,第二次加锁。
- volatile:禁止指令重排,防止半初始化对象被引用。
- 静态内部类:JVM 加载时初始化,天然线程安全。
- 枚举:JVM 保证枚举实例唯一,防反射和序列化破坏。
原理流程
- DCL:if (instance == null) { synchronized { if (instance == null) instance = new Singleton(); } }。
- 静态内部类:static class Holder { static final Singleton INSTANCE = new Singleton(); },外部类加载时不初始化 Holder,首次访问才加载。
- 枚举:public enum Singleton { INSTANCE; }。
代码 / 示例
// DCL
class Singleton {
private static volatile Singleton instance;
private Singleton() {}
static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) instance = new Singleton();
}
}
return instance;
}
}
// 静态内部类
class Singleton2 {
private Singleton2() {}
private static class Holder { static final Singleton2 INSTANCE = new Singleton2(); }
static Singleton2 getInstance() { return Holder.INSTANCE; }
}
// 枚举
enum Singleton3 { INSTANCE; }
常见误区
- 误区:DCL 不加 volatile;正解:
new Singleton()不是原子操作,可能先分配内存再赋值,其他线程看到非 null 但未初始化的对象。 - 误区:静态内部类会外部类加载时初始化;正解:静态内部类只有首次被引用时才加载,是懒加载。
追问 / 延伸
- Q:枚举单例为什么防反射? A:枚举类构造器反射调用被 JVM 禁止。
- Q:DCL 和静态内部类哪个好? A:静态内部类更简洁,DCL 适合需要延迟初始化且要控制初始化逻辑的场景。
02.10.4-007 ThreadLocal 原理与内存泄漏
频率 ★★★★ | 难度 进阶
一句话结论
每个 Thread 对象持有一个 ThreadLocalMap,key 是 ThreadLocal 实例(弱引用),value 是存储的值;ThreadLocalMap 的 key 是弱引用,value 是强引用;线程池场景下线程不销毁,value 可能泄漏,需要手动 remove。
概念解释
- ThreadLocalMap:Thread 对象内部的 map。
- key:ThreadLocal 实例,弱引用。
- value:存储的值,强引用。
- 泄漏:线程池线程复用,key 被 GC 回收变 null,但 value 仍被 Entry 强引用。
原理流程
- 每个 Thread 持有 threadLocals(ThreadLocalMap)。
- set(v):以 ThreadLocal 实例为 key,v 为 value 存入 map。
- get():以 ThreadLocal 实例为 key 查 map。
- 线程池场景:线程不销毁,map 一直存在,key 弱引用被 GC 后 value 泄漏。
代码 / 图示
Thread -> ThreadLocalMap
Entry: WeakReference<ThreadLocal> -> value
key 弱引用,value 强引用
线程池线程复用 -> map 不销毁 -> key=null -> value 泄漏
常见误区
- 误区:ThreadLocal 是静态的;正解:ThreadLocal 实例是 key,每个线程独立 value。
- 误区:ThreadLocal 自动清理;正解:key 弱引用被 GC 后 value 仍存在,必须手动 remove。
追问 / 延伸
- Q:为什么 key 用弱引用? A:防止 ThreadLocal 实例本身泄漏,因为 ThreadLocal 通常是 static 的。
- Q:InheritableThreadLocal? A:子线程可继承父线程的 ThreadLocal 值。
02.10.4-008 ConcurrentHashMap 分段锁演进
频率 ★★★★ | 难度 进阶
一句话结论
JDK 7 用 Segment 数组(继承 ReentrantLock),每个 Segment 守护一个哈希桶;JDK 8 取消 Segment,改用 CAS + synchronized 锁住单个桶头节点;粒度更细,并发度更高。
概念解释
- JDK 7:Segment 数组,默认 16 个 Segment,每个 Segment 一把锁。
- JDK 8:数组 + 链表/红黑树,每个桶头节点用 synchronized 锁。
- CAS:空桶插入用 CAS,不用加锁。
原理流程
- JDK 7:put 时定位到 Segment,加 Segment 锁,再操作桶。
- JDK 8:put 时定位到桶,空桶用 CAS 插入,非空桶 synchronized 锁头节点。
- 链表长度超过 8 转红黑树。
代码 / 图示
JDK 7:
Segment[](16 个)
每个 Segment: HashEntry[] + 锁
锁粒度:Segment
JDK 8:
Node[] + 链表/红黑树
空桶 CAS,非空桶 synchronized 锁头
锁粒度:桶
常见误区
- 误区:JDK 8 完全无锁;正解:空桶 CAS,非空桶仍 synchronized。
- 误区:ConcurrentHashMap 允许 null 值;正解:key 和 value 都不允许 null,因为并发下无法区分是 null 还是不存在。
追问 / 延伸
- Q:为什么 JDK 8 链表转红黑树? A:哈希冲突严重时,链表查找 O(n),红黑树 O(log n)。
- Q:并发度多少? A:JDK 7 默认 16,JDK 8 桶数等于数组长度,并发度更高。
待整理清单
- [ ] Disruptor 无锁队列
- [ ] LongAdder 分段计数
- [ ] StampedLock 读写锁