了解 LRU 快取：高效率的資料儲存和檢索-js教程-PHP中文網

了解 LRU 快取：高效率的資料儲存和檢索

Linda Hamilton

發布： 2025-01-18 20:33:11

原創

651 人瀏覽過

Understanding LRU Cache: Efficient Data Storage and Retrieval

高效的資料儲存和檢索是軟體開發的重要方面，特別是在處理大量資料集或有限記憶體時。 最近最少使用 (LRU) 快取 為此常見挑戰提供了一個優雅的解決方案。這篇文章探討了 LRU 快取：它們的功能、重要性、實現和實際應用。

了解 LRU 快取

LRU 快取是一種資料結構，旨在儲存預定數量的項目。其核心功能在於當快取達到其容量時驅逐最近最少存取的項目。這確保了經常存取的資料仍然可用，而不經常使用的資料則被丟棄。

本質上：

LRU： 最近最少使用。
功能：維護有限數量的項目。滿後，最長未使用的項目將被刪除以容納新資料。

LRU 快取對於記憶體快取、網頁瀏覽和資料庫管理等應用程式來說非常寶貴，在這些應用程式中，快速存取常用資料至關重要，但記憶體卻受到限制。

使用 LRU 快取的好處

整合 LRU 快取有幾個關鍵優勢：

增強的效能：儲存最近存取的資料可顯著加快重複請求的檢索時間。
最佳化記憶體使用：它透過僅保留最關鍵或最頻繁存取的資料來防止記憶體過載。
大型資料集處理：透過僅將相關項目保留在記憶體中，最大限度地減少從較慢的儲存（例如資料庫或 API）中重複獲取，從而有效管理大型資料集。
減少延遲：透過最大限度地減少從較慢的來源檢索資料來加快回應時間。

LRU 快取機制

LRU 快取通常採用兩種資料結構的組合：

雙向鍊錶：保留存取順序（最近到最近）。
雜湊映射（或字典）： 啟用對快取項目的恆定時間 O(1) 存取。

流程如下：

專案存取：訪問的項目被移到雙向鍊錶的頭部（最近使用的）。
達到快取限制：最近最少使用的項目（清單尾部）將被逐出以騰出空間。
新項目插入：如果快取未滿，新項目將會新增到清單的頭部和雜湊映射中，以進行 O(1) 存取。

此雜湊映射和雙向鍊錶組合確保 get 和 put 操作的恆定時間 O(1) 複雜度。

實用的 LRU 快取實作 (JavaScript)

使用 Map（維護插入順序）和容量限制的簡單 JavaScript 實作如下：

範例程式碼（JavaScript）：

<code class="language-javascript">class LRUCache {
    constructor(capacity) {
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, val);
        return val;
    }

    put(key, value) {
        if (this.cache.has(key)) this.cache.delete(key);
        else if (this.cache.size >= this.capacity) this.cache.delete(this.cache.keys().next().value);
        this.cache.set(key, value);
    }
}

// Usage Example:
const cache = new LRUCache(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
console.log(cache.get(1)); // "A"
cache.put(4, "D"); // Evicts 2
console.log(cache.get(2)); // -1
console.log(cache.get(3)); // "C"
console.log(cache.get(4)); // "D"</code>

登入後複製