什么是LRU Cache
LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法
什么是Cache
狭义的Cache指的是位于CPU和主存间的快速RAM, 通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术,广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构.除了CPU与主存之间有Cache, 内存与硬盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等
Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容.LRU Cache 的替换原则就是将最近最少使用的内容替换掉
其实,LRU译成最久未使用会更形象, 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容
LRU Cache的实现
实现LRU Cache的方法和思路很多,但是要保持高效实现O(1)的put和get,那么使用双向链表和哈希表的搭配是最高效和经典的
使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除,使用哈希表是因为哈希表的增删查改也是O(1)
LRU缓存OJ：
结构设计分析
实现结构1:
private:
unordered_map<int,int>_hashMap; //hash能做到查找get更新是O(1)
list<pair<int,int>>_LRUList;//假设尾部数据就是最近少用的,最近使用的放在头部
size_t_capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
此时:
intget(intkey) {}
voidput(intkey, intvalue) {}
get: 直接查map,时间复杂度是O(1)
put: 如果是新增元素就是O(1),直接插入, 但是如果是修改更新: 就是O(N), 因为要在map查找完成后,在_LRUList中找到该元素key所在位置 ,只能遍历查找,时间复杂度是O(N) ,然后把该元素key放在头部O(1)
破局点:找到key之后,就要找到key对应存储的数据在链表中的位置
所以: hashMap中可以存list的迭代器！ 我们实现过list,所以知道list的迭代器本质是节点的指针
typedeflist<pair<int,int>>::iteratorLtIter;
private:
unordered_map<int,LtIter>_hashMap; //key:值 Value:list的迭代器,即key对应在list的位置
list<pair<int,int>>_LRUList;
size_t_capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
这个结构,相当于真正的数据在list里面！在map中查找key,就可以直接在链表中找到这个节点, 然后把这个节点转移到链表头部
list的splice函数介绍:
splice函数用于两个list容器之间的拼接(数据转移),其有三种拼接方式：
- 将整个容器拼接到另一个容器的指定迭代器位置.
- 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置.
- 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置.
#include <iostream>
#include <list>
usingnamespacestd;
intmain()
{
list<int>lt1(4, 2);
list<int>lt2(4, 6);
lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
for (autoe : lt1)
{
cout<<e<<" ";
}
cout<<endl; //6 6 6 6 2 2 2 2
list<int>lt3(4, 2);
list<int>lt4(4, 6);
lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
for (autoe : lt3)
{
cout<<e<<" ";
}
cout<<endl; //6 2 2 2 2
list<int>lt5(4, 2);
list<int>lt6(4, 6);
lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
for (autoe : lt5)
{
cout<<e<<" ";
}
cout<<endl; //6 6 6 6 2 2 2 2
return0;
}
注意： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了.（实际上就是将链表当中的指定结点拼接到了另一个容器当中）
当然也可以把节点转移到自己身上
例如:
#include<list>
intmain()
{
list<int>lt{ 1,2,3,4,5 };
lt.splice(lt.begin(), lt, --lt.end());//把尾部的数据放到头部
for (autoe : lt)
{
cout<<e<<" "; // 5 1 2 3 4
}
return0;
}
我们待会要用这个函数来把节点转移到链表的头部!
get函数的实现:
1)在map中查找key是否存在 .如果不存在,返回-1
2)如果存在,把该key放到list的头部 -> 转移节点 ,然后返回key对应的值
元素存在list里面, _hashMap中的键:key 值:list的迭代器(LtIter),
如果key对应的值存在,则取出迭代器, 这里就可以看出hashmap的value存的是list的iterator的好处：找到key 也就找到key存的值在list中的iterator,也就直接删除,再进行头插,实现O(1)的数据挪动
intget(intkey)
{
//_hashMap中的key:key value：list的迭代器(LtIter)
autoret=_hashMap.find(key);//先查找是否在哈希表中
if(ret!=_hashMap.end())
{
//更新当前元素到链表头部
LtIterit=ret->second;//该元素在list中的位置
_LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部,相当于头插,但是这这里不用更新迭代器,因为迭代器里面存的还是这个节点的指针
//it:是链表的迭代器,调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*
//pair<int,int> 我们要的是第二个成员的值
//本来应该是it->->second 但是省略了一个箭头
returnit->second;//返回key对应的value
}
else //该元素不存在
{
return-1;
}
}
put函数的实现:
1)在map中查找key是否存在 .如果不存在,那就要新增
- 1.判断是否满了,如果满了,需要先删除list中尾部的数据. 然后在哈希表中也要删除该元素
2.然后把该该 {key-value}头插到链表中 , 在哈希表中新增键值对{key-该位置在链表的迭代器}
注意点:判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)
2)如果已经存在了,那就修改数据, 然后把该key放到list的头部
voidput(intkey, intvalue)
{
autoret=_hashMap.find(key);
//新增
if(ret==_hashMap.end())
{
//判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)
//if(_capacity == _LRUList.size()) 不建议
if(_capacity==_hashMap.size()) //容量满了
{
pair<int,int>back=_LRUList.back();//取出链表尾部的数据
//在哈希表中删除该数据 + 在链表弹出该元素
_hashMap.erase(back.first);//back.first是key
_LRUList.pop_back();
}
//头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}
_LRUList.push_front(make_pair(key,value));
_hashMap[key] =_LRUList.begin();
}
else
{
//修改节点的值 + 当前数据放到链表头部
LtIterit=ret->second;//it是list的迭代器
it->second=value;//更新节点的值
_LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部
}
}
整体代码:
classLRUCache {
public:
typedeflist<pair<int,int>>::iteratorLtIter; //list的迭代器重命名为LtIter
LRUCache(intcapacity) {
_capacity=capacity;
}
intget(intkey) {
//_hashMap中的key:key value：list的迭代器(LtIter)
autoret=_hashMap.find(key);//先查找是否在哈希表中
if(ret!=_hashMap.end())
{
//更新当前元素到链表头部
LtIterit=ret->second;//该元素在list中的位置
_LRUList.splice(_LRUList.begin(),_LRUList,it);//把元素转移到链表头部
//it:是链表的迭代器,it-> 调用operator->,返回数据的地址,list中的数据是pair,所以返回的是pair*
//pair<int,int> 我们要的是第二个成员的值
//本来应该是it->->second 但是省略了一个箭头
returnit->second;//返回key对应的value
}
else //该元素不存在
{
return-1;
}
}
voidput(intkey, intvalue)
{
autoret=_hashMap.find(key);
//新增
if(ret==_hashMap.end())
{
//判断容量的时候,最好不要使用求list的大小来判断, 因为C++中,这个方法可能不是O(1)
//if(_capacity == _LRUList.size()) 不建议
if(_capacity==_hashMap.size()) //容量满了
{
pair<int,int>back=_LRUList.back();//取出链表尾部的数据
//在哈希表中删除该数据 + 在链表弹出该元素
_hashMap.erase(back.first);//back.first是key
_LRUList.pop_back();
}
//头插入当前元素 + 哈希表新增键值对{key-该元素在list的位置(链表头部)}
_LRUList.push_front(make_pair(key,value));
_hashMap[key] =_LRUList.begin();
}
else
{
//修改节点的值 + 当前数据放到链表头部
LtIterit=ret->second;//it是list的迭代器
it->second=value;//更新节点的值
_LRUList.splice(_LRUList.begin(),_LRUList,it);//把当前节点转移到头部
}
}
private:
unordered_map<int,LtIter>_hashMap; //key:值 Value:list的迭代器,即key对应在list的位置
list<pair<int,int>>_LRUList;
size_t_capacity;//标记容量,满了就弹出链表尾的元素+在哈希表删除该元素的键值对
};
/**
* 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);
*/
其实这里有两种更新常用元素的方式:
1.用内置的splice函数转移节点
2.先保存节点信息,然后erase节点,然后push_front. 然后更新key对应的迭代器, 因为原迭代器指向我们删除的数据,迭代器失效了!!
使用unordered_map,让搜索效率达到O(1) 需要注意：这里最巧的设计就是将unordered_map的value type放成list<pair<int,int>>::iterator,因为这样,当get一个已有的值以后,就可以直接找到key在list中对应的iterator,然后将这个值移动到链表的头部保持LRU
int get(int key)
{
// 如果key对应的值存在,就可以取出元素位置迭代器,这里就可以看出hashmap的value存的是list的 terator的好处：找到key
// 也就找到key存的值在list中的iterator,也就直接删除,再进行头插,实现O(1)的数据挪动
auto hashit = _hashmap.find(key);
if(hashit != _hashmap.end())
{
auto listit = hashit->second;//list的迭代器
pair<int, int> kv = *listit; //调用operator* 返回节点数据的内容,list的数据是pair
_list.erase(listit);//通过迭代器删除该节点
_list.push_front(kv);//然后头插
_hashmap[key] = _list.begin();//更新迭代器的位置
return kv.second;//返回key对应的value
}
else
{
return -1;
}
}
void put(int key, int value)
{
// 1.如果没有数据则进行插入数据
// 2.如果有数据则进行数据更新
auto hashit = _hashmap.find(key);
if(hashit == _hashmap.end())
{
// 插入数据时,如果数据已经达到上限,则删除链表头的数据和hashmap中的数据,两个删除操作都是O(1)
if(_list.size() >= _capacity)
{
_hashmap.erase(_list.back().first); //在哈希表中删除最后一个节点的信息,通过key删除. _list.back().first:最后一个节点的第一个成员就是key
_list.pop_back();//尾删最后一个节点
}
_list.push_front(make_pair(key,value));//头插
_hashmap[key] = _list.begin();//新建键值对
}
else
{
// 更新数据 将数据挪动list前面
auto listit = hashit->second;//list的迭代器
pair<int, int> kv = *listit;//调用operator* 返回节点数据的内容,list的数据是pair,先保留数据
kv.second = value;//更新值
_list.erase(listit);//通过迭代器删除该节点
_list.push_front(kv);//头插
_hashmap[key] = _list.begin();//更新迭代器的位置
}
}
