👋 大家好，欢迎来到我的技术博客！
💻 作为一名热爱 Java 与软件开发的程序员，我始终相信：清晰的逻辑 + 持续的积累 = 稳健的成长。
📚 在这里，我会分享学习笔记、实战经验与技术思考，力求用简单的方式讲清楚复杂的问题。
🎯 本文将围绕数据结构与算法这个话题展开，希望能为你带来一些启发或实用的参考。
🌱 无论你是刚入门的新手，还是正在进阶的开发者，希望你都能有所收获！

---

数据结构与算法 - 面试手撕：LRU缓存的设计与实现 💾

在系统设计和算法面试中，LRU 缓存（Least Recently Used Cache） 是一道高频经典题。它不仅考察你对基础数据结构（哈希表、双向链表）的掌握，还检验你对时间复杂度优化、内存管理、工程权衡的理解。无论是 LeetCode 第 146 题，还是 Google、Amazon、字节跳动等大厂的后端/系统岗面试，LRU 几乎是必考内容。

本文将带你从零开始，深入剖析 LRU 缓存的核心思想、设计难点，并提供 多种 Java 实现方案——从朴素版本到工业级优化，再到 JDK 内置工具类的使用。我们还将通过 mermaid 可视化图表 展示缓存的访问与淘汰过程，分析时间/空间复杂度，并探讨其在真实系统（如 Redis、操作系统页缓存）中的应用场景。无论你是准备面试，还是想提升系统设计能力，这篇文章都会成为你的坚实后盾！🚀

---

什么是 LRU 缓存？🤔

LRU（Least Recently Used，最近最少使用） 是一种常用的缓存淘汰策略。它的核心思想非常直观：

“当缓存满时，优先淘汰最久未被访问的数据。”

举个生活中的例子 🍎：
你有一个只能放 3 个水果的果盘（缓存容量=3）。今天你依次拿了苹果、香蕉、橙子。明天你想吃葡萄，但果盘满了，于是你把最早拿的苹果扔掉，放入葡萄。如果这时你又想吃香蕉，就把它拿出来再放回去（表示“最近使用”），那么下次淘汰的就是橙子。

在计算机中，LRU 被广泛用于：

• 操作系统的页面置换算法
• 数据库的缓冲池管理
• Web 服务器的热点数据缓存
• 浏览器的历史记录/Tab 管理

✅ 面试关键点：LRU 的 get 和 put 操作必须都是 O(1) 时间复杂度，否则无法满足高性能要求。

---

LRU 的核心操作要求 ⚙️

一个标准的 LRU 缓存需要支持以下两个方法：

// 获取 key 对应的 value；若不存在，返回 -1
int get(int key);

// 插入或更新 key-value；若缓存已满，需淘汰最久未使用的项
void put(int key, int value);

同时满足：

• 容量固定（capacity）
• 自动淘汰（当 size > capacity 时）
• 访问即更新（get 或 put 已存在的 key 会将其变为“最近使用”）

例如：

LRUCache cache = new LRUCache(2); // 容量为2
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1 → 此时 1 变为最近使用
cache.put(3, 3);    // 淘汰 2（因为 1 刚被访问过）
cache.get(2);       // 返回 -1（2 已被淘汰）

---

设计挑战：如何实现 O(1) 的 get 和 put？🧩

要实现 O(1) 的 get 和 put，我们需要同时解决两个问题：

1. 快速查找：给定 key，能否在 O(1) 内找到 value？→ 哈希表（HashMap）
2. 快速定位最久未使用项并更新顺序：如何知道哪个元素最老？如何将刚访问的元素移到“最新”位置？→ 双向链表（Doubly Linked List）

为什么需要双向链表？

• 单向链表无法在 O(1) 内删除中间节点（需要前驱指针）
• 双向链表支持 头插（最新） 和 尾删（最旧），且能 O(1) 删除任意节点

组合策略：哈希表 + 双向链表

• HashMap<key, Node>：存储 key 到链表节点的映射
• DoublyLinkedList：按访问时间排序，头部 = 最近使用，尾部 = 最久未使用

这个结构可以用下面的 mermaid 图 清晰表示：

