什么是LRU?

英文就是Least Recently Used，最近最久未使用法。它是按照一个非常著名的计算机操作系统基础理论得来的：

最近使用的数据会在未来一段时期内仍然被使用，已经很久没有使用的数据很有可能在未来较长的一段时间内仍然不会被使用。

基于这个思想，会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！

LRU实现

class LRU {
  constructor (max = 10) {
    this.max = max; // 最大缓存数量
    this.list = []; // 记录key，最新的在尾部，最久未使用在头部
    this.map = new Map(); // 储存值
  }

  // 设置数据
  setItem (key, val) {
    if (this.map.has(key)) {
      this._updateKey(key);
      return this.map.set(key, val); // 已有的直接设置更新
    }
    this.list.push(key);
    if (this.list.length > this.max) {
      const unUsedKey = this.list.shift(); // 超出最大限制，去掉前面的key
      this.map.delete(unUsedKey);// 去掉无用的item
    }
    this.map.set(key, val);
  }

  // 获取数据
  getItem (key) {
    this._updateKey(key);
    return this.map.get(key);
  }

  // 更新key在数组中的位置
  _updateKey (key) {
    const index = this.list.findIndex(i => i === key);
    if (index === -1) return;
    // 拿出来的key放到尾部
    this.list.splice(index, 1);
    this.list.push(key);
  }
}

LRU的日常应用场景

• 对于频繁切换的数据，并且数据短期不会变化，避免每次切换都要重新走一遍获取数据流程浪费时间
• 数据无限多，但是需要一个固定单位数的数据存放处

不适用的场景

• 数据每次获取都不一定相同的场景
• 数据单位数少，而数据存放处足够大

LRU算法与备忘录模式的区别

之前我写了另外一篇文章 js性能优化-利用备忘模式进行结果缓存

• 共同点：都是对不变的数据进行存储
• 不同点：LRU 的关注点在缓存淘汰机制， 而备忘录模式关注点在于数据的二次获取效率