LRU 缓存置换

• LRU（Least Recently Used）(最久未使用)缓存置换算法
• 在限定的空间已存满数据时，再要增加缓存应当先把一个最近未使用的数据置换出去，然后把新的数据插入到缓存中。

实现

class LRUCache {
  #map;
  #length;
  constructor(len) {
    this.#length = len;
    this.#map = new Map();
  }
  has(key) {
    return this.#map.has(key);
  }
  //获取缓存->获取到了就是最新的缓存访问，所以需要添加到队列头部
  get(key) {
    if (!this.has(key)) return null;
    let value = this.#map.get(key);
    //删除当前key，添加到队列头部
    this.#map.delete(key);
    this.#map.set(key, value);
    return value;
  }
  //设置缓存
  set(key, value) {
    //溢出，删除队列尾部
    if (this.#map.size >= this.#length) {
      this.#map.delete(this.#map.keys().next().value);
    }
    //修改缓存
    if (this.has(key)) {
      this.#map.delete(key);
    }
    this.#map.set(key, value);
  }
}
//测试
let cache = new LRUCache(3);
cache.set("a", 1);
cache.set("b", 2);
cache.set("c", 3);
console.log(cache);
// 0: {"a" => 1} 1: {"b" => 2}2: {"c" => 3}
cache.get("a");
// 0: {"b" => 2}1: {"c" => 3}2: {"a" => 1}
console.log(cache);
cache.set("d", 4);
//0: {"c" => 3}1: {"a" => 1}2: {"d" => 4}
console.log(cache);