graph LR
    A[HashMap] -->|key=1| B[Node(1,1)]
    A -->|key=2| C[Node(2,2)]
    A -->|key=3| D[Node(3,3)]

    subgraph DoublyLinkedList
        B <--> C
        C <--> D
    end

    style B fill:#cff,stroke:#333
    style C fill:#cfc,stroke:#333
    style D fill:#fcc,stroke:#333

    note1["Head (最近使用)"] --> B
    D --> note2["Tail (最久未使用)"]

💡 关键洞察：每次 get 或 put 时，都将对应节点移动到链表头部；当容量满时，删除尾部节点并从 HashMap 中移除。

---

方案一：手写双向链表 + HashMap（面试推荐）✍️

这是面试中最常考察的实现方式，展示你对底层数据结构的掌控力。

步骤分解：

1. 定义双向链表节点 Node
2. 维护虚拟头尾节点（dummy head/tail），简化边界处理
3. 实现 addToHead(node)、removeNode(node)、moveToHead(node)、removeTail() 等辅助方法
4. 在 get 和 put 中调用这些方法

Java 代码实现

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node() {}

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, Node> cache = new HashMap<>();
    private int capacity;
    private int size;
    private Node head; // 虚拟头节点
    private Node tail; // 虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        // 初始化虚拟头尾，互相连接
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 将该节点移到头部（标记为最近使用）
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            // 新增节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 淘汰尾部节点
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
                --size;
            }
        } else {
            // 更新现有节点
            node.value = value;
            moveToHead(node);
        }
    }

    // --- 辅助方法 ---

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

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

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

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

    // 测试
    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1)); // 1
        lru.put(3, 3); // 淘汰 2
        System.out.println(lru.get(2)); // -1
        lru.put(4, 4); // 淘汰 1
        System.out.println(lru.get(1)); // -1
        System.out.println(lru.get(3)); // 3
        System.out.println(lru.get(4)); // 4
    }
}

✅ 面试亮点：

• 使用虚拟头尾节点避免空指针判断
• 方法职责清晰（moveToHead = remove + add）
• 时间复杂度：get/put 均为 O(1)，空间复杂度 O(capacity)

---

方案二：利用 Java 内置 LinkedHashMap（简洁版）⚡

Java 的 LinkedHashMap 天然支持按访问顺序排列，只需重写 removeEldestEntry 方法即可实现 LRU！

Java 代码实现

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheSimple extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCacheSimple(int capacity) {
        // accessOrder=true 表示按访问顺序排序（而非插入顺序）
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    // 当 map.size() > capacity 时，自动删除最旧条目
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCacheSimple lru = new LRUCacheSimple(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1)); // 1
        lru.put(3, 3);
        System.out.println(lru.get(2)); // -1
    }
}

💡 优势：代码极简，适合快速实现或笔试。

⚠️ 注意：accessOrder=true 是关键！默认是 false（按插入顺序）。

🔗 官方文档：Java LinkedHashMap

---

LRU 缓存的执行过程可视化 📊

让我们用 mermaid 序列图 模拟一次完整的 LRU 操作流程（capacity=2）：

可以看到，每一步都严格维护了“最近使用在前”的顺序，并在溢出时淘汰尾部。

---

常见变种与扩展问题 🧪

1. 带过期时间的 LRU（TTL LRU）

• 每个 entry 增加 expireTime
• get 时检查是否过期，过期则删除
• 可结合定时任务清理（或懒删除）

2. 线程安全的 LRU

• 使用 ConcurrentHashMap + ReentrantLock
• 或直接使用 Collections.synchronizedMap（性能较差）
• 更优方案：分段锁（类似 ConcurrentHashMap）

3. LFU vs LRU

• LFU（Least Frequently Used）：淘汰使用频率最低的
• 适用于“热点数据长期稳定”的场景
• 实现更复杂（需维护频次计数）

📘 对比参考：LRU vs LFU – GeeksforGeeks

---

LRU 在真实系统中的应用 🌍

1. Redis 的 maxmemory-policy

