并发与设计类手撕 - 面试题

#

★★★

1. 手写生产者-消费者中 wait/notify 与 BlockingQueue 两种实现的虚假唤醒防御？

问题

手写生产者-消费者，说明 wait/notify 与 BlockingQueue 两种实现，以及虚假唤醒防御？

考察点

wait/notify 的 while 循环防御
BlockingQueue 封装同步
条件变量与锁

答案

wait/notify 实现：生产者等队列满（wait），生产后 notify；消费者等队列空（wait），消费后 notify。关键防御：wait 必须放在 while 循环中（while(buffer.isFull()) wait()），因为① 虚假唤醒（spurious wakeup）——线程可能无通知被唤醒；② 唤醒后需重新检查条件（notify 可能唤醒多个，条件可能已被其他线程改变）。BlockingQueue 实现：用 ArrayBlockingQueue/LinkedBlockingQueue，put 阻塞（满时）、take 阻塞（空时），内部已处理同步与等待，无需手写 wait/notify，更简单安全。生产者用 put、消费者用 take 即可。两者核心都是"条件等待 + 循环检查"。

解析

虚假唤醒防御是并发手写的核心考点：wait 必须在 while 中而非 if 中，因为唤醒后不能假设条件仍成立。BlockingQueue 把条件等待与队列操作封装，规避手写 wait/notify 的错误。生产消费是"条件变量 + 同步容器"的经典应用。

示例代码

// wait/notify 版本（生产者线程）
synchronized (buffer) {
    while (buffer.size() == capacity) buffer.wait(); // while 防虚假唤醒
    buffer.add(item);
    buffer.notifyAll();
}
// 消费者
synchronized (buffer) {
    while (buffer.isEmpty()) buffer.wait();
    item = buffer.remove();
    buffer.notifyAll();
}

#

★★★

2. 三个线程交替打印 ABC 的多种实现（synchronized/Lock+Condition/Semaphore）？

问题

三个线程交替打印 ABC，用 synchronized、Lock+Condition、Semaphore 三种方式实现？

考察点

synchronized + wait/notifyAll 轮转
Lock + Condition 精准唤醒
Semaphore 计数的轮转

答案

synchronized 实现：共享一个"当前应打印哪个"的状态（0/1/2），每个线程自旋等待到自己序号，打印后状态+1 并 notifyAll，唤醒所有线程后由下一序号线程继续。Lock+Condition 实现：每个线程一个 Condition，线程等待自己的 condition，打印后 signal 下一个线程的 condition，实现精准唤醒，避免惊群。Semaphore 实现：三个信号量 A、B、C 初始为 1,0,0，线程 A 先 acquire(A) 打印后 release(B)，线程 B acquire(B) 打印后 release(C)，线程 C acquire(C) 打印后 release(A)，形成循环。三者核心都是"轮转调度 + 精确唤醒"，Semaphore 最简洁。

解析

三种实现体现"共享状态 + 同步原语"的演进：synchronized 用 notifyAll 广播（靠状态判断谁继续），Lock+Condition 用精准 signal，Semaphore 用信号量计数天然轮转。Semaphore 因"一个信号量对应一个线程"最优雅。

示例代码

// Semaphore 实现
Semaphore a = new Semaphore(1), b = new Semaphore(0), c = new Semaphore(0);
// 线程 A
for (int i = 0; i < n; i++) { a.acquire(); System.out.print("A"); b.release(); }
// 线程 B
for (int i = 0; i < n; i++) { b.acquire(); System.out.print("B"); c.release(); }
// 线程 C
for (int i = 0; i < n; i++) { c.acquire(); System.out.print("C"); a.release(); }

#

★★★

3. 手写令牌桶限流器（Token Bucket）中字段设计（capacity/rate/tokens/lastRefillTime）、tryAcquire 的原子性保证（CAS vs synchronized）、分布式场景下 Redis + Lua 的实现

问题

手写令牌桶限流器，说明字段设计、tryAcquire 的原子性保证，以及分布式场景下 Redis + Lua 的实现？

考察点

字段：capacity/rate/tokens/lastRefillTime
tryAcquire 原子性（CAS vs synchronized）
分布式 Redis + Lua 原子性

答案

