LRU 缓存结构

LRU

• 优先去除最久没有访问到的数据。

实现

• 通过组合哈希表（Hash Table）和双向链表（Doubly Linked List）实现 LRU 缓存。并且以 O(1) 的时间复杂度执行 get 和 put 操作
• 核心是对节点的新增、访问都会让节点移动到双向链表头部，当容量超过时，直接删除尾部节点即可

class LRUCache {constructor(capacity) {// 容量this.capacity = capacity;this.cache = new Map();// 用于记录访问顺序的双向链表，声明空的头节点和尾节点this.head = {};this.tail = {};// 头和尾相连this.head.next = this.tail;this.tail.prev = this.head;}get(key) {const map = this.cache;if (!map.has(key)) {return -1;}// 每次把使用的节点放到链表的头部const node = map.get(key);this._moveToHead(node);return node.value;}put(key, value) {const map = this.cache;// 如果 key 已存在，更新并移动到双向链表头部if (map.has(key)) {const node = map.get(key);node.value = value;this._moveToHead(node);} else {if (map.size >= this.capacity) {// 缓存容量已满，移除尾部节点const leastUsedKey = this.tail.prev.key;this._removeNode(this.tail.prev);map.delete(leastUsedKey);}// 创建新节点，和更新 HashMap，并移动到链表头部const newNode = this._addNode({ key, value });map.set(key, newNode);}}// 双向链表删除节点_removeNode(node) {node.prev.next = node.next;node.next.prev = node.prev;}// 删除双向链表旧节点位置，然后移动到头部_moveToHead(node) {this._removeNode(node);this._addNode(node);}// 添加节点并移动到头部_addNode(node) {node.prev = this.head;node.next = this.head.next;this.head.next.prev = node;this.head.next = node;return node;}
}// 使用示例
const cache = new LRUCache(2);
cache.put(1, 10);
console.log(cache.get(1)); // 10
cache.put(2, 20);
cache.put(3, 30);
console.log(cache.get(1)); // -1