十分鐘用 JS 寫出 LRU Cache 算法

簡介

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

需求分析

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

  1. 需要提供put方法，用於寫入不同的緩存數據，假設每條數據形式是{'域名','info'}, 例如{'https://segmentfault.com': '一些關鍵信息'}（如果是同一站點重複寫入，就覆蓋）;

  2. 當緩存達到上限時， 調用put寫入緩存之前, 要刪除最近最少使用的數據；

  3. 提供get方法，用於讀取緩存數據，同時需要把被讀取的數據，移動到最近使用數據 ；

  4. 考慮到讀取性能，希望get操作的複雜度是O(1)（簡單理解就是，讀取緩存時不能去遍歷所有數據）

數據選型

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

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

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

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

空間未滿時插入數據：

空間已滿時插入數據：

讀取數據：

算法實現

接下來就可以一步步是實現代碼了，首先是最基本的 構造函數:

1// 第一步代碼
2class LRUCache {
3constructor(n){
4this.size = n; // 初始化最大緩存數據條數n
5this.data = new Map(); // 初始化緩存空間map
6}
7}
8

接下來是put方法，put方法要處理 3 個邏輯：

  1. 如果待寫入的域名，已存在於內存之中，直接更新數據並移動到末尾；

  2. 如果當前未達到緩存數量上限，直接寫入新數據；

  3. 如果當前已經達到緩存數量上限， 要先刪除最不經常使用的數據，再寫入數據；

其他都可以直接操作，移動到末尾這個行爲，可以拆成 " 先刪除該數據，再從末尾重新插入一條該數據 "，這樣就簡單多了。所以我們繼續更新代碼：

代碼如下：

 1// 第一步代碼
 2class LRUCache {
 3constructor(n){
 4this.size = n; // 初始化最大緩存數據條數n
 5this.data = new Map(); // 初始化緩存空間map
 6}
 7// 第二步代碼
 8put(domain, info){
 9if(this.data.has(domain)){
10this.data.delete(domain); // 移除數據
11this.data.set(domain, info)// 在末尾重新插入數據
12return;
13}
14if(this.data.size >= this.size) {
15// 刪除最不常用數據
16const firstKey= this.data.keys().next().value; // 不必當心data爲空，因爲this.size 一般不會取0，滿足this.data.size >= this.size時，this.data自然也不爲空。
17this.data.delete(firstKey);
18}
19this.data.set(domain, info) // 寫入數據
20}
21}
22

接着就只剩下get方法了，get方法同樣也要處理 2 種邏輯：

  1. 根據給定的key，查找是否有對應的信息，若不存在則返回 false；

  2. 若第一步結果存在，則把被訪問數據移動到末尾；

 1// 第一步代碼
 2class LRUCache {
 3constructor(n){
 4this.size = n; // 初始化最大緩存數據條數n
 5this.data = new Map(); // 初始化緩存空間map
 6}
 7// 第二步代碼
 8set(domain, info){
 9if(this.data.size >= this.size) {
10// 刪除最不常用數據
11const firstKey= [...this.data.keys()][0];// 次數不必當心data爲空，因爲this.size 一般不會取0，滿足this.data.size >= this.size時，this.data自然也不爲空。
12this.data.delete(firstKey);
13}
14this.data.set(domain, info) // 寫入數據
15}
16
17// 第三步代碼
18get (domain) {
19if(!this.data.has(domain)){
20return false;
21}
22const info = this.data.get(domain); //獲取結果
23this.data.delete(domain); // 移除數據
24this.data.set(domain, info); // 重新添加該數據
25      
26      return info;
27  }
28}
29
30

這一步要稍微注意的是，我們是先移除數據後添加數據，嚴格遵循最大數量不超過n。

小結

到這裏其實代碼就結束了，也是一個相對輕鬆的一篇文章，估計花個十分鐘稍微看看也就大概掌握了，當然，細心的同學可能留意到了，標題裏有個 (上) 字，意味着還有個（下）篇，因爲本文的思路主要藉助了es6中Map的特點和優勢來完成，有點取巧。而下一篇裏會介紹只用es5來處理這個場景。確切的說，下一篇會介紹更加正規和通用的處理方案

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/HaOWNa3zvIub-ayGiPEieA

猜你喜歡