JS如何实现O(1)时间复杂度删除固定大小Map的最久未使用条目

你要实现的是LRU（最近最少使用）缓存策略，依托JavaScript原生Map的有序特性，可以完全做到所有操作O(1)时间复杂度，不需要额外复杂的数据结构。

核心原理 #

• 原生Map的遍历顺序严格遵循键值对的插入顺序，自带的get/set/delete操作本身就是O(1)复杂度
• 每次操作（新增/修改/查询）某个key时，先删除该key对应的旧条目，再重新插入到Map中，此时该条目会自动排在Map的尾部，标记为「最近使用」
• 当set操作完成后如果Map大小超过设定的阈值，直接删除Map的第一个条目（最久未被操作的条目）即可

完整代码实现 #

class LRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.cache = new Map();
  }

  // 查询操作，同样会更新key的使用时间
  get(key) {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  // 新增/修改操作
  set(key, value) {
    if (this.cache.has(key)) {
      // 已存在的key先删除旧条目，保证新插入的条目排在末尾
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    // 超过大小阈值时直接删除最旧的第一个条目
    if (this.cache.size > this.maxSize) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
  }
}

效果验证 #

用你给出的示例测试，运行结果完全符合预期：

const cache = new LRUCache(3);

cache.set('one', 1);
cache.set('two', 2);
cache.set('three', 3);
// 此时cache顺序：one → two → three

cache.set('two', 'two');
// 先删除旧的two条目，重新插入后顺序变为：one → three → two

cache.set('four', 4);
// 插入后大小为4，删除第一个最旧的条目one，最终顺序：three → two → four

最终cache内容如下：

{
  ['three', 3],
  ['two', 'two'],
  ['four', 4]
}

内容的提问来源于stack exchange，提问作者Lizard Derad