前端开发者需要了解的算法
LRU（Least Recently Used）算法
核心概念
LRU（最近最少使用） 是一种缓存淘汰策略，其核心思想是：当缓存空间不足时，优先淘汰最长时间未被使用的数据。它基于”局部性原理”（程序在一段时间内倾向于访问相同的数据集合）。
工作原理图解
graph LR
A[访问数据A] --> B[A移动到头部]
C[访问数据C] --> D[C移动到头部]
E[缓存满时添加新数据] --> F[淘汰尾部数据D]关键数据结构
双向链表
维护数据的访问顺序
头部：最近访问的数据
尾部：最久未访问的数据
节点结构：
class Node { constructor(key, value) { this.key = key; this.value = value; this.prev = null; this.next = null; } }
哈希表
- 实现O(1)时间复杂度的数据访问
- 键：数据标识
- 值：链表节点指针
算法实现（JavaScript）
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 缓存容量
this.map = new Map(); // 哈希表
this.head = new Node(0, 0); // 链表头哨兵
this.tail = new Node(0, 0); // 链表尾哨兵
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 添加节点到链表头部
_addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
// 移除节点
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移动节点到头部
_moveToHead(node) {
this._removeNode(node);
this._addToHead(node);
}
// 移除尾部节点
_popTail() {
const node = this.tail.prev;
this._removeNode(node);
return node;
}
// 获取数据
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._moveToHead(node); // 更新为最近访问
return node.value;
}
// 添加/更新数据
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.value = value;
this._moveToHead(node);
} else {
const newNode = new Node(key, value);
this.map.set(key, newNode);
this._addToHead(newNode);
// 超过容量时淘汰尾部数据
if (this.map.size > this.capacity) {
const tailNode = this._popTail();
this.map.delete(tailNode.key);
}
}
}
}操作步骤详解
- 数据访问（get）
- 在哈希表中查找键
- 找到则移动对应节点到链表头部
- 返回节点值
- 数据插入（put）
- 键存在：更新值并移动节点到头部
- 键不存在：
- 创建新节点
- 添加到链表头部
- 存入哈希表
- 如果超过容量：
- 移除链表尾部节点
- 从哈希表删除对应键
- 缓存淘汰
- 当缓存满时
- 移除链表尾部节点（最久未访问）
- 同步从哈希表中删除
时间复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问数据 | O(1) | 哈希表直接访问 |
| 插入数据 | O(1) | 链表头部插入 |
| 淘汰数据 | O(1) | 链表尾部移除 |
| 更新顺序 | O(1) | 链表节点移动 |
实际应用场景
- 数据库缓存：MySQL查询缓存
- 操作系统：内存页面置换
- Web服务器：Nginx反向代理缓存
- 前端框架：React Query缓存管理
- CDN服务：内容分发网络缓存
- 浏览器：HTTP缓存策略
LRU变种算法
- LRU-K
- 记录最近K次访问时间
- 解决”一次性扫描”问题
- 更精确识别冷热数据
- 2Q（Two Queues）
- 使用两个队列：
- FIFO队列：新进入的数据
- LRU队列：至少访问两次的数据
- 平衡新老数据比例
- 使用两个队列：
- ARC（Adaptive Replacement Cache）
- 结合LRU和LFU（最不经常使用）
- 动态调整缓存策略
- 适应多种访问模式
优缺点分析
优点：
- 实现相对简单
- 符合时间局部性原理
- O(1)时间复杂度操作
- 高效处理热点数据
缺点：
- 需要额外存储空间（哈希表+链表）
- 对”扫描式访问”不友好
- 可能淘汰即将访问的数据
- 链表操作需要同步维护
实际应用示例（浏览器缓存）
// 实现图片资源缓存
const imageCache = new LRUCache(20); // 缓存20张图片
async function loadImage(url) {
// 1. 尝试从缓存获取
if (imageCache.get(url)) {
return imageCache.get(url);
}
// 2. 网络请求加载图片
const response = await fetch(url);
const blob = await response.blob();
const image = URL.createObjectURL(blob);
// 3. 存入缓存
imageCache.put(url, image);
return image;
}
// 使用示例
document.querySelectorAll('img').forEach(img => {
loadImage(img.dataset.src).then(url => {
img.src = url;
});
});