快捷導(dǎo)航

JavaScript實現(xiàn)LRU緩存淘汰算法的詳細步驟

更新時間：2024年12月27日 11:21:09 作者：匹馬夕陽

這篇文章主要介紹了JavaScript實現(xiàn)LRU緩存淘汰算法,下面是用 JavaScript 實現(xiàn) LRU（Least RecentlyUsed,最近最少使用）緩存淘汰算法的代碼,并附上詳細的步驟解釋,需要的朋友可以參考下

代碼實現(xiàn)

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity; // 緩存的最大容量
        this.cache = new Map(); // 使用 Map 來存儲緩存數(shù)據(jù)
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1; // 如果緩存中沒有這個 key，返回 -1
        }

        // 獲取值，并將該 key 移動到 Map 的末尾表示最近使用過
        const value = this.cache.get(key);
        this.cache.delete(key); // 先刪除 key
        this.cache.set(key, value); // 重新插入 key-value 使其成為最新的

        return value; // 返回找到的值
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // 如果緩存中已經(jīng)有這個 key，先刪除它
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // 如果緩存已滿，刪除最老的（第一個）元素
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }

        // 插入新的 key-value
        this.cache.set(key, value);
    }
}

// 示例使用
const lruCache = new LRUCache(2);
lruCache.put(1, 1); // 緩存是 {1=1}
lruCache.put(2, 2); // 緩存是 {1=1, 2=2}
console.log(lruCache.get(1));    // 返回 1，緩存是 {2=2, 1=1}
lruCache.put(3, 3); // 緩存容量已滿，淘汰最老的鍵 2，緩存是 {1=1, 3=3}
console.log(lruCache.get(2));    // 返回 -1（未找到）
lruCache.put(4, 4); // 緩存容量已滿，淘汰最老的鍵 1，緩存是 {3=3, 4=4}
console.log(lruCache.get(1));    // 返回 -1（未找到）
console.log(lruCache.get(3));    // 返回 3，緩存是 {4=4, 3=3}
console.log(lruCache.get(4));    // 返回 4，緩存是 {3=3, 4=4}

代碼解釋

初始化緩存：

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity; // 緩存的最大容量
        this.cache = new Map(); // 使用 Map 來存儲緩存數(shù)據(jù)
    }
}

- capacity 表示緩存的最大容量。
- cache 使用 Map 數(shù)據(jù)結(jié)構(gòu)來存儲緩存內(nèi)容。
獲取緩存內(nèi)容：

get(key) {
    if (!this.cache.has(key)) {
        return -1; // 如果緩存中沒有這個 key，返回 -1
    }

    // 獲取值，并將該 key 移動到 Map 的末尾表示最近使用過
    const value = this.cache.get(key);
    this.cache.delete(key); // 先刪除 key
    this.cache.set(key, value); // 重新插入 key-value 使其成為最新的

    return value; // 返回找到的值
}

- 檢查緩存中是否存在指定的 key。
- 如果存在，將該 key 移動到 Map 的末尾，表示最近使用過。
插入緩存內(nèi)容：

put(key, value) {
    if (this.cache.has(key)) {
        // 如果緩存中已經(jīng)有這個 key，先刪除它
        this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
        // 如果緩存已滿，刪除最老的（第一個）元素
        const oldestKey = this.cache.keys().next().value;
        this.cache.delete(oldestKey);
    }

    // 插入新的 key-value
    this.cache.set(key, value);
}

- 如果緩存中已經(jīng)存在 key，刪除舊的 key。
- 如果緩存容量達到上限，刪除最老的元素。
- 插入新的 key-value 對。

使用示例

const lruCache = new LRUCache(2);
lruCache.put(1, 1); // 緩存是 {1=1}
lruCache.put(2, 2); // 緩存是 {1=1, 2=2}
console.log(lruCache.get(1));    // 返回 1，緩存是 {2=2, 1=1}
lruCache.put(3, 3); // 緩存容量已滿，淘汰最老的鍵 2，緩存是 {1=1, 3=3}
console.log(lruCache.get(2));    // 返回 -1（未找到）
lruCache.put(4, 4); // 緩存容量已滿，淘汰最老的鍵 1，緩存是 {3=3, 4=4}
console.log(lruCache.get(1));    // 返回 -1（未找到）
console.log(lruCache.get(3));    // 返回 3，緩存是 {4=4, 3=3}
console.log(lruCache.get(4));    // 返回 4，緩存是 {3=3, 4=4}

以上代碼實現(xiàn)了一個簡單的 LRU 緩存算法，使用 Map 數(shù)據(jù)結(jié)構(gòu)來存儲緩存內(nèi)容，并通過操作 Map 實現(xiàn)最近最少使用的更新策略。

LRU（Least Recently Used，最近最少使用）緩存算法是一種常見的緩存替換策略，廣泛應(yīng)用于各種領(lǐng)域。

主要的應(yīng)用場景：

操作系統(tǒng)中的頁面置換：
- 在操作系統(tǒng)的虛擬內(nèi)存管理中，LRU 算法用于決定在內(nèi)存不足時，哪一頁（page）應(yīng)該被置換出內(nèi)存。
- 通過淘汰最近最少使用的頁面，可以提高內(nèi)存的利用效率和系統(tǒng)的性能。
數(shù)據(jù)庫緩存：
- 數(shù)據(jù)庫系統(tǒng)會使用緩存來加速查詢操作。
- LRU 算法可以用于管理數(shù)據(jù)庫緩存中的數(shù)據(jù)塊，確保最常用的數(shù)據(jù)優(yōu)先保留在緩存中，提高查詢效率。
瀏覽器緩存：
- 瀏覽器會緩存用戶訪問過的網(wǎng)頁資源（如圖片、CSS 文件、JavaScript 文件等）。
- 使用 LRU 算法可以有效管理這些緩存資源，使得用戶在回訪時能更快地加載網(wǎng)頁。
內(nèi)容分發(fā)網(wǎng)絡(luò)（CDN）：
- CDN 會緩存常用的內(nèi)容以減少服務(wù)器負(fù)載和提高用戶訪問速度。
- LRU 算法用于管理這些緩存內(nèi)容，確保最常訪問的資源保留在 CDN 的緩存中。
網(wǎng)絡(luò)路由器緩存：
- 路由器會緩存最近訪問過的路由信息以加速數(shù)據(jù)包的轉(zhuǎn)發(fā)。
- 使用 LRU 算法可以有效管理路由器緩存，減少查找延遲。
文件系統(tǒng)緩存：
- 文件系統(tǒng)會緩存最近訪問的文件或目錄信息。
- LRU 算法用于管理這些緩存，提高文件訪問的速度。
應(yīng)用程序中的數(shù)據(jù)緩存：
- 各種應(yīng)用程序（如 Web 應(yīng)用、移動應(yīng)用等）都會使用緩存來存儲臨時數(shù)據(jù)。
- 使用 LRU 算法可以有效管理這些緩存數(shù)據(jù)，提升應(yīng)用性能。
硬件緩存（如 CPU 緩存）：
- 在計算機硬件中，CPU 緩存用于加速數(shù)據(jù)讀取和寫入操作。
- LRU 算法可以用于管理緩存中的數(shù)據(jù)塊，確保最常用的數(shù)據(jù)保留在高速緩存中，提高處理器的效率。