LRU Cache（LRU 缓存）

题目 / Problem

中文： 设计一个遵循最近最少使用（Least Recently Used，LRU）淘汰策略的缓存。

实现 LRUCache 类：

LRUCache(capacity)：使用正整数容量 capacity 初始化缓存。
get(key)：如果键存在，返回对应值，否则返回 -1。访问成功的键会变为最近使用。
put(key, value)：如果键存在，更新其值并将其标记为最近使用；否则插入新的键值对。如果缓存超过容量，删除最近最少使用的键。

get 和 put 的平均时间复杂度都必须为 O(1)。

English: Design a cache that follows the Least Recently Used (LRU) eviction policy.

Implement the LRUCache class:

LRUCache(capacity) initializes the cache with positive capacity.
get(key) returns the value if the key exists, otherwise -1. A successful access makes the key most recently used.
put(key, value) updates an existing key or inserts a new key-value pair. If the cache exceeds capacity, evict the least recently used key.

Both get and put must run in O(1) average time.

示例 / Example

Input:
["LRUCache", "put", "put", "get", "put", "get",
 "put", "get", "get", "get"]
[[2], [1,1], [2,2], [1], [3,3], [2],
 [4,4], [1], [3], [4]]

Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]

const cache = new LRUCache(2);

cache.put(1, 1); // cache: {1=1}
cache.put(2, 2); // cache: {1=1, 2=2}
cache.get(1);    // 1，键 1 变为最近使用 / key 1 becomes most recent
cache.put(3, 3); // 淘汰键 2 / evict key 2
cache.get(2);    // -1
cache.put(4, 4); // 淘汰键 1 / evict key 1
cache.get(1);    // -1
cache.get(3);    // 3
cache.get(4);    // 4

约束 / Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
get 和 put 最多被调用 2 × 10^5 次。
At most 2 × 10^5 calls are made to get and put.

为什么需要两种数据结构？ / Why Are Two Data Structures Needed?

LRU 缓存需要同时高效完成两类操作：
An LRU cache must efficiently support two different requirements:

根据 key 快速找到对应节点。
Find a node quickly by key.
快速更新使用顺序，并删除最久未使用的节点。
Update recency order and remove the least recent node quickly.

单独使用一种常见数据结构无法同时满足两者：
One common data structure alone does not conveniently provide both:

数据结构 / Structure	优点 / Strength	缺点 / Weakness
哈希表 / Hash map	按键查找平均 `O(1)`	不直接维护 LRU 顺序
数组 / Array	可以保存顺序	中间删除或移动需要 `O(n)`
单向链表 / Singly linked list	插入头部 `O(1)`	删除已知节点仍需寻找前驱
双向链表 / Doubly linked list	已知节点可在 `O(1)` 删除和移动	不能按键快速查找

因此组合使用：
Therefore, combine:

Map<key, node> + 双向链表 / doubly linked list

链表顺序 / List Order

使用两个哨兵节点 least 和 most：
Use two sentinel nodes, least and most:

least ⇄ 最久未使用 ⇄ ... ⇄ 最近使用 ⇄ most
        least recent          most recent

least.next 始终是真正的最近最少使用节点。
least.next is always the actual least recently used node.
most.prev 始终是真正的最近使用节点。
most.prev is always the actual most recently used node.
新插入或刚访问的节点放到 most 前面。
Newly inserted or accessed nodes are placed immediately before most.

哨兵节点不保存真实缓存数据，只用于统一边界操作，避免频繁判断头尾节点是否存在。
Sentinels do not store real cache entries. They simplify boundary operations by eliminating special cases for empty lists and end nodes.

双向链表基本操作 / Doubly Linked List Operations

删除节点 / Remove a Node

node.prev.next = node.next;
node.next.prev = node.prev;

因为节点同时保存前驱和后继，所以已知节点时可以在 O(1) 时间删除。
Because each node stores both its predecessor and successor, a known node can be removed in O(1) time.

插入到最近使用端 / Insert at the Most-Recent End

把节点插入 most 之前：
Insert a node immediately before most:

const previous = most.prev;

previous.next = node;
node.prev = previous;
node.next = most;
most.prev = node;

移动到最近使用端 / Move to the Most-Recent End

先删除节点 / Remove the node
       ↓
再插入 most 前面 / Insert it before most

JavaScript 实现 / JavaScript Implementation

class ListNode {
  constructor(key = 0, value = 0) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  /**
   * @param {number} capacity
   */
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();

