摘要：中采用算法來實(shí)現(xiàn)緩存的高效管理。通過這兩個(gè)屬性，將緩存中的變量連接起來。以上圖舉例緩存這個(gè)對(duì)象中保存了三個(gè)變量。如果緩存數(shù)組為空，則返回將為傳入?yún)?shù)的緩存對(duì)象標(biāo)識(shí)為最常使用的，即，并調(diào)整雙向鏈表，返回改變后的。

vue.js入坑也有了小半年的時(shí)間了，圈子里一直流傳著其源碼優(yōu)雅、簡(jiǎn)潔的傳說。
最近的一次技術(shù)分享會(huì)，同事分享vue.js源碼的緩存部分，鄙人將其整理出來，與大家一起學(xué)習(xí)

首先我們來看一下鏈表的定義：

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)

其中的雙向鏈表是我們今天的主角：

雙向鏈表也叫雙鏈表。雙向鏈表中不僅有指向后一個(gè)節(jié)點(diǎn)的指針，還有指向前一個(gè)節(jié)點(diǎn)的指針。這樣可以從任何一個(gè)節(jié)點(diǎn)訪問前一個(gè)節(jié)點(diǎn)，當(dāng)然也可以訪問后一個(gè)節(jié)點(diǎn)，以至整個(gè)鏈表。一般是在需要大批量的另外儲(chǔ)存數(shù)據(jù)在鏈表中的位置的時(shí)候用。

圖示如下（圖片來自維基百科-鏈表）：

想象一群人手拉手站成一排，除了隊(duì)頭跟隊(duì)尾，可以根據(jù)每個(gè)人的左手以及右手找到排在其左邊或者右邊的人，這也可以看成一種雙向鏈表

在JavaScript中，我們可以通過對(duì)象的屬性來實(shí)現(xiàn)雙向鏈表。

而在vue.js中，作者正是利用類似雙向鏈表的方式實(shí)現(xiàn)緩存的利用

在緩存中，利用類似雙向鏈表來管理緩存并不難的。難的是如何更加高效的管理緩存，如何在緩存達(dá)到其最大內(nèi)存空間，刪除程序中最不常用的變量，而不是隨機(jī)刪除，造成最常用的變量被誤刪的情況。

vue.js中采用LRU算法來實(shí)現(xiàn)緩存的高效管理。

LRU是Least Recently Used的簡(jiǎn)稱，具體內(nèi)容可以查看GitHub，其有以下優(yōu)點(diǎn)：

基于雙向鏈表改變緩存對(duì)象中entry的排序，復(fù)雜度低

緩存對(duì)象有一個(gè)head（最近最少使用的項(xiàng)）和一個(gè)tail（最近最多使用的項(xiàng)）

head和tail都是entry，一個(gè)entry可能會(huì)有一個(gè)newer entry以及一個(gè)older entry（雙向鏈接，older entry更接近head，newer entry更接近tail）

使用一個(gè)key就可以遍歷這個(gè)緩存對(duì)象，也就意味著只有o(1)的復(fù)雜度，內(nèi)存消耗非常小

可以通過下面的圖來更好的理解LRU算法:

    entry             entry             entry             entry        
    ______            ______            ______            ______       
   | head |.newer => |      |.newer => |      |.newer => | tail |      
   |  A   |          |  B   |          |  C   |          |  D   |      
   |______| <= older.|______| <= older.|______| <= older.|______|      
                                                                       
removed  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  added

如果緩存達(dá)到最大，那么每次只需要將head刪除就行了，保證了刪除的項(xiàng)是最不常用的項(xiàng)

還是拿站成一排的人來舉例。

有兩個(gè)指示牌，上面分別寫著tail以及head。head指向隊(duì)伍的第一個(gè)人，tail指向隊(duì)伍的最后一個(gè)人。

假設(shè)隊(duì)伍有10個(gè)人，按照隊(duì)伍的排列從隊(duì)首到隊(duì)尾依次編號(hào)a b c d ··· j，head指向a，tail指向j。

下面分成五種情況來說明隊(duì)伍的變化：

如果叫到a（使用了數(shù)組里面第一個(gè)變量），就將a放到隊(duì)尾，再手拉手重新組成一個(gè)新的隊(duì)伍。并將原來指向j的tail現(xiàn)在指向a。再讓原來指向a的head指向現(xiàn)在隊(duì)伍的第一個(gè)人b

如果叫到b c d ··· i之間任何一個(gè)人，則將其從隊(duì)伍中抽出，放到隊(duì)尾，重新排隊(duì)，再改變tail的指向?yàn)檫@個(gè)人

如果叫到j,則保持隊(duì)伍不變

隊(duì)伍達(dá)到最大人數(shù)，則去掉head指向的編號(hào)a，并改變head指向編號(hào)b,再在隊(duì)尾增加一個(gè)人，假定編號(hào)為k，最后則將tail指向編號(hào)k

隊(duì)伍沒有達(dá)到最大人數(shù)，需要增加隊(duì)伍人數(shù)。只需要在隊(duì)尾增加編號(hào)為k的人。再將tail指向編號(hào)k

我們可以通過一張圖來先簡(jiǎn)單理解作者的數(shù)據(jù)結(jié)構(gòu)：

作者在caches對(duì)象的_keymap里面保存所需要緩存的變量，通過older以及newer這兩個(gè)屬性來實(shí)現(xiàn)雙向鏈表。older指向其前一個(gè)對(duì)象，newer指向其后一個(gè)對(duì)象。通過這兩個(gè)屬性，將緩存中的變量連接起來。

