LRU（Least Recently Used）缓存机制是一种常见的缓存淘汰策略，其核心思想是优先淘汰最近最少使用的数据。以下是针对该问题的详细解答：
核心思路数据结构选择：
哈希表（Map）：用于快速查找键值对，时间复杂度为O(1)。
双向链表：维护数据的访问顺序，头部为最新访问，尾部为最久未访问，插入和删除操作均为O(1)。
关键操作：
访问数据（get）：若存在，将节点移至链表头部并返回值；否则返回-1。
插入数据（put）：
若键存在，更新值并移至头部。
若键不存在，创建新节点插入头部；若超出容量，删除尾部节点。
代码实现（JavaScript）class DLinkedNode { constructor(key = 0, value = 0) { this.key = key; this.value = value; this.prev = null; this.next = null; }}class LRUCache { constructor(capacity) { this.capacity = capacity; this.size = 0; this.map = new Map(); this.head = new DLinkedNode(); // 哨兵头节点 this.tail = new DLinkedNode(); // 哨兵尾节点 this.head.next = this.tail; this.tail.prev = this.head; } 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 DLinkedNode(key, value); this.map.set(key, node); this.addToHead(node); // 新增节点到头部 this.size++; if (this.size > this.capacity) { const removed = this.removeTail(); // 删除尾部节点 this.map.delete(removed.key); this.size--; } } } // 添加节点到头部 addToHead(node) { node.prev = this.head; node.next = this.head.next; this.head.next.prev = node; this.head.next = node; } // 删除节点 deleteNode(node) { node.prev.next = node.next; node.next.prev = node.prev; } // 移动节点到头部 moveToHead(node) { this.deleteNode(node); this.addToHead(node); } // 删除尾部节点（哨兵节点前一个） removeTail() { const node = this.tail.prev; this.deleteNode(node); return node; }}关键点解析哨兵节点：
head和tail作为虚拟节点，简化边界条件处理（如删除唯一节点时无需特殊判断）。
操作顺序：
访问/插入时：先处理哈希表，再调整链表顺序。
删除时：先调整链表，再从哈希表中删除。
时间复杂度：
所有操作（get/put）均为O(1)，得益于哈希表的快速查找和链表的指针操作。
示例流程假设容量为2：
- put(1, 1) → 链表：head ? 1 ? tail，哈希表：{1: node1}。
- put(2, 2) → 链表：head ? 2 ? 1 ? tail，哈希表：{1: node1, 2: node2}。
- get(1) → 返回1，链表调整为：head ? 1 ? 2 ? tail。
- put(3, 3) → 超出容量，删除尾部节点2，链表：head ? 3 ? 1 ? tail，哈希表：{1: node1, 3: node3}。
总结- LRU的核心是通过双向链表维护访问顺序，哈希表保证快速访问。
- 边界处理需注意哨兵节点的作用，避免空指针异常。
- 扩展性：此设计可轻松修改为其他淘汰策略（如LFU）。
