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),哈希表。