了解 LRU 之前，我們應該了解一下緩存，大家都知道計算機具有緩存內存，可以臨時存儲最常用的數據，當緩存數據超過一定大小時，系統會進行回收，以便釋放出空間來緩存新的數據，但從系統中檢索數據的成本比較高。

緩存要求：

  • 固定大?。壕彺嫘枰幸恍┫拗苼硐拗苾却媸褂?。
  • 快速訪問：緩存插入和查找操作應該很快，最好是 O(1) 時間。
  • 在達到內存限制的情況下替換條目：緩存應該具有有效的算法來在內存已滿時驅逐條目

如果提供一個緩存替換算法來輔助管理，按照設定的內存大小，刪除最少使用的數據，在系統回收之前主動釋放出空間，會使得整個檢索過程變得非?？欤虼?LRU 緩存淘汰算法就出現了。

LRU 原理與實現

LRU (Least Recently Used) 緩存淘汰算法提出最近被頻繁訪問的數據應具備更高的留存，淘汰那些不常被訪問的數據，即最近使用的數據很大概率將會再次被使用，拋棄最長時間未被訪問的數據，目的是為了方便以后獲取數據變得更快，例如 Vue 的 keep-live 組件就是 LRU 的一種實現。

實現的中心思想拆分為以下幾步：

  • 新的數據插入到鏈表頭部。
  • 每當緩存命中（即緩存數據被訪問），則將數據移到鏈表頭部。
  • 當緩存內存已滿時（鏈表數量已滿時），將鏈表尾部的數據淘汰。

Example

這里使用一個例子來說明 LRU 實現的流程，詳細請參考這里。

  1. 最開始時，內存空間是空的，因此依次進入A、B、C是沒有問題的
  2. 當加入D時，就出現了問題，內存空間不夠了，因此根據LRU算法，內存空間中A待的時間最為久遠，選擇A,將其淘汰
  3. 當再次引用B時，內存空間中的B又處于活躍狀態，而C則變成了內存空間中，近段時間最久未使用的
  4. 當再次向內存空間加入E時，這時內存空間又不足了，選擇在內存空間中待的最久的C將其淘汰出內存，這時的內存空間存放的對象就是E->B->D

基于雙向鏈表和 HashMap 實現 LRU

常見的 LRU 算法是基于雙向鏈表和 HashMap 實現的。

雙向鏈表：用于管理緩存數據結點的順序，新增數據和緩存命中（最近被訪問）的數據被放置在 Header 結點，尾部的結點根據內存大小進行淘汰。

HashMap：存儲所有結點的數據，當 LRU 緩存命中（進行數據訪問）時，進行攔截進行數據置換和刪除操作。

雙向鏈表

雙向鏈表是眾多鏈表中的一種，鏈表都是采用鏈式存儲結構，鏈表中的每一個元素，我們稱之為數據結點。

每個數據結點都包含一個數據域和指針域，指針域可以確定結點與結點之間的順序，通過更新數據結點的指針域的指向可以更新鏈表的順序。

雙向鏈表的每個數據結點包含一個數據域和兩個指針域：

  • proir 指向上一個數據結點；
  • data 當前數據結點的數據；
  • next 指向下一個數據結點；

指針域確定鏈表的順序，那么雙向鏈表擁有雙向指針域，數據結點的之間不在是單一指向，而是雙向指向。即 proir 指針域指向上一個數據結點，next 指針域指向下一個數據結點。

同理：

  • 單向鏈表只有一個指針域。
  • 循環（環狀）鏈表則是擁有雙向指針域，且頭部結點的指針域指向尾部結點，尾部結點的指針域指向頭部結點。

特殊結點：Header 和 Tailer 結點

鏈表中還有兩個特殊的結點，那就算 Header 結點和 Tailer 結點，分別表示頭部結點和尾部結點，頭部結點表示最新的數據或者緩存命中（最近訪問過的數據），尾部結點表示長時間未被使用，即將被淘汰的數據節點。

作為算法大家都會關注其時間和空間復雜度 O(n)，基于雙向鏈表雙向指針域的優勢，為了降級時間復雜度，因此
為了保證 LRU 新數據和緩存命中的數據都位于鏈表最前面（Header），緩存淘汰的時候刪除最后的結點（Tailer），又要避免數據查找時從頭到尾遍歷，降低算法的時間復雜度，同時基于雙向鏈表帶來的優勢，可以改變個別數據結點的指針域從而達到鏈表數據的更新,如果提供 Header 和 Tailer 結點作為標識的話，可以使用頭插法快速增加結點，根據 Tailer 結點也可以在緩存淘汰時快速更新鏈表的順序，避免遍歷從頭到尾遍歷，降低算法的時間復雜度。

排序示例

