转载

探索vue源码之缓存篇

vue.js 入坑也有了小半年的时间了，圈子里一直流传着其源码优雅、简洁的传说。

最近的一次技术分享会，同事分享 vue.js 源码的缓存部分，鄙人将其整理出来，与大家一起学习

一、从链表说起

首先我们来看一下链表的定义：

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)

其中的双向链表是我们今天的主角：

双向链表也叫 双链表 。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。

图示如下（图片来自维基百科-链表）：

在 JavaScript 中，我们可以通过对象的属性来实现双向链表。

而在 vue.js 中，作者正是利用类似双向链表的方式实现缓存的利用

二、LRU算法

在缓存中，利用类似双向链表来管理缓存并不难的。难的是如何更加高效的管理缓存，如何在缓存达到其最大内存空间，删除程序中最不常用的变量，而不是随机删除，造成最常用的变量被误删的情况。

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 删除就行了，保证了删除的项是 最不常用的项

三、源码分析

文件位置： 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  <D>  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
}