#146. LRU 缓存

LeetCode 原题链接

#题目描述

实现固定容量的 LRU（最近最少使用）缓存：

• get(key)：存在时返回值并标记为最近使用，否则返回 -1。
• put(key, value)：写入或更新；超出容量时淘汰最久未使用项。
• 两个操作都要求平均 O(1)。

#题型判断

JavaScript 的 Map 不仅可以平均 O(1) 查找数据，还会按照插入顺序保存键。利用这个特性，可以让 Map 中的顺序表示数据的使用顺序：

• 第一个 key 表示最久未使用的数据。
• 最后一个 key 表示最近使用的数据。
• 访问一个 key 时，先删除再重新插入，即可把它移动到最后。

#核心思路

最久未使用 → ... → 最近使用
   Map 首部             Map 尾部

• 命中 get：保存值，删除该 key 后重新插入，将它标记为最近使用。
• 更新 put：先删除旧 key，再用新值重新插入。
• 新增 put：直接插入 Map 尾部。
• 超出容量：通过 this.cache.keys().next().value 取得并删除第一个 key。

#代码实现

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.cache = new Map();
};

LRUCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1;
  }

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

  this.cache.delete(key);
  this.cache.set(key, value);

  return value;
};

LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    this.cache.delete(key);
  }

  this.cache.set(key, value);

  if (this.cache.size > this.capacity) {
    const leastRecentlyUsedKey = this.cache.keys().next().value;
    this.cache.delete(leastRecentlyUsedKey);
  }
};

#复杂度与易错点

• get、put：平均 O(1)。
• 空间复杂度：O(capacity)。
• 判断 key 是否存在必须使用 this.cache.has(key)，不能使用 if (!this.cache.get(key))，否则值为 0 时会被误判为不存在。
• 更新已有 key 时必须写入本次传入的 value，不能重新写入旧值。
• 无论新增还是更新，都要在写入后统一判断容量，避免新增 key 后提前返回而漏掉淘汰。
• 仅调用 set 更新已有 key 的值不会改变它原来的顺序，因此必须先 delete 再 set。
• 该解法依赖 JavaScript Map 保持插入顺序的语言特性；在不具备有序哈希表的语言中，通常需要使用“哈希表 + 双向链表”实现严格的 O(1) 操作。