LRU 缓存

LRU 缓存的语义是什么？

• 容量限制: 最多保存 capacity 个键值对;
• get(key): 命中则返回并标记为最近使用, 未命中返回 -1;
• put(key, value): 存在则更新并标记为最近使用; 不存在则插入, 超容量时淘汰最久未使用的一项;
• 目标复杂度: get、put 均为 $O(1)$;

为什么用哈希表加双向链表？

• 哈希表: 提供 key → 结点 的 $O(1)$ 定位, 解决"找不到结点就无法移动它"的问题;
• 双向链表: 提供 $O(1)$ 摘除与插入, 并维护使用顺序 (表头最旧, 表尾最新);
• 哨兵: 双向循环链表只用一个 dummy 即可同时代表头尾;

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.dummy = { key: 0, val: -1, prev: null, next: null };
    this.dummy.prev = this.dummy.next = this.dummy;
    this.hash = new Map();
  }

  #remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #push(node) {
    const tail = this.dummy.prev;
    tail.next = node;
    node.prev = tail;
    node.next = this.dummy;
    this.dummy.prev = node;
  }

  get(key) {
    if (!this.hash.has(key)) return -1;
    const node = this.hash.get(key);
    this.#remove(node);
    this.#push(node);
    return node.val;
  }

  put(key, value) {
    if (this.hash.has(key)) {
      const node = this.hash.get(key);
      this.#remove(node);
      this.#push(node);
      node.val = value;
      return;
    }
    const node = { key, val: value, prev: null, next: null };
    this.#push(node);
    this.hash.set(key, node);
    if (this.hash.size > this.capacity) {
      const oldest = this.dummy.next;
      this.#remove(oldest);
      this.hash.delete(oldest.key);
    }
  }
}

只用 Map 怎么实现？

• 依据: Map 迭代顺序等于插入顺序, 且 delete 后重新 set 会把键移到末尾;
• 命中: delete 再 set 同一键值对, 相当于"移到最近使用";
• 淘汰: this.map.keys().next().value 即最久未使用的键;

class LRUCacheWithMap {
  constructor(capacity) {
    this.map = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}