Redis 支持多种淘汰策略，其中 allkeys-lru 和 volatile-lru 就是基于 LRU 思想（实际是近似 LRU，用随机采样优化性能）。

🔗 官方文档：Redis Maxmemory Policies

2. 操作系统页面缓存

Linux 的 Page Cache 使用 LRU 或其变种（如 LRU-K）管理内存页，确保频繁访问的文件数据驻留内存。

3. 浏览器缓存

Chrome 等浏览器对 HTTP 缓存使用 LRU 策略，避免磁盘缓存无限增长。

4. 数据库 Buffer Pool

MySQL InnoDB 的 Buffer Pool 使用改进版 LRU（分为 young 和 old 区域），防止全表扫描污染缓存。

📚 深入阅读：MySQL Buffer Pool LRU

---

性能分析与复杂度 📈

操作	时间复杂度	空间复杂度
get(key)	O(1)	O(1)
put(key, value)	O(1)	O(1) （均摊）
总体空间	—	O(capacity)

✅ 为什么是 O(1)？

• HashMap 查找/插入：平均 O(1)
• 双向链表头插/尾删/中间删：O(1)
• 淘汰操作只发生在 put 且满时，且仅删一个节点

---

面试高频问题 & 回答模板 💬

Q1：为什么不用单向链表？

答：单向链表删除中间节点需要 O(n) 时间找前驱，无法满足 O(1) 要求。双向链表通过 prev 指针实现 O(1) 删除。

Q2：虚拟头尾节点的作用是什么？

答：避免处理 head == null 或 tail == null 的边界情况，使插入/删除逻辑统一，代码更简洁健壮。

Q3：LinkedHashMap 如何实现按访问顺序排序？

答：内部维护了一个双向链表，当 accessOrder=true 时，每次 get 或 put（更新）都会将 entry 移到链表尾部（表示最新）。

Q4：LRU 有什么缺点？

答：

• 对周期性访问模式不友好（如循环访问 N+1 个元素，导致缓存抖动）
• 无法区分高频短期访问和低频长期访问
• 改进方案：LRU-K、2Q、ARC 等

---

工业级优化：近似 LRU（Approximate LRU）🛠️

在超大规模缓存（如 Redis）中，维护精确的 LRU 链表开销太大。因此采用近似算法：

• Redis 的 LRU：为每个 key 记录 24 位 LRU 时钟（非精确时间），淘汰时随机采样若干 key，淘汰 LRU 值最小的。
• 优点：内存开销小，性能高
• 缺点：不是严格 LRU，但实践中效果接近

🔗 技术细节：Redis LRU Approximation

---

扩展思考：如何支持 O(1) 删除任意 key？🗑️

标准 LRU 只支持 get/put，但有时需要 delete(key)。

解决方案：

• 在 Node 中存储 key
• delete(key) 时：
  1. 从 HashMap 获取 node
  2. 从双向链表中删除 node
  3. 从 HashMap 中移除 key

这正是我们手写版本已经支持的能力！

---

总结：LRU 面试通关秘籍 🏆

1. 理解核心思想：最近使用放前面，满时删最后
2. 掌握数据结构组合：HashMap + 双向链表
3. 能手写完整实现（带虚拟头尾）
4. 知道 LinkedHashMap 简洁写法
5. 了解真实应用场景与局限性

LRU 看似简单，却蕴含了缓存设计、数据结构组合、性能权衡的深刻智慧。掌握它，你不仅能通过面试，更能理解现代高性能系统的设计哲学！✨

---

📚 延伸学习资源（均可正常访问）：

• LeetCode 146. LRU Cache
• Visualizing LRU Cache – VisuAlgo
• Caching Algorithms – Wikipedia

Happy coding! 💻🔥

---

🙌 感谢你读到这里！
🔍 技术之路没有捷径，但每一次阅读、思考和实践，都在悄悄拉近你与目标的距离。
💡 如果本文对你有帮助，不妨 👍 点赞、📌 收藏、📤 分享 给更多需要的朋友！
💬 欢迎在评论区留下你的想法、疑问或建议，我会一一回复，我们一起交流、共同成长 🌿
🔔 关注我，不错过下一篇干货！我们下期再见！✨