JavaScript实现LRU缓存的三种方式详解

LRU（Least Recently Used）缓存是一种常用的缓存算法，它根据数据的访问时间来决定哪些数据应该被保留，哪些数据应该被淘汰。在JavaScript中，可以使用以下三种方式来实现LRU缓存。

方式一：使用Map和双向链表实现LRU缓存

以下是使用Map和双向链表实现LRU缓存的示例代码：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = null;
    this.tail = null;
  }

  get(key) {
    if (!this.map.has(key)) {
      return -1;
    }
    const value = this.map.get(key).value;
    this.removeNode(this.map.get(key));
    this.addNode(new Node(key, value));
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.removeNode(this.map.get(key));
    }
    const node = new Node(key, value);
    this.addNode(node);
    this.map.set(key, node);
    if (this.map.size > this.capacity) {
      this.map.delete(this.tail.key);
      this.removeNode(this.tail);
    }
  }

  addNode(node) {
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
  }

  removeNode(node) {
    if (node === this.head) {
      this.head = node.next;
      if (this.head !== null) {
        this.head.prev = null;
      }
    } else if (node === this.tail) {
      this.tail = node.prev;
      if (this.tail !== null) {
        this.tail.next = null;
      }
    } else {
      node.prev.next = node.next;
      node.next.prev = node.prev;
    }
  }
}

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

上述代码中，使用Map来存储缓存数据，使用双向链表来维护缓存数据的访问顺序。当访问缓存数据时，先从Map中获取数据，然后将该节点移动到链表头部。当添加新的缓存数据时，先判断Map中是否已经存在该数据，如果存在，则将该节点移动到链表头部，否则添加新的节点到链表头部，并将该节点添加到Map中。当缓存数据超过容量时，删除链表尾部的节点，并从Map中删除该节点。

方式二：使用ES6 Map和Proxy实现LRU缓存

以下是使用ES6 Map和Proxy实现LRU缓存的示例代码：

function createLRUCache(capacity) {
  const cache = new Map();
  return new Proxy(cache, {
    get(target, key) {
      if (target.has(key)) {
        const value = target.get(key);
        target.delete(key);
        target.set(key, value);
        return value;
      }
      return -1;
    },
    set(target, key, value) {
      if (target.has(key)) {
        target.delete(key);
      }
      target.set(key, value);
      if (target.size > capacity) {
        target.delete(target.keys().next().value);
      }
      return true;
    },
  });
}

上述代码中，使用ES6 Map来存储缓存数据，使用Proxy来拦截对Map的访问。当访问缓存数据时，先从Map中获取数据，然后将该节点移动到Map的末尾。当添加新的缓存数据时，先判断Map中是否已经存在该数据，如果存在，则将该节点移动到Map的末尾，否则添加新的节点到Map的末尾。当缓存数据超过容量时，删除Map中第一个节点。

方式三：使用ES6 Map和Symbol实现LRU缓存

以下是使用ES6 Map和Symbol实现LRU缓存的示例代码：

const LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
  this.keys = [];
};

LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return -1;
  }
  const value = this.map.get(key);
  this.keys.splice(this.keys.indexOf(key), 1);
  this.keys.push(key);
  return value;
};

LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    this.keys.splice(this.keys.indexOf(key), 1);
  }
  this.keys.push(key);
  this.map.set(key, value);
  if (this.keys.length > this.capacity) {
    const firstKey = this.keys.shift();
    this.map.delete(firstKey);
  }
};

上述代码中，使用ES6 Map来存储缓存数据，使用Symbol来存储缓存数据的访问顺序。当访问缓存数据时，先从Map中获取数据，然后将该节点移动到Symbol对应的数组的末尾。当添加新的缓存数据时，先判断Map中是否已经存在该数据，如果存在，则将该节点移动到Symbol对应的数组的末尾，否则添加新的节点到Symbol对应的数组的末尾。当缓存数据超过容量时，删除Symbol对应的数组的第一个节点，并从Map中删除该节点。

总结

本文介绍了JavaScript实现LRU缓存的三种方式，包括使用Map和双向链表、ES6 Map和Proxy以及ES6 Map和Symbol等方式。了解这些内容可以帮助我们更好地使用LRU缓存算法来提高应用程序的性能和响应速度。