146. LRU 缓存
题目描述
设计一个容量固定的缓存 LRUCache。缓存满了需要腾出位置时，删掉最久没有被访问的那个键。get 和 put 都算一次访问。
LRUCache(int capacity)：用正整数 capacity 作为容量创建缓存。
int get(int key)：键 key 在缓存中时返回对应的值，否则返回 -1。
void put(int key, int value)：键已存在就把值更新为 value；不存在就加入这对键值。若加入后键的个数超过 capacity，移除最久未访问的键。
get 和 put 的平均时间复杂度都必须是 O(1)。输入以操作名列表和参数列表给出，输出是每次操作的返回值，没有返回值的操作记为 null。
示例 1
输入：操作 = ["LRUCache","put","put","get","put","get","put","get","get","get"] 参数 = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] 输出：[null,null,null,1,null,-1,null,-1,3,4]
解释：容量为 2。放入键 3 时键 2 最久未用，被移除；放入键 4 时键 1 被移除；最后键 3 和 4 仍可取到。
数据范围
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5get和put合计最多调用2 * 10^5次。
解题思路：有序字典
使用 OrderedDict 的哈希索引和双向有序结构；访问或写入后移到尾部，头部始终是最久未使用项。
为什么正确
键从头到尾按最近使用时间由旧到新排列，容量不超限。
复杂度分析
get、put 平均时间 O(1)，空间 O(capacity)。
易错点
更新已有键也算一次使用；淘汰发生在最旧端。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)class LRUCache {
private final int capacity;
private final LinkedHashMap<Integer, Integer> data = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!data.containsKey(key))
return -1;
int value = data.remove(key);
data.put(key, value);
return value;
}
public void put(int key, int value) {
data.remove(key);
data.put(key, value);
if (data.size() > capacity)
data.remove(data.keySet().iterator().next());
}
}class LRUCache {
int capacity;
list<pair<int, int>> data;
unordered_map<int, list<pair<int, int>>::iterator> pos;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (!pos.count(key))
return -1;
data.splice(data.end(), data, pos[key]);
return pos[key]->second;
}
void put(int key, int value) {
if (pos.count(key)) data.erase(pos[key]);
data.emplace_back(key, value);
pos[key] = prev(data.end());
if ((int)data.size() > capacity) {
pos.erase(data.front().first);
data.pop_front();
}
}
};type entry struct{ key, value int }
type LRUCache struct {
capacity int
data *list.List
pos map[int]*list.Element
}
func Constructor(capacity int) LRUCache {
return LRUCache{capacity, list.New(), map[int]*list.Element{}}
}
func (this *LRUCache) Get(key int) int {
e, ok := this.pos[key]
if !ok {
return -1
}
this.data.MoveToBack(e)
return e.Value.(*entry).value
}
func (this *LRUCache) Put(key int, value int) {
if e, ok := this.pos[key]; ok {
e.Value.(*entry).value = value
this.data.MoveToBack(e)
} else {
this.pos[key] = this.data.PushBack(&entry{key, value})
}
if this.data.Len() > this.capacity {
e := this.data.Front()
this.data.Remove(e)
delete(this.pos, e.Value.(*entry).key)
}
}var LRUCache = function(capacity) {
this.capacity = capacity;
this.data = new Map();
};
LRUCache.prototype.get = function(key) {
if (!this.data.has(key))
return -1;
const value = this.data.get(key);
this.data.delete(key);
this.data.set(key, value);
return value;
};
LRUCache.prototype.put = function(key, value) {
this.data.delete(key);
this.data.set(key, value);
if (this.data.size > this.capacity)
this.data.delete(this.data.keys().next().value);
};class LRUCache {
private capacity: number;
private data = new Map<number, number>();
constructor(capacity: number) {
this.capacity = capacity;
}
get(key: number): number {
if (!this.data.has(key))
return -1;
const value = this.data.get(key)!;
this.data.delete(key);
this.data.set(key, value);
return value;
}
put(key: number, value: number): void {
this.data.delete(key);
this.data.set(key, value);
if (this.data.size > this.capacity)
this.data.delete(this.data.keys().next().value!);
}
}其他解法
两种方法的结构相同，都是哈希表加双向链表；有序字典由库封装，代码最短；手写版本把链表操作写出来，更通用，也更能体现原理。
解法 2：哈希表 + 双向链表 时间 O(1)，空间 O(capacity)
双向链表按使用时间从旧到新排列节点，头尾各放一个哨兵节点。哈希表把键映射到链表节点。get 和 put 命中时，把节点摘下再接到尾部。插入新键后若超出容量，就删除头哨兵后面的节点，并从哈希表中删掉它的键。
不依赖语言自带的有序字典，所有语言都能写出，也是面试要求手写的版本。代码更长，摘链和接链时要同时维护 prev 和 next 指针。
class DLinkedNode:
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 = DLinkedNode()
self.tail = DLinkedNode()
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):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
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 = DLinkedNode(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 {
private static class DLinkedNode {
int key, value;
DLinkedNode prev, next;
DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, DLinkedNode> cache = new HashMap<>();
private final DLinkedNode head = new DLinkedNode(0, 0);
private final DLinkedNode tail = new DLinkedNode(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToTail(DLinkedNode node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
removeNode(node);
addToTail(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
node.value = value;
removeNode(node);
addToTail(node);
return;
}
node = new DLinkedNode(key, value);
cache.put(key, node);
addToTail(node);
if (cache.size() > capacity) {
DLinkedNode lru = head.next;
removeNode(lru);
cache.remove(lru.key);
}
}
}class LRUCache {
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(int k = 0, int v = 0) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void addToTail(DLinkedNode* node) {
node->prev = tail->prev;
node->next = tail;
tail->prev->next = node;
tail->prev = node;
}
public:
LRUCache(int capacity) : capacity(capacity) {
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) return -1;
DLinkedNode* node = it->second;
removeNode(node);
addToTail(node);
return node->value;
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
DLinkedNode* node = it->second;
node->value = value;
removeNode(node);
addToTail(node);
return;
}
DLinkedNode* node = new DLinkedNode(key, value);
cache[key] = node;
addToTail(node);
if ((int)cache.size() > capacity) {
DLinkedNode* lru = head->next;
removeNode(lru);
cache.erase(lru->key);
delete lru;
}
}
};type dLinkedNode struct {
key, value int
prev, next *dLinkedNode
}
type LRUCache struct {
capacity int
cache map[int]*dLinkedNode
head, tail *dLinkedNode
}
func Constructor(capacity int) LRUCache {
head, tail := &dLinkedNode{}, &dLinkedNode{}
head.next = tail
tail.prev = head
return LRUCache{capacity, map[int]*dLinkedNode{}, head, tail}
}
func (this *LRUCache) removeNode(node *dLinkedNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) addToTail(node *dLinkedNode) {
node.prev = this.tail.prev
node.next = this.tail
this.tail.prev.next = node
this.tail.prev = node
}
func (this *LRUCache) Get(key int) int {
node, ok := this.cache[key]
if !ok {
return -1
}
this.removeNode(node)
this.addToTail(node)
return node.value
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.cache[key]; ok {
node.value = value
this.removeNode(node)
this.addToTail(node)
return
}
node := &dLinkedNode{key: key, value: value}
this.cache[key] = node
this.addToTail(node)
if len(this.cache) > this.capacity {
lru := this.head.next
this.removeNode(lru)
delete(this.cache, lru.key)
}
}var LRUCache = function(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.head = { key: 0, value: 0, prev: null, next: null };
this.tail = { key: 0, value: 0, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
};
LRUCache.prototype.removeNode = function(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
};
LRUCache.prototype.addToTail = function(node) {
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev.next = node;
this.tail.prev = node;
};
LRUCache.prototype.get = function(key) {
const node = this.cache.get(key);
if (!node) return -1;
this.removeNode(node);
this.addToTail(node);
return node.value;
};
LRUCache.prototype.put = function(key, value) {
let node = this.cache.get(key);
if (node) {
node.value = value;
this.removeNode(node);
this.addToTail(node);
return;
}
node = { key, value, prev: null, next: null };
this.cache.set(key, node);
this.addToTail(node);
if (this.cache.size > this.capacity) {
const lru = this.head.next;
this.removeNode(lru);
this.cache.delete(lru.key);
}
};class DLinkedNode {
key: number;
value: number;
prev: DLinkedNode | null = null;
next: DLinkedNode | null = null;
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
}
}
class LRUCache {
private capacity: number;
private cache = new Map<number, DLinkedNode>();
private head = new DLinkedNode();
private tail = new DLinkedNode();
constructor(capacity: number) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
private removeNode(node: DLinkedNode): void {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private addToTail(node: DLinkedNode): void {
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev!.next = node;
this.tail.prev = node;
}
get(key: number): number {
const node = this.cache.get(key);
if (!node) return -1;
this.removeNode(node);
this.addToTail(node);
return node.value;
}
put(key: number, value: number): void {
let node = this.cache.get(key);
if (node) {
node.value = value;
this.removeNode(node);
this.addToTail(node);
return;
}
node = new DLinkedNode(key, value);
this.cache.set(key, node);
this.addToTail(node);
if (this.cache.size > this.capacity) {
const lru = this.head.next!;
this.removeNode(lru);
this.cache.delete(lru.key);
}
}
}