题目链接：LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
这道题的要求是设计并实现LRU缓存的数据结构，要求支持get和set操作。
- get(key)：返回key对应的值，如果不存在，返回-1。
- set(key, value)：根据key设置value或者插入（如果key不存在）。当缓存到达容量的时候，在插入前删除最远使用的值。
LRU是Least Recently Used的缩写，即最少使用页面置换算法，是为虚拟页式存储管理服务的。
关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式—— 在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。
然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。因而，采取尽量好的算法以减少读取外存的次数，也是相当有意义的事情。
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是LRU算法的全部内容。
举个LRU例子：
- 假设序列为：4、3、4、2、3、1、4、2，物理块有3个 则
- 首轮 4调入内存 4
- 次轮 3调入内存 3 4
- 之后 4调入内存 4 3
- 之后 2调入内存 2 4 3
- 之后 3调入内存 3 2 4
- 之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
- 之后 4调入内存 4 1 3（原理同上）
- 最后 2调入内存 2 4 1
————以上出自百度百科
接下来考虑如何实现LRU缓存的数据结构。首先，需要根据key找到对应的value，这理所应当采用Hash表实现；其次，需要对key按照先后使用的顺序排序，又要满足频繁的插入和删除操作，可以考虑采用双向链表（可以注意到，只在头部插入，只在尾部删除）。所以，采用Hash表加双向链表实现LRU缓存的数据结构。
至于具体实现：
- get的时候，根据key在Hash表中查找，如果没找到，返回-1；如果找到，将其移到链表头部，并更新Hash中key对应的值，最后返回key对应的value值。
- set的时候，同样根据key在Hash表中查找，如果找到，将其移到链表头部，并更新对应value的值；如果没找到，这需要判断缓存是否满了（如果满了，则需要在Hash中删除最后节点对应的key，同时删除最后节点），然后在头部插入新节点(key,value)。最后，都需要更新Hash中key对应的值。
时间复杂度：O(1)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class LRUCache
{
typedef list<pair<int, int>> lii;
typedef unordered_map<int, lii::iterator> mip;
lii cache; // 缓存容器
mip hash; // 缓存哈希
int capacity; // 缓存容量
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key)
{
auto it = hash.find(key); // 在Hash中查找
if(it == hash.end()) // 如果没找到，返回-1
return -1;
putFirst(it -> second); // 把key对应节点放到链表头部
hash[key] = cache.begin(); // 更新Hash中key对应的值
return it -> second -> second;
}
void set(int key, int value)
{
auto it = hash.find(key); // 在Hash中查找
if(it != hash.end()) // 如果找到
{
putFirst(it -> second); // 把key对应节点放到链表头部
cache.begin() -> second = value; // 更新对应value的值
}
else // 如果没找到
{
if(cache.size() == capacity) // 如果缓存已满
{
hash.erase(cache.back().first); // 在Hash中删除最后节点对应的key
cache.pop_back(); // 删除最后节点
}
cache.push_front({key, value}); // 在头部插入新节点(key,value)
}
hash[key] = cache.begin(); // 更新Hash中key对应的值
}
private:
// 把it指向的节点放到链表头部
void putFirst(lii::iterator it)
{
auto c = *it; // 记录当前节点
cache.erase(it); // 删除当前节点
cache.push_front(c); // 将已记录的节点插到头部
}
};