十分鐘用JS寫出LRU Cache 算法

作者：安歌
來源：SegmentFault 思否社區(qū)

簡介

關于緩存，有個常見的例子是，當用戶訪問不同站點時，瀏覽器需要緩存在對應站點的一些信息，這樣當下次訪問同一個站點的時候，就可以使訪問速度變快（因為一部分數(shù)據可以直接從緩存讀?。?。但是想想房價都那么高了，內存空間同樣也是珍貴的（嗚嗚嗚），所以必須有一些規(guī)則來管理緩存的使用，而LRU（Least Recently Used） Cache就是其中之一，直接翻譯就是“最不經常使用的數(shù)據，重要性是最低的，應該優(yōu)先刪除”。這個規(guī)則還蠻人性化的，經常訪問的，肯定相對更重要。

需求分析

假設我們要實現(xiàn)一個簡化版的這個功能，遵循下隔壁后端大佬同事的crud原則，先整理下需求：

1. 需要提供put方法，用于寫入不同的緩存數(shù)據，假設每條數(shù)據形式是{'域名','info'},例如{'https://segmentfault.com': '一些關鍵信息'}（如果是同一站點重復寫入，就覆蓋）;
2. 當緩存達到上限時， 調用put寫入緩存之前, 要刪除最近最少使用的數(shù)據；
3. 提供get方法，用于讀取緩存數(shù)據，同時需要把被讀取的數(shù)據，移動到最近使用數(shù)據 ；
4. 考慮到讀取性能，希望get操作的復雜度是O(1)（簡單理解就是，讀取緩存時不能去遍歷所有數(shù)據）

數(shù)據選型

首先題目里很明顯的提到了，需要能夠標記數(shù)據的插入或使用順序， 所以肯定不能簡單使用object實現(xiàn)，需要借助數(shù)組，或者es6的Map和Set實現(xiàn)(Map和Set數(shù)據遍歷是有序的，遍歷順序即插入順序)；

其次需要實現(xiàn)O(1)復雜度，那就也無法用單純使用數(shù)組來實現(xiàn)，所以可以考慮的只有Map和Set，那么最后再考慮下數(shù)據重復性的問題，會發(fā)現(xiàn)這道題不太需要考慮這個場景，所以我們可以先使用Map來實現(xiàn)。

由于Map的特性是：新插入的數(shù)據排在后面，舊數(shù)據放在前面， 所以我們只要專注于維持這個邏輯就好了:

• 如果遇到要刪除數(shù)據，則優(yōu)先從前面刪除, 因為最前面的必定是最不常用數(shù)據；
• 如果讀取某條數(shù)據，則應該把數(shù)據放到末尾，保證該數(shù)據變?yōu)樽罱褂脭?shù)據；

簡單用幾個圖來表示對應的場景:

空間未滿時插入數(shù)據：

算法實現(xiàn)

// 第一步代碼
class LRUCache {
constructor(n){
this.size = n; // 初始化最大緩存數(shù)據條數(shù)n
this.data = new Map(); // 初始化緩存空間map
}
}

1. 如果待寫入的域名，已存在于內存之中，直接更新數(shù)據并移動到末尾；
2. 如果當前未達到緩存數(shù)量上限，直接寫入新數(shù)據；
3. 如果當前已經達到緩存數(shù)量上限， 要先刪除最不經常使用的數(shù)據，再寫入數(shù)據；

// 第一步代碼
class LRUCache {
constructor(n){
this.size = n; // 初始化最大緩存數(shù)據條數(shù)n
this.data = new Map(); // 初始化緩存空間map
}
// 第二步代碼
put(domain, info){
if(this.data.has(domain)){
this.data.delete(domain); // 移除數(shù)據
this.data.set(domain, info)// 在末尾重新插入數(shù)據
return;
}
if(this.data.size >= this.size) {
// 刪除最不常用數(shù)據
const firstKey= this.data.keys().next().value; // 不必當心data為空，因為this.size 一般不會取0，滿足this.data.size >= this.size時，this.data自然也不為空。
this.data.delete(firstKey);
}
this.data.set(domain, info) // 寫入數(shù)據
}
}

1. 根據給定的key，查找是否有對應的信息，若不存在則返回false；
2. 若第一步結果存在，則把被訪問數(shù)據移動到末尾；

// 第一步代碼
class LRUCache {
constructor(n){
this.size = n; // 初始化最大緩存數(shù)據條數(shù)n
this.data = new Map(); // 初始化緩存空間map
}
// 第二步代碼
set(domain, info){
if(this.data.size >= this.size) {
// 刪除最不常用數(shù)據
const firstKey= [...this.data.keys()][0];// 次數(shù)不必當心data為空，因為this.size 一般不會取0，滿足this.data.size >= this.size時，this.data自然也不為空。
this.data.delete(firstKey);
}
this.data.set(domain, info) // 寫入數(shù)據
}

// 第三步代碼
get (domain) {
if(!this.data.has(domain)){
return false;
}
const info = this.data.get(domain); //獲取結果
this.data.delete(domain); // 移除數(shù)據
this.data.set(domain, info); // 重新添加該數(shù)據
      
      return info;
  }
}

小結