面試官：請(qǐng)使用JS完成一個(gè)LRU緩存？

前言

LRU 緩存算法是一個(gè)非常經(jīng)典的算法，在很多面試中經(jīng)常問(wèn)道，不僅僅包括前端面試。小伙伴們?nèi)绻⑦^(guò) Leetcode 算法題，相信你一定遇到過(guò) LRU 算法的題，那么 LRU 算法到底是一個(gè)怎樣的算法呢？今天我們就給大家好好講講，順便使用 JS 把它實(shí)現(xiàn)出來(lái)！

1.什么是 LRU？

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

百度百科：

LRU 是一種常用的頁(yè)面置換算法，選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間 t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其 t 值最大的，即最近最少使用的頁(yè)面予以淘汰。

百度百科解釋的比較窄，它這里只使用了頁(yè)面來(lái)舉例，我們通俗點(diǎn)來(lái)說(shuō)就是：假如我們最近訪問(wèn)了很多個(gè)頁(yè)面，內(nèi)存把我們最近訪問(wèn)的頁(yè)面都緩存了起來(lái)，但是隨著時(shí)間推移，我們還在不停的訪問(wèn)新頁(yè)面，這個(gè)時(shí)候?yàn)榱藴p少內(nèi)存占用，我們有必要?jiǎng)h除一些頁(yè)面，而刪除哪些頁(yè)面呢？我們可以通過(guò)訪問(wèn)頁(yè)面的時(shí)間來(lái)決定，或者說(shuō)是一個(gè)標(biāo)準(zhǔn)：在最近時(shí)間內(nèi)，最久未訪問(wèn)的頁(yè)面把它刪掉。

百度百科的解釋只是單純的解釋算法，而我們這里可以結(jié)合我們的前端和實(shí)際應(yīng)用場(chǎng)景來(lái)給大家解釋一下。

通俗的解釋：

假如我們有一塊內(nèi)存，專門用來(lái)緩存我們最近發(fā)訪問(wèn)的網(wǎng)頁(yè)，訪問(wèn)一個(gè)新網(wǎng)頁(yè)，我們就會(huì)往內(nèi)存中添加一個(gè)網(wǎng)頁(yè)地址，隨著網(wǎng)頁(yè)的不斷增加，內(nèi)存存滿了，這個(gè)時(shí)候我們就需要考慮刪除一些網(wǎng)頁(yè)了。這個(gè)時(shí)候我們找到內(nèi)存中最早訪問(wèn)的那個(gè)網(wǎng)頁(yè)地址，然后把它刪掉。
這一整個(gè)過(guò)程就可以稱之為 LRU 算法。

雖然上面的解釋比較好懂了，但是我們還有很多地方?jīng)]有考慮到，比如如下幾點(diǎn)：

• 當(dāng)我們?cè)L問(wèn)內(nèi)存中已經(jīng)存在了的網(wǎng)址，那么該網(wǎng)址是否需要更新在內(nèi)存中的存儲(chǔ)順序。
• 當(dāng)我們內(nèi)存中還沒(méi)有數(shù)據(jù)的時(shí)候，是否需要執(zhí)行刪除操作。

最后我們?cè)谏弦粡垐D，大家應(yīng)該就更容易理解了，如下圖：

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

2.使用場(chǎng)景

LRU 算法使用的場(chǎng)景非常多，這里簡(jiǎn)單舉幾個(gè)例子即可：

1. 我們操作系統(tǒng)底層的內(nèi)存管理，其中就包括有 LRU 算法
2. 我們常見(jiàn)的緩存服務(wù)，比如 redis 等等
3. 比如瀏覽器的最近瀏覽記錄存儲(chǔ)，如下圖：

總之 LRU 算法的運(yùn)用場(chǎng)景還是蠻多的，所以我們很有必要掌握它。

3.梳理實(shí)現(xiàn) LRU 思路

我們學(xué)習(xí)了 LRU 算法的基本概念和使用場(chǎng)景之后，那么我們就應(yīng)該考慮如何實(shí)現(xiàn)它了。要想實(shí)現(xiàn)一個(gè)算法，我們很有必要梳理一下思路，這樣才能讓我們更好更快的編寫出代碼。

首先我們來(lái)梳理一下 LRU 算法的特點(diǎn)。

特點(diǎn)分析：

