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

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 充滿所分配的內(nèi)存塊，那么最新出現(xiàn)的 E 將替代最低使用的 A(0)，訪問順序?yàn)?A -> B -> C -> D -> E -> D -> F。

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

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

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

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

    // 運(yùn)行定時(shí)器，定時(shí)檢查過期值
    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();

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

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

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

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

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

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

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

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

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

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

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

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

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

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