public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // 第三个参数 accessOrder=true 开启访问顺序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // 容量超过阈值时，淘汰最久未使用的节点
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

手撕 LRU 核心实现 ✍️

面试常要求从零手写，核心是自己实现双向链表 + 哈希表，代码如下：

public class LRUCache {
    // 双向链表节点
    static class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private final int capacity;
    // 虚拟头尾节点：规避边界空指针判断，简化代码
    private final DLinkedNode head;
    private final DLinkedNode tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    // 查询：O(1)
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        // 访问后移到链表头，标记为最近使用
        moveToHead(node);
        return node.value;
    }

    // 写入/更新：O(1)
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 新节点：插头部，超容量则淘汰尾节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode oldTail = removeTail();
                cache.remove(oldTail.key);
                size--;
            }
        } else {
            // 已存在：更新值，移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    // --- 辅助方法：均为 O(1) 操作 ---
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

手写加分点 ✨

用虚拟头尾节点规避边界判空，减少代码冗余，降低出错概率
节点同时存 key+value，淘汰时能同步清理哈希表
抽取公共辅助方法，逻辑分层清晰

高频追问速答 🧐

1.get/put 的时间复杂度？

均为 O (1)，哈希查询、链表增删都是常数时间。

2.LRU 有什么缺陷？

存在缓存污染：一次批量冷数据访问，会把热点数据全部挤出缓存（比如全表扫描场景）。

3.常见优化方案？

LRU-K、2Q 算法、冷热数据分离 LRU，降低缓存污染的影响。

4.和 LFU 的区别？

LRU 看「最近访问时间」，LFU 看「历史访问次数」；LFU 能保留高频热点，但实现复杂，冷数据可能长期不淘汰。

核心亮点代码拆解 🎯

我把面试中最能体现编码功底的核心片段单独拆解，每一处都是评分加分项：

1. 虚拟哨兵节点设计（高频加分点）

// 初始化虚拟头尾哨兵节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;

✅ 技术亮点：用两个无业务意义的哨兵节点统一所有增删操作的边界逻辑，彻底规避头尾节点为空的 if-else 判空分支，代码简洁且不易出 bug，是工业级实现的标准写法。

2. 原子操作分层封装

// 三个底层原子操作，所有业务逻辑都基于它们组合实现
private void addToHead(DLinkedNode node) { ... }
private void removeNode(DLinkedNode node) { ... }
private void moveToHead(DLinkedNode node) {
    removeNode(node);
    addToHead(node);
}

✅ 技术亮点：遵循单一职责原则，把链表底层操作和业务逻辑解耦；moveToHead 由两个原子操作组合而成，代码零冗余，可读性和可维护性拉满。

3. 淘汰逻辑的一致性保证

if (size > capacity) {
    DLinkedNode oldTail = removeTail();
    // 必须通过节点内的key反向删除哈希表映射
    cache.remove(oldTail.key);
    size--;
}

✅ 技术亮点：节点同时存储 key 和 value，淘汰时能反向定位哈希表的 key，保证双数据结构的强一致性；如果只存 value，会出现链表删了但哈希表残留的内存泄漏问题。

4. 生产级极简实现（工程落地首选）

// 仅重写1个方法，基于JDK原生能力实现完整LRU
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > capacity;
}

✅ 技术亮点：基于 JDK 原生LinkedHashMap实现，经过亿级场景验证，性能和稳定性远高于手写实现，是真实业务项目中的首选方案。

技术难点与解决方案对照表 🧩

