摘要：在上圖中，一旦充滿所分配的內存塊，那么最新出現的將替代最低使用的，訪問順序為。滿額時，從鏈表尾部開始往前刪除指定數目的數據，即可解決。

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.

在上圖中，一旦 A B C D 充滿所分配的內存塊，那么最新出現的 E 將替代最低使用的 A(0)，訪問順序為 A -> B -> C -> D -> E -> D -> F。

這里將會出現一個性能瓶頸，也就是在 Cache 滿時，淘汰那些不常用的數據，空出空間存儲新的數據。假設每一條數據都有一個最后訪問時間， 當滿額的時候，將要遍歷所有元素，才能刪除訪問時間最小的那個元素，時間復雜度為 $O(1)$，數據量越大,性能越低。

所以選擇使用 鏈表，每訪問一次數據，把最新的訪問數據放至頭部，那尾部的數據就是最舊未訪問的數據。 滿額時，從鏈表尾部開始往前刪除指定數目的數據，即可解決。

class LruCache {
  constructor(maxsize) {
    this._cache = {}; // 緩存
    this._queue = []; // 隊列
    this._maxsize = maxsize; // 最大值

    // 如果最大值輸入非法 默認無限大
    if (!this._maxsize || !(typeof this._maxsize === "number") || this._maxsize <= 0) {
      this._maxsize = Infinity;
    }

    // 運行定時器，定時檢查過期值
    setInterval(() => {
      this._queue.forEach((el, idx) => {
        const key = el;
        const insertTime = this._cache[key].insertTime;
        const expire = this._cache[key].expire;
        const curTime = +new Date();

        // 如果存在過期時間且超期，移除數據
        if (expire && curTime - insertTime > expire) {
          this._queue.splice(idx--, 1);
          delete this._cache[key];
        }
      });
    }, 1000);
  }

  // 生成唯一索引
  _makeSymbol(key) {
    return Symbol.for(key);
  }

  // 更新隊列
  _update(queue, key) {
    // 移除
    queue.forEach((el, idx) => {
      if (el === key) {
        queue.splice(idx, 1);
      }
    });

    // 前置
    queue.unshift(key);
    return queue;
  }

  // 插入數據
  set(key, value, expire) {
    key = this._makeSymbol(key); // 生成唯一索引

    // 如果已經存在該值，則重新賦值
    if (this._cache[key]) {
      this._cache[key] = {
        value,
        expire,
        insertTime: this._cache[key].insertTime
      }
      this._queue = this._update(this._queue, key); // 更新隊列
    } else {
      // 如果不存在，則插入
      this._cache[key] = {
        value,
        expire,
        insertTime: +new Date()
      }

      // 索引置前
      this._queue.unshift(key);

      // 超出最大值，截斷
      while (this._queue.length > this._maxsize) {
        const item = this._queue.pop(); // 尾截斷
        delete this._cache[item]; // 刪除
      }
    }
  }

  // 獲取數據
  get(key) {
    key = this._makeSymbol(key);

    // 如果存在該值
    if (this._cache[key]) {
      const insertTime = this._cache[key].insertTime; // 插入時間
      const expire = this._cache[key].expire; // 過期時間
      const curTime = +new Date(); // 當前時間

      // 如果不存在過期時間 或 存在過期時間但尚未過期
      if (!expire || (expire && curTime - insertTime < expire)) {
        // 更新隊列，前置索引
        this._queue = this._update(this._queue, key);

        return this._cache[key].value;
      } else if (expire && curTime - insertTime > expire) {
        // 已經過期
        this._queue.forEach((el, idx) => {
          if (el === key) {
            this._queue.slice(idx, 1);
            delete this._cache[key];
          }
        })

        return null
      }
    } else {
      return null;
    }
  }
}

同步至我的個人博客：https://blog.trevor.top/item/34