摘要：通過(guò)深度優(yōu)先遍歷兩棵樹(shù)，每層節(jié)點(diǎn)進(jìn)行對(duì)比，記錄下每個(gè)節(jié)點(diǎn)的差異。所以可以對(duì)那棵樹(shù)也進(jìn)行深度優(yōu)先遍歷，遍歷的時(shí)候從步驟二生成的對(duì)象中找出當(dāng)前遍歷的節(jié)點(diǎn)差異，然后進(jìn)行操作。

把一個(gè)div元素的屬性打印出來(lái)，如下：

可以看到僅僅是第一層，真正DOM的元素是非常龐大的，這也是DOM加載慢的原因。
相對(duì)于DOM對(duì)象，原生的JavaScript對(duì)象處理起來(lái)更快，而且更簡(jiǎn)單。DOM樹(shù)上的結(jié)構(gòu)、屬性信息都可以用JavaScript對(duì)象表示出來(lái)：

var element = {
  tagName: "ul", // 節(jié)點(diǎn)標(biāo)簽名
  props: { // DOM的屬性，用一個(gè)對(duì)象存儲(chǔ)鍵值對(duì)
    id: "list"
  },
  children: [ // 該節(jié)點(diǎn)的子節(jié)點(diǎn)
    {tagName: "li", props: {class: "item"}, children: ["Item 1"]},
    {tagName: "li", props: {class: "item"}, children: ["Item 2"]},
    {tagName: "li", props: {class: "item"}, children: ["Item 3"]},
  ]
}

上面對(duì)應(yīng)的HTML寫(xiě)法是：

  
Item 1
  
Item 2
  
Item 3

DOM樹(shù)的信息可以用JavaScript對(duì)象表示出來(lái)，則說(shuō)明可以用JavaScript對(duì)象去表示樹(shù)結(jié)構(gòu)來(lái)構(gòu)建一棵真正的DOM樹(shù)。

狀態(tài)變更->重新渲染整個(gè)視圖的方式可以用新渲染的對(duì)象樹(shù)去和舊的樹(shù)進(jìn)行對(duì)比，記錄這兩棵樹(shù)的差異。兩者的不同之處就是我們需要對(duì)頁(yè)面真正的DOM操作，然后把它們應(yīng)用在真正的DOM樹(shù)上，頁(yè)面就變更了。這樣可以做到：視圖的結(jié)構(gòu)確實(shí)是整個(gè)全新渲染了，但是最后操作DOM的只有變更不同的地方。

用JavaScript對(duì)象結(jié)構(gòu)表示DOM樹(shù)的結(jié)構(gòu)，然后用這個(gè)樹(shù)構(gòu)建一個(gè)真正的DOM樹(shù)，插到文檔當(dāng)中

當(dāng)狀態(tài)變更的時(shí)候，重新構(gòu)建一棵新的對(duì)象樹(shù)。然后用新的樹(shù)和舊的樹(shù)進(jìn)行比較，記錄兩棵樹(shù)的差異

把2所記錄的差異應(yīng)用到步驟1所構(gòu)建的的真正的DOM樹(shù)上，視圖就更新了

Virtual DOM本質(zhì)就是在JS和DOM之間做了一個(gè)緩存，JS操作Virtual DOM，最后再應(yīng)用到真正的DOM上。

步驟一：用JS對(duì)象模擬虛擬DOM樹(shù)

用JavaScript來(lái)表示一個(gè)DOM節(jié)點(diǎn)，則需要記錄它的節(jié)點(diǎn)類(lèi)型、屬性、子節(jié)點(diǎn)：
element.js

function Element (tagName, props, children) {
  this.tagName = tagName
  this.props = props
  this.children = children
}

module.exports = function (tagName, props, children) {
  return new Element(tagName, props, children)
}

上面的DOM結(jié)構(gòu)可以表示為：

var el = require("./element")

var ul = el("ul", {id: "list"}, [
  el("li", {class: "item"}, ["Item 1"]),
  el("li", {class: "item"}, ["Item 2"]),
  el("li", {class: "item"}, ["Item 3"])
])

現(xiàn)在ul只是一個(gè)JavaScript對(duì)象表示的DOM結(jié)構(gòu)，頁(yè)面上并沒(méi)有這個(gè)結(jié)構(gòu)?？梢愿鶕?jù)這個(gè)ul構(gòu)建真正的

：