以上圖舉例：
緩存caches這個(gè)對(duì)象中保存了三個(gè)變量:key1、key2、key3。

header指向key1

tail指向key2

指向如下：

         key1              key2              key3       
        ______            ______            ______       
       | head |.newer => |      |.newer => | tail |      
       |      |          |      |          |      |      
       |______| <= older.|______| <= older.|______|  

下面我們來看作者對(duì)這些數(shù)據(jù)的處理所使用的方法

文件位置：src/cache.js

首先export構(gòu)造函數(shù)Cache

export default function Cache (limit) {
  // 標(biāo)識(shí)當(dāng)前緩存數(shù)組的大小
  this.size = 0
  // 標(biāo)識(shí)緩存數(shù)組能達(dá)到的最大長(zhǎng)度
  this.limit = limit
  // head（最不常用的項(xiàng)），tail（最常用的項(xiàng)）全部初始化為undefined
  this.head = this.tail = undefined
  this._keymap = Object.create(null)
}

接下來作者在Cache的原型鏈上面分別定義了：

put：在緩存中加入一個(gè)key-value對(duì)象，如果緩存數(shù)組已經(jīng)達(dá)到最大值，則返回被刪除的entry，即head,否則返回undefined

shift：在緩存數(shù)組中移除最少使用的entry，即head，返回被刪除的entry。如果緩存數(shù)組為空，則返回undefined

get：將key為傳入?yún)?shù)的緩存對(duì)象標(biāo)識(shí)為最常使用的entry，即tail，并調(diào)整雙向鏈表，返回改變后的tail。如果不存在key為傳入?yún)?shù)的緩存對(duì)象，則返回undefined

a) get:

Cache.prototype.get = function (key, returnEntry) {
  var entry = this._keymap[key]
  // 如果查找不到含有`key`這個(gè)屬性的緩存對(duì)象
  if (entry === undefined) return
  // 如果查找到的緩存對(duì)象已經(jīng)是 tail (最近使用過的)
  if (entry === this.tail) {
    return returnEntry
      ? entry
      : entry.value
  }
  // HEAD--------------TAIL
  //   <.older   .newer>
  //  <--- add direction --
  //   A  B  C    E
  if (entry.newer) {
  // 處理 newer 指向
    if (entry === this.head) {
      // 如果查找到的緩存對(duì)象是 head (最近最少使用過的)
      // 則將 head 指向原 head 的 newer 所指向的緩存對(duì)象
      this.head = entry.newer
    }
    // 將所查找的緩存對(duì)象的下一級(jí)的 older 指向所查找的緩存對(duì)象的older所指向的值
    // 例如：A B C D E
    // 如果查找到的是D，那么將E指向C，不再指向D
    entry.newer.older = entry.older // C <-- E.
  }
  if (entry.older) {
  // 處理 older 指向
    // 如果查找到的是D，那么C指向E，不再指向D
    entry.older.newer = entry.newer // C. --> E
  }
  // 處理所查找到的對(duì)象的 newer 以及 older 指向
  entry.newer = undefined // D --x
  // older指向之前使用過的變量，即D指向E
  entry.older = this.tail // D. --> E
  if (this.tail) {
    // 將E的newer指向D
    this.tail.newer = entry // E. <-- D
  }
  // 改變 tail 為D 
  this.tail = entry
  return returnEntry
    ? entry
    : entry.value
}

b) put:

Cache.prototype.put = function (key, value) {
  var removed

  var entry = this.get(key, true)
  // 如果不存在 key 這樣屬性的緩存對(duì)象，才能調(diào)用 put 方法
  if (!entry) {
    if (this.size === this.limit) {
    // 如果緩存數(shù)組達(dá)到上限，則先刪除 head 指向的緩存對(duì)象
      removed = this.shift()
    }
    // 初始化賦值
    entry = {
      key: key
    }
    this._keymap[key] = entry
    if (this.tail) {
    // 如果存在tail（緩存數(shù)組的長(zhǎng)度不為0），將tail指向新的 entry
      this.tail.newer = entry
      entry.older = this.tail
    } else {
    // 如果緩存數(shù)組的長(zhǎng)度為0，將head指向新的entry
      this.head = entry
    }
    this.tail = entry
    this.size++
  }
  entry.value = value

  return removed
}

c) shift：

Cache.prototype.shift = function () {
  var entry = this.head
  if (entry) {
    // 刪除 head ，并改變指向
    this.head = this.head.newer
    this.head.older = undefined
    entry.newer = entry.older = undefined
    // 同步更新 _keymap 里面的屬性值
    this._keymap[entry.key] = undefined
    // 同步更新 緩存數(shù)組的長(zhǎng)度
    this.size--
  }
  return entry
}

從整個(gè)的代碼來看，需要學(xué)習(xí)的不僅僅是LRU算法，作者的對(duì)于Object的處理方式也值的我們?cè)u(píng)味一番。

沒有選擇去遍歷entry，選擇通過在Cache內(nèi)增加一個(gè)_keymap屬性，通過這個(gè)屬性來管理entry，實(shí)現(xiàn)key與newer、older狀態(tài)的分離，減少代碼的復(fù)雜度

源碼版本為v1.0.26

主要內(nèi)容來自愛屋吉屋FE團(tuán)隊(duì)的技術(shù)分享會(huì)