建站模板工程造价,北京网站域名备案,深圳商城网站,聊天软件开发公司文章目录 一、定义二、LRU模拟实现二、代码实现 一、定义
LRU是Least Recently Used的缩写#xff0c;意思是最近最少使用#xff0c;它是一种Cache替换算法。 Cache的容量有限#xff0c;因此当Cache的容量用完后#xff0c;而又有新的内容需要添加进来时#xff0c; 就… 文章目录 一、定义二、LRU模拟实现二、代码实现 一、定义
LRU是Least Recently Used的缩写意思是最近最少使用它是一种Cache替换算法。 Cache的容量有限因此当Cache的容量用完后而又有新的内容需要添加进来时 就需要挑选并舍弃原有的部分内容从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。
二、LRU模拟实现
146.LRU缓存
下面我们就借力扣的这道题来简单实现一个
题目中要求我们以O1的时间复杂度来完成查找的话我们首先肯定会想到哈希表但又涉及一个问题我们查找完之后还需要更新一下刚刚查找数据的位置将这个数据置为是新的数据我们如何解决查找完改变数据的标识也做到O1呢 要保持高效实现O(1)的put和get那么使用双向链表和 哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除使用哈希表是因为哈希表的增删查改也是O(1)。 需要注意这里最巧的设计就是将unordered_map的value type放成listpairint, int::iterator因为这样当get一个已有的值以后就可以直接找到key在list中对应的iterator然后将这个值移动到链表的头部保持LRU。 二、代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includelist
#includeunordered_mapusing namespace std;class LRUCache {public:LRUCache(int capacity):_capacity(capacity){}int get(int key) {auto ret _hashMap.find(key);//在hash中找到了key存的地方if (ret ! _hashMap.end()) {LtIter it ret-second;//将it移动到_LRUList的头部_LRUList.splice(_LRUList.begin(), _LRUList, it);return it-second;}else {return -1;}}void put(int key, int value) {auto ret _hashMap.find(key);//原来没有key的数据则添加if (ret _hashMap.end()) {//LRU满了删除最近最少使用的就是链表尾部if (_capacity _hashMap.size()) {pairint, intback _LRUList.back();_hashMap.erase(back.first);//删哈希里面//链表里面k存的和哈希的是同一个key_LRUList.pop_back();//删链表尾部}//放入新的数据到链表头部_LRUList.push_front(make_pair(key, value));//哈希表中添加_hashMap[key] _LRUList.begin();}//原来有key的数据则更新else {LtIter it ret-second;it-second value;//将这个位置移到链表头部_LRUList.splice(_LRUList.begin(), _LRUList, it);}}private://链表存kv结构//k为key值v为我们要更新的数据typedef listpairint, int::iterator LtIter;//重命名链表迭代器int _capacity; // 容量大小超过容量则换出保持LRU//_LRUList假设链表头部为最近使用的尾部为最近最少使用listpairint, int _LRUList;//hash中存放的是key值与对应链表迭代器的的映射关系unordered_mapint, LtIter_hashMap;};
