LRU_Cache_1">一、LRU Cache概念

 LRU（Least Recently Used）最近最少使用，是一种cache替换算法。Cache的容量是优先的，当容量达到上限时，如果还有新的数据需要插入，此时我们通常将最近最少使用的数据丢弃，腾出空间存放新数据！

 狭义上的Cache是指CPU和主存直接快速RAM，他并不像系统主存哪些采用DRAM，而是使用造价更高、速度更快的SRAM。而广义上的Cache是指位于两种速度差距较大的硬件间，用于协调两者之间传输效率差异的结构。

LRU_Cache_6">二、LRU Cache的实现

 LRU Cache的实现方式有很多，但需要保证所有的操作（增删查改）的时间复杂度都为O(1)，最经典的方式就是用哈希表和双向链表实现。

1. 我们用哈希表保存数据，双向链表保存使用情况，最近一次使用的数据在链表开头，最久未使用的数据在链表尾部。
2. 对哈希表的增删查改时间复杂度为O(1)，满足要求。但我们在查改数据时，需要将该数据对应链表节点进行更新，首先查找到对应节点，然后移到开头。但显然在链表中查找数据采用线性遍历。时间复杂度为O(N)，不符合要求。
3. 所以我们对哈希表进行特殊处理，将数据保存到链表中，哈希表的value存储对应链表节点的迭代器。进行查改时，我们通过哈希表直接找到对应链表节点。
   

三、实现

146. LRU 缓存

class LRUCache {
public:LRUCache(int capacity) :_capacity(capacity){}int get(int key) {auto iter = _hash.find(key);if(iter == _hash.end()) return -1;else{// 更新使用节点在list中的位置_list.splice(_list.begin(), _list, iter->second);return iter->second->second;}}void put(int key, int value) {auto iter = _hash.find(key);if(iter != _hash.end()) //更新数据{_list.splice(_list.begin(), _list, iter->second);iter->second->second = value;}else{ // 插入数据// 这里计算数据的大小时，不要用list.size()。原有在于有的版本list中并不存在直接保存元素个数的成员size，//而是线性遍历看看存在多少数据。此时时间复杂度又回到O(N)if(_capacity == _hash.size()) // 达到容量上线，删除最久未使用数据{_hash.erase(_list.back().first);_list.pop_back();}_list.push_front({key, value});_hash.insert({key, _list.begin()});}}
private:unordered_map<int, list<pair<int, int>>::iterator> _hash;list<pair<int, int>> _list;int _capacity;
};