638 字
3 分钟
LRU 缓存：哈希表 + 双向链表
LRU 缓存要求在 O(1) 时间内完成 get 和 put，并在容量满时淘汰最久未使用的键。核心结构是“哈希表 + 双向链表”：哈希表负责 O(1) 定位节点，双向链表负责维护访问顺序。
思路
- 链表头部是最近使用的节点，尾部是最久未使用的节点。
get：哈希表命中后，把节点从原位置摘下，移到头部。put：key 已存在时更新值并移到头部；不存在时新建节点插入头部，若超出容量，删除尾部节点并同步从哈希表移除。- 节点里保存 key，是为了在淘汰尾节点时能同步删除哈希表中的条目。
- 双向链表能在 O(1) 内删除任意节点；单链表需要先找前驱。头尾哨兵节点则省去了空链表和边界判断。
C++ 实现
class LRUCache {
private:
struct Node { int key, val; Node* prv; Node* nxt;
Node(int key, int val) { this->key = key; this->val = val; prv = nullptr; nxt = nullptr; } };
int capacity; unordered_map<int, Node*> mp; Node* head; Node* tail;
public: LRUCache(int capacity) { this->capacity = capacity;
head = new Node(0, 0); tail = new Node(0, 0); head->nxt = tail; tail->prv = head; }
int get(int key) { if(!mp.count(key)) return -1; else { Node* node = mp[key]; removeNode(node); addToHead(node);
return node->val; } }
void put(int key, int value) { if(mp.count(key)) { Node* node = mp[key]; node->val = value; removeNode(node); addToHead(node); } else { Node* node = new Node(key, value); addToHead(node); mp[key] = node;
if(mp.size() > capacity) { Node* out = tail->prv; removeNode(out); mp.erase(out->key); delete(out); } } }
void addToHead(Node* node) { node->nxt = head->nxt; node->prv = head; head->nxt = node; node->nxt->prv = node; }
void removeNode(Node* node) { node->prv->nxt = node->nxt; node->nxt->prv = node->prv;
node->nxt = nullptr; node->prv = nullptr; }};
/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */Java 实现
class LRUCache {
private class Node { int key, val; Node pre; Node nxt;
Node(int key, int val) { this.key = key; this.val = val; } }
private int capacity; private Map<Integer, Node> mp = new HashMap<>(); private Node head, tail;
public LRUCache(int capacity) { this.capacity = capacity;
head = new Node(0, 0); tail = new Node(0, 0); head.nxt = tail; tail.pre = head; }
private void addToHead(Node node) { node.nxt = head.nxt; node.pre = head; head.nxt.pre = node; head.nxt = node; }
private void removeNode(Node node) { node.pre.nxt = node.nxt; node.nxt.pre = node.pre;
node.nxt = null; node.pre = null; }
public int get(int key) { if(!mp.containsKey(key)) return -1; else { Node node = mp.get(key); removeNode(node); addToHead(node);
return node.val; } }
public void put(int key, int value) { if(mp.containsKey(key)) { Node node = mp.get(key); node.val = value; removeNode(node); addToHead(node); } else { Node node = new Node(key, value); addToHead(node); mp.put(key, node);
if(mp.size() > capacity) { Node out = tail.pre; removeNode(out); mp.remove(out.key); } } }
}
/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */复杂度
- 时间复杂度：
get和put均为 O(1)。 - 空间复杂度：O(capacity)。
题目
目录