张家港建网站费用,免费ppt模板下载公众号,个人网站域名所有权,设计网页通常用什么语言LRU#xff08;Least Recently Used#xff0c;最近最少使用#xff09;是通过记录缓存项的访问顺序来决定淘汰的策略#xff1a;当缓存满时#xff0c;移除最久未被使用的项。
核心概念#xff1a;
缓存存储#xff1a;使用 Map 存储键值对#xff0c;用于快速访问缓…LRULeast Recently Used最近最少使用是通过记录缓存项的访问顺序来决定淘汰的策略当缓存满时移除最久未被使用的项。
核心概念
缓存存储使用 Map 存储键值对用于快速访问缓存内容。访问顺序跟踪通过 双向链表LinkedList 跟踪缓存的访问顺序访问过的元素会被移动到链表的前端最久未访问的元素位于链表的尾部。淘汰机制缓存容量满时删除链表尾部的元素即最少使用的元素。
代码实现
LRUCache 类负责管理缓存使用 Map 存储键值对使用 LinkedList 跟踪访问顺序。LinkedList 类双向链表用于按访问顺序排列缓存项支持移动元素到链表前端、删除尾部元素等操作。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; // 获取尾部节点的值ifthis.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); // 超过最大容量移除最后使用的key3LRU 缓存淘汰策略总结
缓存项访问顺序每次访问都会将该缓存项移到前端表示最近使用。满缓存时淘汰如果缓存超出最大容量淘汰链表尾部的最久未访问项LRU。效率Map 提供 O(1) 时间复杂度的缓存存取LinkedList 保证了 O(1) 的插入、移动和删除操作。
记忆要点
LRU最近最少使用的缓存项会被淘汰。双向链表用来维护缓存项的访问顺序确保 O(1) 时间复杂度。缓存淘汰超出容量时淘汰最久未访问的缓存项。
