LRU Cache

1.什么是LRU CacheLRU是least Recently Used的缩写意思是最近最少使用他是一种Cache替换算法。什么是Cache狭义的Cache指的是位于CPU和主存之间的快速RAM通常它不像系统主存那样使用DRAM技术而使用昂贵但较快速的SRAM技术。广义上的Cache指的是位于速度相差较大的两种硬件之间用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache内存与磁盘之间也有Cache乃至在硬盘与网络之间也有某种意义上的Cache——称为Internet临时文件夹或网络内容缓存等。Cache的容量有限因此当Cache的容量用完后而又有新的内容需要添加进来时就需要挑选并舍弃原有的部分内容从而腾出空间来放新内容。LRU Cache的替换原则就是将最近最少使用的内容替换掉。2. LRU Cache的实现实现LRU Cache的方法和思路很多但是要保持高效实现O(1)的put和get那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表也可以实现任意位置O(1)的插入和删除使用哈希表是因为哈希表的增删改查也是O(1)。3. LRU Cache的OJ题_LRUlist的作用 ——维护元素的使用顺序把最近使用的放头部最久未使用的放尾部方便 O (1) 时间删除尾部元素。但只有链表绝对无法满足题目要求的 O (1) 平均时间复杂度_hash的核心作用就是解决链表 查找慢 的致命缺陷。unordered_mapint, listpairint, int::iterator _hash的本质是用 key 作为哈希表的键值是该 key 在双向链表中对应的节点的迭代器这样就实现了O (1) 时间找到任意 key 对应的链表节点完美弥补了链表查找慢的缺点。class LRUCache { public: LRUCache(int capacity) :_capacity(capacity) {} int get(int key) { auto ret _hash.find(key); if(ret ! _hash.end())//在缓冲中,使用过了这个值将这个值提前 { listpairint, int::iterator it ret-second; _LRUlist.splice(_LRUlist.begin(), _LRUlist, it); return it-second; } else//不在缓冲中 { return -1; } } void put(int key, int value) { auto ret _hash.find(key); if(ret _hash.end())//如果没有找到 { if(_capacity _hash.size())//此时插入关键字数量超过capacity { pairint, int back _LRUlist.back();//记录最后一个元素 _hash.erase(back.first);//将最后一个元素对应hash表中的数据也删除 _LRUlist.pop_back(); } _LRUlist.push_front(make_pair(key, value));//头插 _hash[key] _LRUlist.begin(); } else//找到了 { //更新key对应值的位置 listpairint, int::iterator it ret-second; it-second value; //splice转移节点 _LRUlist.splice(_LRUlist.begin(), _LRUlist, it); } } private: size_t _capacity;//记录缓冲的最大容量 //unordered_map中存放listpairint, int::iterator迭代器就是为了更快的找到链表中的节点 unordered_mapint, listpairint, int::iterator _hash; //用来实现LRU将最近最少使用的放在链表最后 listpairint, int _LRUlist; }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj new LRUCache(capacity); * int param_1 obj-get(key); * obj-put(key,value); */