如何在 JavaScript 中实现一个 LRU Cache?

实现了一个高效的 LRU(最近最少使用)缓存机制,使用哈希表和双向链表以 O (1) 时间复杂度处理 get 和 put 操作。

算法与数据结构 困难 数据结构 JavaScript 算法

LRU (Least Recently Used) 缓存通过哈希表和双向链表实现,确保 getput 操作的时间复杂度为 O(1)。实现思路如下:

  1. 双向链表节点:存储键值对,并维护前后指针。
  2. 哈希表:快速定位节点位置。
  3. 容量管理:超出容量时移除链表尾部的最近最少使用节点。
class ListNode {
  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 ListNode(0, 0); // 哨兵头节点
    this.tail = new ListNode(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; // 返回被移除的节点以便删除 Map 中的键
  }

  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 ListNode(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, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 返回 1
cache.put(3, 3); // 移除 key 2
console.log(cache.get(2)); // 返回 -1 (已移除)

关键操作说明

  • _moveToHead:在访问或更新节点时将其移至链表头部。
  • _removeTail:当缓存满时删除尾部节点(LRU 策略)。
  • 哈希表:确保 O(1) 时间访问节点,双向链表维护使用顺序。