带你读《图解算法小抄》九、LRU（3）

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.keySet = new Set();
  }
  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      // 更新访问顺序
      this.keySet.delete(key);
      this.keySet.add(key);
      return value;
    }
    return -1;
  }
  put(key, value) {
    if (this.cache.has(key)) {
      // 更新已存在的键值对
      this.cache.set(key, value);
      // 更新访问顺序
      this.keySet.delete(key);
      this.keySet.add(key);
    } else {
      // 插入新的键值对
      if (this.cache.size === this.capacity) {
        // 达到容量上限，移除最久未使用的键值对
        const oldestKey = this.keySet.values().next().value;
        this.cache.delete(oldestKey);
        this.keySet.delete(oldestKey);
      }
      // 添加新的键值对
      this.cache.set(key, value);
      this.keySet.add(key);
    }
  }}