什麼是 LRU 緩存？LRUCache 原理詳解和 C-- 代碼實現

什麼時候會用到緩存 (Cache)

緩存（Cache）通常用於兩個速度不同的介質之間，以提高數據訪問的速度和效率。這裏有幾個典型的應用場景：

處理器和內存之間：處理器（CPU）的運算速度遠快於從內存中讀取數據的速度。因此，在 CPU 和內存之間會有多級緩存（L1、L2、甚至 L3 緩存），用來臨時存儲即將被 CPU 使用的數據和指令。這樣做可以大幅減少 CPU 等待數據的時間，提高整體計算效率。

內存和硬盤之間：內存的訪問速度也遠快於硬盤（無論是 HDD 還是 SSD）。操作系統會使用一部分內存作爲硬盤緩存（有時稱爲 “磁盤緩存” 或“緩衝區緩存”），用於臨時存儲最近訪問過的數據和文件。當再次請求這些數據時，可以直接從內存中獲得，而不是從較慢的硬盤中讀取。

數據庫系統中： 數據庫管理系統（DBMS）也會使用緩存技術來提高查詢速度和數據處理效率。緩存可以存儲經常訪問的查詢結果、數據庫索引等信息，從而加速後續相同或相似查詢的處理速度。

網絡請求： 在網絡請求中，緩存也是提高數據訪問速度的重要技術。例如，Web 瀏覽器會緩存訪問過的網頁資源（如 HTML 文件、圖片等），當再次訪問這些資源時，可以直接從本地緩存讀取，而不需要重新從網絡下載。

緩存的關鍵在於它能夠存儲一份數據副本，在訪問速度較慢的介質之前提供快速訪問路徑。這樣，即使背後的存儲介質響應較慢，系統性能也不會受到太大影響。然而，緩存管理（如緩存更新、緩存失效策略等）是實現高效緩存系統的一個挑戰。正確和高效地使用緩存可以顯著提高系統性能，減少數據處理和響應時間。

緩存滿了，怎麼辦？

緩存空間滿了之後，更新數據，我要進去，誰出去呢？

什麼是 LRUCache

LRU 是 Least Recently Used 的縮寫，意思是最近最少使用，它是一種 Cache 替換算法。什麼是 Cache？狹義的 Cache 指的是位於 CPU 和主存間的快速 RAM， 通常它不像系統主存那樣使用 DRAM 技術，而使用昂貴但較快速的 SRAM 技術。廣義上的 Cache 指的是位於速度相差較大的兩種 硬件之間， 用於協調兩者數據傳輸速度差異的結構。除了 CPU 與主存之間有 Cache， 內存與硬盤 之間也有 Cache，乃至在硬盤與網絡之間也有某種意義上的 Cache── 稱爲 Internet 臨時文件夾或 網絡內容緩存等。

Cache 的容量有限，因此當 Cache 的容量用完後，而又有新的內容需要添加進來時， 就需要挑選並捨棄原有的部分內容，從而騰出空間來放新內容。LRUCache 的替換原則就是將最近最少使用的內容替換掉。其實，LRU 譯成最久未使用會更形象， 因爲該算法每次替換掉的就是一段時間內最久沒有使用過的內容。

LRUCache 的實現

要設計一個 LRUCache 不難，要設計一個高效的 LRUCache 有難度，即：任意操作都是 O(1)。

使用雙向鏈表和哈希表的搭配是最高效和經典的。使用雙向鏈表是因爲雙向鏈表可以實現任意位置 0(1) 的插入和刪除，使用哈希表是因爲哈希表的增刪查改也是 O(1)。

別急，我們從實現 LRU 要用的哈希表和雙向鏈表開始。

哈希表（unordered_map）

在 C++ 中，unordered_map 是標準模板庫（STL）中的一個關聯容器，它基於哈希表的實現。它存儲了鍵值對，允許通過鍵快速訪問和修改值。unordered_map 提供了平均常數時間複雜度的訪問、插入和刪除操作。

主要特性

1. 基於哈希表：通過哈希函數將鍵映射到存儲位置，實現快速查找。

2. 鍵不重複：每個鍵在容器中是唯一的。

3. 無序存儲：元素的存儲順序不依賴於插入順序，因此迭代器的遍歷順序可能與插入順序不同。

常用操作

構造和初始化：

• unordered_map()：創建一個空的 unordered_map。

• unordered_map(initializer_list<value_type>)：使用初始化列表創建 unordered_map。

插入操作：

• insert(value_type)：插入一個鍵值對。

• insert(initializer_list<value_type>)：插入多個鍵值對。

訪問操作：

• operator[]：通過鍵訪問對應的值，如果鍵不存在，則插入一個新元素。

• at(key)：通過鍵訪問對應的值，如果鍵不存在，則拋出 std::out_of_range 異常。

