答案：通过哈希表和双向链表结合实现LRU缓存，get和put操作均O(1)。1. 每次访问将节点移至链表头部；2. 插入新节点超容时淘汰尾部节点。示例验证了正确性。
为了实现一个支持 LRU（Least Recently Used，最近最少使用）策略的缓存类，我们需要结合哈希表和双向链表的优势：哈希表提供 O(1) 的查找性能，而双向链表可以高效地调整元素顺序，将最近访问的节点移动到头部，淘汰时从尾部移除最久未使用的节点。
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：虚拟头尾节点，简化边界处理class LruCache {
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) 时间复杂度，符合高频场景下的性能要求。
基本上就这些。
以上就是如何利用 JavaScript 实现一个支持 LRU 缓存策略的缓存类？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/43238.html
微信扫一扫 
支付宝扫一扫 