字段设计：capacity（桶容量）、rate（每秒补充速率）、tokens（当前令牌数）、lastRefillTime（上次补充时间）。tryAcquire(1)：先按时间补令牌（tokens=min(capacity, tokens+rate×(now-lastRefillTime))，更新 lastRefillTime），若 tokens≥1 则 tokens-- 返回 true，否则 false。原子性：因为令牌数在多线程下是共享可变状态，需保证"检查+更新"原子。单机可用 synchronized（简单）或 CAS（自旋，无锁）保证；CAS 用 AtomicLong 存 tokens，compareAndSet 循环更新。分布式：多实例共享令牌桶，用 Redis 存储 tokens/lastRefillTime，用 Lua 脚本（原子执行）实现"补充+判断+扣减"，保证分布式下原子性，避免竞态。

解析

令牌桶核心是"惰性补充 + 原子扣减"。原子性是并发正确性的关键，单机用 CAS/synchronized，分布式用 Redis Lua（保证原子执行）。固化"计时补充"避免定时器，用 lastRefillTime 惰性计算补充量是常见优化。

示例代码

// 单机令牌桶
class TokenBucket {
    long capacity, rate, tokens, lastRefill;
    synchronized boolean tryAcquire() {
        tokens = Math.min(capacity, tokens + rate * (System.currentTimeMillis() - lastRefill) / 1000);
        lastRefill = System.currentTimeMillis();
        if (tokens >= 1) { tokens--; return true; }
        return false;
    }
}
// Redis Lua：KEYS[1]=tokens, ARGV[1]=capacity, ARGV[2]=rate, ARGV[3]=now
// local t = redis.call('get', KEYS[1]); t = math.min(cap, t + rate*(now-last)); ...

#

★★★

4. 手写 LRU Cache（LeetCode 146）中 HashMap + 双向链表的 O(1) get/put、边界处理（capacity=0、重复 key 更新）、线程安全版本的锁粒度选择（全局锁 vs 分段锁 vs ConcurrentHashMap + 链表锁）

问题

手写 LRU Cache，说明 HashMap + 双向链表的 O(1) get/put、边界处理，以及线程安全版本的锁粒度选择？

考察点

HashMap + 双向链表实现 O(1)
边界：capacity=0、重复 key 更新
线程安全：全局锁 vs 分段锁

答案

HashMap 存 key→链表节点，双向链表按访问顺序（头部最近使用、尾部最久未使用）。get(key)：命中则把节点移到头部，返回 value；未命中返回 -1。put(key,value)：若 key 存在，更新值并移到头部；若不存在，插入头部并加入 map，若超容量则删除尾部节点及其 map 项。双向链表保证 O(1) 删除任意节点（有前驱即可定位）。边界：capacity=0 时任何 put 都无效（无空间）；重复 key 更新只需改值+移头，不新增节点。线程安全：全局锁（synchronized 整个操作）最简单但并发度低；分段锁（分桶锁）提升并发但实现复杂；ConcurrentHashMap + 链表锁（只锁链表操作）平衡，但需保证组合操作的原子性。Java 的 LinkedHashMap 可用于单线程。

解析

O(1) 的关键是"HashMap 定位 + 双向链表任意位置删除"。双向链表用哨兵头尾简化边界。线程安全是工程问题，锁粒度从粗到细权衡并发与复杂度。这是"集合 + 数据结构"的经典手写题。

示例代码

class LRUCache {
    int capacity;
    Map<Integer, Node> map = new HashMap<>();
    Node head = new Node(), tail = new Node(); // 哨兵
    class Node { int key, val; Node prev, next; }
    int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n); return n.val;
    }
    void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; moveToHead(n); }
        else {
            n = new Node(); n.key = key; n.val = value;
            addHead(n); map.put(key, n);
            if (map.size() > capacity) { Node last = removeTail(); map.remove(last.key); }
        }
    }
}

#

★★★

5. 手写限流的滑动窗口中如何用时间戳队列实现固定窗口与滑动窗口，边界请求如何处理？

问题

手写限流的滑动窗口，说明如何用时间戳队列实现固定窗口与滑动窗口，以及边界请求如何处理？

考察点

固定窗口 vs 滑动窗口
时间戳队列维护窗口内请求
边界请求处理

答案