技术难点	问题影响	对应解决方案
如何保证`get/put`双操作均为 O (1) 时间复杂度	单一数据结构无法同时满足快速查询和快速排序，性能不达标	哈希表 + 双向链表组合架构：哈希表负责 O (1) 查询定位，双向链表负责 O (1) 维护访问顺序和节点增删
链表头尾边界操作频繁出现空指针异常	代码充斥大量判空分支，冗余且易出错	引入虚拟头尾哨兵节点，所有节点操作都在中间区域执行，彻底消除边界判空逻辑
哈希表与双向链表数据不一致	出现内存泄漏、脏读、重复 key 等隐蔽问题	1. 节点同时存储 key+value，淘汰时双向同步删除； 2. 所有写操作必须同时更新两个数据结构，封装成原子方法
多线程并发读写场景下线程不安全	链表断链、死循环、数据错乱	1. 简单方案：对读写方法加读写锁； 2. 生产方案：直接使用 Caffeine、Guava Cache 等成熟的线程安全缓存组件
LRU 缓存污染：批量冷数据访问冲掉全部热点数据	缓存命中率骤降，接口性能雪崩	1. 算法优化：升级为 LRU-K、2Q 算法； 2. 工程优化：冷热数据分区链表，冷数据区访问多次才晋升热数据区
大缓存场景下的内存溢出与 GC 压力	服务频繁 GC 卡顿，甚至 OOM 宕机	1. 增加过期时间淘汰机制； 2. 对非核心数据用软引用 / 弱引用包装； 3. 限制单 value 最大体积，超大值不走本地缓存

真实面试模拟

面试官 🤝：

同学你好，先做个简单自我介绍吧，然后咱们直接进入正题。今天想和你探讨一道经典题目——实现一个 LRU 缓存。

不急着写代码，先说说你的理解，LRU 是什么，你打算怎么设计？

候选人 💡：

面试官好。LRU 就是 Least Recently Used，当缓存容量满了以后，优先淘汰最久没被访问的数据。

为了保证 get 和 put 都是 O(1)，我计划用 双向链表 + 哈希表 的组合。

双向链表维护访问顺序，头是最近访问，尾是最久未访问；
哈希表用来 O(1) 查找 key 对应的节点。

访问数据时，把节点移到链表头部；淘汰时，删除尾部节点并在哈希表中移除。

面试官 👍：

思路很清晰，虚拟头尾是防止空指针的好习惯。

那现在请你把核心代码写一下，get 和 put 的实现，时间复杂度 O(1)。

候选人 🚀：

好的。我写一个泛型缓存吧，代码带详细注释：

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // 虚拟头
    private final Node tail = new Node(0, 0); // 虚拟尾

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);   // 标记为最近使用
        return node.val;
    }

    public void put(int key, int val) {
        Node node = map.get(key);
        if (node != null) {
            node.val = val;
            moveToHead(node);       // 更新也要移动
        } else {
            Node newNode = new Node(key, val);
            map.put(key, newNode);
            addToHead(newNode);
            if (map.size() > capacity) {
                Node last = removeTail();
                map.remove(last.key); // 淘汰尾部
            }
        }
    }

    // ----- 原子操作 -----
    private void addToHead(Node n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    private void removeNode(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void moveToHead(Node n) {
        removeNode(n);
        addToHead(n);
    }

    private Node removeTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }
}

面试官 🔍：

不错，moveToHead 复用 removeNode + addToHead 很干净。

那我想问两个延伸点：

不用手写双向链表，Java 里有现成的类能快速实现吗？
你的实现是线程安全的吗？如果不是，怎么处理并发场景？

候选人 🧠：

有的，可以用 LinkedHashMap，它内部就是哈希表 + 双向链表。

设置 accessOrder = true，再重写 removeEldestEntry 就能轻松实现：

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
    private final int capacity;
    public LRULinkedHashMap(int capacity) {
        super(capacity, 0.75f, true); // 按访问顺序
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > capacity;
    }
}

我手写的版本非线程安全。并发下链表可能断链或哈希表不一致。

改进思路：

简单粗暴：Collections.synchronizedMap，但复合操作仍需外部同步。
方法加 synchronized，锁粒度大，性能一般。
更优：使用 ReentrantReadWriteLock，读多写少场景性能好。
企业级：直接使用 Guava 的 Cache 或 Caffeine，内部用分段锁 + LRU 变体。

面试官 😃：

很好，能横向对比工具类，还能聊到并发优化，说明你对集合框架和并发包都比较熟。

📊 面试总结卡

