LRU 缓存

GitHub跳转原题关系图返回列表

哈希表 O(1) 找节点，双向链表按最近使用顺序维护，头为新、尾为旧。

OJ: leetcodecn

题目 ID: lru-cache

难度:普及+/提高

标签:设计哈希表链表cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

实现 LRU（最近最少使用）缓存。get 和 put 都必须 O(1)。

思路

unordered_map + list：map 记录 key 到链表节点迭代器的映射，list 维护 (key,value) 按最近使用的顺序排列。访问或更新时将节点移到链表头部，淘汰时删除链表尾部。

Python 直接用 OrderedDict。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：unordered_map + list，O(1) get/put。
#include <bits/stdc++.h>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int, int>> lst;
    unordered_map<int, decltype(lst)::iterator> mp;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end())
            return -1;
        lst.splice(lst.begin(), lst, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            it->second->second = value;
            lst.splice(lst.begin(), lst, it->second);
            return;
        }
        if ((int)lst.size() == cap) {
            mp.erase(lst.back().first);
            lst.pop_back();
        }
        lst.push_front({key, value});
        mp[key] = lst.begin();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cap, ops;
    cin >> cap >> ops;
    LRUCache cache(cap);
    while (ops--) {
        string op;
        cin >> op;
        if (op == "get") {
            int k;
            cin >> k;
            cout << cache.get(k) << ' ';
        } else {
            int k, v;
            cin >> k >> v;
            cache.put(k, v);
        }
    }
    return 0;
}
python
#!/usr/bin/env python3
from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
            return
        if len(self.cache) == self.cap:
            self.cache.popitem(last=False)
        self.cache[key] = value


def main() -> None:
    cap, ops = map(int, input().split())
    cache = LRUCache(cap)
    for _ in range(ops):
        parts = input().split()
        if parts[0] == "get":
            print(cache.get(int(parts[1])), end=" ")
        else:
            cache.put(int(parts[1]), int(parts[2]))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(1) get 和 put。
  • 空间复杂度：O(capacity)。

总结

LRU 是"哈希表 + 双向链表"的组合数据结构经典案例。哈希表提供 O(1) 查找，链表维护顺序信息。