题目
题目来源:力扣(LeetCode)
设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
LRUCache cache = new LRUCache( 2 / 缓存容量 / );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
思路分析
LRU 是一种十分常见的页面置换算法。
将 LRU 翻译成大白话就是:当不得不淘汰某些数据时(通常是容量已满),选择最久未被使用的数据进行淘汰。
题目让我们实现一个容量固定的 LRUCache 。如果插入数据时,发现容器已满时,则先按照 LRU 规则淘汰一个数据,再将新数据插入,其中「插入」和「查询」都算作一次“使用”。
可以通过 🌰 来理解,假设我们有容量为 22 的 LRUCache 和 测试键值对 [1-1,2-2,3-3] ,将其按照顺序进行插入 & 查询:
插入 1-1,此时最新的使用数据为 1-1
插入 2-2,此时最新使用数据变为 2-2
查询 1-1,此时最新使用数据为 1-1
插入 3-3,由于容器已经达到容量,需要先淘汰已有数据才能插入,这时候会淘汰 2-2,3-3 成为最新使用数据
键值对存储方面,我们可以使用「哈希表」来确保插入和查询的复杂度为 O(1)O(1)。
另外我们还需要额外维护一个「使用顺序」序列。
我们期望当「新数据被插入」或「发生键值对查询」时,能够将当前键值对放到序列头部,这样当触发 LRU 淘汰时,只需要从序列尾部进行数据删除即可。
具体地:
- LRU的缓存策略就像是维护一个队列,每次把访问的节点移动过到队列的末尾,当队列的长度 大于缓存的长度,就把队列首部的元素给删除。
- 在调用get和put的时候,访问或者修改了的数据要被更新到最新访问的位置,所以会在这里处理数据 的顺序。
- 其次存取的数据要能记录访问顺序,或者说要有序。
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
// 最大缓存容量
this.capacity = parseInt(capacity, 10);
// 数据缓存对象
this.cache = {};
// 键名缓存数组,还可提供 key 的访问时间顺序
this.keys = [];
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
const idx = this.keys.indexOf(key);
if (idx === -1) {
return -1;
}
// 更新 keys 的顺序
this.keys.push(this.keys.splice(idx, 1)[0]);
return this.cache[key];
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
const idx = this.keys.indexOf(key);
if (idx !== -1) {
// 更新原有数据和访问时间顺序
this.keys.push(this.keys.splice(idx, 1)[0]);
} else {
if (this.keys.length === this.capacity) {
// 超出缓存容量,删除缓存中最少使用的缓存
this.cache[this.keys.shift()] = null;
}
this.keys.push(key);
}
this.cache[key] = value;
};