跳转至

LRU

Least Recently Used (LRU) cache 是一个经典的数据结构。它基于时间局部性(最近访问的数据,在之后应该还会访问)的想法,在Cache满的时候总是淘汰最久没有被访问的数据。

他的编程实践也是简单的。通常只需要一个 哈希表 + 链表。哈希表保存 数据和数据对应的链表位置,链表则 暗示了数据的上次访问时间——每次读写数据都把数据移动到链表头,满了则删除链表尾对应的数据。

#include <iostream>
#include <unordered_map>

using namespace std;

// 定义模板的双向链表节点
template<typename K, typename V>
struct Node {
    K key;
    V value;
    Node* prev;
    Node* next;
    Node(K k, V v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

template<typename K, typename V>
class LRUCache {
    int capacity;
    Node<K, V>* head, *tail;
    unordered_map<K, Node<K, V>*> cache;

    void addNode(Node<K, V>* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void removeNode(Node<K, V>* node) {
        Node<K, V>* prev = node->prev;
        Node<K, V>* next = node->next;
        prev->next = next;
        next->prev = prev;
    }

    void moveToHead(Node<K, V>* node) {
        removeNode(node);
        addNode(node);
    }

    Node<K, V>* popTail() {
        Node<K, V>* res = tail->prev;
        removeNode(res);
        return res;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node<K, V>(K(), V());
        tail = new Node<K, V>(K(), V());
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache() {
        Node<K, V>* current = head;
        while (current != nullptr) {
            Node<K, V>* next = current->next;
            delete current;
            current = next;
        }
    }

    V get(K key) {
        if (cache.find(key) == cache.end()) return V(); // 返回默认构造的值
        Node<K, V>* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(K key, V value) {
        if (cache.find(key) != cache.end()) {
            Node<K, V>* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            Node<K, V>* newNode = new Node<K, V>(key, value);
            if (cache.size() == capacity) {
                Node<K, V>* tail = popTail();
                cache.erase(tail->key);
                delete tail;
            }
            addNode(newNode);
            cache[key] = newNode;
        }
    }
};

int main() {
    LRUCache<int, string> cache(2);
    cache.put(1, "one");
    cache.put(2, "two");
    cout << cache.get(1) << endl; // 输出 "one"
    cache.put(3, "three"); // 移除键2
    cout << cache.get(2) << endl; // 输出空字符串,因为键2已被移除
    cache.put(4, "four"); // 移除键1
    cout << cache.get(1) << endl; // 输出空字符串,因为键1已被移除
    cout << cache.get(3) << endl; // 输出 "three"
    cout << cache.get(4) << endl; // 输出 "four"
    return 0;
}