緩存 是我們寫代碼過程中常用的一種手段，是一種空間換時(shí)間的做法。就拿我們經(jīng)常使用的 HTTP 協(xié)議，其中也存在強(qiáng)緩存和協(xié)商緩存兩種緩存方式。當(dāng)我們打開一個(gè)網(wǎng)站的時(shí)候，瀏覽器會(huì)查詢該請求的響應(yīng)頭，通過判斷響應(yīng)頭中是否有 Cache-Control、Last-Modified、ETag 等字段，來確定是否直接使用之前下載的資源緩存，而不是重新從服務(wù)器進(jìn)行下載。

下面就是當(dāng)我們訪問百度時(shí)，某些資源命中了協(xié)商緩存，服務(wù)端返回 304 狀態(tài)碼，還有一部分資源命中了強(qiáng)緩存，直接讀取了本地緩存。

但是，緩存并不是無限制的，會(huì)有大小的限制。無論是我們的 cookie(不同瀏覽器有所區(qū)別，一般在 4KB 左右)，還是 localStorage(和 cookie 一樣，不同瀏覽器有所區(qū)別，有些瀏覽器為 5MB，有些瀏覽器為 10MB)，都會(huì)有大小限制。

這個(gè)時(shí)候就需要涉及到一種算法，需要將超出大小限制的緩存進(jìn)行淘汰，一般的規(guī)則是淘汰掉最近沒有被訪問到的緩存，也就是今天要介紹的主角：LRU (Least recently used：最近最少使用)。當(dāng)然除了 LRU，常見的緩存淘汰還有 FIFO(first-in, first-out：先進(jìn)先出) 和 LFU(Least frequently used：最少使用)。

什么是 LRU?

LRU (Least recently used：最近最少使用)算法在緩存寫滿的時(shí)候，會(huì)根據(jù)所有數(shù)據(jù)的訪問記錄，淘汰掉未來被訪問幾率最低的數(shù)據(jù)。也就是說該算法認(rèn)為，最近被訪問過的數(shù)據(jù)，在將來被訪問的幾率最大。

為了方便理解 LRU 算法的全流程，畫了一個(gè)簡單的圖：

1. 假設(shè)我們有一塊內(nèi)存，一共能夠存儲(chǔ) 5 數(shù)據(jù)塊。
2. 依次向內(nèi)存存入A、B、C、D、E，此時(shí)內(nèi)存已經(jīng)存滿。
3. 再次插入新的數(shù)據(jù)時(shí)，會(huì)將在內(nèi)存存放時(shí)間最久的數(shù)據(jù)A淘汰掉。
4. 當(dāng)我們在外部再次讀取數(shù)據(jù)B時(shí)，已經(jīng)處于末尾的B會(huì)被標(biāo)記為活躍狀態(tài)，提到頭部，數(shù)據(jù)C就變成了存放時(shí)間最久的數(shù)據(jù)。
5. 再次插入新的數(shù)據(jù)G，存放時(shí)間最久的數(shù)據(jù)C就會(huì)被淘汰掉。

算法實(shí)現(xiàn)

下面通過一段簡單的代碼來實(shí)現(xiàn)這個(gè)邏輯。

class LRUCache {
 list = [] // 用于標(biāo)記先后順序
 cache = {} // 用于緩存所有數(shù)據(jù)
 capacity = 0 // 緩存的最大容量
 constructor (capacity) {
    // 存儲(chǔ) LRU 可緩存的最大容量
  this.capacity = capacity
 }
}

基本的結(jié)構(gòu)如上所示，LRU需要實(shí)現(xiàn)的就是兩個(gè)方法：get 和 put。

class LRUCache {
  // 獲取數(shù)據(jù)
 get (key) { }
  // 存儲(chǔ)數(shù)據(jù)
 put (key, value) { }
}

我們現(xiàn)在看看如何進(jìn)行數(shù)據(jù)的存儲(chǔ)：

class LRUCache {
  // 存儲(chǔ)數(shù)據(jù)
 put (key, value) {
    // 存儲(chǔ)之前需要先判斷長度是否達(dá)到上限
    if (this.list.length >= this.capacity) {
      // 由于每次存儲(chǔ)后，都會(huì)將 key 放入 list 最后，
      // 所以，需要取出第一個(gè) key，并刪除cache中的數(shù)據(jù)。
   const latest = this.list.shift()
   delete this.cache[latest]
  }
    // 寫入緩存
  this.cache[key] = value
    // 寫入緩存后，需要將 key 放入 list 的最后
  this.list.push(key)
  }
}

然后，在每次獲取數(shù)據(jù)時(shí)，都需要更新 list，將當(dāng)前獲取的 key 放到 list 的最后。

class LRUCache {
  // 獲取數(shù)據(jù)
 get (key) {
  if (this.cache[key] !== undefined) {
     // 如果 key 對應(yīng)的緩存存在
      // 在返回緩存之前，需要重新激活 key
   this.active(key)
   return this.cache[key]
  }
  return undefined
  }
  // 重新激活key，將指定 key 移動(dòng)到 list 最后
 active (key) {
    // 先將 key 在 list 中刪除
  const idx = this.list.indexOf(key)
  if (idx !== -1) {
   this.list.splice(idx, 1)
    }
    // 然后將 key 放到 list 最后面
  this.list.push(key)
 }
}

這個(gè)時(shí)候，其實(shí)還沒有完全實(shí)現(xiàn)，因?yàn)槌?get 操作，put 操作也需要將對應(yīng)的 key 重新激活。

class LRUCache {
  // 存儲(chǔ)數(shù)據(jù)
 put (key, value) {
  if (this.cache[key]) {
   // 如果該 key 之前存在，將 key 重新激活
   this.active(key)
   this.cache[key] = value
      // 而且此時(shí)緩存的長度不會(huì)發(fā)生變化
      // 所以不需要進(jìn)行后續(xù)的長度判斷，可以直接返回
   return
  }

    // 存儲(chǔ)之前需要先判斷長度是否達(dá)到上限
    if (this.list.length >= this.capacity) {
      // 由于每次存儲(chǔ)后，都會(huì)將 key 放入 list 最后，
      // 所以，需要取出第一個(gè) key，并刪除cache中的數(shù)據(jù)。
   const latest = this.list.shift()
   delete this.cache[latest]
  }
    // 寫入緩存
  this.cache[key] = value
    // 寫入緩存后，需要將 key 放入 list 的最后
  this.list.push(key)
  }
}

可能會(huì)有人覺得這種算法在前端沒有什么應(yīng)用場景，說起來，在 Vue 的內(nèi)置組件 keep-alive 中就使用到了 LRU 算法。

后續(xù)應(yīng)該還會(huì)繼續(xù)介紹一下 LFU 算法，敬請期待。