leetcode146. LRU 缓存

题目链接
请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

LRU是什么？

最近最少使用算法（LRU）是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。具体解释见百度百科
该算法的思路是，发生缺页中断时，选择未使用时间最长的页面置换出去。
利用 LRU 算法对例子进行页面置换的结果如图所示。当进程第一次对页面 2 进行访问时，由于页面 7 是最近最久未被访问的，故将它置换出去。之后对页面0进行了访问，导致页面1比页面0成为了最久未使用的页。所以之后当进程第一次对页面 3进行访问时，第 1 页成为最近最久未使用的页，将它换出。

LRU实现

在实现上，LRU通常使用一个哈希表和一个双向链表来实现。哈希表存储键和链表节点的指针，而双向链表则按照数据被访问的顺序来组织数据。当缓存满了之后，链表尾部的节点（即最近最少使用的节点）会被移除，以腾出空间给新加入的数据。

1.定义结构体

首先，定义了一个名为Dlinkednode的结构体，它代表双向链表中的一个节点。每个节点包含以下成员：

int key//键值。
int value//与键值关联的数据。
Dlinkednode* pre//指向前一个节点的指针。
Dlinkednode* nex//指向后一个节点的指针。
构造函数：Dlinkednode()是默认构造函数，初始化所有成员为默认值。
Dlinkednode(int _key, int _value)是带参数的构造函数，用于创建具有特定键值和数据的节点。

2.定义LRU缓存类

接下来，定义了一个名为LRUCache的类，它用于实现LRU缓存机制。类中包含以下成员：

Dlinkednode* head//指向双向链表头部的指针。
Dlinkednode* tail//指向双向链表尾部的指针。
unordered_map<int, Dlinkednode*> cache//哈希表，用于存储键值和对应节点的指针。
int size//当前缓存中元素的数量。
int capacity//缓存的最大容量。
LRUCache(int _capacity)是类的构造函数，它初始化缓存的最大容量，
并创建一个空的双向链表，链表的头尾节点不存储实际数据，仅用于维护链表结构。
int get(int key)//获取键值对应的数据。如果键值不存在，则返回-1。
//如果键值存在，则将其对应的节点移动到链表头部（最近使用），并返回节点的数据。
void put(int _key, int _value)//添加或更新键值对。如果键值不存在，则创建新节点并添加到链表头部。
//如果键值已存在，则更新其数据并移动节点到链表头部。
//如果添加新节点后缓存超出容量，则移除链表尾部的节点（最少使用），并从哈希表中删除对应的键值。
void movetohead(Dlinkednode* node)//将节点移动到链表头部，表示该节点最近被使用。
void removenode(Dlinkednode* node)//从链表中移除指定节点。
void addtohead(Dlinkednode* node)//将节点添加到链表头部。
Dlinkednode* removetail()//移除并返回链表尾部的节点，表示该节点是最少使用的。

3.函数具体实现

get函数首先检查哈希表中是否存在键值，如果不存在，则返回-1。如果存在，则获取对应的节点指针，并调用movetohead函数将其移动到链表头部，最后返回节点的值。

put函数首先检查哈希表中是否存在键值。如果不存在，创建新节点并将其添加到链表头部，然后更新哈希表。如果键值已存在，则更新节点的值并移动到链表头部。如果缓存已满，则调用removetail函数移除最少使用的节点，并更新哈希表。

movetohead、removenode、addtohead和removetail函数是辅助函数，用于维护双向链表的结构，确保节点可以正确地添加到头部或从尾部移除。

具体代码如下：

// 定义双向链表节点结构体
struct Dlinkednode {
    int key;           // 节点的键值
    int value;         // 节点的值
    Dlinkednode* pre;  // 指向前一个节点的指针
    Dlinkednode* nex;  // 指向后一个节点的指针

    // 构造函数，初始化节点的所有成员
    Dlinkednode() : key(0), value(0), pre(NULL), nex(NULL) {}
    Dlinkednode(int _key, int _value) : key(_key), value(_value), pre(NULL), nex(NULL) {}
};

// 定义LRU缓存类
class LRUCache {
private:
    Dlinkednode* head;  // 双向链表的头部节点，不存储实际数据
    Dlinkednode* tail;  // 双向链表的尾部节点，不存储实际数据
    unordered_map<int, Dlinkednode*> cache;  // 哈希表，存储键和节点指针的映射
    int size;  // 当前缓存中的元素数量
    int capacity;  // 缓存的最大容量

public:
    // 构造函数，初始化缓存的最大容量和双向链表的头尾节点
    LRUCache(int _capacity) : capacity(_capacity), size(0) {
        head = new Dlinkednode();
        tail = new Dlinkednode();
        head->nex = tail;  // 头部节点的下一个指向尾部节点
        tail->pre = head;  // 尾部节点的上一个指向头部节点
    }
    
    // 获取缓存中键值对应的数据
    int get(int key) {
        if (cache.count(key) == 0) {
            return -1;  // 如果键值不在缓存中，返回-1
        }
        Dlinkednode* node = cache[key];  // 获取节点指针
        movetohead(node);  // 将节点移动到链表头部，表示最近使用
        return node->value;  // 返回节点的值
    }
    
    // 添加或更新缓存中的键值对
    void put(int _key, int _value) {
        if (cache.count(_key) == 0) {
            Dlinkednode* node = new Dlinkednode(_key, _value);  // 创建新节点
            cache[_key] = node;  // 更新哈希表
            addtohead(node);  // 将新节点添加到链表头部
            ++size;  // 缓存大小加1
            if (size > capacity) {
                Dlinkednode* removed = removetail();  // 移除链表尾部节点
                cache.erase(removed->key);  // 从哈希表中删除键值
                delete removed;  // 删除节点
                --size;  // 缓存大小减1
            }
        } else {
            Dlinkednode* node = cache[_key];  // 获取已存在的节点指针
            node->value = _value;  // 更新节点的值
            movetohead(node);  // 将节点移动到链表头部
        }
    }
    
    // 将节点移动到链表头部
    void movetohead(Dlinkednode* node) {
        removenode(node);  // 从当前位置移除节点
        addtohead(node);  // 将节点添加到链表头部
    }
    
    // 从链表中移除指定节点
    void removenode(Dlinkednode* node) {
        node->pre->nex = node->nex;  // 前一个节点的下一个指向当前节点的下一个
        node->nex->pre = node->pre;  // 后一个节点的上一个指向当前节点的上一个
    }
    
    // 将节点添加到链表头部
    void addtohead(Dlinkednode* node) {
        node->nex = head->nex;  // 新节点的下一个指向头节点的下一个
        node->pre = head;  // 新节点的上一个指向头节点
        head->nex->pre = node;  // 头节点的下一个的上一个指向新节点
        head->nex = node;  // 头节点的下一个指向新节点
    }
    
    // 移除并返回链表尾部的节点
    Dlinkednode* removetail() {
        Dlinkednode* node = tail->pre;  // 获取尾部节点的前一个节点
        removenode(node);  // 从链表中移除该节点
        return node;  // 返回被移除的节点
    }
};

/**
 * 下面是LRUCache类的使用示例：
 * 创建一个容量为capacity的LRUCache对象
 * LRUCache* obj = new LRUCache(capacity);
 * 通过get(key)获取键为key的数据，如果不存在则返回-1
 * int param_1 = obj->get(key);
 * 通过put(key, value)添加或更新键为key的数据，值为value
 * obj->put(key, value);
 */