当前位置：首页 > JavaScript

js实现lru

2026-03-14 06:43:01JavaScript

实现LRU缓存算法的JavaScript方法

LRU（Least Recently Used）缓存算法是一种常见的缓存淘汰策略，核心思想是当缓存空间不足时，优先淘汰最近最少使用的数据。以下是两种JavaScript实现方式：

使用Map实现LRU缓存

Map的插入顺序特性天然适合LRU逻辑，结合其O(1)时间复杂度的操作：

js实现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);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  }
}

特点：

js实现lru

Map维护键值对的插入顺序，keys().next().value直接获取最久未使用的键
所有操作时间复杂度均为O(1)
代码简洁，直接利用语言特性

双向链表+哈希表实现

更经典的实现方式，显式维护访问顺序：

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.dummyHead = new ListNode();
    this.dummyTail = new ListNode();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

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

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

  _addToHead(node) {
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = 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._addToHead(newNode);
      this.size++;
      if (this.size > this.capacity) {
        const tail = this.dummyTail.prev;
        this._removeNode(tail);
        delete this.hash[tail.key];
        this.size--;
      }
    }
  }
}

特点：