面试高频题——LRU

LRU的思路很简单，说白了就是用哈希表和双向链表来实现，当访问到存在于缓存中的节点时，将其置换到链表尾部即可，而当LRU缓存中保存的数据达到容量后，需要将链表头部的节点置换出缓存。

虽然总体的实现思路简单，但是相关的细节还是很多，从而很难做到在短时间内BUG FREE，从而错失了面试中完成本题的机会，所以需要提前准备，也就是先自己实现背板一下，以下是一个C++的实现。

```cpp
struct Node {
    int key;
    int val;
    Node* next;
    Node* prev;
    Node(): key(-1), val(-1), prev(nullptr), next(nullptr) {}
    Node(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
    unordered_map<int, Node*> map;
    Node* head;
    Node* tail;
    int cap;
    int len;
public:
    LRUCache(int capacity) {
        cap = capacity;
        len = 0;
        head = new Node();
        tail = new Node();
    }

int get(int key) {
        if (map.count(key)) {
            cout << "get " << key << ",swap to tail" << endl;
            Node* tmp = map[key];

// 已经在尾部，无需置换
            if (tmp->next == tail) return tmp->val;
            // 节点原位置前后节点替换
            tmp->prev->next = tmp->next;
            tmp->next->prev = tmp->prev;
            // 节点放入尾部
            tmp->next = tail;
            tmp->prev = tail->prev;
            // 尾部节点重新指向
            tail->prev->next = tmp;
            tail->prev = tmp;

return tmp->val;
        }
        return -1;
    }
  
    void put(int key, int value) {
        // 首个元素放入，特殊情况处理
        if (len == 0) {
            cout << "first insert " << key << endl;
            Node* tmp = new Node(key, value);
            // 插入节点指向
            tmp->prev = head;
            tmp->next = tail;
            // 头尾指向对应节点
            head->next = tmp;
            tail->prev = tmp;

map[key] = tmp;
            len++;
            return;
        }

// 访问到缓存内存有的数据，将其置换到链表最后，并重新赋值val
        if (map.count(key)) {
            cout << "set exist key " << key << ", swap to tail and replace value " << value << endl;
            Node* tmp = map[key];
            tmp->val = value;
            // 已经在尾部，无需置换
            if (tmp->next == tail) return;
            // 节点原位置前后节点替换
            tmp->prev->next = tmp->next;
            tmp->next->prev = tmp->prev;
            // 节点放入尾部
            tmp->next = tail;
            tmp->prev = tail->prev;
            // 尾部节点重新指向
            tail->prev->next = tmp;
            tail->prev = tmp;
            return;
        }

// 到达缓存容量，换出链表首位的数据
        if (len == cap) {
            Node* tmp = head->next;
            cout << "swap out " << tmp->key << endl;
            head->next = tmp->next;
            tmp->next->prev = head;
            // 删除哈希表记录
            map.erase(tmp->key);
            delete tmp;
            len--;
        }

// 新节点放入链表尾部
        Node* tmp = new Node(key, value);
        // 节点指向尾部
        tmp->next = tail;
        tmp->prev = tail->prev;
        // 节点前后更改指向
        tail->prev->next = tmp;
        tail->prev = tmp;
        // 放入哈希表记录
        map[key] = tmp;
        len++;
        cout << "insert " << key << endl;
    }
};

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

Last modification：August 29, 2023