阿里、腾讯都爱问的 LRU 缓存，你能手写出来吗？（附详细代码及GitHub面试题汇总仓库）

最近在整理计算机方向的26届校招面试题, 刷到一个高频题：LRU 缓存机制。

这题几乎是 Java/C++ 后端面试的常客，腾讯、字节、阿里、拼多多等公司都问过类似的原题。

而面试官的经典台词是：

🧑‍💼：“你知道 LRU 吗？你能手写一个简化版吗？”

有人一脸懵，有人写了 50 行崩溃现场，也有人用 LinkedHashMap 一把梭。

今天我们就一起来彻底搞懂：什么是 LRU？如何手写？面试中如何高效答？

一、什么是 LRU 缓存机制？

LRU 全称是 Least Recently Used，最少最近使用。

核心思想是：优先淘汰最近最少使用的数据。

通常 LRU 需要实现两个操作：

• get(key)：获取键值，若存在，则提升其“最近使用”级别

• put(key, value)：写入键值，如果超过容量，则删除“最久未使用”的那个元素

而面试时你通常会被要求：

• 手写一个类 LRUCache

• 支持上述两个方法

• 要求：时间复杂度为 O(1)

二、实现思路（面试官关注重点）

为了实现 O(1) 的操作，通常使用：

哈希表 HashMap → 存 key 对应的节点 双向链表 Double Linked List → 存储数据顺序，快速移动最近使用项

结构图如下👇

        head <-> node1 <-> node2 <-> node3 <-> tail
                ↑                   ↑
             最近用          最久未使用

• 每次访问后，将节点移动到 head 旁

• put 新数据时，如果超容量，就把 tail 前的节点删掉

三、Java 实现代码（附注释）

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

    private int capacity;
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0), tail = new Node(0, 0);

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insert(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        if (map.size() == capacity) remove(tail.prev);
        insert(new Node(key, value));
    }

    private void insert(Node node) {
        map.put(node.key, node);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

四、面试回答建议（结构化答题）

面试官：“你能手写一个简化版的 LRU 缓存吗？”

你可以这样答：

• 第一步：先口头说明 LRU 是什么、适用场景（缓存淘汰策略）

• 第二步：说明时间复杂度要求是 O(1)，所以你用 HashMap + 双向链表

• 第三步：手写核心代码结构，说明 get / put 的操作逻辑

🎯 重点是：先讲思路，再写代码，不要一上来就开敲！

五、更多高频题 + 各大厂真题合集（GitHub 项目推荐）

如果你正在准备校招/实习，可以看看我整理的 github 项目：

阿里/腾讯/字节/美团等大厂最新且真实的面试题 + 高频算法题 + 系统设计题库，项目地址👇

🔗 0voice/Campus_recruitment_interview_questions

📌 包含内容：

• 算法精选题目详解（含视频讲解）

• Redis/操作系统/数据库/消息队列高频知识点

• C++/Java/Python/Golang 专项复习笔记

• 腾讯/字节/阿里 真实笔经面经总结

✨ 欢迎 Star 收藏，一起上岸！