罗罗编程学习记录
本页内容 展开查看

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(等待不满)。

原理流程

  1. put(e):加锁,队列满则 notFull.await;否则入队,signal notEmpty。
  2. take():加锁,队列空则 notEmpty.await;否则出队,signal notFull。
  3. 数组用 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 实现。

概念解释

  • 缓冲区:解耦生产和消费速度。
  • 有界:防止生产者无限生产。
  • 等待/通知:满时等,空时等,变化时通知。

原理流程

  1. 生产者:队列满则 wait,否则生产并 notify。
  2. 消费者:队列空则 wait,否则消费并 notify。
  3. 必须在 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 失败说明有并发修改,重读重试。

原理流程

  1. push(v):new Node(v, oldTop),CAS top 从 oldTop 改成 newNode;成功返回,失败重读 oldTop 重试。
  2. 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。

原理流程

  1. enqueue(v):new Node(v),读 tail 和 tail.next;若 tail.next==null,CAS tail.next 从 null 改成 newNode;再 CAS tail 从 oldTail 改成 newNode。
  2. 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 下一个。

原理流程

  1. 三个线程 A、B、C,共享 state(0、1、2)。
  2. A 线程:state==0 则打印 A,state=1,通知;否则 wait。
  3. B 线程:state==1 则打印 B,state=2,通知;否则 wait。
  4. 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 保证枚举实例唯一,防反射和序列化破坏。

原理流程

  1. DCL:if (instance == null) { synchronized { if (instance == null) instance = new Singleton(); } }。
  2. 静态内部类:static class Holder { static final Singleton INSTANCE = new Singleton(); },外部类加载时不初始化 Holder,首次访问才加载。
  3. 枚举: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 强引用。

原理流程

  1. 每个 Thread 持有 threadLocals(ThreadLocalMap)。
  2. set(v):以 ThreadLocal 实例为 key,v 为 value 存入 map。
  3. get():以 ThreadLocal 实例为 key 查 map。
  4. 线程池场景:线程不销毁,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,不用加锁。

原理流程

  1. JDK 7:put 时定位到 Segment,加 Segment 锁,再操作桶。
  2. JDK 8:put 时定位到桶,空桶用 CAS 插入,非空桶 synchronized 锁头节点。
  3. 链表长度超过 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 读写锁