js实现lru

LRU缓存算法的实现思路

LRU（Least Recently Used）缓存算法是一种常见的缓存淘汰策略，其核心思想是淘汰最久未使用的数据。在JavaScript中可以通过Map或双向链表实现。

使用Map实现LRU

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) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, 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.cache = {};
    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);
  }

  _popTail() {
    const res = this.tail.prev;
    this._removeNode(res);
    return res;
  }

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

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

两种实现方式的比较

Map实现方式代码更简洁，适合容量不大的缓存场景。双向链表实现方式性能更高，特别是在频繁操作的大容量缓存场景下，能保证O(1)时间复杂度。

在实际应用中，如果缓存容量较小且对性能要求不高，可以选择Map实现。对于需要高性能的大规模缓存系统，推荐使用双向链表+哈希表的实现方式。