146.LRU缓存

发表于 分类于 阅读次数：

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["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]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

解题思路

这是一道经典的设计题，考察对LRU缓存的理解和实现。

核心思想

  • 使用哈希表 + 双向链表的数据结构
  • 哈希表提供O(1)的查找
  • 双向链表维护访问顺序，支持O(1)的插入和删除

方法一：哈希表 + 双向链表（推荐）

时间复杂度 O(1)、空间复杂度 O(capacity)

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.head = new DLinkedNode();
    this.tail = new DLinkedNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.cache.has(key)) {
        return -1;
    }
    
    // 移动到头部
    const node = this.cache.get(key);
    this.moveToHead(node);
    return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // 更新值并移动到头部
        const node = this.cache.get(key);
        node.value = value;
        this.moveToHead(node);
    } else {
        // 创建新节点
        const newNode = new DLinkedNode(key, value);
        this.cache.set(key, newNode);
        this.addToHead(newNode);
        this.size++;
        
        if (this.size > this.capacity) {
            // 删除最久未使用的节点
            const removed = this.removeTail();
            this.cache.delete(removed.key);
            this.size--;
        }
    }
};

// 双向链表节点
function DLinkedNode(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
}

// 移动到头部
LRUCache.prototype.moveToHead = function(node) {
    this.removeNode(node);
    this.addToHead(node);
};

// 添加到头部
LRUCache.prototype.addToHead = function(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
};

// 删除节点
LRUCache.prototype.removeNode = function(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
};

// 删除尾部节点
LRUCache.prototype.removeTail = function() {
    const res = this.tail.prev;
    this.removeNode(res);
    return res;
};

方法二：使用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
25
26
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
};

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // 删除并重新添加，使其成为最新访问的
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }
    return -1;
};

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
        // 删除最久未使用的（Map的第一个键）
        const firstKey = this.cache.keys().next().value;
        this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
};

方法三：使用Object模拟

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
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = {};
    this.keys = [];
};

LRUCache.prototype.get = function(key) {
    if (this.cache[key] !== undefined) {
        // 更新访问顺序
        this.keys = this.keys.filter(k => k !== key);
        this.keys.push(key);
        return this.cache[key];
    }
    return -1;
};

LRUCache.prototype.put = function(key, value) {
    if (this.cache[key] !== undefined) {
        // 更新值
        this.cache[key] = value;
        this.keys = this.keys.filter(k => k !== key);
        this.keys.push(key);
    } else {
        // 添加新值
        if (this.keys.length >= this.capacity) {
            // 删除最久未使用的
            const oldestKey = this.keys.shift();
            delete this.cache[oldestKey];
        }
        this.cache[key] = value;
        this.keys.push(key);
    }
};

解题要点

  1. 数据结构选择：

    • 哈希表：提供O(1)的查找
    • 双向链表：维护访问顺序，支持O(1)的插入和删除

  2. LRU策略：

    • 最近使用的放在头部
    • 最久未使用的在尾部
    • 容量满时删除尾部节点

  3. 操作实现：

    • get操作：查找并移动到头部
    • put操作：更新或添加，并移动到头部

面试要点

  • 高频考点：这道题是面试中的高频设计题
  • 数据结构：考察对哈希表和链表的理解
  • 时间复杂度：要求O(1)的操作复杂度
  • 设计思维：考察系统设计能力

相关题目

扩展思考

  1. 为什么使用双向链表？

    • 支持O(1)的插入和删除
    • 可以方便地移动到头部或删除尾部

  2. 时间复杂度分析

    • get操作：O(1)
    • put操作：O(1)
    • 空间复杂度：O(capacity)

  3. 实际应用

    • 浏览器缓存
    • 数据库查询缓存
    • 操作系统页面置换

  4. 变种问题

    • LFU缓存（最不经常使用）
    • 带过期时间的缓存
    • 分布式缓存

  5. 优化思路

    • 使用Map的内置特性简化实现
    • 考虑内存使用和性能平衡
    • 处理并发访问问题

最后更新: 2021-09-18