LFU缓存

一. 使用两个哈希实现

一个哈希进行直接索引，另一个哈希根据访问频率索引双向链表

/*
定义Node类 双链表节点，包含键、值、前驱、后继

定义LFUCache 类
变量
min_freq：当前最小频率层次
capacity:容量
key_to_node:根据键值索引节点的哈希
freq_to_dummy:根据频率索引双链表的哈希

方法
get_node：根据键获取并更新节点
new_list ：创建一个新的双链表头结点
push_front：在对应频率的双链表上插入节点
remove ：在链表结构中删除该节点，如果链表为空，删除该链表
release ： 释放出一个内存

get： 根据键获取对应值
put： 插入键值对
*/

class Node { //双向链表节点，同时要存储键和值
public:
    int key, value, freq = 1; 
    Node *prev, *next;
    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LFUCache {
private:
    int min_freq;//记录最小一层的频率，用于移除释放
    int capacity;
    unordered_map<int, Node*> key_to_node;  //一个哈希直接找对应节点
    unordered_map<int, Node*> freq_to_dummy; //一个哈希找对应频率的双链表

    Node *get_node(int key) { //获取并更新节点
        auto it = key_to_node.find(key); //直接通过键值哈希查找
        if (it == key_to_node.end())  // 没有该节点
            return nullptr;
        auto node = it->second; // 有该节点
        remove(node); // 从当前链表抽出

        //找该节点的双链表
        push_front(++node->freq, node); // 放到下一层最前面
        return node;
    }

    // 创建一个新的双向链表头尾节点
    Node *new_list() {
        auto dummy = new Node(); // 哨兵节点
        dummy->prev = dummy;
        dummy->next = dummy;
        return dummy;
    }

    // 在对应频率的链表头添加一个节点
    void push_front(int freq, Node *x) {
        auto it = freq_to_dummy.find(freq);
        if (it == freq_to_dummy.end())  // 这个哈希还没有初始化双链表
            it = freq_to_dummy.emplace(freq, new_list()).first;

        //获取对应的双链表，并添加至头部（头插法）
        auto dummy = it->second;
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    // 删除一个节点，删除在链表中的关系,同时链表为空后删除链表
    void remove(Node *x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;

        //主要是判断更新当前最小频率双链表
        auto dummy = freq_to_dummy[x->freq];
        if (dummy->prev == dummy) { // 抽出来后，双链表为空
            freq_to_dummy.erase(x->freq); // 移除空链表
            delete dummy; // 释放内存
            if (min_freq == x->freq) //更新最小频率
                min_freq++;
        }
    }

    void release(){ //频率最小的双链表上,最后节点进行释放
        auto dummy = freq_to_dummy[min_freq];
        auto back_node = dummy->prev; // 找最后的节点
        key_to_node.erase(back_node->key); // 移除在哈希上的关系，这里relea直接删除，remove并不会直接删除
        remove(back_node); // 移除
        delete back_node;
    }

public:
    LFUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        auto node = get_node(key);
        if (node) { // 有这个节点
            node->value = value; // 更新 value
            return;
        }
        if (key_to_node.size() == capacity)  //释放内存
            release();
        
        key_to_node[key] = node = new Node(key, value); // 新节点
        push_front(1, node); // 放在「看过 1 次」的最上面
        min_freq = 1;
    }
};