LRU算法

LRU全称Least Recently Used，即最近最久未使用算法，表示如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。时间复杂度$O(1)$，空间复杂度$O(1)$。

一、代码

#include <iostream>

using namespace std;

template<class K, class V, class H = hash<K>, int SIZE = 1024>
class LRUCache {
private:
    struct Node {
        K key;
        V value;
        Node *hash_prev;
        Node *hash_next;
        Node *list_prev;
        Node *list_next;

        Node() = default;
    };

public:
    LRUCache() : count(0), hash_map(), head(nullptr), tail(nullptr) {}

    ~LRUCache() {
        for (Node *p = head, *n = nullptr; p; n = p->list_next, delete (p), p = n);
    }

private:
    Node *find(const K &key) {
        size_t hash_key = hash(key) % SIZE;
        for (Node *p = hash_map[hash_key].hash_next; p; p = p->hash_next) {
            if (p->key == key) {
                return p;
            }
        }
        return nullptr;
    }

public:
    bool get(const K &key, V &value) {
        Node *target = find(key);
        if (target) {
            value = target->value;
            return true;
        }

        return false;
    }

    void put(const K &key, const V &value) {
        Node *target = find(key);

        if (target) {
            target->value = value;
            if (target->list_prev)target->list_prev->list_next = target->list_next;
            if (target->list_next)target->list_next->list_prev = target->list_prev;
            target->list_prev = nullptr;
            target->list_next = head;
            head->list_prev = target;
            head = target;
            return;
        }

        target = new Node();
        target->key = key;
        target->value = value;
        target->list_next = head;
        if (head)head->list_prev = target;
        head = target;
        if (tail == nullptr)tail = target;

        size_t hash_key = hash(key) % SIZE;
        if (hash_map[hash_key].hash_prev == nullptr) {
            hash_map[hash_key].hash_prev = target;
            hash_map[hash_key].hash_next = target;
        } else {
            target->hash_prev = hash_map[hash_key].hash_prev;
            hash_map[hash_key].hash_prev->hash_next = target;
            hash_map[hash_key].hash_prev = target;
        }

        if (count<SIZE) {
            count++;
            return;
        }

        Node *new_tail = tail;
        if (tail->hash_prev)tail->hash_prev->hash_next = tail->hash_next;
        if (tail->hash_next)tail->hash_next->hash_prev = tail->hash_prev;
        delete (tail);

        tail = new_tail;
        tail->list_next = nullptr;
    }

private:
    size_t count;
    Node hash_map[SIZE];
    Node *head;
    Node *tail;
    H hash;
};

二、测试代码

int main() {
    LRUCache<int, int> cache;
    cache.put(1, 1);
    cache.put(2, 2);
    cache.put(3, 3);

    int out;
    if (cache.get(3, out)) cout << out << endl;
    return 0;
}

赏

非常感谢,我会继续努力的！

支付宝

微信

• 本文作者： killf
• 本文链接： http://www.killf.info/编程语言/算法/LRU算法/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！