什么是 LRU

LRU 是一种缓存淘汰算法，用于管理缓存中的数据。算法思路是保留最近使用过的数据，淘汰最久未被使用的数据

需要实现的功能如下：

1. 设置缓存大小:初始化容量，当容量达到上线时，需要淘汰数据
2. 设置数据: 将数据写入缓存。需要判断缓存容量，并将当前的值设置为最新使用的
3. 获取数据: 从缓存中读取数据，并将当前的值设置为最新使用的
4. 淘汰数据: 缓存容量达到上线时，需要删除最久未使用的数据

代码逻辑如下:

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

JavaScript 中的 Map

Map.prototype.keys() 会返回一个 map 的 keys 对象的迭代器

const myMap = new Map();
myMap.set('0', 'foo');
myMap.set(1, 'bar');
myMap.set({}, 'baz');

const mapIter = myMap.keys();

console.log(mapIter);

console.log(mapIter.next());
console.log(mapIter.next());
console.log(mapIter.next());

可以看到，map keys 迭代器返回的顺序，就是设置 key 的数据。越早设置，在迭代器中的位置越靠前

基于此，可以使用 Map 这种数据结构实现 LRU

代码实现

lru.ts

/**
 *  Least Recently Used
 */
class LRUCache {
  capacity: number;
  cache: Map<any, any>;
  constructor(capacity: number) {
    this.capacity = capacity || 5;
    this.cache = new Map();
  }

  /**
   * 向缓存中设置值
   * 1. 如果缓存中存在 key， 覆盖对应的值，将本次的值设为 LRU
   * 2. 如果缓存中不存在 key
   *    2.1 缓存未满，直接设置值，并将本次的值设置为 LRU
   *    2.2 缓存已满，删除最久未被使用的值; 设置本次的值为 LRU
   * @param {*} key
   * @param {*} value
   */
  put(key: any, value: any) {
    if (this.cache.get(key)) {
      this.cache.set(key, value);
      this.refresh(key);
      return null;
    }

    if (this.cache.size >= this.capacity) {
      // map.keys 返回的顺序是设置的顺序，越早设置的越靠前
      this.cache.delete(this.cache.keys().next().value);
    }

    this.cache.set(key, value);
    return null;
  }

  /**
   *
   * 获取缓存中对应键的值
   * 如果存在，返回对应的值，并刷新为 "LRU"
   * 如果不存在，返回 null
   * @param {*} index
   */
  get(key: any) {
    if (!this.cache.has(key)) {
      return -1;
    }

    // 刷新为 LRU
    this.refresh(key);
    return this.cache.get(key);
  }

  private refresh(key: any) {
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
  }
}

const cache = new LRUCache(2);

console.log(cache.put(1, 1)); // 返回 null   此时cache为【1】
console.log(cache.put(2, 2)); // 返回 null   此时cache为【2,1】
console.log(cache.get(1)); // 返回 1         此时cache为【1,2】，因为使用了1,1变成“新鲜的”
console.log(cache.put(3, 3)); // 返回 null   此时cache为【3,1】，超过容量了，把“老油条”2淘汰
console.log(cache.get(2)); // 返回 -1        此时cache为【3,1】
console.log(cache.put(4, 4)); // 返回 null   此时cache为【4,3】，超过容量了，把“老油条”1淘汰
console.log(cache.get(1)); // 返回 -1        此时cache为【4,3】
console.log(cache.get(3)); // 返回 3         此时cache为【3,4】
console.log(cache.get(4)); // 返回 4         此时cache为【4,3】