查找操作：

• find(key)：查找鍵是否存在，返回一個迭代器。

• count(key)：返回鍵出現的次數（對於 unordered_map 總是返回 0 或 1）。

刪除操作：

• erase(it)：刪除迭代器 it 指向的元素。

• erase(first, last)：刪除從 first 到 last（不包括 last）範圍內的所有元素。

• erase(key)：刪除指定鍵的所有元素。

大小和容量：

• size()：返回容器中元素的數量。

• empty()：如果容器爲空，返回 true。

迭代器：

• begin()：返回指向容器開始的迭代器。

• end()：返回指向容器結束的迭代器。

示例代碼

以下是使用 unordered_map 的一個簡單示例：

#include <iostream>
#include <unordered_map>

int main() {
    // 創建一個 unordered_map，鍵爲 int，值爲 string
    unordered_map<int, string> umap;

    // 插入元素
    umap[1] = "one";
    umap[2] = "two";
    umap[3] = "three";

    // 訪問並打印元素
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 訪問特定鍵的值
    try {
        std::cout << "Value for key 2: " << umap.at(2) << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << e.what() << std::endl;
    }

    // 查找鍵是否存在
    auto it = umap.find(3);
    if (it != umap.end()) {
        std::cout << "Key 3 found, value: " << it->second << std::endl;
    }

    // 刪除元素
    umap.erase(2);
    std::cout << "After erasing key 2:" << std::endl;
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

輸出：

1: one
2: two
3: three
Value for key 2: two
Key 3 found, value: three
After erasing key 2:
1: one
3: three

在這個示例中：

• 創建了一個 unordered_map 並插入了一些鍵值對。

• 遍歷並打印了 unordered_map 中的所有元素。

• 使用 at() 方法安全地訪問特定鍵的值。

• 使用 find() 方法查找鍵是否存在，並訪問對應的值。

• 使用 erase() 方法刪除了鍵爲 2 的元素，並再次打印了剩餘的元素。

雙向鏈表（list）

在 C++ 中，list 是標準模板庫（STL）中的一個容器類，它提供了雙向鏈表的實現。與數組或向量（vector）不同，list 允許在任意位置高效地插入和刪除元素，而不需要移動其他元素。

以下是 list 的一些主要特性和常用操作：

特性

1. 雙向鏈表：每個元素都是鏈表中的一個節點，可以從前向後或從後向前遍歷。

2. 動態大小：list 的大小可以根據需要動態變化，不需要預先定義大小。

3. 插入和刪除操作：可以在常數時間內在任意位置插入或刪除元素，不需要像 vector 那樣移動其他元素。

常用操作

插入操作：

• push_front(value)：在鏈表頭部插入一個元素。

• push_back(value)：在鏈表尾部插入一個元素。

• insert(position, value)：在指定位置插入一個元素。

• insert(position, n, value)：在指定位置插入 n 個相同的元素。

• insert(position, first, last)：在指定位置插入一個範圍內的元素。

刪除操作：

• pop_front()：刪除鏈表頭部的元素。

• pop_back()：刪除鏈表尾部的元素。

• erase(position)：刪除指定位置的元素。

• erase(first, last)：刪除從 first 到 last（不包括 last）範圍內的所有元素。

訪問操作：

• front()：返回鏈表頭部的元素。

• back()：返回鏈表尾部的元素。

迭代器：

• begin()：返回指向鏈表頭部的迭代器。

• end()：返回指向鏈表尾部的迭代器。

大小和容量：

• size()：返回鏈表中元素的數量。

• empty()：如果鏈表爲空，返回 true。

示例代碼

以下是使用 list 的一個簡單示例：

#include <iostream>
#include <list>

int main() {
    list<int> myList;

    // 向鏈表中添加元素
    myList.push_back(10);
    myList.push_back(20);
    myList.push_front(5);

    // 訪問並打印鏈表中的元素
    for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 刪除頭部元素
    myList.pop_front();
    std::cout << "After popping front: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 刪除尾部元素
    myList.pop_back();
    std::cout << "After popping back: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

輸出：

5 10 20 
After popping front: 10 20 
After popping back: 10

在這個示例中，我們創建了一個 list 並添加了一些整數元素。然後，我們遍歷並打印鏈表中的元素，刪除頭部和尾部的元素，並再次打印鏈表中的元素。

到這裏，你已經掌握實現 LRU 緩存的兩個條件了，馬上你就要成功了！！！

不信你往下看！

LRU 緩存（C++）

#include <iostream>
#include <list>
#include <unordered_map>

// 使用 using namespace std; 來簡化代碼，避免重複書寫 std:: 前綴
using namespace std;

// LRUCache 類定義
class LRUCache {
private:
    int capacity;  // 緩存的容量
    list<int> keys;  // 使用雙向鏈表存儲鍵，保持訪問順序
    unordered_map<int, pair<int, list<int>::iterator>> cache;  // 存儲鍵值對和對應的鏈表迭代器

public:
    // 構造函數，初始化緩存容量
    LRUCache(int capacity) : capacity(capacity) {}

    // 獲取緩存中鍵對應的值
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;  // 如果鍵不存在，返回 -1
        }
        // 更新訪問順序，將該鍵移動到鏈表頭部
        keys.erase(it->second.second);
        keys.push_front(key);
        it->second.second = keys.begin();
        return it->second.first;  // 返回鍵對應的值
    }

    // 插入或更新緩存中的鍵值對
    void put(int key, int value) {
        if (cache.size() >= capacity && cache.find(key) == cache.end()) {
            // 如果緩存已滿且鍵不存在，淘汰最不常用的鍵（鏈表尾部的鍵）
            auto last = keys.back();
            cache.erase(cache.find(last));
            keys.pop_back();
        }
        // 插入或更新鍵值對，並更新訪問順序
        cache[key] = {value, keys.insert(keys.begin(), key)};
    }
};

