01

60 秒回答模板

LRU 缓存要让 `get`、`put`、淘汰都接近 O(1)。标准做法是 HashMap 保存 `key -> node`，双向链表按访问新旧排序，头部是最近使用，尾部是最久未使用。`get` 命中后把节点移动到头部；`put` 已有 key 时更新值并移动到头部；`put` 新 key 时插入头部，若超过容量就删除尾部节点并同步删除 map。实现时用 dummy head/tail 简化边界，拆出 `removeNode`、`addFirst`、`moveToHead`、`removeLast`，避免指针错误。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚
02

深入解析

01

函数契约先说清

`get(key)` 命中返回值并刷新最近使用顺序，未命中返回约定哨兵值；`put(key, value)` 插入或更新缓存，并在容量超限时淘汰最久未使用项。

02

HashMap 和双向链表缺一不可

HashMap 负责 O(1) 找节点，双向链表负责 O(1) 删除任意节点并插入头部。单链表删除任意节点需要前驱，数组移动元素会退化到 O(n)。

03

dummy 节点降低边界复杂度

使用虚拟 head 和 tail，真实节点永远在两者之间。插入头部和删除尾部都不用单独判断空链表、首节点、尾节点，代码更稳定。

04

put 分支要完整

已有 key：改 value，moveToHead，不增加 size。新 key：创建节点，放入 map，addFirst，size 增加；超过 capacity 时 removeLast，并用被淘汰节点的 key 删除 map。

05

边界和并发要说明范围

capacity 小于等于 0 时可以直接不缓存或构造时报错；capacity 为 1 要验证反复淘汰。普通手写版本不是线程安全的，并发场景要加锁、分段或使用成熟缓存库。

java

HashMap + 双向链表实现 LRU

class LRUCache {
  private static class Node {
    int key;
    int value;
    Node prev;
    Node next;

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

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

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

  int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    moveToHead(node);
    return node.value;
  }

  void put(int key, int value) {
    if (capacity <= 0) return;
    Node node = map.get(key);
    if (node != null) {
      node.value = value;
      moveToHead(node);
      return;
    }

    Node created = new Node(key, value);
    map.put(key, created);
    addFirst(created);
    if (map.size() > capacity) {
      Node removed = removeLast();
      map.remove(removed.key);
    }
  }

  private void moveToHead(Node node) {
    remove(node);
    addFirst(node);
  }

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

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

  private Node removeLast() {
    Node node = tail.prev;
    remove(node);
    return node;
  }
}
  • 面试讲解时重点解释 dummy head/tail、命中移动、已有 key 更新、容量超限同步删除 map。这个版本不处理并发。
03

易错点

  • 命中 `get` 后忘记移动到头部，退化成插入顺序淘汰。
  • 淘汰链表尾节点后忘记删除 HashMap，留下悬挂节点。
  • 更新已有 key 时错误增加 size，导致提前淘汰。
  • 指针更新顺序不完整，漏改 prev 或 next 造成链表断裂。
04

面试官追问

为什么不能只用 HashMap？

HashMap 能 O(1) 查找，但不知道谁最久未使用。必须额外维护访问顺序，才能快速淘汰。

为什么用双向链表而不是单链表？

命中节点后要从原位置删除，单链表需要找到前驱，无法稳定 O(1)；双向链表节点自带 prev，可直接断链。

更新已有 key 算一次访问吗？

通常算。`put` 已有 key 要更新 value 并移动到头部，否则最近使用语义不完整。

并发场景怎么处理？

手写结构需要互斥锁保护 map 和链表的一致性。高并发生产场景更常用分段锁或 Caffeine 这类成熟缓存库。