如何利用 JavaScript 实现一个支持 LRU 缓存策略的缓存类？-js教程-PHP中文网

如何利用 JavaScript 实现一个支持 LRU 缓存策略的缓存类？

幻影之瞳

发布： 2025-09-25 15:02:01

原创

177人浏览过

答案：通过哈希表和双向链表结合实现LRU缓存，get和put操作均O(1)。1. 每次访问将节点移至链表头部；2. 插入新节点超容时淘汰尾部节点。示例验证了正确性。

如何利用 javascript 实现一个支持 lru 缓存策略的缓存类？

为了实现一个支持 LRU（Least Recently Used，最近最少使用）策略的缓存类，我们需要结合哈希表和双向链表的优势：哈希表提供 O(1) 的查找性能，而双向链表可以高效地调整元素顺序，将最近访问的节点移动到头部，淘汰时从尾部移除最久未使用的节点。

LRU 缓存的核心机制

LRU 策略的关键在于“访问即更新”：每次 get 或 put 操作后，对应的数据应被移到链表头部表示其为最新使用。当缓存满时，自动删除尾部节点（最久未使用）。

JavaScript 中没有原生的双向链表，但我们可以用对象模拟节点，并维护 key 到节点的映射，同时手动管理前后指针。

实现一个双向链表节点结构

每个节点存储 key 和 value，以及 prev 和 next 指针：

class ListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

构建 LruCache 类

该类包含以下核心部分：

立即学习“Java免费学习笔记（深入）”；

存了个图

视频图片解析/字幕/剪辑，视频高清保存/图片源图提取

查看详情

capacity：最大容量
cache：Map 对象，用于 key → 节点的快速查找
head 与 tail：虚拟头尾节点，简化边界处理

class LruCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    // 哨兵节点，避免空判断
    this.head = new ListNode('head');
    this.tail = new ListNode('tail');
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // 移除链表中的节点
  _removeNode(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }

  // 将节点插入链表头部
  _addToHead(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const node = this.cache.get(key);
    this._removeNode(node);
    this._addToHead(node);
    return node.value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this._removeNode(node);
      this._addToHead(node);
    } else {
      const newNode = new ListNode(key, value);
      this.cache.set(key, newNode);
      this._addToHead(newNode);

      // 检查是否超容
      if (this.cache.size > this.capacity) {
        const tailNode = this.tail.prev;
        this._removeNode(tailNode);
        this.cache.delete(tailNode.key);
      }
    }
  }
}

使用示例与验证行为

测试基本功能：

const cache = new LruCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1，访问后 1 变为最新
cache.put(3, 3); // 容量满，淘汰 key=2
console.log(cache.get(2)); // -1，已被移除
console.log(cache.get(3)); // 3

这个实现保证了 get 和 put 操作均为 O(1) 时间复杂度，符合高频场景下的性能要求。

基本上就这些。

以上就是如何利用 JavaScript 实现一个支持 LRU 缓存策略的缓存类？的详细内容，更多请关注php中文网其它相关文章！