int main() {
    // 創建一個容量爲 2 的 LRU 緩存
    LRUCache cache(2);

    // 插入鍵值對 (1, 1)
    cache.put(1, 1);
    // 訪問鍵 1，輸出其值
    cout << "get(1) = " << cache.get(1) << endl; // 返回 1

    // 插入鍵值對 (2, 2)
    cache.put(2, 2);
    // 訪問鍵 2，輸出其值
    cout << "get(2) = " << cache.get(2) << endl; // 返回 2

    // 插入鍵值對 (3, 3)，由於緩存已滿，鍵 1 被淘汰
    cache.put(3, 3);
    // 訪問鍵 1，由於已被淘汰，返回 -1
    cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
    // 訪問鍵 3，輸出其值
    cout << "get(3) = " << cache.get(3) << endl; // 返回 3

    // 插入鍵值對 (4, 4)，由於緩存已滿，鍵 2 被淘汰
    cache.put(4, 4);
    // 訪問鍵 1，由於已被淘汰，返回 -1
    cout << "get(1) = " << cache.get(1) << endl; // 返回 -1
    // 訪問鍵 3，輸出其值
    cout << "get(3) = " << cache.get(3) << endl; // 返回 3
    // 訪問鍵 2，由於已被淘汰，返回 -1
    cout << "get(2) = " << cache.get(2) << endl; // 返回 -1
    // 訪問鍵 4，輸出其值
    cout << "get(4) = " << cache.get(4) << endl; // 返回 4

    return 0;
}

這段代碼首先定義了一個 LRUCache 類，該類使用 unordered_map 和 list 來實現 LRU 緩存機制。get 方法用於獲取緩存中的值，如果鍵存在，則返回其值並更新訪問順序；如果鍵不存在，則返回 -1。put 方法用於插入或更新緩存中的鍵值對，如果緩存已滿，則淘汰最不常用的鍵（鏈表尾部的鍵）。在 main 函數中，創建了一個 LRUCache 對象並進行了一些操作來演示其功能。

什麼？看不懂？沒關係，結合下面的過程看，你應該就明白了！

初始化狀態

Cache: {}
Keys: []

執行 cache.put(1, 1)

Cache: {1: (1, it1)}
Keys: [1]

執行 cache.put(2, 2)

Cache: {1: (1, it1), 2: (2, it2)}
Keys: [2, 1]  (2 最近使用，1 最少使用)

執行 cache.put(3, 3)

• 緩存已滿，淘汰鍵 1

Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]  (3 最近使用，2 次之)

執行 cache.get(1)

• 鍵 1 不存在，返回 -1

Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]

執行 cache.get(3)

• 鍵 3 存在，返回 3，並更新爲最近使用

Cache: {2: (2, it2), 3: (3, it3)}
Keys: [3, 2]

執行 cache.put(4, 4)

• 緩存已滿，淘汰鍵 2

Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]  (4 最近使用，3 次之)

執行 cache.get(1)

• 鍵 1 不存在，返回 -1

Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]

執行 cache.get(3)

• 鍵 3 存在，返回 3，並更新爲最近使用

Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]

執行 cache.get(2)

• 鍵 2 不存在，返回 -1

Cache: {3: (3, it3), 4: (4, it4)}
Keys: [3, 4]

執行 cache.get(4)

• 鍵 4 存在，返回 4，並更新爲最近使用

Cache: {3: (3, it3), 4: (4, it4)}
Keys: [4, 3]

至此，你就算沒有搞明白，也一定了解 LRU 了。收藏可以方便下次鞏固哦！！！！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rJvKkv9I3o4iF3Pe_eUZFA