LeetCode 146通关：LRU缓存机制手撕代码从原理到实战

在Java后端大厂面试中，**LeetCode 146 LRU缓存机制手撕代码**是当之无愧的“高频天花板”题型——据鳄鱼java社区2026年面试数据统计，82%的一线互联网公司（阿里、字节、腾讯、美团）会将其作为算法手撕环节的必考题。掌握这道题不仅能理解“最近最少使用”的缓存淘汰逻辑，更能体现你对双向链表、哈希表等核心数据结构的灵活运用能力，直接决定面试是否能进入后续的技术面环节。

一、LRU缓存机制核心原理：为什么需要双向链表+哈希表？

LRU（Least Recently Used，最近最少使用）缓存的核心逻辑是：当缓存容量达到上限时，自动淘汰最近最少使用的缓存条目，同时保证数据的访问和插入操作时间复杂度为O(1)。要实现这一点，单一数据结构无法满足需求：

1. **哈希表的优势与局限**：哈希表可以在O(1)时间内查找缓存条目，但无法维护数据的访问顺序，无法快速找到“最近最少使用”的条目； 2. **双向链表的优势与局限**：双向链表可以在O(1)时间内插入、删除节点，轻松维护数据的访问顺序（最近使用的移到头部，最少使用的留在尾部），但无法快速查找目标节点。

因此，LRU缓存的经典实现方案是**双向链表+哈希表**的组合：双向链表维护数据的访问顺序，哈希表存储“key-节点”的映射，实现查找和修改的O(1)时间复杂度。这也是LeetCode 146题目要求的核心考点——手撕这种组合结构的实现逻辑。

二、LeetCode 146 LRU缓存机制手撕代码：两种实现方式

针对LeetCode 146的要求（实现get和put方法，时间复杂度O(1)），鳄鱼java社区的面试训练营通常会教授两种手撕方式：一种是利用Java自带的LinkedHashMap快速实现，适合面试快速作答；另一种是手动实现双向链表+哈希表，深入体现数据结构能力，是面试加分项。

1. 快速实现：基于LinkedHashMap的极简写法

Java的LinkedHashMap本身就支持“按访问顺序排序”的特性，底层正是双向链表+哈希表的结构，因此只需重写removeEldestEntry方法即可实现LRU逻辑：

 
class LRUCache extends LinkedHashMap { 
    private int capacity; 
public LRUCache(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); 
} 

// 当缓存大小超过容量时，移除最久未使用的条目 
@Override 
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 
    return size() > capacity; 
} 

}

这种写法仅需20余行代码，面试中若时间紧张可快速写出，但需注意：面试官大概率会追问LinkedHashMap的底层原理，若答不上来会减分——这也是手动实现的必要性所在。

2. 进阶实现：手动构建双向链表+哈希表

手动实现是LeetCode 146 LRU缓存机制手撕代码的核心考察点，需要自定义双向链表节点、LRUCache类，并实现get和put方法的核心逻辑：

步骤1：定义双向链表节点

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

}

节点中同时存储key和value的原因：当缓存满了需要移除尾部节点时，需要通过节点的key去哈希表中删除对应的条目，这是很多面试者容易忽略的坑点。

步骤2：实现LRUCache核心逻辑

 
class LRUCache { 
    private Map cache; // 哈希表：key -> Node 
    private int capacity; // 缓存容量 
    private Node head, tail; // 虚拟头、尾节点，简化边界处理 
public LRUCache(int capacity) { 
    this.capacity = capacity; 
    cache = new HashMap<>(); 
    // 初始化虚拟头、尾节点，避免空指针 
    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; // 缓存未命中，返回-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); 
        // 判断容量是否超标 
        if (cache.size() > capacity) { 
            // 移除尾部节点（最少使用） 
            Node removed = removeTail(); 
            // 同时从哈希表中删除 
            cache.remove(removed.key); 
        } 
    } else { 
        // 缓存命中，更新value并移到头部 
        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; 
} 

}

手动实现需要重点掌握虚拟头/尾节点的作用（避免处理空指针的边界情况）、put方法中缓存命中/未命中的逻辑、以及辅助方法的复用性——这些细节能体现你的工程化思维，是面试加分的关键。

三、LeetCode 146面试坑点：90%的开发者容易踩这些雷

在LeetCode 146 LRU缓存机制手撕代码的面试中，鳄鱼java社区统计了三大高频坑点：

1. **节点仅存储value，未存储key**：当缓存满了要删除尾部节点时，无法通过节点找到对应的key去哈希表中删除条目，导致哈希表出现“脏数据”； 2. **未使用虚拟头/尾节点**：处理空链表、单节点链表时容易出现空指针异常，比如移除头部节点时需要判断前驱是否为空； 3. **put方法未处理缓存命中的情况**：仅处理了缓存未命中的插入逻辑，忘记更新已存在节点的value并移到头部，导致缓存逻辑错误。

比如鳄鱼java社区的一位学员，第一次面试时因节点只存value，导致删除尾部节点后哈希表无法同步删除，被面试官指出后慌乱修改，最终面试失败；后来在训练营中针对性练习，第二次面试时完美避坑，成功拿到字节跳动的offer。

四、实战演练：用LeetCode测试用例验证代码

实现代码后，需要用LeetCode的官方测试用例验证逻辑是否正确：

 
输入： 
["LRUCache","put","put","get","put","get","put","get","get","get"] 
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] 
预期输出：