描述

LRU —— 最近最少使用

LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。 Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容

LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容

分析

利用map可以顺利实现，因为map的api非常好用

代码实现

class LRUCache {
  constructor(length) {
    if (length < 1) {
      throw new Error("长度不能小于1");
    }
    this.length = length;
    this._datas = new Map();
  }

  set(key, value) {
    let datas = this._datas;
    // 如果有了，那要删了之后重新set，保持set的是最新位置
    if (datas.has(key)) {
      datas.delete(key);
    }
    // 没有就放
    datas.set(key, value);

    // 判断长度是否超过设置的长度了
    if (datas.size > this.length) {
      const keyVal = datas.keys().next().value;
      datas.delete(keyVal);
    }
  }

  get(key) {
    if (!this._datas.has(key)) {
      return null;
    }
    let val = this._datas.get(key);
    this._datas.delete(key);
    this._datas.set(key, val);
    return val;
  }
}

// ----------------------test-----------------------
const lruCache = new LRUCache(2);
lruCache.set("1", 1); // Map(1) {1 => 1}
console.log("lruCache: ", lruCache);

lruCache.set("2", 2); // Map(2) {1 => 1, 2 => 2}
console.log("lruCache: ", lruCache);

console.log(lruCache.get("1")); // Map(2) {2 => 2, 1 => 1}
console.log("lruCache: ", lruCache);

lruCache.set("3", 3); // Map(2) {1 => 1, 3 => 3}
console.log("lruCache: ", lruCache);
console.log(lruCache.get("2")); // null

lruCache.set("4", 4); // Map(2) {3 => 3, 4 => 4}
console.log("lruCache: ", lruCache);
console.log(lruCache.get("1")); // null
console.log(lruCache.get("3")); // Map(2) {4 => 4, 3 => 3}
console.log(lruCache.get("4")); // Map(2) {3 => 3, 4 => 4}
console.log("lruCache: ", lruCache);

/* 
  lruCache:  LRUCache { length: 2, _datas: Map(1) { '1' => 1 } }
  lruCache:  LRUCache { length: 2, _datas: Map(2) { '1' => 1, '2' => 2 } }
  1
  lruCache:  LRUCache { length: 2, _datas: Map(2) { '2' => 2, '1' => 1 } }
  lruCache:  LRUCache { length: 2, _datas: Map(2) { '1' => 1, '3' => 3 } }
  null
  lruCache:  LRUCache { length: 2, _datas: Map(2) { '3' => 3, '4' => 4 } }
  null
  3
  4
  lruCache:  LRUCache { length: 2, _datas: Map(2) { '3' => 3, '4' => 4 } }
*/