浅谈Vue中keep-alive的LRU算法实现

最近面试的过程中，经常被问到 Vue 的 keep-alive 的实现原理，项目中使用多了，只知道它是咋用的，对其实现原理了解还真不多，最直接办法就是翻开源码去看，我在这儿贴一下源码位置，想要深入了解的可以去看下。

在这里，我们主要是讨论一下 keep-alive 中用到的 LRU缓存策略 ，我们可以看到源码的 created 钩子里绑定了两个属性 catch 和keys ，我简单描述下实现方法，就是通过 catch 数组缓存所有组件的 vNode 实例，当 catch 内原有组件被使用时会将该组件 key 从 keys 数组中删除，然后 push 到 keys 数组最后，如果新增后的缓存超过 max ，则将 keys 的首项删除掉。

created () {
    this.cache = Object.create(null)
    this.keys = []
}

cacheVNode() {
  const { cache, keys, vnodeToCache, keyToCache } = this
  if (vnodeToCache) {
    const { tag, componentInstance, componentOptions } = vnodeToCache
    cache[keyToCache] = {
      name: getComponentName(componentOptions),
      tag,
      componentInstance,
    }
    keys.push(keyToCache)
    // prune oldest entry
    if (this.max && keys.length > parseInt(this.max)) {
      pruneCacheEntry(cache, keys[0], keys, this._vnode) //删除首项
    }
    this.vnodeToCache = null
  }
}

什么是LRU

LRU 是Least Recently Used的缩写，即最近最少使用算法，LRU 算法的基本思想当缓存空间已满时，优先淘汰最近最少使用的缓存数据，以腾出更多的缓存空间，因此，LRU算法需要维护一个缓存空间。

基本原理如下图所示

接下来，我们尝试实现一下

实现方法

数组

我们用数组模拟一个栈，对数组进行操作。

class LRUCatcByArray {
  length = 0; // 缓存量
  catch = Object.create(null); // 缓存数据
  keys = []; // 通过数组模拟栈，以及当前缓存在栈中的排序

  constructor(length) {
    if (length < 1) throw Error("缓存长度参数不合法");
    this.length = length;
  }

  get(key) {
    // 如果当前缓存中不存在，则返回null
    if (!this.catchs[key]) return null;
    // 需要将访问的缓存，放到当前栈顶，表示是最新数据
    const index = this.getKeyIndex();
    // 删除原数据
    this.keys.splice(index, 1);
    // 并将其插入到栈顶
    this.keys.unshift(key);
    // 返回缓存中的数据
    return this.catchs[key];
  }

  set(key, newCatch) {
    const index = this.getKeyIndex(key);
    if (index !== -1) {
      // 如果存在数据，则需要将原数据删除，并插入到栈顶
      this.keys.splice(index, 1);
      this.keys.unshift(key);
    } else {
      // 如果不存在数据，则直接插入栈顶
      this.keys.unshift(key);
    }
    // 更新当前缓存中的数据
    this.catchs[key] = newCatch;
    // 更新栈后，需要校验当前栈是否溢出
    if (this.length < this.keys.length) {
      // 如果溢出，则将栈尾数据剔除
      const tmp = this.keys.pop();
      // 并删除当前缓存中的数据，避免已删除的缓存可能被访问到
      delete this.catchs[tmp];
    }
  }

  getKeyIndex(key) {
    // 返回key在当前栈中的下标
    return this.keys.findIndex(item => item === key);
  }
}

我们来测试验证一下吧

const lru = new LRUCatchByArray(3);
lru.set(4, 'a') // catchs:{4: 'a'} keys:[4]
lru.set(7, 'b') // catchs:{4: 'a', 7: 'b'} keys:[7,4]
lru.set(1, 'c') // catchs:{1: 'c', 4: 'a', 7: 'b'} keys:[1,7,4]
lru.get(4) // catchs:{1: 'c', 4: 'a', 7: 'b'} keys:[4,1,7]
lru.set(0, 'd') // catchs:{0: 'd', 1: 'c', 4: 'a'} keys:[0,4,1]

Map

基于对象属性值只能是字符串的限制，我们可以通过 Map 来优化，同时 Map 在设置数据时，是按照其设置的先后顺序进行入栈，那么我们就可以利用这个优点来模拟栈顺序。

class LRUCatcByMap {
  length = 0;
  catchs = new Map();

  constructor(length) {
    if (length < 1) throw Error("缓存长度参数不合法");
    this.length = length;
  }

  get(key) {
    const { catchs } = this;
    // 如果当前缓存中不存在，则返回null
    if (!catchs.has(key)) return null;
    // 如果存在数据，则需要将原数据删除，并插入到尾部
    const value = catchs.get(key);
    catchs.delete(key);
    catchs.set(key, value);
    return value;
  }

  set(key, value) {
    const { catchs, length } = this;
    // 判断当前缓存中是否存在，如果存在则删除数据
    if (catchs.has(key)) {
      catchs.delete(key);
    }
    // 删除数组后，并将数据插入到尾部
    catchs.set(key, value);
    // 更新栈后，需要校验当前栈是否溢出
    if (catchs.size > length) {
      // 如果溢出，则将头部数据删除
      const delKey = catchs.keys().next().value; // Map.keys返回的属性迭代器，可通过.next()来依次获取
      catchs.delete(delKey)
    }
  }
}

同样，我们来测试验证一下吧

const lru = new LRUCatcByMap(3)
lru.set(4, 'a') // {4 => 'a'}
lru.set(7, 'b') // {4 => 'a', 7 => 'b'}
lru.set(1, 'c') // {4 => 'a', 7 => 'b', 1 => 'c'}
lru.get(4) // {7 => 'b', 1 => 'c', 4 => 'a'}
lru.set(0, 'd') // {1 => 'c', 4 => 'a', 0 => 'd'}

总结

以上两种实现 LRU缓存 的方法，其中使用Map是最佳的方式，通过 Array 方式，需要每次遍历查询下标位置，性能开销上比较大。