Vue 内置组件 keep-alive 中 LRU 缓存淘汰策略和实现

LRU（Least Recently Used，最近最少使用）是通过记录缓存项的访问顺序来决定淘汰的策略：当缓存满时，移除最久未被使用的项。

核心概念：

• 缓存存储：使用 Map 存储键值对，用于快速访问缓存内容。
• 访问顺序跟踪：通过 双向链表（LinkedList） 跟踪缓存的访问顺序，访问过的元素会被移动到链表的前端，最久未访问的元素位于链表的尾部。
• 淘汰机制：缓存容量满时，删除链表尾部的元素，即最少使用的元素。

代码实现：

1. LRUCache 类：负责管理缓存，使用 Map 存储键值对，使用 LinkedList 跟踪访问顺序。
2. LinkedList 类：双向链表，用于按访问顺序排列缓存项，支持移动元素到链表前端、删除尾部元素等操作。
3. Node 类：链表节点，用于存储缓存项。

工作方式：

• get(key)：如果缓存存在，移至链表前端，表示最近使用。
• put(key, value)：插入新缓存或更新现有缓存，满时淘汰尾部项。

代码示例：

// 双向链表节点定义
class Node {constructor(value) {this.value = value; // 节点值this.prev = null;   // 指向前一个节点this.next = null;   // 指向后一个节点}
}// LRUCache 类实现 LRU 缓存
class LRUCache {constructor(maxSize) {this.maxSize = maxSize;this.cache = new Map(); // Map 存储缓存，保证插入顺序this.list = new LinkedList();// 链表记录访问顺序}// 获取缓存值	get(key) {if (this.cache.has(key)) { // 如果缓存中存在该 keythis.list.moveToFront(key); // 将该 key 移动到链表头return this.cache.get(key); // 返回缓存值}return null; // 如果没有找到，返回 null}// 插入或更新缓存put(key, value) {// 如果缓存中已经有该 key，将该项移到链表前端if (this.cache.has(key)) {this.list.moveToFront(key);} else {if (this.cache.size >= this.maxSize) { // 如果缓存已满// 移除尾部的最久未使用项，从缓存中删除该项const lastKey = this.list.removeLast();this.cache.delete(lastKey);}this.list.addAtFront(key); // 将新项添加到链表头}this.cache.set(key, value); // 更新缓存的值}
}// 双向链表实现
class LinkedList {constructor() {// 初始化链表为空this.head = this.tail = null;  // 初始化链表为空}// 将节点插入到链表前端addAtFront(value) {const newNode = new Node(value); // 创建新节点if (this.head) { // 1.如果链表非空：新节点的 next 指向当前头节点。当前头节点的 prev 指向新节点newNode.next = this.head;this.head.prev = newNode;} else {this.tail = newNode; // 2.如果链表为空，新的节点是尾节点}this.head = newNode; // 3.新节点为头节点}// 将某个节点移动到链表头moveToFront(value) {const node = this.find(value); // 查找节点if (node === this.head) return; // 如果该节点已在头部，直接返回   // 更新 node 的前后节点，使其从链表中移除。// 当前节点的前一个节点 node.prev 的 next 指针，指向当前节点的下一个节点 node.nextif (node.prev) node.prev.next = node.next;// 当前节点的下一个节点 node.next 的 prev 指针，指向 当前节点的前一个节点 node.previf (node.next) node.next.prev = node.prev;// 如果是尾节点，更新尾节点if (this.tail === node) this.tail = node.prev; // 将节点插入到链表前端this.addAtFront(value);}// 移除链表尾部节点并返回其 keyremoveLast() {const value = this.tail.value; // 获取尾部节点的值if（this.head === this.tail） {  // 如果链表只有一个节点this.head = this.tail = null // 清空链表} else {this.tail = this.tail.prev // 更新尾节点this.tail.next = null // 断开尾节点与原节点的链接}return value; // 返回移除值}// 查找链表中某个节点find(value) {let current = this.head;// 遍历链表，找到目标节点while (current && current.value !== value) {current = current.next;}return current;}
}

注释解释

• LRUCache 类：实现了缓存的主要功能，包括存储数据、获取数据、添加新数据、以及缓存淘汰。其中 get 和 put 方法：实现了缓存读取和更新逻辑，并保证缓存的顺序和容量。
• LinkedList 类：双向链表，用来维护缓存访问顺序。链表的头节点表示最近使用的缓存项，尾节点表示最久未使用的缓存项。
• Node 类：链表中的节点，每个节点包含值以及指向前后节点的指针。

操作示例：

const cache = new LRUCache(3);
cache.put('key1', 'value1');
cache.put('key2', 'value2');
cache.put('key3', 'value3');
cache.get('key1'); // 最近使用过，移到前端
cache.put('key4', 'value4'); // 超过最大容量，移除最后使用的key3

LRU 缓存淘汰策略总结：

1. 缓存项访问顺序：每次访问都会将该缓存项移到前端，表示最近使用。
2. 满缓存时淘汰：如果缓存超出最大容量，淘汰链表尾部的最久未访问项（LRU）。
3. 效率：Map 提供 O(1) 时间复杂度的缓存存取，LinkedList 保证了 O(1) 的插入、移动和删除操作。

记忆要点：

• LRU：最近最少使用的缓存项会被淘汰。
• 双向链表：用来维护缓存项的访问顺序，确保 O(1) 时间复杂度。
• 缓存淘汰：超出容量时，淘汰最久未访问的缓存项。