LRU缓存

介绍

LRU缓存实际就是将最近最少使用的数据删除的缓存策略，举个例子

• 缓存长度为3，目前有三个值分别是 [1, 2, 3]
• 然后我们访问缓存的顺序为 1 1 1 2 3
• 此时我们需要新增一个缓存，因为超过缓存长度所以我们需要先将1删除空出位置，因为最近访问了2和3，1是最早访问的故删除(即使他之前访问次数最多)

实现

因为get和put都需要O(1)，因此我们采用哈希表来做，具体做法就是

• 如果缓存命中，则将数据移动到哈希尾部(先删除再插入)，没命中则返回-1

• 插入新数据

  • 如果数据存在则进行更新操作(先删除再插入)
  • 如果不存在则判断容量是否足够，足够则直接插入，不足则需要删除头部的数据后插入

代码

class LRUCache {
  private capacity: number; // 容量
  private map: Map<number, number>; // 哈希

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key: number): number {
    // 命中缓存则删除后重新添加到尾部
    if (this.map.has(key)) {
      const value = this.map.get(key);
      this.map.delete(key);
      this.map.set(key, value!);
      return value!;
    }
    // 没有命中则返回-1
    return -1;
  }

  put(key: number, value: number): void {
    if (this.capacity === 0) return;
    if (this.map.has(key)) {
      // 如果缓存存在则变更内容 也是先删除后添加新值
      this.map.delete(key);
      this.map.set(key, value);
    } else {
      // 如果缓存不存在则添加 先判断超过容量要先移除头部
      if (this.map.size >= this.capacity) {
        const key = this.map.keys().next().value;
        this.map.delete(key);
      }
      this.map.set(key, value);
    }
  }
}