前言

LRU 緩存算法是一個非常經典的算法，在很多面試中經常問道，不僅僅包括前端面試。

1.什么是 LRU？

LRU 英文全稱是 Least Recently Used，英譯過來就是”最近最少使用“的意思。 它是頁面置換算法中的一種，我們先來看一段百度百科的解釋。

百度百科：

• LRU 是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

百度百科解釋的比較窄，它這里只使用了頁面來舉例，我們通俗點來說就是：假如我們最近訪問了很多個頁面，內存把我們最近訪問的頁面都緩存了起來，但是隨著時間推移，我們還在不停的訪問新頁面，這個時候為了減少內存占用，我們有必要刪除一些頁面，而刪除哪些頁面呢？我們可以通過訪問頁面的時間來決定，或者說是一個標準：在最近時間內，最久未訪問的頁面把它刪掉。

百度百科的解釋只是單純的解釋算法，而我們這里可以結合我們的前端和實際應用場景來給大家解釋一下。

通俗的解釋：

• 假如我們有一塊內存，專門用來緩存我們最近發訪問的網頁，訪問一個新網頁，我們就會往內存中添加一個網頁地址，隨著網頁的不斷增加，內存存滿了，這個時候我們就需要考慮刪除一些網頁了。這個時候我們找到內存中最早訪問的那個網頁地址，然后把它刪掉。
• 這一整個過程就可以稱之為 LRU 算法。

雖然上面的解釋比較好懂了，但是我們還有很多地方沒有考慮到，比如如下幾點：

• 當我們訪問內存中已經存在了的網址，那么該網址是否需要更新在內存中的存儲順序。
• 當我們內存中還沒有數據的時候，是否需要執行刪除操作。

最后我們在上一張圖，大家應該就更容易理解了，如下圖：

上圖就很好的解釋了 LRU 算法在干嘛了，其實非常簡單，無非就是我們往內存里面添加或者刪除元素的時候，遵循最近最少使用原則。

2.使用場景

LRU 算法使用的場景非常多，這里簡單舉幾個例子即可：

• 我們操作系統底層的內存管理，其中就包括有 LRU 算法
• 我們常見的緩存服務，比如 redis 等等
• 比如瀏覽器的最近瀏覽記錄存儲，如下圖：

總之 LRU 算法的運用場景還是蠻多的，所以我們很有必要掌握它。

3.梳理實現 LRU 思路

我們學習了 LRU 算法的基本概念和使用場景之后，那么我們就應該考慮如何實現它了。要想實現一個算法，我們很有必要梳理一下思路，這樣才能讓我們更好更快的編寫出代碼。

首先我們來梳理一下 LRU 算法的特點。

特點分析：

• 我們需要一塊有限的存儲空間，因為無限的化就沒必要使用 LRU 算發刪除數據了。
• 我們這塊存儲空間里面存儲的數據需要是有序的，因為我們必須要順序來刪除數據，所以可以考慮使用 Array、Map 數據結構來存儲，不能使用 Object，因為它是無序的。
• 我們能夠刪除或者添加以及獲取到這塊存儲空間中的指定數據。
• 存儲空間存滿之后，在添加數據時，會自動刪除時間最久遠的那條數據。

實現需求：

• 實現一個 LRUCache 類型，用來充當存儲空間
• 采用 Map 數據結構存儲數據，因為它的存取時間復雜度為 O(1)，數組為 O(n)
• 實現 get 和 set 方法，用來獲取和添加數據
• 我們的存儲空間有長度限制，所以無需提供刪除方法，存儲滿之后，自動刪除最久遠的那條數據
• 當使用 get 獲取數據后，該條數據需要更新到最前面

現在我們已經把 LRU 算法的特點以及實現思路列了出來，那么接下來就然我們一起去實現它吧！

4.具體實現

首先我們定義一個 LRUCache 類，封裝所有的方法和變量。

代碼如下：

<script>
 class LRUCache {
   constructor(lenght) {
     this.length = lenght; // 存儲長度
     this.data = new Map(); // 存儲數據
   }
   // 存儲數據，通過鍵值對的方式
   set(key, value) { }
   // 獲取數據
   get(key) { }
 }
 const lruCache = new LRUCache(5);
</script>

上段代碼只是我們最簡單的一個架子，我們需要去實現具體的 get 和 set 方法。

代碼如下：

<script>
 class LRUCache {
   constructor(lenght) {
     this.length = lenght; // 存儲長度
     this.data = new Map(); // 存儲數據
   }
   // 存儲數據，通過鍵值對的方式
   set(key, value) {
     const data = this.data;
     if (data.has(key)) {
       data.delete(key)
     }
     data.set(key, value);
     // 如果超出了容量，則需要刪除最久的數據
     if (data.size > this.length) {
       const delKey = data.keys().next().value;
       data.delete(delKey);
     }
   }
   // 獲取數據
   get(key) {
     const data = this.data;
     // 未找到
     if (!data.has(key)) {
       return null;
     }
     const value = data.get(key); // 獲取元素
     data.delete(key); // 刪除元素
     data.set(key, value); // 重新插入元素
   }
 }
 const lruCache = new LRUCache(5);
</script>

上段代碼中實現實現了 get 和 set 方法，下面說一下這兩個方法的實現思路：

• set 方法：往 map 里面添加新數據，如果添加的數據存在了，則先刪除該條數據，然后再添加。如果添加數據后超長了，則需要刪除最久遠的一條數據。data.keys().next().value 便是獲取最后一條數據的意思。
• get 方法：首先從 map 對象中拿出該條數據，然后刪除該條數據，最后再重新插入該條數據，確保將該條數據移動到最前面。

接下來我們使用一些測試用例來試試行不行。

存儲數據 set：

lruCache.set('name', '小豬課堂');
lruCache.set('age', 22);
lruCache.set('sex', '男');
lruCache.set('height', 176);
lruCache.set('weight', '100');
console.log(lruCache);

輸出結果：

繼續插入數據，此時會超長，代碼如下：

lruCache.set('grade', '10000');
console.log(lruCache);

輸出結果：

此時我們發現存儲時間最久的 name 已經被移除了，新插入的數據變為了最前面的一個。

我們使用 get 獲取數據，代碼如下：

lruCache.get('sex');
console.log(lruCache);

輸出結果：

我們發現此時 sex 字段已經跑到最前面去了。

總結

LRU 算法其實邏輯非常的簡單，明白了原理之后實現起來非常的簡單。最主要的是我們需要使用什么數據結構來存儲數據，因為 map 的存取非常快，所以我們采用了它，當然數組其實也可以實現的。還有一些小伙伴使用鏈表來實現 LRU，這當然也是可以的。