LRU 缓存算法

问题

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

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

解答

方法一：使用 Map

ES6 的 Map 会保持插入顺序，可以利用这个特性实现 LRU。

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

  get(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;
  }

  put(key, value) {
    // 如果 key 已存在，先删除
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    // 插入新值
    this.cache.set(key, value);
    // 超出容量，删除最久未使用的（Map 的第一个元素）
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}

方法二：双向链表 + 哈希表

经典实现，手动维护访问顺序。

// 双向链表节点
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;
  }

  // 将节点移到链表头部（最近使用）
  _moveToHead(node) {
    this._removeNode(node);
    this._addToHead(node);
  }

  // 从链表中删除节点
  _removeNode(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;
  }

  // 删除尾部节点（最久未使用）
  _removeTail() {
    const node = this.tail.prev;
    this._removeNode(node);
    return node;
  }

  get(key) {
    if (!this.map.has(key)) {
      return -1;
    }
    const node = this.map.get(key);
    this._moveToHead(node);
    return node.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      // 更新已有节点
      const node = this.map.get(key);
      node.value = value;
      this._moveToHead(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._removeTail();
        this.map.delete(removed.key);
      }
    }
  }
}

测试

const cache = new LRUCache(2);

cache.put(1, 'a');
cache.put(2, 'b');
console.log(cache.get(1)); // 'a'，此时 1 变为最近使用

cache.put(3, 'c'); // 容量满，淘汰 key=2
console.log(cache.get(2)); // -1，已被淘汰

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

关键点

• Map 方案：利用 Map 的插入顺序特性，删除再插入实现”最近使用”
• 链表方案：头部是最近使用，尾部是最久未使用，哈希表保证 O(1) 查找
• 虚拟节点：head 和 tail 作为哨兵，避免处理空指针边界
• put 时先检查：key 存在时要先删除再插入，保证顺序正确
• 淘汰时机：插入新元素后检查容量，超出则删除尾部节点