什么是 LRU 算法？

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

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

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

這個時候就需要涉及到一種算法，需要將超出大小限制的緩存進(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：最近最少使用）算法在緩存寫滿的時候，會根據(jù)所有數(shù)據(jù)的訪問記錄，淘汰掉未來被訪問幾率最低的數(shù)據(jù)。也就是說該算法認(rèn)為，最近被訪問過的數(shù)據(jù)，在將來被訪問的幾率最大。

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

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

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

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

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

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

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

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

class?LRUCache?{
??//?存儲數(shù)據(jù)
?put?(key,?value)?{
????//?存儲之前需要先判斷長度是否達(dá)到上限
????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)
?}
}

這個時候，其實(shí)還沒有完全實(shí)現(xiàn)，因?yà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ā)生變化
??????//?所以不需要進(jìn)行后續(xù)的長度判斷，可以直接返回
???return
??}

????//?存儲之前需要先判斷長度是否達(dá)到上限
????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 算法，敬請期待……