LRU 缓存 图解题解

LRU 缓存到底要实现什么

LRU（Least Recently Used，最近最少使用）是一种淘汰策略：缓存容量有限，装满之后再写入新键，就把最久没被用过的那个键扔掉。题目要求实现 get 和 put 两个操作，get 未命中返回 -1，并且两个操作都必须 O(1)。难点不在语义，而在这个 O(1)——它同时要求「按 key 查得快」和「随时知道谁最旧」，任何单一数据结构都做不到。

为什么哈希表和链表单独用都不够

只用哈希表，查任何 key 都是 O(1)，但哈希表不记录使用顺序，容量满了不知道该淘汰谁，除非 O(n) 遍历一遍。只用链表，可以把节点按使用先后排好，最旧的永远在头部，但想找到某个 key 对应的节点得从头扫，get 退化成 O(n)。两者的短板恰好互补，解法于是自然成形：哈希表存「key 到链表节点」的映射负责定位，双向链表负责排新旧，每次操作两边同步维护。

链表为什么必须双向，哨兵节点是干什么的

每次 get 或 put 命中，都要把节点从当前位置摘下来、接到链表尾部表示「刚用过」。摘除一个节点需要同时改它前驱和后继的指针，单向链表拿不到前驱、得再花 O(n) 去找，而双向链表两头都有引用，摘除只改固定几根指针，O(1) 完成。

再在头尾各放一个不存数据的哨兵节点 HEAD 和 TAIL，任何真实节点就都有左右邻居，删除和插入不必判空，边界代码大幅简化；「最旧的节点」也永远等于 head.next，一步锁定，淘汰不需要任何查找。

get 和 put 的每一步为什么这么设计

get 命中后不能只返回值：这个 key 刚被使用过，必须把节点摘下再接到尾部刷新新旧顺序，否则它会被误当成旧数据提前淘汰。put 时若 key 已存在，同样先摘掉旧节点再把新节点接到尾部——更新值也算一次使用，这是最容易被忽略的规则。

插入后如果超出容量，取 head.next 这个最旧节点，把它从链表摘掉，同时从哈希表里删掉对应的 key。链表和哈希表必须同步增删：只删链表不删哈希表，之后 get 会命中一个已经脱链的僵尸节点，数据从此不一致，还会泄漏内存。

复杂度怎么算，有没有现成的写法

get 与 put 各由「哈希定位 + 常数次指针改动」构成，均为 O(1)；空间是哈希表和双向链表各存至多 capacity 个节点，O(capacity)。Python 的 collections.OrderedDict 内置了同一套「哈希 + 双向链表」组合，用 move_to_end 和 popitem 几行就能写完，但面试通常要求手写，考察的正是这两个结构如何咬合。

Python

class Node:
    def __init__(self, k=0, v=0):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}                 # key -> Node
        self.head, self.tail = Node(), Node()  # 哨兵
        self.head.next = self.tail
        self.tail.prev = self.head
    def _remove(self, n):               # 摘下一个节点
        n.prev.next, n.next.prev = n.next, n.prev
    def _add_to_tail(self, n):          # 接到 TAIL 前(最新)
        n.prev, n.next = self.tail.prev, self.tail
        self.tail.prev.next = n; self.tail.prev = n
    def get(self, key):
        if key not in self.cache: return -1
        n = self.cache[key]
        self._remove(n); self._add_to_tail(n)  # 刷新为最新
        return n.v
    def put(self, key, value):
        if key in self.cache: self._remove(self.cache[key])
        n = Node(key, value); self.cache[key] = n
        self._add_to_tail(n)
        if len(self.cache) > self.cap:  # 超容,淘汰最旧
            lru = self.head.next; self._remove(lru)
            del self.cache[lru.k]

C++

struct Node{int k,v;Node*prev,*next;Node(int k=0,int v=0):k(k),v(v),prev(0),next(0){}};
class LRUCache{
  int cap; unordered_map<int,Node*> cache; Node *head,*tail;
  void rm(Node*n){n->prev->next=n->next; n->next->prev=n->prev;}
  void addTail(Node*n){n->prev=tail->prev; n->next=tail; tail->prev->next=n; tail->prev=n;}
public:
  LRUCache(int c):cap(c){head=new Node();tail=new Node();head->next=tail;tail->prev=head;}
  int get(int key){
    if(!cache.count(key)) return -1;
    Node*n=cache[key]; rm(n); addTail(n); return n->v;
  }
  void put(int key,int value){
    if(cache.count(key)) rm(cache[key]);
    Node*n=new Node(key,value); cache[key]=n; addTail(n);
    if((int)cache.size()>cap){Node*lru=head->next; rm(lru); cache.erase(lru->k); delete lru;}
  }
};

Java

class LRUCache {
  class Node{int k,v;Node prev,next;Node(int k,int v){this.k=k;this.v=v;}}
  int cap; Map<Integer,Node> cache=new HashMap<>(); Node head=new Node(0,0),tail=new Node(0,0);
  public LRUCache(int c){cap=c; head.next=tail; tail.prev=head;}
  void rm(Node n){n.prev.next=n.next; n.next.prev=n.prev;}
  void addTail(Node n){n.prev=tail.prev; n.next=tail; tail.prev.next=n; tail.prev=n;}
  public int get(int key){
    if(!cache.containsKey(key)) return -1;
    Node n=cache.get(key); rm(n); addTail(n); return n.v;
  }
  public void put(int key,int value){
    if(cache.containsKey(key)) rm(cache.get(key));
    Node n=new Node(key,value); cache.put(key,n); addTail(n);
    if(cache.size()>cap){Node lru=head.next; rm(lru); cache.remove(lru.k);}
  }
}