网站做gzip压缩,seo技术培训唐山,益阳做网站,免费软件下载存在哪些风险目录 1.什么是LRU Cache#xff1f;2.LRU Cache实现 1.什么是LRU Cache#xff1f;
LRU是Least Recently Used的缩写#xff0c;意思是最近最少使用#xff0c;它是一种Cache替换算法。什么是 Cache#xff1f; 狭义的Cache指的是位于CPU和主存间的快速RAM 通常它不像系统… 目录 1.什么是LRU Cache2.LRU Cache实现 1.什么是LRU Cache
LRU是Least Recently Used的缩写意思是最近最少使用它是一种Cache替换算法。什么是 Cache 狭义的Cache指的是位于CPU和主存间的快速RAM 通常它不像系统主存那样使用DRAM技术而使用昂贵但较快速的SRAM技术 广义上的Cache指的是位于速度相差较大的两种硬件之间 用于协调两者数据传输速度差异的结构除了CPU与主存之间有Cache 内存与硬盘之间也有Cache乃至在硬盘与网络之间也有某种意义上的Cache ── 称为Internet临时文件夹或网络内容缓存等 Cache的容量有限因此当Cache的容量用完后而又有新的内容需要添加进来时 就需要挑选并舍弃原有的部分内容从而腾出空间来放新内容LRU Cache的替换原则就是将最近最少使用的内容替换掉 其实LRU译成最久未使用会更形象因为该算法每次替换掉的就是一段时间内最久没有使用过的内容 2.LRU Cache实现 实现LRU Cache的方法和思路很多但是要保持高效实现O(1)的Put和Get那么使用双向链表和哈希表的搭配是最高效和经典的 双向链表是因为双向链表可以实现任意位置O(1)的插入和删除哈希表是因为哈希表的增删查改也是O(1) 关键找到key就要找到key对应存储数据在list中的位置
class LRUCache
{
public:LRUCache(int capacity): _capacity(capacity){}int Get(int key){auto ret _hashMap.find(key);if (ret ! _hashMap.end()){LtIter it ret-second;// 更新key对应值的位置splice转移结点_LRUList.splice(_LRUList.begin(), _LRUList, it);return it-second;}else{return -1;}}void Put(int key, int value){auto ret _hashMap.find(key);if (ret _hashMap.end()) // 1.新增{if (_hashMap.size() _capacity){// 若满则先删除LRU的数据pairint, int back _LRUList.back();_hashMap.erase(back.first);_LRUList.pop_back();}_LRUList.push_front({ key, value });_hashMap[key] _LRUList.begin();}else // 2.更新{LtIter it ret-second;it-second value; // 更新// 更新key对应值的位置splice转移结点_LRUList.splice(_LRUList.begin(), _LRUList, it);}}
private:typedef listpairint, int::iterator LtIter;// hash做到查找更新是O(1)value值存的是list的iteratorunordered_mapint, LtIter _hashMap;// LRU假设尾部数据就是最近最少用listpairint, int _LRUList;size_t _capacity;
};