固定窗口：把时间切成固定长度窗口（如 1 秒），每秒一个计数器，窗口内请求数达上限则拒绝，窗口结束重置。实现简单，但边界有突刺问题（两窗口边界处可瞬间放行 2× 上限）。滑动窗口：维护一个时间戳队列（或环形数组），记录窗口内每个请求的时间戳；新请求到达时，先移除窗口外（早于 now-window）的时间戳，再判断队列长度是否达上限，若未达则加入并放行，否则拒绝。边界请求：滑动窗口用"按时间戳精确移除过期请求"，避免固定窗口的边界突刺；也可用"子窗口计数"（把窗口切成若干小段，逐段滑动）近似，降低内存。滑动窗口用 O(窗口内请求数) 内存，固定窗口 O(1)。

解析

固定窗口 O(1) 但边界突刺；滑动窗口精确但存时间戳（内存 O(请求数)）。折中是用子窗口计数（滑动窗口+分桶）。边界请求（恰在窗口边界）是滑动窗口更精确的原因。这是限流器从粗糙到精确的演进。

示例代码

// 滑动窗口（时间戳队列）
class SlidingWindow {
    Deque<Long> q = new ArrayDeque<>();
    int limit; long windowMs;
    boolean allow() {
        long now = System.currentTimeMillis();
        while (!q.isEmpty() && now - q.peekFirst() >= windowMs) q.pollFirst(); // 移除过期
        if (q.size() >= limit) return false;
        q.addLast(now); return true;
    }
}

#

★★★

6. 手写时间轮/延迟任务调度器中环形数组加轮询指针如何调度延时任务，与 DelayQueue 堆实现的复杂度对比

问题

手写时间轮/延迟任务调度器，说明环形数组加轮询指针如何调度延时任务，与 DelayQueue 堆实现的复杂度对比？

考察点

时间轮：环形数组 + 轮询指针
每格存该时刻到期的任务链表
与 DelayQueue（堆）复杂度对比

答案

时间轮：一个环形数组（桶），每个槽位代表一个时间片，一个指针随时间 tick 前进。任务按"到期时间所在槽位"放入对应槽的链表。指针每前进一格，处理该槽所有到期任务。多级时间轮可处理大跨度延迟。复杂度：添加/删除任务 O(1)（定位槽位入链表），tick 推进 O(1)（每格处理）。DelayQueue（堆）：用优先队列按到期时间排序，取队首（最早到期）任务，复杂度添加 O(log n)、取最早 O(1)（但需 poll 阻塞）。对比：时间轮添加 O(1) 优于堆的 O(log n)，适合大量定时任务、高吞吐；堆适合需要精确到期时间、任务数量多但插入频繁的场景。时间轮按时间片粒度，重任务需多级。

解析

时间轮是"空间换时间"的调度优化：用环形数组把"按到期时间排序"变成"按槽位哈希"，添加 O(1)。tick 推进调度到期任务。堆是一种平衡树实现，添加 O(log n)。时间轮常用于网络/IO 框架（如高性能定时器），堆常用于 Java DelayQueue/ScheduledThreadPoolExecutor。

示例代码

// 时间轮简化
class TimerWheel {
    int ticks; long tickMs; List<List<Task>> wheel; int cur;
    void add(Task t, long delay) {
        int pos = (cur + (int)(delay / tickMs)) % ticks;
        wheel.get(pos).add(t);
    }
    void tick() {
        List<Task> due = wheel.get(cur);
        cur = (cur + 1) % ticks;
        for (Task t : due) t.run();
    }
}

#

★★

7. 手写 Semaphore（计数信号量）中用 lock 加 condition 实现 acquire/release，为什么释放时要通知所有等待者？

问题

手写 Semaphore，用 lock 加 condition 实现 acquire/release，说明为何释放时要通知所有等待者？

考察点

acquire/release 的计数逻辑
释放时通知所有等待者
与公平性

答案

手写 Semaphore：用一把锁 + 一个 Condition。acquire：加锁后 while(permits<=0) condition.await()；permits--；解锁。release：加锁后 permits++；解锁后 condition.signalAll()。为什么释放时通知所有等待者：acquire 的等待条件是"permits>0"，释放一个许可后，可能有多个线程在等待；signalAll 唤醒所有等待者，让它们重新竞争许可（因为一次释放可能让多个已满足条件的 acquire 通过，或需公平竞争）。若只 signal 一个，可能唤醒的不是"许可仍够"的线程，或造成忙等。实际上用 while 循环 + signalAll 最安全（即使多个唤醒，各自重新检查条件）。

解析

