LRU 缓存 图解题解

这道题到底在问什么

操作

put(1,1) put(2,2) get(1) put(3,3) get(2) ...

容量

2

关键输出

get(1)＝1，put(3,3) 后 get(2)＝-1（2 被淘汰）

最优解：一步一步想明白

1. 3最朴素的想法是 dict 存 key-value、再用一个数组记录使用顺序。查值很快，但把一个 key 挪到最新、或删掉最旧 key 时，数组要搬一大片元素，最坏是大 O n。
2. 4转折：哈希表 cache 让任意 key 都能 O(1) 找到它的链表节点；双向链表维护使用顺序，HEAD 后面是最久未使用，TAIL 前面是最近使用。下面动画上行是链表顺序，下行是哈希表 cache。
3. 5self.cache = {}; head.next = tail; tail.prev = head手写时用 HEAD 和 TAIL 两个哨兵节点夹住所有真实节点，这样删除和插入永远有左右邻居，不用写 null 判断。中间的空槽只是布局占位。
4. 6node = Node(1,1); cache[1] = node; _add_to_tail(node)新 key 一律插到 TAIL 前面，代表它刚被用过。同时哈希表登记 key=1 指向这个节点。
5. 7node = Node(2,2); cache[2] = node; _add_to_tail(node)容量满了。链表从左到右是 1、2，所以下次淘汰会拿 HEAD 后面的 1。
6. 8node = self.cache[1] # 不用从 HEAD 顺着找哈希表负责 O(1) 定位，不需要从 HEAD 一个个走到 1。命中后还要刷新它的使用顺序，下面三帧慢放这套指针手术。
7. 9node.prev.next = node.next # HEAD.next = 节点2删一个节点要断它的左右两根 next/prev。第一刀：让它的左邻 HEAD 的 next 直接跳过 1、指向 1 的右邻 2。注意 HEAD 通向 1 的箭头已经断开。
8. 10node.next.prev = node.prev # 节点2.prev = HEAD第二刀：让右邻 2 的 prev 回指 HEAD。现在节点 1 左右两根指针都被绕过去了，它彻底脱链——但 cache[1] 还指着它，所以不会丢，等会儿原封不动接到尾部。
9. 11p = tail.prev; p.next = node; node.prev = p; node.next = tail; tail.prev = node把节点 1 接到 TAIL 前面，要接四根指针：原尾巴 2 的 next 指向 1、1 的 prev 指向 2、1 的 next 指向 TAIL、TAIL 的 prev 指向 1。顺序从 1、2 变成 2、1。整套删除加插入只改了常数条指针，所以是 O(1)，get 返回 1。
10. 12node = Node(3,3); cache[3] = node; _add_to_tail(node); len(cache)=3先把 3 接到 TAIL 前面，链表临时变成 3 个真实节点。容量只有 2，所以下一步必须淘汰 HEAD 后面的 LRU，也就是 2。
11. 13lru = head.next; _remove(lru); del cache[lru.key]超容量时，lru = head.next，就是 HEAD 后面那个节点 2。链表里用同一套指针手术摘掉它，再 del cache[2]——链表和哈希表必须同步删，少删一个就会内存泄漏或读到脏 key。
12. 14if key not in self.cache: return -1未命中的 get 不改变任何顺序，这就是官方输出里的第一个 -1。
13. 15_add_to_tail(Node(4,4)); 超容量 → _remove(head.next=节点1); del cache[1]和淘汰 2 是同一套动作：先把 4 接到 TAIL 前，临时是 1、3、4 三个；超容量就删 head.next=1 并 del cache[1]。所以接着 get(1) 又是 -1，对应官方输出的第二个 -1。
14. 16node = cache[3]; _remove(node); _add_to_tail(node); return 3访问 3 也算一次使用：摘下、接尾，3 变最新、4 变最旧。这一步底层就是前面慢放的三刀指针手术，只是这里直接给结果。返回值 3。
15. 17node = cache[4]; _remove(node); _add_to_tail(node); return 4访问 4 后 4 又回到最右。官方序列最后两个返回值就是 3 和 4。
16. 20LRU 的不变量：链表左端永远最久未使用、右端永远最近使用；每次 get 命中和 put，都把对应节点先 _remove 再 _add_to_tail，刷新到右端。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):
        prev = self.tail.prev
        prev.next = node
        node.prev = prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_tail(node)
            return
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_tail(node)
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

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

class LRUCache {
    class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } }
    private final int capacity;
    private final Map<Integer, Node> cache = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addToTail(Node node) {
        Node prev = tail.prev;
        prev.next = node; node.prev = prev;
        node.next = tail; tail.prev = node;
    }
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        remove(node); addToTail(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key); node.val = value;
            remove(node); addToTail(node);
            return;
        }
        Node node = new Node(key, value);
        cache.put(key, node); addToTail(node);
        if (cache.size() > capacity) {
            Node lru = head.next;
            remove(lru); cache.remove(lru.key);
        }
    }
}

# 凡是要求“O(1) 查 + O(1) 调整顺序/淘汰”的设计题，套这个骨架：
# 1) 哨兵双向链表：维护顺序，左端=最该淘汰，右端=最新
# 2) 哈希表 cache: key -> 链表节点，负责 O(1) 定位

def _remove(node):       # 改 2 根，绕过自己
    node.prev.next = ____    # 左邻 next 跳过 node
    node.next.prev = ____    # 右邻 prev 跳过 node

def _add_to_tail(node):  # 改 4 根，缝到 tail 前
    p = tail.prev
    p.next = node;  node.prev = p
    node.next = tail;  tail.prev = node

def touch(node):         # 任何“被使用”都调它
    _remove(node); _add_to_tail(node)

# get  命中: touch(node) 再返回值；未命中: 返回 -1
# put  命中: 改值 + touch；新增: 建节点 + add_to_tail
#      然后 if len(cache) > capacity: 删 head.next 同步 del cache[key]

// O(1) 查 + O(1) 调序/淘汰 的通用骨架
// 哨兵 head/tail 双向链表 + unordered_map<key, Node*> cache

void remove(Node* node) {     // 改 2 根
    node->prev->next = ____;   // 左邻越过 node
    node->next->prev = ____;   // 右邻越过 node
}
void addToTail(Node* node) {  // 改 4 根，缝到 tail 前
    Node* p = tail->prev;
    p->next = node; node->prev = p;
    node->next = tail; tail->prev = node;
}
// touch(node) = remove(node); addToTail(node);  // 凡被使用就调
// 超容量: lru=head->next; remove(lru); cache.erase(lru->key);

// O(1) 查 + O(1) 调序/淘汰 的通用骨架
// 哨兵 head/tail 双向链表 + HashMap<Integer,Node> cache

void remove(Node node) {      // 改 2 根
    node.prev.next = ____;     // 左邻越过 node
    node.next.prev = ____;     // 右邻越过 node
}
void addToTail(Node node) {   // 改 4 根，缝到 tail 前
    Node p = tail.prev;
    p.next = node; node.prev = p;
    node.next = tail; tail.prev = node;
}
// touch(node) = remove(node); addToTail(node);  // 凡被使用就调
// 超容量: Node lru=head.next; remove(lru); cache.remove(lru.key);

复杂度

面试官可能追问