前端進階演算法3：從瀏覽器快取淘汰策略和Vue的keep-alive學習LRU演算法
引言
這個標題已經很明顯的告訴我們：前端需要了解 LRU 演算法！
這也是前端技能的亮點，當面試官在問到你前端開發中遇到過哪些演算法，你也可以把這部分丟過去！
本節按以下步驟切入：
由瀏覽器快取策略引出 LRU 演算法原理
然後走進
vue
中
keep-alive
的應用
接著，透過
vue
中
keep-alive
原始碼看
LRU
演算法的實現
最後，來一道 leetcode 題目，我們來實現一個 LRU 演算法
按這個步驟來，完全掌握 LRU 演算法，點亮前端技能，下面就開始吧
一、LRU 快取淘汰策略
快取
在計算機網路上隨處可見，例如：當我們首次訪問一個網頁時，開啟很慢，但當我們再次開啟這個網頁時，開啟就很快。
這就涉及快取在瀏覽器上的應用：
瀏覽器快取
。當我們開啟一個網頁時，例如
https：//github。com/sisterAn/JavaScript-Algorithms
，它會在發起真正的網路請求前，查詢瀏覽器快取，看是否有要請求的檔案，如果有，瀏覽器將會攔截請求，返回快取檔案，並直接結束請求，不會再去伺服器上下載。如果不存在，才會去伺服器請求。
其實，瀏覽器中的快取是一種在本地儲存資源副本，它的大小是有限的，當我們請求數過多時，快取空間會被用滿，此時，繼續進行網路請求就需要確定快取中哪些資料被保留，哪些資料被移除，這就是
瀏覽器快取淘汰策略
，最常見的淘汰策略有 FIFO（先進先出）、LFU（最少使用）、LRU（最近最少使用）。
LRU （
Least Recently Used
：最近最少使用 ）快取淘汰策略，故名思義，就是根據資料的歷史訪問記錄來進行淘汰資料，其核心思想是
如果資料最近被訪問過，那麼將來被訪問的機率也更高
，優先淘汰最近沒有被訪問到的資料。
畫個圖幫助我們理解：
二、LRU 在 keep-alive (Vue) 上的實現
1. keep-alive
keep-alive 在 vue 中用於實現元件的快取，當元件切換時不會對當前元件進行解除安裝。
<！—— 基本 ——>
最常用的兩個屬性：
include
、
exculde
，用於元件進行有條件的快取，可以用逗號分隔字串、正則表示式或一個數組來表示。
在 2。5。0 版本中，
keep-alive
新增了
max
屬性，用於最多可以快取多少元件例項，一旦這個數字達到了，在新例項被建立之前，已快取元件中最久沒有被訪問的例項會被銷燬掉，
看，這裡就應用了 LRU 演算法
。即在
keep-alive
中快取達到
max
，新增快取例項會優先淘汰最近沒有被訪問到的例項
下面我們透過 vue 原始碼看一下具體的實現
2. 從 vue 原始碼看 keep-alive 的實現
export default {
name： “keep-alive”，
// 抽象元件屬性 ，它在元件例項建立父子關係的時候會被忽略，發生在 initLifecycle 的過程中
abstract： true，
props： {
// 被快取元件
include： patternTypes，
// 不被快取元件
exclude： patternTypes，
// 指定快取大小
max： ［String， Number］
}，
created（） {
// 初始化用於儲存快取的 cache 物件
this。cache = Object。create（null）；
// 初始化用於儲存VNode key值的 keys 陣列
this。keys = ［］；
}，
destroyed（） {
for （const key in this。cache） {
// 刪除所有快取
pruneCacheEntry（this。cache， key， this。keys）；
}
}，
mounted（） {
// 監聽快取（include）/不快取（exclude）元件的變化
// 在變化時，重新調整 cache
// pruneCache：遍歷 cache，如果快取的節點名稱與傳入的規則沒有匹配上的話，就把這個節點從快取中移除
this。$watch（“include”， val => {
pruneCache（this， name => matches（val， name））；
}）；
this。$watch（“exclude”， val => {
pruneCache（this， name => ！matches（val， name））；
}）；
}，
render（） {
// 獲取第一個子元素的 vnode
const slot = this。$slots。default；
const vnode： VNode = getFirstComponentChild（slot）；
const componentOptions： ？VNodeComponentOptions =
vnode && vnode。componentOptions；
if （componentOptions） {
// name 不在 inlcude 中或者在 exlude 中則直接返回 vnode，否則繼續進行下一步
// check pattern
const name： ？string = getComponentName（componentOptions）；
const { include， exclude } = this；
if （
// not included
（include && （！name || ！matches（include， name））） ||
// excluded
（exclude && name && matches（exclude， name））
） {
return vnode；
}
const { cache， keys } = this；
// 獲取鍵，優先獲取元件的 name 欄位，否則是元件的 tag
const key： ？string =
vnode。key == null
？ // same constructor may get registered as different local components
// so cid alone is not enough （#3269）
componentOptions。Ctor。cid +
（componentOptions。tag ？ `：：${componentOptions。tag}` ： “”）
： vnode。key；
// ——————————————————————————
// 下面就是 LRU 演算法了，
// 如果在快取裡有則調整，
// 沒有則放入（長度超過 max，則淘汰最近沒有訪問的）
// ——————————————————————————
// 如果命中快取，則從快取中獲取 vnode 的元件例項，並且調整 key 的順序放入 keys 陣列的末尾
if （cache［key］） {
vnode。componentInstance = cache［key］。componentInstance；
// make current key freshest
remove（keys， key）；
keys。push（key）；
}
// 如果沒有命中快取，就把 vnode 放進快取
else {
cache［key］ = vnode；
keys。push（key）；
// prune oldest entry
// 如果配置了 max 並且快取的長度超過了 this。max，還要從快取中刪除第一個
if （this。max && keys。length > parseInt（this。max）） {
pruneCacheEntry（cache， keys［0］， keys， this。_vnode）；
}
}
// keepAlive標記位
vnode。data。keepAlive = true；
}
return vnode || （slot && slot［0］）；
}
}；
// 移除 key 快取
function pruneCacheEntry （
cache： VNodeCache，
key： string，
keys： Array
current？： VNode
） {
const cached = cache［key］
if （cached && （！current || cached。tag ！== current。tag）） {
cached。componentInstance。$destroy（）
}
cache［key］ = null
remove（keys， key）
}
// remove 方法（shared/util。js）
/**
* Remove an item from an array。
*/
export function remove （arr： Array
if （arr。length） {
const index = arr。indexOf（item）
if （index > -1） {
return arr。splice（index， 1）
}
}
}
keep-alive原始碼路徑
在
keep-alive
快取超過
max
時，使用的快取淘汰演算法就是 LRU 演算法，它在實現的過程中用到了
cache
物件用於儲存快取的元件例項及
key
值，
keys
陣列用於儲存快取元件的
key
，當
keep-alive
中渲染一個需要快取的例項時：
判斷快取中是否已快取了該例項，快取了則直接獲取，並調整
key
在
keys
中的位置（移除
keys
中
key
，並放入
keys
陣列的最後一位）
如果沒有快取，則快取該例項，若
keys
的長度大於
max
（快取長度超過上限），則移除
keys［0］
快取
下面我們來自己實現一個 LRU 演算法吧⛽️⛽️⛽️
三、leetcode：LRU 快取機制
運用你所掌握的資料結構，設計和實現一個 LRU （最近最少使用） 快取機制。它應該支援以下操作： 獲取資料
get
和寫入資料
put
。
獲取資料
get（key）
- 如果金鑰 （
key
） 存在於快取中，則獲取金鑰的值（總是正數），否則返回
-1
。 寫入資料
put（key， value）
- 如果金鑰不存在，則寫入資料。當快取容量達到上限時，它應該在寫入新資料之前刪除最久未使用的資料，從而為新資料留出空間。
進階:
你是否可以在
O(1)
時間複雜度內完成這兩種操作？
示例:
LRUCache cache = new LRUCache（ 2 /* 快取容量 */ ）；
cache。put（1， 1）；
cache。put（2， 2）；
cache。get（1）； // 返回 1
cache。put（3， 3）； // 該操作會使得金鑰 2 作廢
cache。get（2）； // 返回 -1 （未找到）
cache。put（4， 4）； // 該操作會使得金鑰 1 作廢
cache。get（1）； // 返回 -1 （未找到）
cache。get（3）； // 返回 3
cache。get（4）； // 返回 4
前面已經介紹過了
keep-alive
中LRU實現原始碼，現在來看這道題是不是很簡單 ，可以嘗試自己解答一下⛽️，然後思考一下有沒有什麼繼續最佳化的！歡迎提供更多的解法
答案已提交到 leetcode146：LRU 快取機制 · Issue #7 · sisterAn/JavaScript-Algorithms
