LRU 算法

题目描述

设计实现一个 LRU 机制，支持 get() 和 put() 方法。

• get(key) ：如果 key 存在缓存中，那么返回缓存中 key 所对应的 value，否则返回 -1。

• put(key, value)： 如果 key 已经存在于缓存中，那么更新其值，如果 key 不存在于缓存中，那么插入这组 key/value。当缓存容量达到上限时，需要删除最久未使用的数据值，进而为新插入的数据让出空间。

Code

class LRU {
  constructor(size) {
    this.size = size;
    this.cache = new Map();
  }
  get(key) {
    if (this.cache.has(key)) {
      // 删除后重新添加，利用 map 的有序性
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }
  put(key, value) {
    // 缓存中已经有该 key，那么视为更新操作
    if (this.cache.has(key)) {
      this.cache.delete(key);
      this.cache.set(key, value);
    } else {
      // 如果容量已满，那么需要先删除最久未使用的数据
      if (this.cache.size === this.size) {
        this.cache.delete(this.cache.entries().next().value[0]);
      }
      this.cache.set(key, value);
    }
  }
}