IT 面试题库

如何设计并实现一个 O(1) 的 LRU 缓存?说明数据结构与淘汰策略

中级简答题后端开发工程师前端开发工程师LRU哈希表双向链表

题目

考察哈希表与双向链表组合、容量淘汰策略

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 54 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

核心结构

复杂度

代码(JavaScript,借助 Map 保序)

class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key); this.map.set(key, v); // 提到最新
    return v;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest); // 淘汰最久未用
    }
  }
}

JavaScript 的 Map 会保留插入顺序,删除再插入即可把节点置为最新,迭代首键即最久未用,从而省去手写双向链表。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题