摘要：中采用算法來實現緩存的高效管理。通過這兩個屬性，將緩存中的變量連接起來。以上圖舉例緩存這個對象中保存了三個變量。如果緩存數組為空，則返回將為傳入參數的緩存對象標識為最常使用的，即，并調整雙向鏈表，返回改變后的。

vue.js入坑也有了小半年的時間了，圈子里一直流傳著其源碼優雅、簡潔的傳說。
最近的一次技術分享會，同事分享vue.js源碼的緩存部分，鄙人將其整理出來，與大家一起學習

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

鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針(Pointer)

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

雙向鏈表也叫雙鏈表。雙向鏈表中不僅有指向后一個節點的指針，還有指向前一個節點的指針。這樣可以從任何一個節點訪問前一個節點，當然也可以訪問后一個節點，以至整個鏈表。一般是在需要大批量的另外儲存數據在鏈表中的位置的時候用。

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

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

在JavaScript中，我們可以通過對象的屬性來實現雙向鏈表。

而在vue.js中，作者正是利用類似雙向鏈表的方式實現緩存的利用

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

vue.js中采用LRU算法來實現緩存的高效管理。

LRU是Least Recently Used的簡稱，具體內容可以查看GitHub，其有以下優點：

基于雙向鏈表改變緩存對象中entry的排序，復雜度低

緩存對象有一個head（最近最少使用的項）和一個tail（最近最多使用的項）

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

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

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

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

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

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

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

假設隊伍有10個人，按照隊伍的排列從隊首到隊尾依次編號a b c d ··· j，head指向a，tail指向j。

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

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

如果叫到b c d ··· i之間任何一個人，則將其從隊伍中抽出，放到隊尾，重新排隊，再改變tail的指向為這個人

如果叫到j,則保持隊伍不變

隊伍達到最大人數，則去掉head指向的編號a，并改變head指向編號b,再在隊尾增加一個人，假定編號為k，最后則將tail指向編號k

隊伍沒有達到最大人數，需要增加隊伍人數。只需要在隊尾增加編號為k的人。再將tail指向編號k

我們可以通過一張圖來先簡單理解作者的數據結構：

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

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

header指向key1

tail指向key2

指向如下：

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

下面我們來看作者對這些數據的處理所使用的方法

文件位置：src/cache.js

首先export構造函數Cache

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

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

put：在緩存中加入一個key-value對象，如果緩存數組已經達到最大值，則返回被刪除的entry，即head,否則返回undefined

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

get：將key為傳入參數的緩存對象標識為最常使用的entry，即tail，并調整雙向鏈表，返回改變后的tail。如果不存在key為傳入參數的緩存對象，則返回undefined

a) get:

Cache.prototype.get = function (key, returnEntry) {
  var entry = this._keymap[key]
  // 如果查找不到含有`key`這個屬性的緩存對象
  if (entry === undefined) return
  // 如果查找到的緩存對象已經是 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) {
      // 如果查找到的緩存對象是 head (最近最少使用過的)
      // 則將 head 指向原 head 的 newer 所指向的緩存對象
      this.head = entry.newer
    }
    // 將所查找的緩存對象的下一級的 older 指向所查找的緩存對象的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
  }
  // 處理所查找到的對象的 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 這樣屬性的緩存對象，才能調用 put 方法
  if (!entry) {
    if (this.size === this.limit) {
    // 如果緩存數組達到上限，則先刪除 head 指向的緩存對象
      removed = this.shift()
    }
    // 初始化賦值
    entry = {
      key: key
    }
    this._keymap[key] = entry
    if (this.tail) {
    // 如果存在tail（緩存數組的長度不為0），將tail指向新的 entry
      this.tail.newer = entry
      entry.older = this.tail
    } else {
    // 如果緩存數組的長度為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
    // 同步更新 緩存數組的長度
    this.size--
  }
  return entry
}

從整個的代碼來看，需要學習的不僅僅是LRU算法，作者的對于Object的處理方式也值的我們評味一番。

沒有選擇去遍歷entry，選擇通過在Cache內增加一個_keymap屬性，通過這個屬性來管理entry，實現key與newer、older狀態的分離，減少代碼的復雜度

源碼版本為v1.0.26

主要內容來自愛屋吉屋FE團隊的技術分享會