Element.prototype.render = function () {
  var el = document.createElement(this.tagName) // 根據(jù)tagName構(gòu)建
  var props = this.props

  for (var propName in props) { // 設(shè)置節(jié)點(diǎn)的DOM屬性
    var propValue = props[propName]
    el.setAttribute(propName, propValue)
  }

  var children = this.children || []

  children.forEach(function (child) {
    var childEl = (child instanceof Element)
      ? child.render() // 如果子節(jié)點(diǎn)也是虛擬DOM，遞歸構(gòu)建DOM節(jié)點(diǎn)
      : document.createTextNode(child) // 如果字符串，只構(gòu)建文本節(jié)點(diǎn)
    el.appendChild(childEl)
  })

  return el
}

render方法會(huì)根據(jù)tagName構(gòu)建一個(gè)真正的DOM節(jié)點(diǎn)，然后設(shè)置這個(gè)節(jié)點(diǎn)的屬性，最后遞歸地把自己的子節(jié)點(diǎn)也構(gòu)建起來(lái)。所以需要：

var ulRoot = ul.render()
document.body.appendChild(ulRoot)

上面的ulRoot是真正的DOM節(jié)點(diǎn)，把它塞進(jìn)文檔中，這樣body里面就有了真正的

的DOM結(jié)構(gòu)：

  
Item 1
  
Item 2
  
Item 3

步驟二：比較兩棵虛擬DOM樹(shù)的差異

比較兩棵DOM樹(shù)的差異是Virtual DOM算法最核心的部分，就是diff算法。兩棵樹(shù)的完全diff算法是一個(gè)時(shí)間復(fù)雜度為O(n^3)的問(wèn)題。但在前端中，很少會(huì)跨越層級(jí)地移動(dòng)DOM元素。所以Virtual DOM只會(huì)對(duì)同一層級(jí)的元素進(jìn)行對(duì)比：

上面的div只會(huì)和同一層級(jí)的div對(duì)比，第二層級(jí)的只會(huì)跟第二層級(jí)對(duì)比。這樣算法復(fù)雜度就可以達(dá)到O(n)。

a.深度優(yōu)先遍歷，記錄差異
在實(shí)際的代碼中，會(huì)對(duì)新舊兩棵樹(shù)進(jìn)行一個(gè)深度優(yōu)先的遍歷，這樣每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)唯一的標(biāo)記：

在深度優(yōu)先遍歷的時(shí)候，每遍歷到一個(gè)節(jié)點(diǎn)就把該節(jié)點(diǎn)和新的樹(shù)進(jìn)行對(duì)比。如果有差異的話就記錄到一個(gè)對(duì)象里面。

// diff 函數(shù)，對(duì)比兩棵樹(shù)
function diff (oldTree, newTree) {
  var index = 0 // 當(dāng)前節(jié)點(diǎn)的標(biāo)志
  var patches = {} // 用來(lái)記錄每個(gè)節(jié)點(diǎn)差異的對(duì)象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 對(duì)兩棵樹(shù)進(jìn)行深度優(yōu)先遍歷
function dfsWalk (oldNode, newNode, index, patches) {
  // 對(duì)比oldNode和newNode的不同，記錄下來(lái)
  patches[index] = [...]

  diffChildren(oldNode.children, newNode.children, index, patches)
}

// 遍歷子節(jié)點(diǎn)
function diffChildren (oldChildren, newChildren, index, patches) {
  var leftNode = null
  var currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    var newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 計(jì)算節(jié)點(diǎn)的標(biāo)識(shí)
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節(jié)點(diǎn)
    leftNode = child
  })
}

例如，上面的div和新的div有差異，當(dāng)前的標(biāo)記是0，那么：

patches[0] = [{difference}, {difference}, ...] // 用數(shù)組存儲(chǔ)新舊節(jié)點(diǎn)的不同

同理p是patches[1]，ul是patches[3]，以此類(lèi)推

b.差異類(lèi)型

對(duì)DOM操作會(huì)有的差異：

替換掉原來(lái)的節(jié)點(diǎn)，例如把上面的div換成了section

移動(dòng)、刪除、新增子節(jié)點(diǎn)，例如上面的div的子節(jié)點(diǎn)，把p和ul順序互換

修改了節(jié)點(diǎn)的屬性

對(duì)于文本節(jié)點(diǎn)，文本內(nèi)容可能會(huì)改變。例如修改上面的文本節(jié)點(diǎn)2內(nèi)容為Virtual DOM2

所以定義了幾種差異類(lèi)型：

var REPLACE = 0
var REORDER = 1
var PROPS = 2
var TEXT = 3

對(duì)于節(jié)點(diǎn)的替換，判斷新舊節(jié)點(diǎn)的tagName和是不是一樣，如果不一樣就替換掉。如div換成section，記錄如下：

patches[0] = [{
  type: REPALCE,
  node: newNode // el("section", props, children)
}]

如果給div新增了屬性id為container，記錄如下：

