最近最少使用缓存

/*
 * 题目：最近最少使用缓存
 * 要求：实现 LRUCache(capacity)，capacity 为正整数；put(key,value) 插入或更新，get(key) 返回值、未命中返回 -1。读命中与更新都刷新最近使用顺序；超容量时淘汰最久未使用项，两操作平均 O(1)。
 * 示例：容量 2，依次 put(1,1)、put(2,2)、get(1)、put(3,3)，再 get(2) 返回 -1，因为键 2 最久未使用。
 */
class LRUCache {
  constructor(capacity) {}
  get(key) {}
  put(key, value) {}
}
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 预期：1
cache.put(3, 3);
console.log(cache.get(2)); // 预期：-1
cache.put(1, 10);
console.log(cache.get(1)); // 预期：10
console.log(cache.get(3)); // 预期：3

class LRUCache {
  constructor(capacity) {
    this.max = capacity;
    this.map = new Map();
  }
  get(key) {
    if (this.map.has(key)) {
      const value = this.map.get(key);
      // 删除后重新插入，使本次读到的键成为最近使用的一项。
      this.map.delete(key);
      this.map.set(key, value);
      return value;
    }

    return -1;
  }
  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
      this.map.set(key, value);
    } else {
      if (this.map.size < this.max) {
        this.map.set(key, value);
      } else {
        // keys() 从最旧键开始迭代；next().value 才是键本身。
        const oldestKey = this.map.keys().next().value;
        this.map.delete(oldestKey);
        this.map.set(key, value);
      }
    }
  }
}

// 三组以上可直接运行的验证。
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 预期：1
cache.put(3, 3);
console.log(cache.get(2)); // 预期：-1
cache.put(1, 10);
console.log(cache.get(1)); // 预期：10
console.log(cache.get(3)); // 预期：3