146. LRU缓存机制

题目来源：https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1)时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得关键字 2 作废

cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 该操作会使得关键字 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

解法

题目要求 O(1) 时间复杂度内完成操作，最先应该想到的是哈希表，则通过牺牲空间复杂度来降低时间复杂度。那哈希表存放的是什么内容呢？哈希表应该存放的是每个缓存的键值以方便对所以缓存的管理。

那下面就有一个很重要的问题了，就是应该用什么结构体去存储这些缓存？是线性表？链表？堆栈？还是队列？要明确这一问题，就要从LRU算法本身入手。

LRU算法是操作系统中页面置换算法之一，即最近最久未使用的算法。如字面意思，每次缓存淘汰的都是最近最久未使用的缓存，这就使得缓存区的缓存始终保持一定的新鲜度。

以操作系统中的页面置换为例，假设要访问的页号是：7，0，1，2，0，3，0，4，内存块大小为3.

初始化	7替换为2	命中	1替换为3	命中	4替换2
7	0	1	2	2	3
0	1	2	0	3	0
1	2	0	3	0	4

（注：第三行始终为最近常使用的缓存块，第一行始终为最近最久未使用的缓存块）

由上图我们可以得到：

1.每次命中的数据块应放置在最近常用的缓存块；

2.每次替换的数据块为最近最久未使用的缓存块，并且将替换的缓存块放入最近常用的缓存块中；

根据以上的特点，这需要更改某些块的位置，显然用双向链表结构体比较合适。

算法大致过程如下：（假设缓存块大小为2）

Head端保持的是最近最常用的缓存块，而Tail端保持的是最近最久未使用的缓存块，如果缓存块已使用的数量达到阈值，那么需要进行替换，删除的是Tail端的缓存块，同时将待替换的缓存块放入Head端。如上图5，由于缓存块已满，所以需要将Tail端的B删除，同时需要将待替换的C插入到Head端之后。

以上算法流程算是清晰了，但是还有一个问题需要解决，那就是在 O(1)时间复杂度内完成上述操作。

现在存在的问题是get如果通过遍历整个链表的方式去获取键值，那么需要消耗O(n)的时间复杂度，这与题目相背。为了解决这一问题，我们需要将键与缓存块的地址相映射，以方便我们更快的找到对应的缓存块并取出值。同时，为了满足 O(1)时间复杂度，需要使用哈希表来存储键与缓存块的映射矩阵。

C++代码：

class Node {
public:
    int key;
    int value;
    Node *pre;
    Node *next;
    Node():key(0),value(0),pre(nullptr),next(nullptr){}
    Node(int key,int value):pre(nullptr),next(nullptr){
        this->key = key;
        this->value = value;
    }
};
class LRUCache {
private:
    Node *head,*tail;
    unordered_map<int, Node*> cache;
    int capacity,size;
public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(!cache.count(key)){
            return -1;
        }
        move_to_Head(cache[key]);
        return cache[key]->value;
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            cache[key]->value = value;
            move_to_Head(cache[key]);
            return;
        }else{
            Node *p = new Node(key,value);
            cache[key] = p;
            add_to_Head(p);
            size++;
            if(size>capacity){
                cache.erase(tail->pre->key);
                remove_Node(tail->pre);
                size--;
            }
        }
    }
    void remove_Node(Node *p)
    {
        p->pre->next = p->next;
        p->next->pre = p->pre;
    }
    void add_to_Head(Node *p)
    {
        p->next = head->next;
        head->next->pre = p;
        head->next = p;
        p->pre = head;
    }
    void move_to_Head(Node *p)
    {
        remove_Node(p);
        add_to_Head(p);
    }
};

/**
 * 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);
 */

复杂度分析：

时间复杂度：O(1)

空间复杂度：O(n)，哈希表。