【每日算法】LeetCode 146. LRU 缓存机制-平芜编程栈

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 146. LRU 缓存机制

1. 题目描述

1.1 问题要求

设计一个LRU（最近最少使用）缓存机制，实现以下两个操作：

get(key)：如果密钥key存在于缓存中，则返回密钥的值，否则返回-1
put(key, value)：如果密钥不存在，则写入数据；当缓存容量达到上限时，删除最久未使用的数据

1.2 注意事项

所有操作（get和put）必须在O(1)时间复杂度内完成
当缓存达到容量上限时，put操作需要淘汰最久未使用的数据
即使只是查询 (get) 数据，该数据也会变为"最近使用"的数据

2. 问题分析

2.1 核心需求分析

LRU缓存的核心需求是：快速访问 + 快速淘汰。这意味着我们需要：

快速查找：通过key快速找到对应值（哈希表的特性）
快速删除和插入：能够快速将某个元素移到"最近使用"位置，或在容量满时删除最久未使用的元素（链表的特性）
维护访问顺序：记录每个key的访问时间顺序

2.2 前端视角的理解

在前端开发中，LRU缓存的应用非常广泛：

浏览器缓存机制
Vue/React的keep-alive组件
图片/资源缓存策略
API响应缓存

3. 解题思路

3.1 可行思路分析

3.1.1 思路一：数组/对象 + 时间戳（不可行）

使用对象存储键值对，记录每个key的最后访问时间
每次操作时更新时间戳，淘汰时遍历查找最旧的时间
缺点：淘汰时需要O(n)遍历，不满足O(1)要求

3.1.2 思路二：Map的天然特性（ES6 Map）

Map按照插入顺序维护键值对，最后插入的在最后
每次访问时先删除再重新插入，可以维护顺序
复杂度：O(1)时间完成所有操作

3.1.3 思路三：哈希表 + 双向链表（经典解法）

哈希表提供O(1)的查找
双向链表提供O(1)的删除和插入，维护访问顺序
头节点表示最近访问，尾节点表示最久未访问

3.2 最优解选择

思路三（哈希表+双向链表）是最经典的LRU实现方案，虽然ES6的Map也可以实现，但了解底层原理对理解缓存机制更有帮助。

4. 各思路代码实现

4.1 思路二：ES6 Map实现

classLRUCache{constructor(capacity){this.capacity=capacity;this.cache=newMap();// Map天然保持插入顺序}get(key){if(!this.cache.has(key))return-1;// 获取值constvalue=this.cache.get(key);// 删除后重新插入，保证在Map最后（最近使用）this.cache.delete(key);this.cache.set(key,value);returnvalue;}put(key,value){// 如果key已存在，先删除if(this.cache.has(key)){this.cache.delete(key);}// 如果容量已满，删除第一个（最久未使用）elseif(this.cache.size>=this.capacity){constfirstKey=this.cache.keys().next().value;this.cache.delete(firstKey);}// 插入新值this.cache.set(key,value);}}

4.2 思路三：哈希表 + 双向链表实现

// 双向链表节点classListNode{constructor(key,value){this.key=key;this.value=value;this.prev=null;this.next=null;}}classLRUCache{constructor(capacity){this.capacity=capacity;this.cache=newMap();// 哈希表：key -> 链表节点this.size=0;// 创建虚拟头尾节点，简化边界判断this.head=newListNode(0,0);// 最近使用this.tail=newListNode(0,0);// 最久未使用this.head.next=this.tail;this.tail.prev=this.head;}// 获取节点get(key){if(!this.cache.has(key))return-1;constnode=this.cache.get(key);// 移动到链表头部（表示最近使用）this.moveToHead(node);returnnode.value;}// 插入节点put(key,value){if(this.cache.has(key)){// 更新已存在的节点constnode=this.cache.get(key);node.value=value;this.moveToHead(node);}else{// 创建新节点constnewNode=newListNode(key,value);this.cache.set(key,newNode);this.addToHead(newNode);this.size++;// 如果超过容量，删除尾部节点if(this.size>this.capacity){consttailNode=this.removeTail();this.cache.delete(tailNode.key);this.size--;}}}// 将节点移动到头部（最近使用）moveToHead(node){this.removeNode(node);this.addToHead(node);}// 从链表中删除节点removeNode(node){node.prev.next=node.next;node.next.prev=node.prev;}// 在头部添加节点addToHead(node){node.prev=this.head;node.next=this.head.next;this.head.next.prev=node;this.head.next=node;}// 删除尾部节点（最久未使用）removeTail(){consttailNode=this.tail.prev;this.removeNode(tailNode);returntailNode;}}

5. 各实现思路的复杂度、优缺点对比表格

实现方案	时间复杂度	空间复杂度	优点	缺点	适用场景
ES6 Map实现	get: O(1) put: O(1)	O(capacity)	1. 代码简洁，易于理解 2. 利用语言特性 3. 开发效率高	1. 隐藏了底层原理 2. Map内部实现不透明	实际项目开发、快速原型
哈希表+双向链表	get: O(1) put: O(1)	O(capacity)	1. 展示完整缓存机制原理 2. 面试中展现扎实基础 3. 可控性更强	1. 代码相对复杂 2. 需要手动维护链表	面试场景、学习缓存原理、需要定制化场景

6. 总结

6.1 技术要点总结

LRU核心思想：最近使用的数据在未来更可能被使用，应该保留
数据结构选择：哈希表提供快速查找，链表维护使用顺序
边界处理：使用虚拟头尾节点可显著简化代码逻辑
时间复杂度保证：所有操作必须为O(1)，这是LRU缓存设计的核心要求

6.2 前端实际应用场景

6.2.1 浏览器缓存

浏览器对静态资源（JS、CSS、图片）的缓存采用类似LRU的策略
HTTP缓存头（Cache-Control）控制缓存行为

6.2.2 Vue Keep-Alive组件

<template> <keep-alive :max="10"> <!-- 最多缓存10个组件实例 --> <component :is="currentComponent"></component> </keep-alive> </template>

Vue的keep-alive内部实现就使用了LRU缓存策略，当超过最大缓存数量时，自动销毁最久未使用的组件实例。

【每日算法】LeetCode 146. LRU 缓存机制