javascript数组怎么实现LRU缓存-js教程-PHP中文网

javascript数组怎么实现LRU缓存

小老鼠

发布： 2025-07-30 09:15:02

原创

563人浏览过

lru缓存的复杂度分析为：get操作平均o(1)，但movetotail导致最坏情况o(n)；put操作在数组实现下最坏情况也为o(n)。1. 使用数组和map实现时，get和put的查找为o(1)，但数组的indexof和splice操作最坏为o(n)。2. 优化方案是采用双向链表+map，通过维护头尾节点实现o(1)的删除和添加。3. movetotail、removenode和addtotail等操作在链表结构中均可o(1)完成。4. 应用场景包括web服务器缓存、数据库查询缓存、浏览器缓存、内存缓存及cdn等，适用于需高效管理有限缓存空间的场景。因此，基于双向链表的实现能显著提升性能，尤其在高频访问下优势明显。

javascript数组怎么实现LRU缓存

JavaScript数组实现LRU缓存，核心在于利用数组的push和splice方法模拟链表结构，同时用Map记录键值对，加速查找。当缓存满时，移除数组头部元素，并更新Map。

解决方案：

首先，我们需要一个类来封装LRU缓存。这个类内部会使用一个数组来存储缓存数据，以及一个Map来存储键值对，方便快速查找。

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

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.keys = []; // 使用数组维护键的顺序
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }

    // 将访问过的key移动到数组末尾，表示最近使用
    this.moveToTail(key);
    return this.cache.get(key);
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.set(key, value);
      this.moveToTail(key);
    } else {
      if (this.cache.size >= this.capacity) {
        // 移除最久未使用的key
        const oldestKey = this.keys.shift();
        this.cache.delete(oldestKey);
      }
      this.cache.set(key, value);
      this.keys.push(key); // 添加到数组末尾
    }
  }

  moveToTail(key) {
    const index = this.keys.indexOf(key);
    this.keys.splice(index, 1);
    this.keys.push(key);
  }
}

登录后复制

这样，我们就实现了一个基本的LRU缓存。

LRU缓存的复杂度分析？

Hugging Face

Hugging Face AI开源社区

135

查看详情

get操作的复杂度主要取决于Map的查找，为O(1)。moveToTail涉及数组的indexOf和splice，在最坏情况下（元素在数组头部），复杂度为O(n)，其中n是缓存的容量。put操作的复杂度也主要取决于Map的查找和删除，以及数组的操作，平均情况下也是O(1)，但最坏情况（需要移动元素）为O(n)。

如何优化LRU缓存的性能？

可以考虑使用双向链表来替代数组，这样moveToTail操作的复杂度可以降到O(1)。不过，JavaScript中没有内置的双向链表，需要手动实现。此外，还可以考虑使用更高效的数据结构，例如使用LinkedHashMap（虽然JavaScript没有直接对应的实现，但可以模拟）。

// 使用模拟双向链表优化
class LRUCacheOptimized {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.head = {}; // Dummy head node
        this.tail = {}; // Dummy tail node
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        const node = this.cache.get(key);
        this.removeNode(node);
        this.addToTail(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.addToTail(node);
        } else {
            const node = { key, value };
            this.cache.set(key, node);
            this.addToTail(node);
            if (this.cache.size > this.capacity) {
                const headNode = this.head.next;
                this.removeNode(headNode);
                this.cache.delete(headNode.key);
            }
        }
    }

    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    addToTail(node) {
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev.next = node;
        this.tail.prev = node;
        this.cache.set(node.key, node);
    }
}

登录后复制

LRU缓存的应用场景有哪些？

LRU缓存广泛应用于各种需要缓存数据的场景，例如：