答案：通过哈希表和双向链表结合实现lru缓存，get和put操作均o(1)。1. 每次访问将节点移至链表头部；2. 插入新节点超容时淘汰尾部节点。示例验证了正确性。
LRU 缓存的核心机制
LRU 策略的关键在于“访问即更新”：每次 get 或 put 操作后，对应的数据应被移到链表头部表示其为最新使用。当缓存满时，自动删除尾部节点（最久未使用）。
JavaScript 中没有原生的双向链表，但我们可以用对象模拟节点，并维护 key 到节点的映射，同时手动管理前后指针。
实现一个双向链表节点结构
每个节点存储 key 和 value，以及 prev 和 next 指针：
class ListNode {constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
构建 LruCache 类
该类包含以下核心部分：
立即学习“Java免费学习笔记（深入）”；
- capacity：最大容量
- cache：Map 对象，用于 key → 节点 的快速查找
- head 与 tail：虚拟头尾节点，简化边界处理
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
// 哨兵节点，避免空判断
this.head = new ListNode('head');
this.tail = new ListNode('tail');
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 移除链表中的节点
_removeNode(node) {
const prev = node.prev;
const next = node.next;
prev.next = next;
next.prev = prev;
}
// 将节点插入链表头部
_addToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
if (!this.cache.has(key)) return -1;
const node = this.cache.get(key);
this._removeNode(node);
this._addToHead(node);
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value;
this._removeNode(node);
this._addToHead(node);
} else {
const newNode = new ListNode(key, value);
this.cache.set(key, newNode);
this._addToHead(newNode);
// 检查是否超容
if (this.cache.size > this.capacity) {
const tailNode = this.tail.prev;
this._removeNode(tailNode);
this.cache.delete(tailNode.key);
}
}
}
}
使用示例与验证行为
测试基本功能：
const cache = new LruCache(2);cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1，访问后 1 变为最新
cache.put(3, 3); // 容量满，淘汰 key=2
console.log(cache.get(2)); // -1，已被移除
console.log(cache.get(3)); // 3
这个实现保证了 get 和 put 操作均为 O(1) 时间复杂度，符合高频场景下的性能要求。
基本上就这些。
