当前位置：首页 > JavaScript

lrucache实现 JS

2026-04-05 05:44:40JavaScript

LRU Cache 实现（JavaScript）

LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，当缓存空间不足时，会优先移除最近最少使用的数据。以下是基于 JavaScript 的实现方案：

使用 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) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 删除最久未使用的键（Map 第一个键）
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

双向链表 + 哈希表实现

更高效的 O(1) 时间复杂度实现：

lrucache实现 JS

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.size = 0;
    this.hash = {};
    this.head = new ListNode(0, 0);
    this.tail = new ListNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _addNode(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  _removeNode(node) {
    const prev = node.prev;
    const next = node.next;
    prev.next = next;
    next.prev = prev;
  }

  _moveToHead(node) {
    this._removeNode(node);
    this._addNode(node);
  }

  get(key) {
    const node = this.hash[key];
    if (!node) return -1;
    this._moveToHead(node);
    return node.value;
  }

  put(key, value) {
    const node = this.hash[key];
    if (node) {
      node.value = value;
      this._moveToHead(node);
    } else {
      const newNode = new ListNode(key, value);
      this.hash[key] = newNode;
      this._addNode(newNode);
      this.size++;
      if (this.size > this.capacity) {
        const tail = this.tail.prev;
        this._removeNode(tail);
        delete this.hash[tail.key];
        this.size--;
      }
    }
  }
}