1. 瀏覽器緩存淘汰策略
當(dāng)我們打開一個網(wǎng)頁時武翎，例如 https://github.com/sisterAn/JavaScript-Algorithms 汉规，它會在發(fā)起真正的網(wǎng)絡(luò)請求前朵锣，查詢?yōu)g覽器緩存砸琅，看是否有要請求的文件迫摔，如果有，瀏覽器將會攔截請求汤踏，返回緩存文件倡缠，并直接結(jié)束請求，不會再去服務(wù)器上下載茎活。如果不存在，才會去服務(wù)器請求琢唾。
其實(shí)载荔，瀏覽器中的緩存是一種在本地保存資源副本，它的大小是有限的采桃，當(dāng)我們請求數(shù)過多時懒熙，緩存空間會被用滿丘损，此時，繼續(xù)進(jìn)行網(wǎng)絡(luò)請求就需要確定緩存中哪些數(shù)據(jù)被保留工扎，哪些數(shù)據(jù)被移除徘钥，這就是瀏覽器緩存淘汰策略，最常見的淘汰策略有 FIFO（先進(jìn)先出）肢娘、LFU（最少使用）呈础、LRU（最近最少使用）。
LRU （ Least Recently Used ：最近最少使用 ）緩存淘汰策略橱健，故名思義而钞，就是根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)，其核心思想是** 如果數(shù)據(jù)最近被訪問過拘荡，那么將來被訪問的幾率也更高** 臼节，優(yōu)先淘汰最近沒有被訪問到的數(shù)據(jù)。
畫個圖幫助我們理解 LRU：
2. Vue 的 keep-alive 源碼解讀
在 keep-alive 緩存超過 max 時珊皿，使用的緩存淘汰算法就是 LRU 算法网缝，它在實(shí)現(xiàn)的過程中用到了 cache 對象用于保存緩存的組件實(shí)例及 key 值，keys 數(shù)組用于保存緩存組件的 key 蟋定，當(dāng) keep-alive 中渲染一個需要緩存的實(shí)例時：
- 判斷緩存中是否已緩存了該實(shí)例粉臊，緩存了則直接獲取，并調(diào)整 key 在 keys 中的位置（移除 keys 中 key 溢吻，并放入 keys 數(shù)組的最后一位）
- 如果沒有緩存维费，則緩存該實(shí)例，若 keys 的長度大于 max （緩存長度超過上限）促王，則移除 keys[0] 緩存
主要實(shí)現(xiàn)LRU代碼：
// --------------------------------------------------
// 下面就是 LRU 算法了犀盟，
// 如果在緩存里有則調(diào)整，
// 沒有則放入（長度超過 max蝇狼，則淘汰最近沒有訪問的）
// --------------------------------------------------
// 如果命中緩存阅畴，則從緩存中獲取 vnode 的組件實(shí)例，
// 并且調(diào)整 key 的順序放入 keys 數(shù)組的末尾
if (cache[key]) {
vnode.componentInstance = cache[key].componentInstance;
// make current key freshest
remove(keys, key);
keys.push(key);
}
// 如果沒有命中緩存,就把 vnode 放進(jìn)緩存
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);
}
}
3. 設(shè)計和實(shí)現(xiàn)一個LRU（最近最少使用）緩存機(jī)制
1. 題目
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)贱枣，設(shè)計和實(shí)現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作：獲取數(shù)據(jù) get 和寫入數(shù)據(jù) put 颤专。
獲取數(shù)據(jù) get(key) - 如果密鑰 ( key ) 存在于緩存中纽哥，則獲取密鑰的值（總是正數(shù)），否則返回 -1 栖秕。寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在春塌，則寫入數(shù)據(jù)。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)只壳，從而為新數(shù)據(jù)留出空間俏拱。
進(jìn)階:
你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？
示例:
var 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
2. 答案
基礎(chǔ)解法：數(shù)組+對象實(shí)現(xiàn)
類 vue keep-alive 實(shí)現(xiàn)
var LRUCache = function(capacity) {
this.keys = []
this.cache = Object.create(null)
this.capacity = capacity
};
LRUCache.prototype.get = function(key) {
if(this.cache[key]) {
// 調(diào)整位置
remove(this.keys, key)
this.keys.push(key)
return this.cache[key]
}
return -1
};
LRUCache.prototype.put = function(key, value) {
if(this.cache[key]) {
// 存在即更新
this.cache[key] = value
remove(this.keys, key)
this.keys.push(key)
} else {
// 不存在即加入
this.keys.push(key)
this.cache[key] = value
// 判斷緩存是否已超過最大值
if(this.keys.length > this.capacity) {
removeCache(this.cache, this.keys, this.keys[0])
}
}
};
// 移除 key
function remove(arr, key) {
if (arr.length) {
const index = arr.indexOf(key)
if (index > -1) {
return arr.splice(index, 1)
}
}
}
// 移除緩存中 key
function removeCache(cache, keys, key) {
cache[key] = null
remove(keys, key)
}
進(jìn)階：Map
利用 Map 既能保存鍵值對吼句，并且能夠記住鍵的原始插入順序
var LRUCache = function(capacity) {
this.cache = new Map()
this.capacity = capacity
}
LRUCache.prototype.get = function(key) {
if (this.cache.has(key)) {
// 存在即更新
let temp = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, temp)
return temp
}
return -1
}
LRUCache.prototype.put = function(key, value) {
if (this.cache.has(key)) {
// 存在即更新（刪除后加入）
this.cache.delete(key)
} else if (this.cache.size >= this.capacity) {
// 不存在即加入
// 緩存超過最大值锅必，則移除最近沒有使用的
this.cache.delete(this.cache.keys().next().value)
}
this.cache.set(key, value)
}
