当前位置：首页 > JavaScript

js实现lru

2026-02-01 08:12:32JavaScript

LRU缓存算法的实现

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

使用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);
    }

    this.cache.set(key, value);

    if (this.cache.size > this.capacity) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
  }
}

使用双向链表和哈希表实现

这种方法结合了双向链表的高效删除/插入和哈希表的快速查找特性。

class Node {
  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 Node(0, 0);
    this.tail = new Node(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 Node(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);
    }
  }
}

使用ES6 Proxy实现

Proxy可以拦截对象的操作，可以用来实现LRU的自动管理。

js实现lru

function createLRUCache(capacity) {
  const cache = new Map();

  return new Proxy({}, {
    get(target, prop) {
      if (cache.has(prop)) {
        const value = cache.get(prop);
        cache.delete(prop);
        cache.set(prop, value);
        return value;
      }
      return undefined;
    },
    set(target, prop, value) {
      if (cache.has(prop)) {
        cache.delete(prop);
      }
      cache.set(prop, value);

      if (cache.size > capacity) {
        const oldestKey = cache.keys().next().value;
        cache.delete(oldestKey);
      }
      return true;
    }
  });
}