js 实现 LRU缓存

LRU是Least Recently Used的缩写，即最近最少使用，是一种常见的缓存置换算法，淘汰最久未使用的数据。

实现思路

1. 设定缓存的最大数据量maxSize

2. 数据按照最近访问时间进行排序，最近访问的数据放在最后

3. 访问时若数据存在则将数据移动到最后

4. 添加数据时：

   1. 数据存在，则移动到最后

   2. 不存在，若队列中数据量已到最大值，删除第一个数据，再添加新数据；否则直接添加新数据

代码

由于Map中的数据根据插入的时间具有先后顺序，所以这里使用map来实现；测试地址

class LRU {
  queue = new Map();

  constructor(capacity = 10) {
    // 设置容量
    this.capacity = capacity;
  }

  // 获取数据
  get(key) {
    if (this.queue.has(key)) {
      const value = this.queue.get(key);
      this.queue.delete(key);
      this.queue.set(key, value);
      return value;
    }
    return undefined;
  }

  // 添加数据， 如果存在则移动位置；若数据已经满了，删除第一个元素后再添加
  put(key, value) {
    if (this.queue.has(key)) {
      this.queue.delete(key);
      this.queue.set(key, value);
      return;
    }

    if (this.queue.size >= this.capacity) {
      this.removeFirstItem();
    }
    this.queue.set(key, value);
  }

  // 删除第一个元素
  removeFirstItem() {
    if (this.queue.size) {
      this.queue.delete(this.queue.keys().next().value);
    }
  }
  // 删除数据
  remove(key) {
    if (this.queue.has(key)) {
      this.queue.delete(key);
    }
  }
}

1. 来测试一把，设置容量为4：

const lru = new LRU(4);
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
console.log([...lru.queue.values()]);

输出:

[1, 2, 3]

2. 读取数据：

const lru = new LRU(4);
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
lru.get(1);
console.log([...lru.queue.values()]);

输出:

[2, 3, 1]

现在1现在在最后了。

3. 当数据超过容量后再插入数据

const lru = new LRU(4);
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
lru.put(4, 4);
lru.put(5, 5);
console.log([...lru.queue.values()]);

输出：

 [2, 3, 4, 5]

数据1被删除了.

结束语

上面就是一个简单版的LRU缓存实现，当然在实际使用中还需要结合自身的业务进行调整。