• 浅谈Vue中keep-alive的LRU算法实现
  • 发布于 2个月前
  • 98 热度
    0 评论
最近面试的过程中,经常被问到 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 LRUCatchByArray {
  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(key);
    // 删除原数据
    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];
    }
  }
   // 堆代码 duidaima.com
  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 LRUCatchByMap {
  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 LRUCatchByMap(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 方式,需要每次遍历查询下标位置,性能开销上比较大。
用户评论