您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

C++ LRU 快取實作完整指南：雙向鏈表 + Hash Map O(1) 存取

編輯：C++ 入門

前言：為什麼需要 LRU 快取？

後端開發中，資料庫查詢是效能瓶頸。LRU（Least Recently Used，最近最少使用）快取策略將熱點資料保留在記憶體中：

讀取時：先查快取，命中直接返回；未命中查資料庫並存入快取
寫入時：更新快取並標記為最近使用
快取滿時：淘汰最久未使用的資料（LRU 端）

核心資料結構

雙向鏈表節點

template <class K, class T>
struct Node {
    K key;
    T data;
    Node *prev, *next;
};

LRU 快取類別架構

template <class K, class T>
class LRUCache {
public:
    LRUCache(size_t capacity);
    ~LRUCache();
    
    void Put(K key, T data);  // 插入/更新
    T Get(K key);             // 查詢
    
private:
    void Attach(Node<K,T>* node);  // 移至頭部（最近使用）
    void Detach(Node<K,T>* node);  // 從鏈表移除
    
    hash_map<K, Node<K,T>*> hashmap;  // O(1) 查找
    vector<Node<K,T>*> freeList;      // 記憶體池：預分配節點
    Node<K,T> *head, *tail;            // 虛擬頭尾節點
    Node<K,T> *nodes;                  // 節點陣列
    size_t capacity;
};

關鍵操作流程圖解

Put(key, data) 插入/更新流程

查 hashmap[key]：
- 存在：更新資料，將節點移至頭部
- 不存在：需分配新節點
分配新節點：
- freeList 不空：取出節點，初始化，加入頭部，更新 hashmap
- freeList 空（快取滿）：淘汰尾部節點（LRU），清除其 hashmap 對應，回收節點重用

Get(key) 查詢流程

查 hashmap[key]：
- 存在：將節點移至頭部，返回資料
- 不存在：返回預設值/拋出異常

完整 C++ 實作

#include <iostream>
#include <vector>
#include <ext/hash_map>

using namespace std;
using namespace __gnu_cxx;

template <class K, class T>
struct Node {
    K key;
    T data;
    Node *prev, *next;
    Node() : prev(nullptr), next(nullptr) {}
};

template <class K, class T>
class LRUCache {
public:
    LRUCache(size_t cap) : capacity(cap) {
        nodes = new Node<K,T>[capacity];
        freeList.reserve(capacity);
        for (size_t i = 0; i < capacity; ++i)
            freeList.push_back(&nodes[i]);
        
        head = new Node<K,T>();
        tail = new Node<K,T>();
        head->next = tail;
        tail->prev = head;
    }
    
    ~LRUCache() {
        delete[] nodes;
        delete head;
        delete tail;
    }
    
    void Put(K key, T data) {
        auto it = hashmap.find(key);
        Node<K,T> *node;
        
        if (it != hashmap.end()) {
            // 更新現有節點
            node = it->second;
            node->data = data;
            Detach(node);
        } else {
            // 需要新節點
            if (freeList.empty()) {
                // 快取滿：淘汰 LRU（tail->prev）
                node = tail->prev;
                Detach(node);
                hashmap.erase(node->key);
            } else {
                node = freeList.back();
                freeList.pop_back();
            }
            node->key = key;
            node->data = data;
            hashmap[key] = node;
        }
        Attach(node);
    }
    
    T Get(K key) {
        auto it = hashmap.find(key);
        if (it == hashmap.end())
            return T();  // 或拋出異常
        
        Node<K,T> *node = it->second;
        Detach(node);
        Attach(node);
        return node->data;
    }
    
private:
    void Attach(Node<K,T>* node) {
        // 插入到 head 之後
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void Detach(Node<K,T>* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    hash_map<K, Node<K,T>*> hashmap;
    vector<Node<K,T>*> freeList;
    Node<K,T> *head, *tail;
    Node<K,T> *nodes;
    size_t capacity;
};

實戰除錯經驗：指標陷阱

現象

所有節點的 next 指向自己，鏈表結構崩壞。

根因分析

// 錯誤寫法
for (size_t i = 0; i < capacity; ++i)
    freeList.push_back(nodes + 1);  // 寫成 1 而非 i！

// 正確寫法
for (size_t i = 0; i < capacity; ++i)
    freeList.push_back(nodes + i);

導致 freeList 中全是同一個節點指標，反覆分配同一塊記憶體，Attach/Detach 操作相互覆蓋指標。