Semaphore 是"许可计数 + 条件等待"。释放时 signalAll 保证所有等待者都有机会重新检查许可条件，避免"只唤醒一个但许可已被抢走"导致的活锁。while 循环 + signalAll 是标准安全写法。这是"锁+条件变量"手写同步原语的经典。

示例代码

class MySemaphore {
    int permits; ReentrantLock lock = new ReentrantLock(); Condition cond = lock.newCondition();
    void acquire() throws InterruptedException {
        lock.lock();
        try { while (permits <= 0) cond.await(); permits--; }
        finally { lock.unlock(); }
    }
    void release() {
        lock.lock();
        try { permits++; cond.signalAll(); } // 通知所有等待者
        finally { lock.unlock(); }
    }
}

#

★★

8. 手写线程安全的单例（双检锁 volatile 的必要性）？

问题

手写线程安全的单例，说明双检锁为何需要 volatile？

考察点

双检锁（DCL）结构
volatile 防止指令重排
三种单例实现对比

答案

双检锁单例：先检查 instance 是否为空（避免每次加锁），非空则同步块内再检查并创建。volatile 的必要性：instance 的创建包含"分配内存、初始化、赋引用"三步，若不 volatile，JVM 可能重排为"先赋引用再初始化"，导致其他线程看到非空但未完全初始化的对象。volatile 禁止该重排，保证"初始化完成才可见引用"。常用写法：私有构造、private static volatile Singleton instance、静态方法 getInstance 双检。也可用静态内部类（Holder，懒加载且线程安全）或枚举（最安全）。volatile 是 DCL 正确性的关键，缺了它是经典 bug。

解析

DCL 是"先无锁检查 + 有锁创建"的优化，volatile 解决"可见性 + 有序性"（阻止半初始化对象暴露）。这是并发单例的经典考点，volatile 的必要性常被追问。静态内部类/枚举是更现代的替代。

示例代码

class Singleton {
    private static volatile Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() {
        if (instance == null) {                 // 第一次检查（无锁）
            synchronized (Singleton.class) {
                if (instance == null) instance = new Singleton(); // 第二次检查
            }
        }
        return instance;
    }
}

#

★★

9. 设计一个线程安全的计数器，synchronized、AtomicLong、LongAdder 的性能层级？

问题

设计线程安全的计数器，说明 synchronized、AtomicLong、LongAdder 的性能层级？

考察点

三种实现的适用场景
AtomicLong 的 CAS 无锁
LongAdder 的分段累加

答案

线程安全计数器三种实现：① synchronized：加锁保护 count++，简单但并发下锁竞争开销大，吞吐低。② AtomicLong：用 CAS 无锁更新，无阻塞、性能好，适合"多线程竞争不激烈"的场景，但高竞争下 CAS 自旋频繁，可能退化为忙等。③ LongAdder：把计数分到多个 cell（分段），并发写时分散到不同 cell，最后 sum 求和，避免单点竞争，吞吐最高，适合"写多读少、高并发"的统计场景（如计数器、指标）。性能层级：高并发写场景 LongAdder > AtomicLong > synchronized。读场景 AtomicLong 的 get 更直接（LongAdder sum 需遍历）。

解析

性能层级本质是"锁（阻塞）vs CAS（无锁自旋）vs 分段（无竞争）"的演进。LongAdder 用"分段求和"消除单点竞争，是并发统计的优化。选择看读写比例与竞争程度。

示例代码

// AtomicLong 计数器
AtomicLong c = new AtomicLong();
c.incrementAndGet(); // CAS 无锁
// LongAdder 计数器
LongAdder adder = new LongAdder();
adder.increment();
long sum = adder.sum(); // 分段求和

#

★★

10. 手写 ReadWriteLock 中读读并发、读写互斥、写写互斥的状态位设计（高 16 位读锁/低 16 位写锁）、写锁降级与读锁升级的禁止原因、公平与非公平策略

问题

手写 ReadWriteLock，说明状态位设计（高 16 位读锁/低 16 位写锁）、写锁降级与读锁升级的禁止原因、公平策略？

考察点

状态位：高 16 位读锁计数、低 16 位写锁
读读并发、读写/写写互斥
写锁降级允许、读锁升级禁止

答案

