1. 题目
设计并实现一个 LRU（Least Recently Used，最近最少使用）缓存，支持 get 和 put 操作，要求两者都是 O(1) 时间复杂度。
- 构造时给定正整数
capacity 表示缓存容量。
get(key)：存在则返回 value，否则返回 -1。put(key, value)：写入数据。若写入导致容量超限，应驱逐最久未使用的键。- 关键：
get 和 put 都要更新「使用顺序」，被访问的键变成「最近使用」。
示例:
1
2
3
4
5
6
7
| LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1，此时 1 变为最新，2 变为最旧
cache.put(3, 3); // 容量满，驱逐最旧的 2
cache.get(2); // 返回 -1（未找到）
cache.get(3); // 返回 3
|
2. 解题思路
LRU 的两大需求互相矛盾：
- O(1) 按 key 查找 —— 需要哈希表。
- O(1) 维护使用顺序、淘汰尾部 —— 需要能在头部/尾部任意增删的有序结构。
答案：哈希表 + 双向链表。这正是浏览器缓存、Redis allkeys-lru、各类内存缓存的标准实现。
- 双向链表：越靠近 head 越「新」，越靠近 tail 越「旧」。淘汰时直接删 tail 前一个。
- 哈希表：
key -> 链表节点，实现 O(1) 定位到某个节点。
- 命中或写入后，把该节点用
addToHead（先 remove 再插入头部）移到最前。
为什么是双向而非单向？因为删除任意节点时需要 O(1) 拿到它的前驱，单向链表做不到。
巧用语言特性：JavaScript 的 Map 本身就维护插入顺序，把 key 重新删除再插入等价于「移到最新」，可以极简实现。面试时建议两种都讲：Map 版展示语言理解，手写双向链表版展示数据结构功底。
3. TypeScript 实现
3.1 极简版：利用 Map 的插入有序性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class LRUCache {
private map = new Map<number, number>();
constructor(private capacity: number) {}
get(key: number): number {
if (!this.map.has(key)) return -1;
const value = this.map.get(key)!;
this.map.delete(key);
this.map.set(key, value);
return value;
}
put(key: number, value: number): void {
if (this.map.has(key)) {
this.map.delete(key);
} else if (this.map.size >= this.capacity) {
const oldest = this.map.keys().next().value!;
this.map.delete(oldest);
}
this.map.set(key, value);
}
}
|
3.2 经典版：哈希表 + 手写双向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| interface DLinkedNode {
key: number;
value: number;
prev: DLinkedNode | null;
next: DLinkedNode | null;
}
class LRUCacheAdvanced {
private map = new Map<number, DLinkedNode>();
private size = 0;
private head: DLinkedNode = { key: 0, value: 0, prev: null, next: null };
private tail: DLinkedNode = { key: 0, value: 0, prev: null, next: null };
constructor(private capacity: number) {
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key: number): number {
const node = this.map.get(key);
if (!node) return -1;
this.moveToHead(node);
return node.value;
}
put(key: number, value: number): void {
const node = this.map.get(key);
if (node) {
node.value = value;
this.moveToHead(node);
return;
}
const newNode: DLinkedNode = { key, value, prev: null, next: null };
this.map.set(key, newNode);
this.addToHead(newNode);
this.size++;
if (this.size > this.capacity) {
const removed = this.removeTail();
this.map.delete(removed.key);
this.size--;
}
}
private addToHead(node: DLinkedNode): void {
node.prev = this.head;
node.next = this.head.next;
this.head.next!.prev = node;
this.head.next = node;
}
private removeNode(node: DLinkedNode): void {
node.prev!.next = node.next;
node.next!.prev = node.prev;
}
private moveToHead(node: DLinkedNode): void {
this.removeNode(node);
this.addToHead(node);
}
private removeTail(): DLinkedNode {
const node = this.tail.prev!;
this.removeNode(node);
return node;
}
}
|
- 时间复杂度：
get / put 均为 O(1)。
- 空间复杂度：
O(capacity)。
4. 面试延伸
- LFU 缓存（LeetCode 460） 是 LRU 的进阶，需要频率桶 + 双向链表，更烧脑。
- 真实工程：Redis 用近似 LRU（随机采样淘汰）省内存；前端
keep-alive、图片缓存、请求缓存都用 LRU 思想。
- 讲题要点：先说清「为什么单结构做不到 O(1)」，再自然引出「哈希 + 双向链表」的组合，展示的是权衡能力而非背代码。
难度：中等 | LeetCode 146 题 | 全栈数据结构压轴题