LRU 鏈表中有 [6，5，4，3，2，1] 6個數據結點，其中 6 所在的數據結點為 Header（頭部）結點，1 所在的數據結點為 Tailer（尾部）結點。如果此時數據 3 被訪問（緩存命中），3 應該被更新至鏈表頭，用數組的思維應該是刪除 3，但是如果我們利用雙向鏈表雙向指針的優勢，可以快速的實現鏈表順便的更新：

  • 3 被刪除時，4 和 2 中間沒有其他結點，即 4 的 next 指針域指向 2 所在的數據結點；同理，2 的 proir 指針域指向 2 所在的數據結點。

HashMap

至于為什么使用 HashMap，用一句話來概括主要是因為 HashMap 通過 Key 獲取速度會快的多，降低算法的時間復雜度。

例如：

  • 我們在 get 緩存的時候從 HashMap 中獲取的時候基本上時間復雜度控制在 O(1)，如果從鏈表中一次遍歷的話時間復雜度是 O(n)。
  • 我們訪問一個已經存在的節點時候，需要將這個節點移動到 header 節點后，這個時候需要在鏈表中刪除這個節點，并重新在 header 后面新增一個節點。這個時候先去 HashMap 中獲取這個節點刪除節點關系，避免了從鏈表中遍歷，將時間復雜度從 O(N) 減少為 O(1)

由于前端沒有 HashMap 的相關 API，我們可以使用 Object 或者 Map 來代替。

代碼實現

現在讓我們運用所掌握的數據結構，設計和實現一個，或者參考 LeeCode 146 題。

鏈表結點 Entry

export class Entry {    value: T    key: string | number    next: Entry    prev: Entry    constructor(val: T) {        this.value = val;    }}

雙向鏈表 Double Linked List

主要職責：

  • 管理頭部結點和尾部結點
  • 插入新數據時，將新數據移到頭部結點
  • 刪除數據時，更新刪除結點前后兩個結點的指向域
/*** Simple double linked list. Compared with array, it has O(1) remove operation.* @constructor*/export class LinkedList {    head: Entry    tail: Entry    private _len = 0    /**    * Insert a new value at the tail    */    insert(val: T): Entry {        const entry = new Entry(val);        this.insertEntry(entry);        return entry;    }    /**    * Insert an entry at the tail    */    insertEntry(entry: Entry) {        if (!this.head) {            this.head = this.tail = entry;        }        else {            this.tail.next = entry;            entry.prev = this.tail;            entry.next = null;            this.tail = entry;        }        this._len++;    }    /**    * Remove entry.    */    remove(entry: Entry) {        const prev = entry.prev;        const next = entry.next;        if (prev) {            prev.next = next;        }        else {            // Is head            this.head = next;        }        if (next) {            next.prev = prev;        }        else {            // Is tail            this.tail = prev;        }        entry.next = entry.prev = null;        this._len--;    }    /**    * Get length    */    len(): number {        return this._len;    }    /**    * Clear list    */    clear() {        this.head = this.tail = null;        this._len = 0;    }}

LRU 核心算法

主要職責：

  • 將數據添加到鏈表并更新鏈表順序
  • 緩存命中時更新鏈表的順序
  • 內存溢出拋棄過時的鏈表數據
/*** LRU Cache*/export default class LRU {    private _list = new LinkedList()    private _maxSize = 10    private _lastRemovedEntry: Entry    private _map: Dictionary> = {}    constructor(maxSize: number) {        this._maxSize = maxSize;    }    /**    * @return Removed value    */    put(key: string | number, value: T): T {        const list = this._list;        const map = this._map;        let removed = null;        if (map[key] == null) {            const len = list.len();            // Reuse last removed entry            let entry = this._lastRemovedEntry;            if (len >= this._maxSize && len > 0) {                // Remove the least recently used                const leastUsedEntry = list.head;                list.remove(leastUsedEntry);                delete map[leastUsedEntry.key];                removed = leastUsedEntry.value;                this._lastRemovedEntry = leastUsedEntry;                }            if (entry) {                entry.value = value;            }            else {                entry = new Entry(value);            }            entry.key = key;            list.insertEntry(entry);            map[key] = entry;        }        return removed;    }    get(key: string | number): T {        const entry = this._map[key];        const list = this._list;        if (entry != null) {            // Put the latest used entry in the tail            if (entry !== list.tail) {                list.remove(entry);                list.insertEntry(entry);            }            return entry.value;        }    }    /**    * Clear the cache    */    clear() {        this._list.clear();        this._map = {};    }    len() {        return this._list.len();    }}

其他 LRU 算法

除了以上常見的 LRU 算法，隨著需求的復雜多樣，基于 LRU 的思想也衍生出了許多優化算法，例如：

參考鏈接