使用 LRU 实现 LFU

Source: Dev.to

📌 核心概念

LFU（Least Frequently Used）意味着：

• 删除 使用频率最低 的键。
• 如果多个键具有相同的频率 → 删除其中 最近最少使用 (LRU) 的键。

📦 使用的数据结构

• key → node （用于 O(1) 访问）
• freq → doubly linked list （按频率分组节点）
• minFreq （跟踪缓存中的最小频率）

🧱 结构可视化

Freq = 1 → [ most recent … least recent ]
Freq = 2 → [ most recent … least recent ]
Freq = 3 → [ most recent … least recent ]

每个频率都有它自己的 LRU 列表.

🚀 示例演练

Capacity = 2

1. put(1,10)

   • Freq 1: [1]
   • minFreq = 1

2. put(2,20)

3. get(1) → 访问键 1

   • 将其频率提升： 1 → 2
   • Freq 1: [2] Freq 2: [1]
   • minFreq = 1

4. put(3,30) （缓存已满）

   • minFreq = 1 → 在 freq 1 中驱逐 LRU (2)
   • 插入后：
     • Freq 1: [3] Freq 2: [1]
     • minFreq = 1

5. get(3) → 将 3 从 freq 1 移动到 freq 2

   • Freq 1: [] Freq 2: [3, 1]
   • minFreq = 2（freq 1 为空）

6. put(4,40) （缓存已满）

   • minFreq = 2 → 在 freq 2 中驱逐 LRU (1)
   • 插入后：
     • Freq 1: [4] Freq 2: [3]
     • minFreq = 1

🔥 关键观察

1. 为什么需要多个列表？
   不同的频率不能放在同一个列表中；每个频率都维护自己的 LRU 顺序。

2. 为什么使用 minFreq？
   它让我们能够在 O(1) 时间内定位需要淘汰的列表。

3. 为什么使用双向链表？
   能够在保持相同频率内部 LRU 顺序的同时，实现 O(1) 的删除。

🧠 心智模型

把 LFU 想象成书架上的书：

• 书架 1 → 使用最少的书
• 书架 2 → 使用适中的书
• 书架 3 → 使用最多的书

删除时，选择使用最少的书架，并从该书架上丢弃最早放入的书。

🧩 映射到代码

🚨 常见错误

当频率列表为空时，必须更新 minFreq：

if (freq == minFreq && list->size == 0)
    minFreq++;

未更新 minFreq 会导致驱逐失效。

代码

class LFUCache {
public:
    class Node {
    public:
        int key, val, freq;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), freq(1), prev(nullptr), next(nullptr) {}
    };

    class List {
    public:
        Node* head;
        Node* tail;
        int size;
        List() : size(0) {
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head->next = tail;
            tail->prev = head;
        }
        void addFront(Node* node) {
            Node* nxt = head->next;
            node->next = nxt;
            node->prev = head;
            head->next = node;
            nxt->prev = node;
            ++size;
        }
        void removeNode(Node* node) {
            Node* prv = node->prev;
            Node* nxt = node->next;
            prv->next = nxt;
            nxt->prev = prv;
            --size;
        }
    };

    int cap;
    int minFreq;
    unordered_map keyNode;   // key → node
    unordered_map freqList;  // freq → DLL

    LFUCache(int capacity) : cap(capacity), minFreq(0) {}

    void updateFreq(Node* node) {
        int f = node->freq;
        freqList[f]->removeNode(node);
        if (f == minFreq && freqList[f]->size == 0)
            ++minFreq;

        ++node->freq;
        if (!freqList.count(node->freq))
            freqList[node->freq] = new List();
        freqList[node->freq]->addFront(node);
    }

    int get(int key) {
        if (!keyNode.count(key)) return -1;
        Node* node = keyNode[key];
        updateFreq(node);
        return node->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (keyNode.count(key)) {
            Node* node = keyNode[key];
            node->val = value;
            updateFreq(node);
            return;
        }
        if (keyNode.size() == cap) {
            List* list = freqList[minFreq];
            Node* evict = list->tail->prev;
            keyNode.erase(evict->key);
            list->removeNode(evict);
        }
        Node* newNode = new Node(key, value);
        minFreq = 1;
        if (!freqList.count(1))
            freqList[1] = new List();
        freqList[1]->addFront(newNode);
        keyNode[key] = newNode;
    }
};