LRU算法全称为least recently use 最近最少使用，核心思路是最近被访问的以后被访问的概率会变高，那么可以把之前没被访问的进行删除，维持一个稳定的最大容量值，从而不会导致内存溢出。
目录
vue的keep-alive内置组件的使用也是使用了改算法，源码如下：
export default { name: "keep-alive", // 抽象组件属性 ,它在组件实例建立父子关系的时候会被忽略,发生在 initLifecycle 的过程中 abstract: true, props: { // 被缓存组件 include: patternTypes, // 不被缓存组件 exclude: patternTypes, // 指定缓存大小 max: [String, Number] }, created() { // 初始化用于存储缓存的 cache 对象 this.cache = Object.create(null); // 初始化用于存储VNode key值的 keys 数组 this.keys = []; }, destroyed() { for (const key in this.cache) { // 删除所有缓存 pruneCacheEntry(this.cache, key, this.keys); } }, mounted() { // 监听缓存（include）/不缓存（exclude）组件的变化 // 在变化时，重新调整 cache // pruneCache：遍历 cache，如果缓存的节点名称与传入的规则没有匹配上的话，就把这个节点从缓存中移除 this.$watch("include", val => { pruneCache(this, name => matches(val, name)); }); this.$watch("exclude", val => { pruneCache(this, name => !matches(val, name)); }); }, render() { // 获取第一个子元素的 vnode const slot = this.$slots.default; const vnode: VNode = getFirstComponentChild(slot); const componentOptions: ?VNodeComponentOptions = vnode && vnode.componentOptions; if (componentOptions) { // name 不在 inlcude 中或者在 exlude 中则直接返回 vnode，否则继续进行下一步 // check pattern const name: ?string = getComponentName(componentOptions); const { include, exclude } = this; if ( // not included (include && (!name || !matches(include, name))) || // excluded (exclude && name && matches(exclude, name)) ) { return vnode; } const { cache, keys } = this; // 获取键，优先获取组件的 name 字段，否则是组件的 tag const key: ?string = vnode.key == null ? // same constructor may get registered as different local components // so cid alone is not enough (#3269) componentOptions.Ctor.cid + (componentOptions.tag ? `::${componentOptions.tag}` : "") : vnode.key; // -------------------------------------------------- // 下面就是 LRU 算法了， // 如果在缓存里有则调整， // 没有则放入（长度超过 max，则淘汰最近没有访问的） // -------------------------------------------------- // 如果命中缓存，则从缓存中获取 vnode 的组件实例，并且调整 key 的顺序放入 keys 数组的末尾 if (cache[key]) { vnode.componentInstance = cache[key].componentInstance; // make current key freshest remove(keys, key); keys.push(key); } // 如果没有命中缓存,就把 vnode 放进缓存 else { cache[key] = vnode; keys.push(key); // prune oldest entry // 如果配置了 max 并且缓存的长度超过了 this.max，还要从缓存中删除第一个 if (this.max && keys.length > parseInt(this.max)) { pruneCacheEntry(cache, keys[0], keys, this._vnode); } } // keepAlive标记位 vnode.data.keepAlive = true; } return vnode || (slot && slot[0]); } }; // 移除 key 缓存 function pruneCacheEntry ( cache: VNodeCache, key: string, keys: Array, current?: VNode ) { const cached = cache[key] if (cached && (!current || cached.tag !== current.tag)) { cached.componentInstance.$destroy() } cache[key] = null remove(keys, key) } // remove 方法（shared/util.js） /** * Remove an item from an array. */ export function remove (arr: Array, item: any): Array | void { if (arr.length) { const index = arr.indexOf(item) if (index > -1) { return arr.splice(index, 1) } } }
实现一个自己的LRU算法
lru算法 的核心api(put get)和一个size最大容器值,本质是类似队列 put实现思路 1 是否存在，存在就先删除，再添加到队头 2 不存在，容量是否满了，删除最后一个队尾，再添加队头 get实现思路： 1.有就返回，同时插入队头 2.没有返回-1 时间复杂度O(1)
class LRU { constructor(size) { this.cache = new Map() this.size = size } put (key, val) { //存在 if (this.cache.has(key)) { //删除 this.cache.delete(key) } else { //不存在，容量是否满了 if (this.size === this.cache.size) { //删除最后一个 this.cache.delete(this.cache.keys().next().value) //拿到队尾的元素 } } //插在队头 this.cache.set(key, val) } get (key) { let val = this.cache.get(key) if (!val) { return -1 } //访问了就需要放在队头 this.put(key, val) return val } }
另一种
//定义节点类 class Node { constructor(pre, next, value, key){ this.pre = pre; this.next = next; this.value = value; this.key = key; } } //定义双向链表 class DoubleList { constructor(head, tail){ this.head = head; this.tail = tail; } } class LRUCache { //构造函数，传入缓存容量 constructor(max){ this.max = max; this.map = new Map(); let node = new Node(null, null, null, null); this.doubleList = new DoubleList(node, node); } /** * 获取缓存值 * 不存在返回-1，存在返回对应value值，并将此节点移到尾巴 * @param {*} key key值 */ get(key){ let node = this.map.get(key) if(!node){ return -1; }else{ this.moveNode2Tail(key, node); return node.value; } } /** * 插入缓存 * 1.不存在对应key值，加到尾巴 * 2.存在对应key值，更新此key值对应value并提到尾巴 * 3.超出容量的话，去掉头部数据 * @param {*} key key值 * @param {*} value value */ put(key, value) { let node = this.map.get(key); if(node){ if(!node.next){ node.value = value; return; } node.pre.next = node.next; node.next.pre = node.pre; } let newNode = new Node(null, null, value, key); newNode.pre = this.doubleList.tail; this.doubleList.tail.next = newNode; this.doubleList.tail = newNode; this.map.set(key, newNode); if(this.map.size > this.max){ this.map.delete(this.doubleList.head.next.key); this.doubleList.head.next = this.doubleList.head.next.next; this.doubleList.head.next.pre = this.doubleList.head; } } //将节点移到尾巴 moveNode2Tail(key,node){ if(!node.next){ return; } //删除节点 node.pre.next = node.next; node.next.pre = node.pre; this.map.delete(key) //新增尾巴节点 let newNode = new Node(null, null, node.value, key); newNode.pre = this.doubleList.tail; this.doubleList.tail.next = newNode; this.doubleList.tail = newNode; this.map.set(key, newNode); } }
以上就是LRU算法在Vue内置组件keep-alive中的使用的详细内容，更多关于Vue LRU算法的资料请关注本站其它相关文章！
以上就是LRU算法在Vue内置组件keep-alive中的使用的详细内容，更多请关注本站其它相关文章！
