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