• 我們需要一塊有限的存儲(chǔ)空間，因?yàn)闊o(wú)限的化就沒(méi)必要使用 LRU 算發(fā)刪除數(shù)據(jù)了。
• 我們這塊存儲(chǔ)空間里面存儲(chǔ)的數(shù)據(jù)需要是有序的，因?yàn)槲覀儽仨氁樞騺?lái)刪除數(shù)據(jù)，所以可以考慮使用 Array、Map 數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)，不能使用 Object，因?yàn)樗菬o(wú)序的。
• 我們能夠刪除或者添加以及獲取到這塊存儲(chǔ)空間中的指定數(shù)據(jù)。
• 存儲(chǔ)空間存滿之后，在添加數(shù)據(jù)時(shí)，會(huì)自動(dòng)刪除時(shí)間最久遠(yuǎn)的那條數(shù)據(jù)。

實(shí)現(xiàn)需求：

• 實(shí)現(xiàn)一個(gè) LRUCache 類型，用來(lái)充當(dāng)存儲(chǔ)空間
• 采用 Map 數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，因?yàn)樗拇嫒r(shí)間復(fù)雜度為 O(1)，數(shù)組為 O(n)
• 實(shí)現(xiàn) get 和 set 方法，用來(lái)獲取和添加數(shù)據(jù)
• 我們的存儲(chǔ)空間有長(zhǎng)度限制，所以無(wú)需提供刪除方法，存儲(chǔ)滿之后，自動(dòng)刪除最久遠(yuǎn)的那條數(shù)據(jù)
• 當(dāng)使用 get 獲取數(shù)據(jù)后，該條數(shù)據(jù)需要更新到最前面

現(xiàn)在我們已經(jīng)把 LRU 算法的特點(diǎn)以及實(shí)現(xiàn)思路列了出來(lái)，那么接下來(lái)就然我們一起去實(shí)現(xiàn)它吧！

4.具體實(shí)現(xiàn)

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

代碼如下：

<script>
  class LRUCache {
    constructor(lenght) {
      this.length = lenght; // 存儲(chǔ)長(zhǎng)度
      this.data = new Map(); // 存儲(chǔ)數(shù)據(jù)
    }
    // 存儲(chǔ)數(shù)據(jù)，通過(guò)鍵值對(duì)的方式
    set(key, value) { }
    // 獲取數(shù)據(jù)
    get(key) { }
  }
  const lruCache = new LRUCache(5);
</script>

上段代碼只是我們最簡(jiǎn)單的一個(gè)架子，我們需要去實(shí)現(xiàn)具體的 get 和 set 方法。

代碼如下：

<script>
  class LRUCache {
    constructor(lenght) {
      this.length = lenght; // 存儲(chǔ)長(zhǎng)度
      this.data = new Map(); // 存儲(chǔ)數(shù)據(jù)
    }
    // 存儲(chǔ)數(shù)據(jù)，通過(guò)鍵值對(duì)的方式
    set(key, value) {
      const data = this.data;
      if (data.has(key)) {
        data.delete(key)
      }
      data.set(key, value);


      // 如果超出了容量，則需要?jiǎng)h除最久的數(shù)據(jù)
      if (data.size > this.length) {
        const delKey = data.keys().next().value;
        data.delete(delKey);
      }
    }
    // 獲取數(shù)據(jù)
    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>

上段代碼中實(shí)現(xiàn)實(shí)現(xiàn)了 get 和 set 方法，下面說(shuō)一下這兩個(gè)方法的實(shí)現(xiàn)思路：

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

接下來(lái)我們使用一些測(cè)試用例來(lái)試試行不行。

存儲(chǔ)數(shù)據(jù) set：

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

輸出結(jié)果：

繼續(xù)插入數(shù)據(jù)，此時(shí)會(huì)超長(zhǎng)，代碼如下：

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

輸出結(jié)果：

此時(shí)我們發(fā)現(xiàn)存儲(chǔ)時(shí)間最久的 name 已經(jīng)被移除了，新插入的數(shù)據(jù)變?yōu)榱俗钋懊娴囊粋€(gè)。

我們使用 get 獲取數(shù)據(jù)，代碼如下：

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

輸出結(jié)果：

我們發(fā)現(xiàn)此時(shí) sex 字段已經(jīng)跑到最前面去了。

總結(jié)

LRU 算法其實(shí)邏輯非常的簡(jiǎn)單，明白了原理之后實(shí)現(xiàn)起來(lái)非常的簡(jiǎn)單。最主要的是我們需要使用什么數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)，因?yàn)?map 的存取非?？?，所以我們采用了它，當(dāng)然數(shù)組其實(shí)也可以實(shí)現(xiàn)的。還有一些小伙伴使用鏈表來(lái)實(shí)現(xiàn) LRU，這當(dāng)然也是可以的。

參考資料