    // 哨兵节点 / Sentinel nodes
    this.least = new ListNode();
    this.most = new ListNode();
    this.least.next = this.most;
    this.most.prev = this.least;
  }

  /**
   * 从链表中删除一个已知节点。
   * Remove a known node from the list.
   * @param {ListNode} node
   * @return {void}
   */
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  /**
   * 将节点插入最近使用端。
   * Insert a node at the most-recent end.
   * @param {ListNode} node
   * @return {void}
   */
  insertMostRecent(node) {
    const previous = this.most.prev;

    previous.next = node;
    node.prev = previous;
    node.next = this.most;
    this.most.prev = node;
  }

  /**
   * @param {number} key
   * @return {number}
   */
  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }

    const node = this.cache.get(key);

    // 访问成功后，该节点变为最近使用
    // A successful access makes this node most recent
    this.remove(node);
    this.insertMostRecent(node);

    return node.value;
  }

  /**
   * @param {number} key
   * @param {number} value
   * @return {void}
   */
  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;

      this.remove(node);
      this.insertMostRecent(node);
      return;
    }

    const node = new ListNode(key, value);
    this.cache.set(key, node);
    this.insertMostRecent(node);

    if (this.cache.size > this.capacity) {
      const leastRecentNode = this.least.next;

      this.remove(leastRecentNode);
      this.cache.delete(leastRecentNode.key);
    }
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * const obj = new LRUCache(capacity);
 * const value = obj.get(key);
 * obj.put(key, value);
 */

执行过程 / Walkthrough

以容量 2 为例。链表顺序从左到右表示从最久未使用到最近使用：
For capacity 2, list order from left to right represents least recent to most recent:

`put(1, 1)`

least ⇄ (1,1) ⇄ most

`put(2, 2)`

least ⇄ (1,1) ⇄ (2,2) ⇄ most

`put(3, 3)`

先插入新节点：
First insert the new node:

least ⇄ (2,2) ⇄ (1,1) ⇄ (3,3) ⇄ most

缓存超过容量，删除 least.next，即键 2：
The cache exceeds capacity, so remove least.next, which is key 2:

least ⇄ (1,1) ⇄ (3,3) ⇄ most

同时从 Map 中删除键 2。
Delete key 2 from the Map as well.

`get` 也会改变顺序 / `get` Also Changes Recency

LRU 的“使用”不仅包括写入，也包括成功读取。因此 get(key) 找到节点后，必须把它移动到最近使用端。
In LRU, usage includes both writes and successful reads. Therefore, after get(key) finds a node, it must move that node to the most-recent end.

如果 get 只返回值而不更新链表，之后可能错误淘汰刚刚访问过的键。
If get returned the value without updating the list, a recently accessed key could be evicted incorrectly.

读取不存在的键不会改变缓存状态。
Reading a missing key does not alter cache state.

更新已存在的键 / Updating an Existing Key

执行 put(key, value) 且键已经存在时：
When put(key, value) is called for an existing key:

更新原节点的 value。
Update the existing node's value.
把该节点移动到最近使用端。
Move that node to the most-recent end.
不创建新节点，缓存大小不变。
Do not create a new node; cache size remains unchanged.

为什么节点需要保存 `key`？ / Why Must Each Node Store Its Key?

淘汰时通过链表找到最近最少使用节点，但还需要从哈希表中删除对应键：
Eviction finds the least recent node through the linked list, but its entry must also be deleted from the hash map:

this.cache.delete(leastRecentNode.key);

因此链表节点必须同时保存 key 和 value。
Therefore, each list node must store both its key and value.

JavaScript `Map` 的简化方案 / Simplified JavaScript `Map` Approach

JavaScript 的 Map 保持插入顺序。可以通过“删除后重新插入”把键移动到末尾，并通过 map.keys().next().value 找到最早插入的键。
JavaScript Map preserves insertion order. Deleting and reinserting a key moves it to the end, while map.keys().next().value identifies the earliest key.

这种写法更短，但“哈希表 + 双向链表”是语言无关的标准 LRU 设计，也更直接展示了要求的数据结构原理。
That version is shorter, but hash map plus doubly linked list is the language-independent standard LRU design and demonstrates the required data-structure mechanics directly.

复杂度 / Complexity

get 平均时间 / Average time: O(1)
put 平均时间 / Average time: O(1)
空间复杂度 / Space: O(capacity)

哈希表查找、插入和删除平均为 O(1)；双向链表在已知节点时删除和插入也是 O(1)。
Hash-map lookup, insertion, and deletion are O(1) on average; doubly linked-list removal and insertion are also O(1) when the node is known.

易错点 / Common Pitfalls

成功执行 get 后必须更新该键的最近使用顺序。
A successful get must update the key's recency.
更新已有键时，既要修改值，也要把节点移动到最近使用端。
Updating an existing key must change its value and move its node to the most-recent end.
淘汰节点时必须同时从链表和 Map 中删除。
Eviction must remove the entry from both the linked list and the Map.
最近最少使用节点是 least.next，不是哨兵 least 本身。
The least recently used real node is least.next, not the least sentinel itself.
最近使用节点应插入 most 之前。
Insert the most recently used node immediately before most.
双向链表节点需要保存 key，否则淘汰时无法从哈希表删除对应项。
List nodes must store their keys so the corresponding map entry can be deleted during eviction.
不要使用数组查找和移动元素，否则无法保证 O(1)。
Do not search and move entries in an array, which cannot guarantee O(1) operations.

LRU Cache