- **正确答案**：需要实现一个线程安全的 Map 结构，支持 put（set）和 get 操作。当调用 get 一个不存在的 key 时，线程会阻塞等待该 key 被 put 进来，直到超时或被唤醒。可以使用 Java 中的 ConcurrentHashMap 配合 Condition 或使用 BlockingQueue 思想模拟等待机制，也可以使用 synchronized + wait/notify + 超时控制实现。 - **解答思路**： 1. 使用线程安全的存储结构（如 ConcurrentHashMap）保存键值对。 2. 对于 get 操作，如果 key 不存在，当前线程应进入等待状态，并在指定超时时间内等待其他线程通过 set 添加该 key。 3. set 操作放入键值后，应通知所有等待该 key 的线程（或所有等待线程）进行唤醒检查。 4. 注意超时处理：get 必须支持带超时时间的阻塞，不能无限等待。 5. 可以使用每个 key 对应一个等待队列的 condition，或者统一管理等待线程。实际上，Java 并没有直接提供“按 key 等待”的并发工具，因此我们需要手动实现等待/通知机制。 - **深度知识讲解**： **1. 底层数据结构选择**： - 存储 key-value：ConcurrentHashMap 是首选，保证线程安全且高并发读写性能好。 - 等待机制：每个 key 可能有多个线程在等待，可以用 ReentrantLock + Condition 实现精确唤醒，或者使用 Object 的 wait/notify 配合 synchronized。 **2. Condition vs wait/notify**： - Condition 更灵活，可以为每个 key 创建独立的等待队列。 - 使用 ReentrantLock 和 Condition 可以实现精准唤醒等待某个 key 的线程。 - wait/notifyAll 则可能造成“惊群效应”，即 notifyAll 唤醒所有线程，但只有目标 key 的线程能继续。 **3. 超时控制原理**： - 使用 Condition.awaitNanos(long nanosTimeout) 可以实现精确超时等待。 - 或使用 Object.wait(long timeout) 实现毫秒级超时。 **4. 线程安全与内存可见性**： - 所有共享变量访问必须保证可见性和原子性。 - 使用 volatile 或锁机制确保 set 后 get 能立即看到更新。 **5. 扩展考虑**： - 是否允许 null key/value？ - 是否支持重复 set？覆盖是否触发通知？ - 是否支持 remove 操作？ - 是否需要限制最大等待时间或总等待线程数？ - **代码示例（Java 风格伪代码）**： ``` class BlockingMap { // 存储实际数据 private final ConcurrentHashMap map = new ConcurrentHashMap<>(); // 锁和条件变量的映射：每个 key 对应一个锁和 condition private final ConcurrentHashMap lockMap = new ConcurrentHashMap<>(); private final ConcurrentHashMap conditionMap = new ConcurrentHashMap<>(); // 获取锁和 condition，懒初始化 private ReentrantLock getOrCreateLock(K key) { return lockMap.computeIfAbsent(key, k -> new ReentrantLock()); } private Condition getOrCreateCondition(K key) { ReentrantLock lock = getOrCreateLock(key); Condition cond = conditionMap.get(key); if (cond == null) { // 必须在持有 lock 的情况下创建 condition lock.lock(); try { // double-check cond = conditionMap.get(key); if (cond == null) { cond = lock.newCondition(); conditionMap.put(key, cond); } } finally { lock.unlock(); } } return cond; } // set 操作：放入值并通知等待者 public void set(K key, V value) { map.put(key, value); Condition cond = conditionMap.get(key); if (cond != null) { ReentrantLock lock = getOrCreateLock(key); lock.lock(); try { cond.signalAll(); // 唤醒所有等待这个 key 的线程 } finally { lock.unlock(); } } } // get 操作：最多等待 timeoutMs 毫秒 public V get(K key, long timeoutMs) throws InterruptedException { V value = map.get(key); if (value != null) { return value; } // 获取该 key 的 condition Condition cond = getOrCreateCondition(key); ReentrantLock lock = getOrCreateLock(key); lock.lock(); try { // 再次检查，避免虚假唤醒 value = map.get(key); if (value != null) { return value; } // 开始等待 long startTime = System.nanoTime(); long remainingNanos = timeoutMs * 1_000_000L; while (remainingNanos > 0) { long awaitStart = System.nanoTime(); // 等待最多 remainingNanos 纳秒 cond.awaitNanos(remainingNanos); // 检查是否已有值 value = map.get(key); if (value != null) { return value; } // 更新剩余时间 long elapsed = System.nanoTime() - awaitStart; remainingNanos -= elapsed; } // 超时仍未获取到 return null; } finally { lock.unlock(); } } // 无超时的 get（不推荐，可能永久阻塞） public V get(K key) throws InterruptedException { V value = map.get(key); if (value != null) return value; Condition cond = getOrCreateCondition(key); ReentrantLock lock = getOrCreateLock(key); lock.lock(); try { while ((value = map.get(key)) == null) { cond.await(); // 无限等待 } return value; } finally { lock.unlock(); } } } ``` - **补充说明与优化点**： 1. **资源清理问题**：当一个 key 被 set 后，其对应的 Lock 和 Condition 占用内存不会自动释放。可考虑在 get 返回后清理，但需注意并发 set/get 同时发生的情况。解决方案：可以在 get 成功返回后尝试移除 lock 和 condition，但要加全局清理锁或使用弱引用。 2. **使用 Future/Promise 模式替代**：更优雅的方式是返回一个 CompletableFuture，让调用方异步获取结果： ``` CompletableFuture getValue(K key); void setValue(K key, V value); ``` 内部维护一个 Map>，get 时若不存在则创建并放入；set 时完成 future。示例： ``` private final ConcurrentHashMap> futures = new ConcurrentHashMap<>(); public CompletableFuture getValue(K key) { return futures.computeIfAbsent(key, k -> new CompletableFuture<>()); } public void setValue(K key, V value) { CompletableFuture f = futures.get(key); if (f != null) { f.complete(value); } // 可选：putIfAbsent 创建后再 complete，保证至少有一个 future 被通知 futures.compute(key, (k, f) -> { if (f == null) { f = new CompletableFuture<>(); f.complete(value); } else { f.complete(value); } return f; }); } ``` 此方式更简洁、高效，天然支持超时： ``` V result = map.getValue("key").get(5, TimeUnit.SECONDS); // 支持超时 ``` 3. **适用场景**： - 分布式协调中的配置等待 - 异步结果传递（生产者-消费者） - RPC 调用结果匹配（请求 id -> response） 4. **底层原理关联**： - Java 并发包中 `BlockingQueue` 的 take/poll(timeout) 就是类似思想。 - Netty 中的 Promise/Future 模型。 - Spring 的 DeferredResult，用于 Web 异步响应。 - **总结**：本题考察的是多线程同步、等待通知机制、超时控制、线程安全数据结构的综合运用。最优解是使用 CompletableFuture 模式，代码简洁且功能强大；次优解是手动实现 Condition 等待机制。面试中应优先提出 CompletableFuture 方案，体现对高阶并发工具的理解。

高德 秋招一面

全站热榜

创作者周榜

高德秋招一面