LRU(Least Recently Used Cache) 筆記

前言

最近由於工作上的需求要研究關於cache，做些功課後發現有個常見的例子是，當用戶訪問不同網頁時，瀏覽器需要cache在對應網頁的一些資料，這樣當下次進到同一個頁面的時候，就可以提升網頁載入速度，頁面資料可以直接從cache讀取。所以必須有一些規則來管理cache的使用，而LRU（Least Recently Used） cache就是其中之一，直接翻譯就是「不常使用的資料重要性是最低的，應該優先刪除」。這個規則還滿人經常使用的資料，肯定相對更重要因此記錄下來。

需求分析

假設我們要實現一個簡化版的這個功能，先整理下需求：

需要提供put方法，用於寫入不同的cache資料，假設每條資料形式是 {'域名','info'} ，例如{'https://segmentfault.com': 'Data'} （如果是同一站點重複寫入就覆蓋）當cache達到上限時，用put寫入cache之前，要刪除最近最少使用的資料；提供get方法，用於讀取cache資料，同時需要把被讀取的資料移動到最近新的一筆。

資料型態選擇，首先明顯的提到需要能夠標記資料的插入或使用順序，所以肯定不能簡單使用object來完成，需要藉助Array，或者es6的Map和Set實現(Map和Set資料是有序的，順序即插入順序)

其次需要實現O(1)複雜度，那就也無法用單純使用數組來實現，所以可以考慮的只有Map和Set，那麼最後再考慮下資料重複性的問題，會發現這道題不太需要考慮這個場景，所以我們可以先使用Map來實現。

由於Map的特性是：新插入的資料排在後面，舊資料放在前面，所以我們只要專注於維持這個邏輯就好了。

如果遇到要刪除資料，則優先從前面刪除，因為最前面的必定是最不常用資料；如果讀取某條資料，則應該把資料放到尾端，保證該資料變為最近使用資料。

實作

接下來就可以一步步是實作了，首先是最基本的建構函數:

// 第一步
class LRUcache {
    constructor(n){
        this.size = n; // 初始化最大cache數n
        this.data = new Map(); // 初始化cache空間map
    }
}

接下來是put方法，put方法要處理3個邏輯：

如果待寫入的域名，已存在於內存之中，直接更新資料並移動到尾端。
如果當前未達到cache數量上限，直接寫入新資料。
如果當前已經達到cache數量上限，要先刪除最不經常使用的資料再寫入資料。

可以理解成”先刪除該資料，再從尾端重新插入一條該資料”，這樣理解就簡單多了。所以我們繼續修改程式碼：

// 第一步
class LRUcache {
    constructor(n){
        this.size = n; // 初始化最大cache數n
        this.data = new Map(); // 初始化cache空間map
    }
    // 第二步
    put(domain，info){
        if(this.data.has(domain)){
            this.data.delete(domain); // 移除資料
            this.data.set(domain，info)// 在尾端重新插入資料
            return;
        }
        if(this.data.size >= this.size) {
            // 删除最不常用資料
            const firstKey= [...this.data.keys()][0]; 
            this.data.delete(firstKey);
        }
        this.data.set(domain，info) // 新增資料
    }
}

接着就只剩下get方法了，get方法同样也要处理2种逻辑：

依照给定的key，查找是否有對應的資料，若不存在則回傳false。
若第一步结果存在，则把被访问資料移动到尾端。

// 第一步
class LRUcache {
    constructor(n){
        this.size = n; // 初始化最大cache數n
        this.data = new Map(); // 初始化cache空間map
    }
    
    // 第二步
    put(domain，info){
        if(this.data.size >= this.size) {
        // 删除最不常用資料
        const firstKey= [...this.data.keys()][0];
        this.data.delete(firstKey);
        }
        this.data.set(domain，info) // 新增資料
    }

    // 第三步
    get(domain) {
        if(!this.data.has(domain)){
            return false;
        }
        const info = this.data.get(domain); //取得结果
        this.data.delete(domain); // 移除資料
        this.data.set(domain，info); // 重新新增資料
        return info;
    }
}

這邊要注意的是先移除資料後新增資料，必須遵守最大數量不超過n。