用单个 int 状态位：高 16 位存读锁计数，低 16 位存写锁计数（或写锁标记）。读锁：读读并发（读锁可重入多持）；写锁：写写互斥、读写互斥。acquireRead：若写锁为 0 则读计数+1；acquireWrite：写锁为 0 且读计数为 0 才可写。写锁降级：持有写锁时再获取读锁是允许的（写锁降级为读锁），因为自己已独占，降级安全。读锁升级：持有读锁时尝试获取写锁被禁止，因为多个读线程同时想升级会造成死锁（无法确定谁先获得写锁）。公平策略：公平锁按队列顺序获取，非公平锁允许抢占；非公平吞吐更高，公平避免饥饿。Java 的 ReentrantReadWriteLock 用此设计。

解析

状态位用 16 位分割是"一个 int 存两个计数"的经典技巧。写锁降级安全（单一持有者），读锁升级死锁（多读竞争写）。公平性与锁语义相关。这是"锁状态设计"的综合考点。

示例代码

// 高 16 位读锁、低 16 位写锁
class MyRWLock {
    int state; // 高16位读计数，低16位写
    void acquireRead() { while ((state & 0xFFFF) != 0) ; state += 1 << 16; } // 无写锁才读
    void acquireWrite() { while (state != 0) ; state += 1; } // 全空才写
    void releaseRead() { state -= 1 << 16; }
    void releaseWrite() { state -= 1; }
}

#

★★

11. 手写 CountDownLatch 与 CyclicBarrier 中 AQS 的 state 计数与 await/signal 机制、CyclicBarrier 的代（generation）概念与 BrokenBarrierException、两者在并发测试框架中的应用

问题

手写 CountDownLatch 与 CyclicBarrier，说明 AQS state 计数与 await/signal 机制、CyclicBarrier 的代概念与 BrokenBarrierException，以及两者在测试框架中的应用？

考察点

CountDownLatch：state 递减、await 阻塞到 0
CyclicBarrier：state 递增、满则放行、可重用
CyclicBarrier 的 generation 与 BrokenBarrierException

答案

CountDownLatch：基于 AQS 的 state 作计数，countDown 使 state 减 1，await 阻塞直到 state 为 0。一次性使用（不可重置）。CyclicBarrier：state 计数参与线程数，每线程 await 使计数+1，达到阈值则所有线程放行，可重用（用 generation 代表示一轮）。代（generation）概念：每轮栅栏一个 generation，若某线程中断/超时/异常导致栅栏"破坏"，则其他等待线程抛 BrokenBarrierException，且 generation 失效。应用：CountDownLatch 用于"等待 N 个操作完成"（如测试中等待所有线程就绪后一并开始，或等待所有线程结束）；CyclicBarrier 用于"多线程同步到同一栅栏点"（如并发测试中所有线程同时开始、或每轮重同步）。两者都常用于并发测试框架的"起跑线/汇合点"。

解析

CountDownLatch 是一次性倒计数，CyclicBarrier 是可重用的栅栏（每轮一个 generation）。BrokenBarrierException 是栅栏被破坏的信号。AQS 的 state 是两者的计数基础。理解"一次性 vs 可重用"与"代"是区分两者的关键。

示例代码

// CountDownLatch：等待所有线程就绪
CountDownLatch ready = new CountDownLatch(threadCount);
// 每个线程启动后 ready.countDown(); ready.await(); 然后执行
// CyclicBarrier：所有线程到达同一栅栏
CyclicBarrier barrier = new CyclicBarrier(n);
// 每个线程 barrier.await(); 同时放行；可重复 await（新 generation）

#

★★

12. 多线程交替打印中用 volatile/自旋、锁与信号量、原子变量三种方案的对比？

问题

多线程交替打印，对比 volatile/自旋、锁与信号量、原子变量三种方案？

考察点

volatile + 自旋判断
Lock/Semaphore 精确控制
AtomicInteger 自旋

答案

① volatile/自旋：共享 volatile 状态（当前应打印序号），每个线程自旋检查是否轮到自己，是则打印、更新状态。CPU 空转、无阻塞，简单但浪费 CPU（自旋）。② 锁与信号量：用 Lock+Condition 或 Semaphore 精确唤醒，等待线程阻塞，不浪费 CPU，更高效。③ 原子变量：AtomicInteger 存当前序号，线程用 CAS 尝试"抢到"自己的序号，类似自旋。对比：volatile/自旋与原子变量都是"自旋式"（无阻塞，适合等待时间短、CPU 核多）；锁/信号量是"阻塞式"（不耗 CPU，适合等待长）。实际交替打印用 Semaphore/Condition 最合适（阻塞节省 CPU），volatile/自旋适合超短临界区。

