实现LRU淘汰算法

问题

LRU（Least Recently Used，最近最少使用）是一种常见的缓存淘汰策略。当缓存容量达到上限时，优先淘汰最久未使用的数据。

需要实现一个 LRU 缓存类，支持以下功能：

• get(key)：获取缓存中的值，如果存在则返回值并更新为最近使用，不存在返回 -1
• put(key, value)：设置缓存值，如果缓存已满则淘汰最久未使用的数据
• 读写操作的时间复杂度都要求为 O(1)

解答

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity; // 缓存容量
    this.cache = new Map(); // 使用 Map 存储缓存数据，Map 会保持插入顺序
  }

  /**
   * 获取缓存值
   * @param {number} key
   * @return {number}
   */
  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;
  }

  /**
   * 设置缓存值
   * @param {number} key
   * @param {number} value
   * @return {void}
   */
  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) {
      // Map.keys() 返回的迭代器按插入顺序排列
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}

使用双向链表 + 哈希表的实现方式：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // 哈希表，存储 key -> 节点的映射
    this.head = { prev: null, next: null }; // 虚拟头节点
    this.tail = { prev: null, next: null }; // 虚拟尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * 将节点移动到链表头部（表示最近使用）
   */
  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }

  /**
   * 在链表头部添加节点
   */
  addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  /**
   * 移除节点
   */
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  /**
   * 移除尾部节点
   */
  removeTail() {
    const node = this.tail.prev;
    this.removeNode(node);
    return node;
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    
    const node = this.cache.get(key);
    this.moveToHead(node); // 移动到头部表示最近使用
    return node.value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      // 更新已存在的节点
      const node = this.cache.get(key);
      node.value = value;
      this.moveToHead(node);
    } else {
      // 创建新节点
      const newNode = { key, value, prev: null, next: null };
      this.cache.set(key, newNode);
      this.addToHead(newNode);
      
      // 检查容量
      if (this.cache.size > this.capacity) {
        const removed = this.removeTail();
        this.cache.delete(removed.key);
      }
    }
  }
}

使用示例

// 创建容量为 2 的 LRU 缓存
const lru = new LRUCache(2);

lru.put(1, 1); // 缓存: {1=1}
lru.put(2, 2); // 缓存: {1=1, 2=2}
console.log(lru.get(1)); // 返回 1，缓存: {2=2, 1=1}

lru.put(3, 3); // 淘汰 key 2，缓存: {1=1, 3=3}
console.log(lru.get(2)); // 返回 -1 (未找到)

lru.put(4, 4); // 淘汰 key 1，缓存: {3=3, 4=4}
console.log(lru.get(1)); // 返回 -1 (未找到)
console.log(lru.get(3)); // 返回 3，缓存: {4=4, 3=3}
console.log(lru.get(4)); // 返回 4，缓存: {3=3, 4=4}

关键点

• 数据结构选择：使用 Map 或双向链表+哈希表组合，保证 O(1) 时间复杂度

  • Map 方案：利用 Map 保持插入顺序的特性，代码简洁
  • 双向链表方案：更符合经典实现，便于理解 LRU 原理

• 访问更新策略：每次 get 或 put 操作都要将对应元素标记为最近使用

  • Map 方案：删除后重新插入到末尾
  • 链表方案：移动节点到链表头部

• 淘汰策略：当容量满时，删除最久未使用的元素

  • Map 方案：删除 Map 的第一个元素（最早插入的）
  • 链表方案：删除链表尾部节点

• 边界处理：

  • 更新已存在的 key 时，需要先删除再插入
  • 使用虚拟头尾节点简化链表操作
  • 同步维护哈希表和链表的一致性