企业官网建设流程全解析

LRU 缓存算法

一、什么是 LRU

LRU（Least Recently Used，最近最少使用）是一种常见的缓存淘汰策略。
核心思想：当缓存空间满了，优先淘汰"最久没有被访问过"的数据，因为我们认为"最近被访问过的数据，未来更有可能再次被访问"。

举个生活化的例子：你桌面上只能放 3 本书，第 4 本要放上来时，就把"最久没翻过"的那本收回书架。

二、为什么要用「哈希表 + 双向链表」

实现 LRU 需要同时满足两个操作都要高效（O(1)）：

1. 快速查找：给定 key，能立刻定位到对应的缓存项。
2. 快速更新顺序：访问某个 key 后，要把它移到"最近使用"的位置；容量满时，要能快速删除"最久未使用"的项。

所以经典做法是：

• 哈希表（unordered_map）：存key -> 链表节点迭代器，用于 O(1) 查找。
• 双向链表（list）：按"使用时间"排序，表头是最近使用，表尾是最久未使用。

三、完整实现代码

classLRUCache{private:unordered_map<int,list<pair<int,int>>::iterator>__hash;// key -> 链表节点list<pair<int,int>>__list;// 双向链表，存 {key, value}int__capacity;// 缓存容量public:LRUCache(intcapacity){__capacity=capacity;}intget(intkey){autoit=__hash.find(key);if(it==__hash.end())return-1;// 没找到__list.splice(__list.begin(),__list,it->second);// 把节点移到表头（最近使用）return__list.begin()->second;// 返回 value}voidput(intkey,intvalue){if(get(key)==-1){// key 不存在，插入新节点__list.insert(__list.begin(),{key,value});__hash[key]=__list.begin();if(__list.size()>__capacity){// 超出容量，淘汰表尾（最久未使用）intpop_key=__list.back().first;__list.pop_back();__hash.erase(pop_key);}}else{// key 已存在，更新 value（节点已在表头）__list.begin()->second=value;}}};

四、核心操作逐行解读

1.get(key)—— 查找并标记为最近使用

intget(intkey){autoit=__hash.find(key);if(it==__hash.end())return-1;__list.splice(__list.begin(),__list,it->second);return__list.begin()->second;}

• __hash.find(key)：O(1) 判断 key 是否存在，并拿到它在链表中的迭代器it->second。
• __list.splice(__list.begin(), __list, it->second)：这是整个实现的关键。
  splice会把it->second指向的节点从原位置摘下，接到表头，整个过程是 O(1)，不需要拷贝数据，也不破坏其他节点的链接。
  这样就把"刚访问过的数据"移动到了最近使用的位置。

2.put(key, value)—— 插入或更新

voidput(intkey,intvalue){if(get(key)==-1){// 不存在 → 新增__list.insert(__list.begin(),{key,value});__hash[key]=__list.begin();if(__list.size()>__capacity){// 超过容量 → 淘汰最久未使用的（表尾）intpop_key=__list.back().first;__list.pop_back();__hash.erase(pop_key);}}else{// 已存在 → 直接更新 value（此时节点已在表头）__list.begin()->second=value;}}