146-LRU缓存

LeetCode 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
  The functions get and put must each run in $O(1)$ average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

method

首先有键值，肯定要哈希表，因为要随机访问节点，并且修改节点的位置，考虑双向链表

• 要通过哈希表找到节点，所以键是key，值是节点指针
• 也要通过节点找到键，然后删除节点的时候删除键值对，所以节点不仅要存储内容value，也要存储key

1、双向链表

next指针指向下一个节点，prev指针指向前一个节点，key和val存储键和值

新建虚拟头节点和尾节点，需要的操作

• 在头结点后面插入addToHead
• 删除节点removeNode
• 移动到头结点后面moveToHead，先断开前后连接，再添加到头结点后面
• 删除最后一个节点removeTail，断开最后一个节点的连接，将其指针返回，要通过它来删除哈希表里的键值对

2、缓存机制

• get(key)：没有返回-1，有就返回value，并且移动到头结点后面
• put(key, value)：没有就新建节点，插入到头结点后面，并添加到哈希表，如果超过最大容量，就把虚拟尾节点的前一个节点删掉，同时删掉哈希表里的键值对；有就修改值，然后提到头结点后面

struct DLinkedNode {
    int key, val;
    DLinkedNode *prev;
    DLinkedNode *next;
    DLinkedNode(): key(0), val(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int k, int v): key(k), val(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> hash;
    DLinkedNode *head;  // 虚拟头结点
    DLinkedNode *tail;  // 虚拟尾节点
    int capacity;       // 最大容量
    int size;           // 当前节点数
public:
    LRUCache(int capacity): capacity(capacity), size(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!hash.count(key)) {
            return -1;  // 没有直接返回-1
        }
        DLinkedNode *node = hash[key];  // 有就通过哈希表找到节点指针
        moveToHead(node);   // 提到最前面
        return node->val;
    }
    
    void put(int key, int value) {
        if (!hash.count(key)) { // 没有就新建节点
            DLinkedNode *node = new DLinkedNode(key, value);
            hash[key] = node;   // 添加到哈希表
            addToHead(node);    // 插入到最前面
            ++size;     // 当前节点数增加
            if (size > capacity) {  // 超过容量
                DLinkedNode *end = removeTail();    // 超出最后节点
                hash.erase(end->key);   // 删除键值对   
                delete end;
                --size;
            }
        }
        else {
            DLinkedNode *node = hash[key];  // 有就找到节点
            node->val = value;  // 更新值
            moveToHead(node);   // 提到最前面
        }
    }
    
    // 插入到最前面
    void addToHead(DLinkedNode *node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    // 删除节点，断开连接
    void removeNode(DLinkedNode *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    // 移动到最前面，先分离，在插入到最前面
    void moveToHead(DLinkedNode *node) {
        removeNode(node);
        addToHead(node);
    }
    // 断开最后一个节点的连接并将其返回
    DLinkedNode* removeTail() {
        DLinkedNode *node = tail->prev;
        removeNode(node);
        return node;
    }
    
};