解析

三方案的本质是"无锁自旋 vs 阻塞"。volatile/原子变量靠自旋（读多写少、短临界区有利），锁/信号量靠阻塞（长等待有利）。交替打印等待时间较长，阻塞式更优。这是"同步原语选型"的对比。

示例代码

// volatile + 自旋：线程 i 打印第 i 个字符
volatile int turn = 0;
while (true) {
    while (turn != i) { /* 自旋 */ }
    System.out.print(ch); turn = (turn + 1) % 3;
}

#

★★

13. 手写限流器中令牌桶 vs 滑动窗口的精度、突发与内存复杂度对比？

问题

手写限流器，对比令牌桶与滑动窗口的精度、突发与内存复杂度？

考察点

令牌桶特性：允许突发、O(1) 内存
滑动窗口特性：精确、存时间戳
精度与突发权衡

答案

令牌桶：以恒定速率补充令牌，允许"积累的令牌"带来突发（burst），内存 O(1)（只存 tokens/lastRefillTime）。精度：基于速率积分，不精确限定"窗口内总请求数"，但能平滑突发。滑动窗口：维护窗口内时间戳，精确统计"最近窗口内请求数"达上限则拒绝，内存 O(窗口内请求数)（需存时间戳）。精度：更精确（无令牌桶的突发超过设定上限），但实现复杂、内存高。对比：令牌桶利于突发（积累令牌可一次性放行 burst），内存低；滑动窗口精确限流（平滑无突刺）、内存高。折中：令牌桶+限制 burst 上限，或滑动窗口+分桶。

解析

令牌桶是"速率控制 + 突发允许"（用桶容量 cap 突发），滑动窗口是"精确计数"（无突发、更平）。令牌桶 O(1) 内存更优，滑动窗口精确但内存 O(n)。选型看是否需要"允许突发"与精确性。

示例代码

// 令牌桶：O(1) 内存，允许 burst（tokens 上限）
// 滑动窗口：Deque<Long> 存时间戳，O(窗口请求数) 内存

#

★★

14. 手写 Future（带结果的异步任务）中如何用锁加条件变量保存结果、异常与取消状态？

问题

手写 Future，说明如何用锁加条件变量保存结果、异常与取消状态？

考察点

Future 的状态机（pending/done/cancelled）
锁 + 条件变量等待结果
get 阻塞、异常抛出、取消处理

答案

手写 Future：维护内部状态（result、exception、cancelled 标志、done 标志），用锁 + Condition 保护。setResult 时设置结果并标记 done、signalAll；get 时若未完成则 await（直到 done 或 cancelled），返回结果或抛异常。cancel 时标记 cancelled 并 signalAll。get 的阻塞：用 while(!done && !cancelled) cond.await()；完成后返回 result，若有异常则抛 ExecutionException。状态机：pending→(done 或 cancelled)。需要锁保证对共享状态的可见性与原子性，Condition 实现"等待完成"的阻塞。FutureTask 是 Java 标准实现。

解析

Future 是"异步结果 + 阻塞获取"的封装。核心是"锁 + 条件变量管理状态机"：set 时唤醒，get 时等待。异常与取消也纳入状态机，保证 get 能正确返回或抛出。这是"异步任务结果传递"的手写题。

示例代码

class MyFuture<T> {
    private final Object lock = new Object();
    private boolean done; private T result; private Throwable err; private boolean cancelled;
    void setResult(T r) { synchronized (lock) { result = r; done = true; lock.notifyAll(); } }
    T get() throws Exception {
        synchronized (lock) {
            while (!done && !cancelled) lock.wait(); // 等待完成
            if (cancelled) throw new CancellationException();
            if (err != null) throw new ExecutionException(err);
            return result;
        }
    }
    void cancel() { synchronized (lock) { cancelled = true; lock.notifyAll(); } }
}

#

★★

15. 手写线程池中任务队列、worker 线程与拒绝策略的完整实现？

问题

手写线程池，说明任务队列、worker 线程与拒绝策略的完整实现？

考察点

任务队列（阻塞队列）
worker 线程循环取任务执行
拒绝策略（超容时）

答案

