一文帶你了解什么是 LRU 算法？
緩存 是我們寫代碼過程中常用的一種手段，是一種空間換時間的做法。就拿我們經常使用的 HTTP 協議，其中也存在強緩存和協商緩存兩種緩存方式。當我們打開一個網站的時候，瀏覽器會查詢該請求的響應頭，通過判斷響應頭中是否有 Cache-Control、Last-Modified、ETag 等字段，來確定是否直接使用之前下載的資源緩存，而不是重新從服務器進行下載。
下面就是當我們訪問百度時，某些資源命中了協商緩存，服務端返回 304 狀態碼，還有一部分資源命中了強緩存，直接讀取了本地緩存。
但是，緩存并不是無限制的，會有大小的限制。無論是我們的 cookie(不同瀏覽器有所區別，一般在 4KB 左右)，還是 localStorage(和 cookie 一樣，不同瀏覽器有所區別，有些瀏覽器為 5MB，有些瀏覽器為 10MB)，都會有大小限制。
這個時候就需要涉及到一種算法，需要將超出大小限制的緩存進行淘汰，一般的規則是淘汰掉最近沒有被訪問到的緩存，也就是今天要介紹的主角：LRU (Least recently used：最近最少使用)。當然除了 LRU，常見的緩存淘汰還有 FIFO(first-in, first-out：先進先出) 和 LFU(Least frequently used：最少使用)。
什么是 LRU?
LRU (Least recently used：最近最少使用)算法在緩存寫滿的時候，會根據所有數據的訪問記錄，淘汰掉未來被訪問幾率最低的數據。也就是說該算法認為，最近被訪問過的數據，在將來被訪問的幾率最大。
為了方便理解 LRU 算法的全流程，畫了一個簡單的圖：
- 假設我們有一塊內存，一共能夠存儲 5 數據塊。
- 依次向內存存入A、B、C、D、E，此時內存已經存滿。
- 再次插入新的數據時，會將在內存存放時間最久的數據A淘汰掉。
- 當我們在外部再次讀取數據B時，已經處于末尾的B會被標記為活躍狀態，提到頭部，數據C就變成了存放時間最久的數據。
- 再次插入新的數據G，存放時間最久的數據C就會被淘汰掉。
算法實現
下面通過一段簡單的代碼來實現這個邏輯。
class LRUCache {
list = [] // 用于標記先后順序
cache = {} // 用于緩存所有數據
capacity = 0 // 緩存的最大容量
constructor (capacity) {
// 存儲 LRU 可緩存的最大容量
this.capacity = capacity
}
}
基本的結構如上所示，LRU需要實現的就是兩個方法：get 和 put。
class LRUCache {
// 獲取數據
get (key) { }
// 存儲數據
put (key, value) { }
}
我們現在看看如何進行數據的存儲：
class LRUCache {
// 存儲數據
put (key, value) {
// 存儲之前需要先判斷長度是否達到上限
if (this.list.length >= this.capacity) {
// 由于每次存儲后，都會將 key 放入 list 最后，
// 所以，需要取出第一個 key，并刪除cache中的數據。
const latest = this.list.shift()
delete this.cache[latest]
}
// 寫入緩存
this.cache[key] = value
// 寫入緩存后，需要將 key 放入 list 的最后
this.list.push(key)
}
}
然后，在每次獲取數據時，都需要更新 list，將當前獲取的 key 放到 list 的最后。
class LRUCache {
// 獲取數據
get (key) {
if (this.cache[key] !== undefined) {
// 如果 key 對應的緩存存在
// 在返回緩存之前，需要重新激活 key
this.active(key)
return this.cache[key]
}
return undefined
}
// 重新激活key，將指定 key 移動到 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)
}
}
這個時候，其實還沒有完全實現，因為除了 get 操作，put 操作也需要將對應的 key 重新激活。
class LRUCache {
// 存儲數據
put (key, value) {
if (this.cache[key]) {
// 如果該 key 之前存在，將 key 重新激活
this.active(key)
this.cache[key] = value
// 而且此時緩存的長度不會發生變化
// 所以不需要進行后續的長度判斷，可以直接返回
return
}
// 存儲之前需要先判斷長度是否達到上限
if (this.list.length >= this.capacity) {
// 由于每次存儲后，都會將 key 放入 list 最后，
// 所以，需要取出第一個 key，并刪除cache中的數據。
const latest = this.list.shift()
delete this.cache[latest]
}
// 寫入緩存
this.cache[key] = value
// 寫入緩存后，需要將 key 放入 list 的最后
this.list.push(key)
}
}
可能會有人覺得這種算法在前端沒有什么應用場景，說起來，在 Vue 的內置組件 keep-alive 中就使用到了 LRU 算法。
后續應該還會繼續介紹一下 LFU 算法，敬請期待。
