LRU 缓存算法一、什么是 LRULRULeast Recently Used最近最少使用是一种常见的缓存淘汰策略。核心思想当缓存空间满了优先淘汰最久没有被访问过的数据因为我们认为最近被访问过的数据未来更有可能再次被访问。举个生活化的例子你桌面上只能放 3 本书第 4 本要放上来时就把最久没翻过的那本收回书架。二、为什么要用「哈希表 双向链表」实现 LRU 需要同时满足两个操作都要高效O(1)快速查找给定 key能立刻定位到对应的缓存项。快速更新顺序访问某个 key 后要把它移到最近使用的位置容量满时要能快速删除最久未使用的项。数据结构查找插入/删除维护顺序数组O(n)O(n)麻烦哈希表O(1)O(1)不支持双向链表O(n)O(1)天然支持哈希表 双向链表O(1)O(1)O(1)所以经典做法是哈希表unordered_map存key - 链表节点迭代器用于 O(1) 查找。双向链表list按使用时间排序表头是最近使用表尾是最久未使用。三、完整实现代码classLRUCache{private:unordered_mapint,listpairint,int::iterator__hash;// key - 链表节点listpairint,int__list;// 双向链表存 {key, value}int__capacity;// 缓存容量public:LRUCache(intcapacity){__capacitycapacity;}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()-secondvalue;}}};四、核心操作逐行解读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()-secondvalue;}}