LRU缓存机制

题目链接

LRU，即Least-Recently-Used。是一种高速缓存替换策略，是一种缓存机制。主要是利用局部性原理。

(资料图片)

局部性原理分两种，空间局部性和时间局部性。

在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次应用。

在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

显然，LRU是利用到了时间局部性。

在CSAPP的P434组相联高速缓存中不命中时的行替换出现。

最近最少使用（LRU）策略会替换最后一次访问时间最久远的那一行。

实现 LRUCache 类：

LRUCache(int capacity)以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key)如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value)如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

来源：力扣（LeetCode）

这是一道很优秀的设计问题，而不是关于某个问题的算法。

题目要求你利用相关的知识，设计一个能够简单实现LRU 缓存机制的类。

根据刚刚所说的CSAPP中的背景知识，可以知道要设计出的类：

那现在留下的问题就是，如何做到逐出。

首先可以想到，利用队列的先进先出原则。

那么如何逐出？拿出怎么做到？这里就遇到了难以删除的问题。

所以，下面介绍双向链表的解法。

双向链表可以利用指向关系做到删除，将节点剔除于链表外。

然而我们在剔除后，对于访问的节点来说，还需要再加到头部节点。而对于没有访问的节点，我们需要真正删除它。

所以代码中有两个delete函数，来避免内存泄漏。

class LRUCache {private:    struct DoubleLinkNode {        int key;        int value;        DoubleLinkNode* prev;        DoubleLinkNode* next;        DoubleLinkNode(): key(0), value(0), prev(nullptr), next(nullptr) {}        DoubleLinkNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}    };    map cache;    DoubleLinkNode* head;    DoubleLinkNode* tail;    int capacity;    int size;    void addNodeHead(DoubleLinkNode* node)//双向链表头插法    {        node->next = head->next;        node->prev = head;        head->next->prev = node;        head->next = node;    }    void deleteNode(DoubleLinkNode* node)//剔除尾节点    {        node->next->prev = node->prev;        node->prev->next = node->next;    }    void moveNodeHead(DoubleLinkNode* node)    {        deleteNode(node);        addNodeHead(node);    }    DoubleLinkNode* deleteTail()//删除尾节点    {        DoubleLinkNode* temp = tail->prev;        deleteNode(temp);        return temp;    }public:    LRUCache(int capacity)     {        this->capacity = capacity;        size = 0;        head = new DoubleLinkNode();        tail = new DoubleLinkNode();        head->next = tail;        tail->prev = head;    }        int get(int key)     {        if (cache.count(key))        {            moveNodeHead(cache[key]);            return cache[key]->value;        }else        {            return -1;        }    }        void put(int key, int value)     {        if (cache.count(key))        {            cache[key]->value = value;            moveNodeHead(cache[key]);        }else        {            DoubleLinkNode* node = new DoubleLinkNode(key, value);            addNodeHead(node);            cache[key] = node;            size += 1;                        if (size > capacity)            {                DoubleLinkNode* temp = deleteTail();                cache.erase(temp->key);                delete temp;//避免内存泄漏                size -= 1;            }        }    }};/** * 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); */

标签：