线程池核心：① 任务队列：BlockingQueue 存待执行任务，worker 从队列取任务；② worker 线程：固定数量的线程循环从队列 take 任务执行；③ 线程管理：提交任务时若 worker 数未满则启动新 worker，满了则入队，队列满则按拒绝策略处理；④ 拒绝策略：队列满且 worker 满时，拒绝（抛异常/丢弃/调用线程执行/丢弃最旧）。生命周期：submit 把任务包装成 Runnable 入队，worker 循环执行；shutdown 停止接收新任务并等待队列清空。核心是"任务队列 + 固定 worker 循环取任务"，生产者（提交）与消费者（worker）解耦。Java 的 ThreadPoolExecutor 是标准实现，含核心线程数、最大线程数、队列、拒绝策略等参数。

解析

线程池是"生产者-消费者"的规模化应用：任务队列解耦提交与执行，worker 是消费者。拒绝策略处理"系统过载"边界。理解"核心/最大线程数 + 队列 + 拒绝策略"的参数组合是线程池设计的关键。

示例代码

// 简化线程池
class MyPool {
    BlockingQueue<Runnable> queue = new ArrayBlockingQueue<>(100);
    void execute(Runnable task) {
        if (!queue.offer(task)) { /* 拒绝策略 */ }
    }
    // worker 线程
    void worker() {
        while (true) {
            Runnable task = queue.take(); // 阻塞取任务
            task.run();
        }
    }
}

#

★★

16. 手写漏斗（leaky bucket）限流中恒定速率出水如何实现，与令牌桶在突发与内存上的差异

问题

手写漏斗（漏桶）限流，说明恒定速率出水如何实现，以及与令牌桶在突发与内存上的差异？

考察点

漏桶恒定速率出水
桶缓冲突发
与令牌桶对比

答案

漏桶：桶有容量（缓冲），水以恒定速率"出"（请求被以固定速率处理），请求到达时若桶满则丢弃。实现：维护桶内水量（当前积压）+ 上次出水时间，恒定速率 rate 出水，新请求为桶加水，超过容量则拒绝。恒定速率出水通常用"惰性计算"：每次请求时按 (now-lastTime)×rate 计算已流出的水量，更新桶水量。与令牌桶差异：漏桶是"恒定速率输出"（输出被限为固定速率，突发被缓冲），令牌桶是"允许突发"（积累令牌可瞬间放行 burst）。内存：漏桶/令牌桶都 O(1)（存桶状态）。漏桶更平滑（恒定速率），令牌桶更灵活（允许突发）。漏桶适合"必须恒定速率"（如网络限速），令牌桶适合"允许突发但总量受限"。

解析

漏桶是"恒定速率"的限流器，用桶缓冲积压、固定速率出水；令牌桶是"速率+突发"的限流器。两者都 O(1) 内存，区别在"是否允许突发"与"恒定 vs 灵活速率"。漏桶强制恒定，令牌桶允许尖峰。

示例代码

// 漏桶：恒定速率出水
class LeakyBucket {
    double rate, capacity, water, lastTime;
    boolean allow() {
        long now = System.currentTimeMillis();
        water = Math.max(0, water - (now - lastTime) * rate); // 出水
        lastTime = now;
        if (water < capacity) { water++; return true; } // 加水
        return false; // 桶满丢弃
    }
}

#

★

17. 生产者-消费者中用锁+条件变量与无锁队列（Ring Buffer）两种方式实现？

问题

生产者-消费者，用锁+条件变量与无锁队列（Ring Buffer）两种方式实现？

考察点

锁+条件变量阻塞式
无锁 Ring Buffer 自旋式
对比与适用

答案

锁+条件变量：用 BlockingQueue 或手写锁+Condition，生产者 put 满时阻塞、消费者 take 空时阻塞，阻塞省 CPU、正确性有保证。无锁 Ring Buffer：用环形数组 + 原子 head/tail 下标，生产者 CAS 推进 tail、消费者 CAS 推进 head，用内存屏障保证可见性，无锁（或 MPMC 用 CAS/版本号）。优点：无阻塞、高吞吐、低延迟，适合高性能场景（如 Disruptor）。缺点：实现复杂（需处理 CAS 竞态、内存屏障、单/多生产者消费者模式），且环形缓冲区满时需丢弃或忙等。对比：锁式简单安全、阻塞省 CPU；无锁式吞吐高、无阻塞但复杂。单生产者单消费者无锁 Ring Buffer 最简单（无需 CAS 竞争），多生产者多消费者需 CAS 与版本控制。