考点	关键点
数据结构	HashMap + 双向链表，虚拟头尾
时间复杂度	get / put 均为 O(1)
空间复杂度	O(capacity)
现成实现	LinkedHashMap (accessOrder = true)
线程安全	加锁 / 读写锁 / Guava Cache
常见变体	LFU（需频次表）、带过期时间的 LRU

💡 面试官小贴士

画图能大幅降低链表指针错误率。
容易漏掉的点：put 更新已存在节点时，除了改值，必须移到头部。
如果问「带过期时间」，可在节点加 expireTime，get 时惰性删除，或后台线程定期清理。

🔥 核心代码与亮点

手写 LRU 完整代码（带注释）：

class LRUCache {
    // 1. 双向链表节点
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // 虚拟头
    private final Node tail = new Node(0, 0); // 虚拟尾

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);          // 最近访问 → 移到头部
        return node.val;
    }

    public void put(int key, int val) {
        Node node = map.get(key);
        if (node != null) {
            node.val = val;
            moveToHead(node);      // ⚠️ 更新也必须移到头部
        } else {
            Node newNode = new Node(key, val);
            map.put(key, newNode);
            addToHead(newNode);
            if (map.size() > capacity) {
                Node last = removeTail();
                map.remove(last.key);  // 淘汰最久未使用
            }
        }
    }

    // ---------- 原子链表操作（高内聚） ----------
    private void addToHead(Node n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    private void removeNode(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void moveToHead(Node n) {
        removeNode(n);
        addToHead(n);
    }

    private Node removeTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }
}

🌟 技术亮点

1.虚拟头尾节点

避免空指针判断，所有插入/删除操作统一处理，代码简洁不易出错。

2.原子操作拆分

addToHead / removeNode / moveToHead / removeTail 四个方法高内聚复用，任何链表结构调整只需调用它们，逻辑清晰。

3.O(1) 时间复杂度

HashMap 负责 O(1) 查找，双向链表负责 O(1) 的节点插入、删除、移动，二者结合实现严格 O(1) 的 get 和 put。

4.更新操作必须移到头部

put 已存在 key 时，不仅要改值，还要执行 moveToHead，这是最容易遗漏的细节。

5.LinkedHashMap 快捷实现

面试中顺口提到 new LinkedHashMap(capacity, 0.75f, true) 并重写 removeEldestEntry，展示 JDK 源码熟悉度。

⚙️ 技术难点与解决方案

难点	具体表现	解决方案
链表指针错误	节点删除、移动时容易断链或形成环	画图辅助；虚拟头尾简化边界；提取 `addToHead` / `removeNode` 原子方法复用
淘汰时哈希映射不同步	只删链表尾节点，忘记 `map.remove(key)`，导致内存泄漏或逻辑错误	封装 `removeTail()` 返回被删节点，调用方立刻从 map 中移除
put 更新时不移动节点	更新已有 key 的值，但节点仍在原位置，导致本来最近访问的反而被提前淘汰	明确规则：任何访问（get / put 更新）都必须 `moveToHead`
多线程并发异常	链表结构和 HashMap 都不是线程安全的，并发下可能死循环或 null 指针	1. 方法加 `synchronized` 2. 使用 `ReentrantReadWriteLock` 提升读并发 3. 直接使用 `ConcurrentLinkedHashMap` 或 Caffeine
容量限制与扩缩容	固定容量下，连续 put 不同 key 必须立即淘汰，不可溢出	`if (map.size() > capacity)` 在插入新节点后判断，保证容量严格控制
LRU 变体扩展	面试官可能追问 LFU（最少频次使用）、带过期时间的 LRU	LFU：新增 `freq` 哈希表；TTL：节点加 `expireTime`，`get` 时惰性删除或后台线程定时清理

面试官总结

今天这道 LRU，你不但能手写出 O(1) 的高内聚代码，还能讲清楚链表操作的边界处理、LinkedHashMap 的便捷实现、以及并发场景的升级方案，表现非常扎实 👍。

把上面的核心代码和难点表多看两遍，下次遇到同类题直接平推！