- **正确答案**：使用 ConcurrentHashMap + 双向链表（或 Java 内置的 LinkedHashMap 配合重写 removeEldestEntry）可实现线程安全、O(1) 的 LRU 缓存；但严格满足线程安全 + O(1) get/put 的工业级方案是：**ConcurrentHashMap + 分段锁（或 CAS + volatile 节点引用）维护双向链表头尾，链表节点使用原子更新指针的方式维护访问顺序**。更优且简洁的实践方案是：**基于 ReentrantLock 分段保护双向链表 + ConcurrentHashMap 映射 key→Node，每个操作锁定最小粒度（仅锁链表头尾及当前节点邻接关系），避免全局锁**。最终推荐实现为：自定义 Node 类 + ConcurrentHashMap 存储 key→Node + 一个 ReentrantLock（或更细粒度的读写锁/StripeLock）保护链表结构变更，get 和 put 均在锁内完成节点移动和头插/淘汰，时间复杂度严格 O(1)。 - **解答思路**： 1. LRU 核心需求：最近最少使用淘汰策略 → 需要按访问时间序维护元素，且能快速定位、删除任意节点、插入到头部； 2. O(1) 要求 → 查找必须哈希（HashMap/ConcurrentHashMap），删除/插入位置必须支持 O(1)（双向链表）； 3. 线程安全要求 → 不能只用 Collections.synchronizedMap 或简单 synchronized 方法块（会串行化所有操作，违背高并发场景）； 4. 关键冲突点：ConcurrentHashMap 支持并发读写 key→Node 映射，但双向链表的结构调整（如 move-to-head、unlink、evict tail）是非原子的多步操作（修改 prev/next 指针），必须同步； 5. 折中方案：对链表操作加锁，但锁粒度要小——不锁整个 cache，而只锁链表结构本身（一个共享锁即可，因为链表修改是互斥的临界区）；ConcurrentHashMap 的 get/put(key) 本身线程安全，但我们的 get 需要“查+挪动节点”，put 需要“存+挪动+可能淘汰”，因此所有涉及链表修改的操作必须进入同一临界区； 6. 最终确定：一个 ReentrantLock 控制链表结构变更（insertHead、unlink、detachTail），ConcurrentHashMap 用于 O(1) 定位 Node；所有 public 方法中，先从 map 获取 Node（无锁），再 lock → 检查是否仍有效（防止 get 时被其他线程淘汰）、执行链表调整、必要时更新 map（put 新节点或 remove 淘汰节点）。 - **深度知识讲解**：【底层数据结构】 - LRU 本质是「有序哈希表」：哈希提供 O(1) 定位，有序性由双向链表保证。单向链表无法 O(1) 删除中间节点（需前驱），故必须双向。 - Node 结构必须含：key（用于 map 删除时反查）、value、volatile Node prev、volatile Node next —— volatile 保证多线程下指针更新可见性（虽锁已保证原子性，但作为防御性设计）。 - ConcurrentHashMap：Java 8+ 使用 CAS + synchronized on node（非全局锁），支持高并发读、分段写；其 size() 是估算值，但本场景无需 size 统计，仅作 key→Node 映射，完全适用。【线程安全关键点】 - ABA 问题？此处无 CAS 修改同一地址多次的场景（链表操作均在锁内），无需 AtomicStampedReference； - 锁升级？ReentrantLock 支持公平/非公平、可中断、超时，比 synchronized 更可控；选用非公平锁（默认）以提升吞吐； - “双重检查”陷阱：不能在 lock 外做 if (map.containsKey(k)) → lock → map.get(k)，因为中间可能被其他线程 remove；正确做法是 lock 后统一处理：先 get Node，若 null 则创建并插入；若非 null，则 detach 再 insertHead； - 淘汰时机：put 时若 size > capacity，必须在 lock 内 detach tail 并从 map 中 remove，确保 map 和链表状态一致（强一致性）；否则出现 map 有残留 key，链表无对应节点，导致内存泄漏或下次 get 返回 null。【为何不用 LinkedHashMap？】 - LinkedHashMap 的 accessOrder=true 虽天然支持 LRU 顺序，但其迭代器、get、put 均未加锁，且内部链表操作非线程安全； - 若包装为 Collections.synchronizedMap(new LinkedHashMap(...))，则所有方法被 synchronized(this) 包裹，变成串行执行，get/put 无法并发，违背 O(1) 平均吞吐预期； - 重写 removeEldestEntry 仅在 put 后触发，但该方法执行时 map 已更新，无法安全淘汰（竞态下可能淘汰错误节点）；且无并发控制。【扩展优化方向】 - 分段锁（StripeLock）：将链表逻辑分 N 段，每段配独立锁，降低争用（适用于超大容量、超高并发）； - 无锁链表（Lock-Free List）：理论上可用 Michael-Scott 队列思想，但 LRU 需双向遍历+任意节点删除，无锁实现极其复杂且易出错，工程中不推荐； - Caffeine 的 W-TinyLFU + Segmented Clock Queue：现代高性能缓存采用近似 LRU + 频率过滤，兼顾时间局部性与空间局部性，但已超出纯 LRU 范畴。 - **代码示例（Java，精简可运行版）**： ``` import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.locks.ReentrantLock; public class ThreadSafeLRUCache { private final int capacity; private final ConcurrentHashMap> map; private final Node head; // dummy head private final Node tail; // dummy tail private final ReentrantLock lock; public ThreadSafeLRUCache(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; this.map = new ConcurrentHashMap<>(); this.head = new Node<>(null, null); this.tail = new Node<>(null, null); this.head.next = tail; this.tail.prev = head; this.lock = new ReentrantLock(); } public V get(K key) { Node node = map.get(key); if (node == null) return null; lock.lock(); try { // Re-check: node may be evicted during lock wait if (map.get(key) != node) return null; detach(node); insertToHead(node); return node.value; } finally { lock.unlock(); } } public void put(K key, V value) { Node node = map.get(key); lock.lock(); try { if (node != null) { node.value = value; detach(node); insertToHead(node); } else { node = new Node<>(key, value); map.put(key, node); insertToHead(node); if (map.size() > capacity) { Node toEvict = tail.prev; detach(toEvict); map.remove(toEvict.key); // safe: key unique, no race with other put } } } finally { lock.unlock(); } } private void detach(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void insertToHead(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } private static class Node { final K key; V value; volatile Node prev; volatile Node next; Node(K key, V value) { this.key = key; this.value = value; } } } ``` 【代码说明】 - 使用哨兵头尾节点（dummy head/tail）极大简化边界判断（无需判空）； - 所有链表结构修改（detach/insertToHead）仅在 lock 内执行，保证原子性； - map.remove(toEvict.key) 安全：因 key 在 map 中唯一，且淘汰前已 detach，其他线程无法通过该 key 访问到此 node，remove 不会误删； - get 中二次校验 map.get(key) == node：防御锁等待期间该 node 被其他 put 淘汰（虽然概率低，但符合强一致性要求）； - volatile 修饰 prev/next：确保多核 CPU 下指针更新立即对其他线程可见（即使锁已保证顺序，此为冗余保障）。

客户端开发一面手撕

全站热榜

创作者周榜