解析

锁式是"阻塞同步"，无锁式是"自旋 + CAS + 内存屏障"。Ring Buffer 用固定数组 + 原子下标实现无锁队列，是高性能中间件的核心。选型看吞吐需求与复杂度容忍度。

示例代码

// SPSC 无锁 Ring Buffer
class RingBuffer<T> {
    Object[] buf; int size; AtomicInteger head = new AtomicInteger(), tail = new AtomicInteger();
    boolean offer(T v) {
        int t = tail.get();
        if (t - head.get() >= size) return false; // 满
        buf[t % size] = v; tail.set(t + 1); return true;
    }
    T poll() {
        int h = head.get();
        if (h >= tail.get()) return null; // 空
        T v = (T) buf[h % size]; head.set(h + 1); return v;
    }
}

#

★

18. 手写对象池/连接池中借出、归还与超时回收的状态管理，泄漏如何检测

问题

手写对象池/连接池，说明借出、归还与超时回收的状态管理，以及泄漏如何检测？

考察点

借出/归还的状态管理
超时回收（idle 超时）
泄漏检测

答案

对象池/连接池：维护空闲队列（可用对象）与借用集合。借出：从空闲队列取对象，标记为"已借用"，加入借用集合；若无空闲则等待或新建。归还：从借用集合移除，重置对象状态，放回空闲队列并通知等待者。超时回收：为每个对象记录最后使用时间，后台线程定期扫描空闲队列，回收"空闲超过阈值"的对象（释放连接）。泄漏检测：借出时记录借用者与时间；若对象借出超时未归还，则告警/强制回收；或用"借用集合大小"监控，异常增长提示泄漏。状态管理核心是"空闲/借用/已回收"三态的流转与并发安全（用锁或并发集合）。

解析

对象池是"有限资源复用"的设计，核心是"借出/归还/回收"的状态机与并发控制。超时回收防资源泄漏，借用记录支持泄漏检测。连接池（如数据库连接池）是典型应用。

示例代码

class ObjectPool<T> {
    Deque<T> idle = new ArrayDeque<>(); Set<T> borrowed = new HashSet<>();
    T borrow() {
        synchronized (this) {
            T obj = idle.poll();
            if (obj == null) obj = create();
            borrowed.add(obj); return obj;
        }
    }
    void return_ (T obj) {
        synchronized (this) {
            borrowed.remove(obj); idle.add(obj); notifyAll();
        }
    }
}

#

★

19. 设计多线程任务分发，生产者-消费者加结果聚合如何实现带依赖的任务执行，与线程池 submit 的取舍

问题

设计多线程任务分发，说明生产者-消费者加结果聚合如何实现带依赖的任务执行，与线程池 submit 的取舍？

考察点

生产者-消费者分发
结果聚合（Future）
带依赖任务（DAG）

答案

多线程任务分发：生产者提交任务到队列，消费者（worker 线程）执行并返回结果，结果聚合（用 Future 或收集结果到容器）。带依赖任务：任务间有依赖关系（DAG），需先完成依赖任务再执行后续。实现：① 用拓扑排序确定执行顺序，或② 用"任务完成回调"（每个任务完成后触发依赖它的任务，用 CompletableFuture 的 then 链）；③ 或用"依赖计数"（每个任务记录依赖数，依赖完成则计数减 1，归零才可执行）。与线程池 submit 对比：线程池 submit 适合"无依赖的独立任务"（提交即执行，结果用 Future.get 获取）；带依赖任务需自定义调度（依赖拓扑/回调），线程池本身不处理依赖。取舍：简单独立任务用线程池 submit；带依赖任务用 CompletableFuture/自定义 DAG 调度，或并行流。

解析

任务分发是"生产者-消费者 + 结果聚合"；带依赖任务是"DAG 调度"（用拓扑/回调/依赖计数）。线程池 submit 是"无依赖任务"的便捷封装，带依赖需额外机制。这是"任务调度"从简单到复杂的设计。

示例代码

// 带依赖任务：CompletableFuture 链式
CompletableFuture<Integer> a = CompletableFuture.supplyAsync(() -> computeA());
CompletableFuture<Integer> b = a.thenApplyAsync(x -> computeB(x)); // 依赖 a
// 或依赖计数：每个任务先 await 依赖，计数归零才执行