LRU 缓存机制

问题

实现一个 LRU (Least Recently Used) 缓存，支持 get 和 put 操作，时间复杂度均为 O(1)。

• get(key): 获取缓存值，不存在返回 -1
• put(key, value): 插入或更新缓存，超出容量时淘汰最久未使用的项

解答

思路

• Hash Map: 存储 key 到链表节点的映射，实现 O(1) 查找
• 双向链表: 维护访问顺序，头部是最近使用，尾部是最久未使用

实现

// 双向链表节点
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> Node

    // 虚拟头尾节点，简化边界处理
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    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._remove(node);
    this._addToHead(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      // 已存在，更新值并移到头部
      const node = this.map.get(key);
      node.value = value;
      this._remove(node);
      this._addToHead(node);
    } else {
      // 新增节点
      const node = new Node(key, value);
      this.map.set(key, node);
      this._addToHead(node);

      // 超出容量，删除尾部节点
      if (this.map.size > this.capacity) {
        const removed = this.tail.prev;
        this._remove(removed);
        this.map.delete(removed.key);
      }
    }
  }

  // 从链表中移除节点
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // 添加到头部
  _addToHead(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
}

测试

const cache = new LRUCache(2);

cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1

cache.put(3, 3); // 淘汰 key=2
console.log(cache.get(2)); // -1

cache.put(4, 4); // 淘汰 key=1
console.log(cache.get(1)); // -1
console.log(cache.get(3)); // 3
console.log(cache.get(4)); // 4

使用 Map 的简化实现

JavaScript 的 Map 保持插入顺序，可以利用这个特性简化实现：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) {
      return -1;
    }
    // 删除再插入，移到末尾（最近使用）
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);

    // 超出容量，删除最早插入的（第一个）
    if (this.map.size > this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
  }
}

关键点

• 双向链表支持 O(1) 删除和插入节点
• Hash Map 提供 O(1) 的 key 查找
• 虚拟头尾节点避免空指针判断
• 每次访问或更新都要将节点移到头部
• JavaScript Map 保持插入顺序，可简化实现