如何在 JavaScript 中实现一个 LRU Cache?
实现了一个高效的 LRU(最近最少使用)缓存机制,使用哈希表和双向链表以 O (1) 时间复杂度处理 get 和 put 操作。
LRU (Least Recently Used) 缓存通过哈希表和双向链表实现,确保 get
和 put
操作的时间复杂度为 O(1)。实现思路如下:
- 双向链表节点:存储键值对,并维护前后指针。
- 哈希表:快速定位节点位置。
- 容量管理:超出容量时移除链表尾部的最近最少使用节点。
class ListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // 存储 key -> node 映射
this.head = new ListNode(0, 0); // 哨兵头节点
this.tail = new ListNode(0, 0); // 哨兵尾节点
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 将节点移动到链表头部(表示最近使用)
_moveToHead(node) {
this._removeNode(node);
this._addToHead(node);
}
// 移除节点
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 在头部添加节点
_addToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
// 移除尾部节点(最近最少使用)
_removeTail() {
const node = this.tail.prev;
this._removeNode(node);
return node; // 返回被移除的节点以便删除 Map 中的键
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node); // 更新为最近使用
return node.value;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._moveToHead(node); // 更新值并移至头部
} else {
const node = new ListNode(key, value);
this.map.set(key, node);
this._addToHead(node); // 新节点添加到头部
if (this.map.size > this.capacity) {
const removed = this._removeTail(); // 超出容量时移除尾部
this.map.delete(removed.key);
}
}
}
}
// 使用示例
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 返回 1
cache.put(3, 3); // 移除 key 2
console.log(cache.get(2)); // 返回 -1 (已移除)
关键操作说明:
_moveToHead
:在访问或更新节点时将其移至链表头部。_removeTail
:当缓存满时删除尾部节点(LRU 策略)。- 哈希表:确保 O(1) 时间访问节点,双向链表维护使用顺序。