patches[0] = [{
  type: REPALCE,
  node: newNode // el("section", props, children)
}, {
  type: PROPS,
  props: {
    id: "container"
  }
}]

如果修改文本節(jié)點(diǎn)，如上面的文本節(jié)點(diǎn)2，記錄如下：

patches[2] = [{
  type: TEXT,
  content: "Virtual DOM2"
}]

c.列表對(duì)比算法

上面如果把div中的子節(jié)點(diǎn)重新排序，看如p，ul，div的順序換成了div，p，ul。按照同層進(jìn)行順序?qū)Ρ鹊脑?，它們都?huì)被替換掉，這樣DOM開(kāi)銷(xiāo)非常大。而實(shí)際上只需要通過(guò)節(jié)點(diǎn)移動(dòng)就可以的了。
假設(shè)現(xiàn)在可以英文字母唯一得標(biāo)志每一個(gè)子節(jié)點(diǎn)：
舊的節(jié)點(diǎn)順序：
a b c d e f g h i
現(xiàn)在對(duì)節(jié)點(diǎn)進(jìn)行刪除、插入、移動(dòng)的操作。新增j節(jié)點(diǎn)，刪除e節(jié)點(diǎn)，移動(dòng)h節(jié)點(diǎn)：
新的節(jié)點(diǎn)順序：
a b c h d f g i j
現(xiàn)在知道了新舊的順序，求最小的插入、刪除操作（移動(dòng)可以看成是刪除和插入操作的結(jié)合）。這個(gè)問(wèn)題抽象出來(lái)其實(shí)是字符串的最小編輯距離問(wèn)題(Edition Distance)，最常見(jiàn)的算法是Levenshtein Distance，
通過(guò)動(dòng)態(tài)規(guī)劃求解，時(shí)間復(fù)雜度為O(M*N)。而我們只需要優(yōu)化一些常見(jiàn)的移動(dòng)操作，犧牲一定的DOM操作，讓算法時(shí)間復(fù)雜度達(dá)到線性的O((max(M,N)))。
獲取某個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)的操作，就可以記錄如下：

patches[0] = [{
  type: REORDER,
  moves: [{remove or insert}, {remove or insert}, ...]
}]

由于tagName是可以重復(fù)的，所以不能用這個(gè)來(lái)進(jìn)行對(duì)比。需要給子節(jié)點(diǎn)加上一盒唯一標(biāo)識(shí)key，列表對(duì)比的時(shí)候，使用key進(jìn)行對(duì)比，這樣就能復(fù)用舊的DOM樹(shù)上的節(jié)點(diǎn)。
通過(guò)深度優(yōu)先遍歷兩棵樹(shù)，每層節(jié)點(diǎn)進(jìn)行對(duì)比，記錄下每個(gè)節(jié)點(diǎn)的差異。完整的diff算法訪問(wèn)：https://github.com/livoras/si...

步驟三：把差異應(yīng)用到真正的DOM樹(shù)上
因?yàn)椴襟E一所構(gòu)建的JavaScript對(duì)象樹(shù)和render出來(lái)的真正的DOM樹(shù)的信息、結(jié)構(gòu)是一樣的。所以可以對(duì)那棵DOM樹(shù)也進(jìn)行深度優(yōu)先遍歷，遍歷的時(shí)候從步驟二生成的patches對(duì)象中找出當(dāng)前遍歷的節(jié)點(diǎn)差異，然后進(jìn)行DOM操作。

function patch (node, patches) {
  var walker = {index: 0}
  dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
  var currentPatches = patches[walker.index] // 從patches拿出當(dāng)前節(jié)點(diǎn)的差異

  var len = node.childNodes
    ? node.childNodes.length
    : 0
  for (var i = 0; i < len; i++) { // 深度遍歷子節(jié)點(diǎn)
    var child = node.childNodes[i]
    walker.index++
    dfsWalk(child, walker, patches)
  }

  if (currentPatches) {
    applyPatches(node, currentPatches) // 對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行DOM操作
  }
}

applyPatches，根據(jù)不同類(lèi)型的差異對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行 DOM 操作：

function applyPatches (node, currentPatches) {
  currentPatches.forEach(function (currentPatch) {
    switch (currentPatch.type) {
      case REPLACE:
        node.parentNode.replaceChild(currentPatch.node.render(), node)
        break
      case REORDER:
        reorderChildren(node, currentPatch.moves)
        break
      case PROPS:
        setProps(node, currentPatch.props)
        break
      case TEXT:
        node.textContent = currentPatch.content
        break
      default:
        throw new Error("Unknown patch type " + currentPatch.type)
    }
  })
}

完整patch代碼訪問(wèn)：https://github.com/livoras/si...