LRU（Least Recently Used）算法是一种常用的缓存淘汰算法，它根据数据的访问时间来确定哪些数据应该被保留在缓存中。
LRU 算法的基本思想是，当缓存空间已满时，优先淘汰最近最少使用的数据。具体实现可以使用哈希表和双向链表来构建一个 LRU 缓存结构。
以下是一个简单的 LRU 算法实现示例：
- 定义一个哈希表用于快速查找缓存中的数据。
- 定义一个双向链表用于维护缓存中数据的访问顺序，最近访问过的节点放在链表头部。
- 当访问一个数据时，如果存在于缓存中，则将其从原位置删除，并重新插入到链表头部表示最近使用过。
- 当需要淘汰数据时，删除链表尾部节点，并从哈希表中删除对应项。
以下是 JavaScript 的示例代码：
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(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;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
const oldestKey = this.cache.keys().next().value; // 获取链表尾部的键
this.cache.delete(oldestKey);
}
this.cache.set(key, value);
}
}
// 使用示例
const cache = new LRUCache(2); // 容量为2的缓存
cache.put(1, 'a');
cache.put(2, 'b');
console.log(cache.get(1)); // 输出: 'a'
cache.put(3, 'c'); // 缓存已满，移除最近未使用的数据项2
console.log(cache.get(2)); // 输出: -1，因为数据项2已被淘汰
cache.put(4, 'd');
console.log(cache.get(1)); // 输出: 'a'
console.log(cache.get(3)); // 输出: -1，因为数据项3已被淘汰
console.log(cache.get(4)); // 输出: 'd'
这是一个简单的实现，并不包含所有可能的情况和优化。在实际应用中，还可以考虑通过双向链表来提高删除操作的效率，或者使用现有库中提供的 LRU 缓存实现。
内容由零声教学AI助手提供，问题来源于学员提问
