聲明：本文copy自深度剖析：如何實現(xiàn)一個 Virtual DOM 算法-戴嘉華续滋，留做記錄已做日后溫習

目錄：

• 1 前言
• 2 對前端應用狀態(tài)管理思考
• 3 Virtual DOM 算法
• 4 算法實現(xiàn)
  • 4.1 步驟一：用JS對象模擬DOM樹
  • 4.2 步驟二：比較兩棵虛擬DOM樹的差異
  • 4.3 步驟三：把差異應用到真正的DOM樹上
• 5 結語
• 6 References

1 前言

本文會在教你怎么用 300~400 行代碼實現(xiàn)一個基本的 Virtual DOM 算法，并且嘗試盡量把 Virtual DOM 的算法思路闡述清楚孵奶。希望在閱讀本文后疲酌，能讓你深入理解 Virtual DOM 算法，給你現(xiàn)有前端的編程提供一些新的思考了袁。

本文所實現(xiàn)的完整代碼存放在 Github朗恳。

2 對前端應用狀態(tài)管理的思考

假如現(xiàn)在你需要寫一個像下面一樣的表格的應用程序，這個表格可以根據(jù)不同的字段進行升序或者降序的展示载绿。

sort-table

這個應用程序看起來很簡單粥诫，你可以想出好幾種不同的方式來寫。最容易想到的可能是崭庸，在你的 JavaScript 代碼里面存儲這樣的數(shù)據(jù)：

var sortKey = "new" // 排序的字段怀浆，新增（new）、取消（cancel）怕享、凈關注（gain）执赡、累積（cumulate）人數(shù)
var sortType = 1 // 升序還是逆序
var data = [{...}, {...}, {..}, ..] // 表格數(shù)據(jù)

用三個字段分別存儲當前排序的字段、排序方向函筋、還有表格數(shù)據(jù)沙合；然后給表格頭部加點擊事件：當用戶點擊特定的字段的時候，根據(jù)上面幾個字段存儲的內容來對內容進行排序跌帐，然后用 JS 或者 jQuery 操作 DOM灌诅，更新頁面的排序狀態(tài)（表頭的那幾個箭頭表示當前排序狀態(tài)，也需要更新）和表格內容含末。

這樣做會導致的后果就是猜拾，隨著應用程序越來越復雜，需要在JS里面維護的字段也越來越多佣盒，需要監(jiān)聽事件和在事件回調用更新頁面的DOM操作也越來越多挎袜，應用程序會變得非常難維護。后來人們使用了 MVC、MVP 的架構模式盯仪，希望能從代碼組織方式來降低維護這種復雜應用程序的難度紊搪。但是 MVC 架構沒辦法減少你所維護的狀態(tài)，也沒有降低狀態(tài)更新你需要對頁面的更新操作（前端來說就是DOM操作）全景，你需要操作的DOM還是需要操作耀石，只是換了個地方。

既然狀態(tài)改變了要操作相應的DOM元素爸黄，為什么不做一個東西可以讓視圖和狀態(tài)進行綁定滞伟，狀態(tài)變更了視圖自動變更，就不用手動更新頁面了炕贵。這就是后來人們想出了 MVVM 模式梆奈，只要在模版中聲明視圖組件是和什么狀態(tài)進行綁定的，雙向綁定引擎就會在狀態(tài)更新的時候自動更新視圖（關于MV*模式的內容称开，可以看這篇介紹）亩钟。

MVVM 可以很好的降低我們維護狀態(tài) -> 視圖的復雜程度（大大減少代碼中的視圖更新邏輯）。但是這不是唯一的辦法鳖轰，還有一個非常直觀的方法清酥，可以大大降低視圖更新的操作：一旦狀態(tài)發(fā)生了變化，就用模版引擎重新渲染整個視圖蕴侣，然后用新的視圖更換掉舊的視圖焰轻。就像上面的表格，當用戶點擊的時候睛蛛，還是在JS里面更新狀態(tài)鹦马，但是頁面更新就不用手動操作 DOM 了，直接把整個表格用模版引擎重新渲染一遍忆肾，然后設置一下innerHTML就完事了荸频。

聽到這樣的做法，經(jīng)驗豐富的你一定第一時間意識這樣的做法會導致很多的問題客冈。最大的問題就是這樣做會很慢旭从，因為即使一個小小的狀態(tài)變更都要重新構造整棵 DOM，性價比太低场仲；而且這樣做的話和悦，input和textarea的會失去原有的焦點。最后的結論會是：對于局部的小視圖的更新渠缕，沒有問題（Backbone就是這么干的）鸽素；但是對于大型視圖，如全局應用狀態(tài)變更的時候亦鳞，需要更新頁面較多局部視圖的時候馍忽，這樣的做法不可取棒坏。

但是這里要明白和記住這種做法，因為后面你會發(fā)現(xiàn)遭笋，其實 Virtual DOM 就是這么做的坝冕，只是加了一些特別的步驟來避免了整棵 DOM 樹變更。

另外一點需要注意的就是瓦呼，上面提供的幾種方法喂窟，其實都在解決同一個問題：維護狀態(tài)，更新視圖央串。在一般的應用當中磨澡，如果能夠很好方案來應對這個問題，那么就幾乎降低了大部分復雜性蹋辅。

3 Virtual DOM算法

DOM是很慢的钱贯。如果我們把一個簡單的div元素的屬性都打印出來挫掏，你會看到：

dom-attr

而這僅僅是第一層侦另。真正的 DOM 元素非常龐大，這是因為標準就是這么設計的尉共。而且操作它們的時候你要小心翼翼褒傅，輕微的觸碰可能就會導致頁面重排，這可是殺死性能的罪魁禍首袄友。

相對于 DOM 對象殿托，原生的 JavaScript 對象處理起來更快，而且更簡單剧蚣。DOM 樹上的結構支竹、屬性信息我們都可以很容易地用 JavaScript 對象表示出來：

var element = {
  tagName: 'ul', // 節(jié)點標簽名
  props: { // DOM的屬性，用一個對象存儲鍵值對
    id: 'list'
  },
  children: [ // 該節(jié)點的子節(jié)點
    {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]},
    {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]},
  ]
}

上面對應的HTML寫法是：

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

既然原來 DOM 樹的信息都可以用 JavaScript 對象來表示鸠按，反過來礼搁，你就可以根據(jù)這個用 JavaScript 對象表示的樹結構來構建一棵真正的DOM樹。

之前的章節(jié)所說的目尖，狀態(tài)變更->重新渲染整個視圖的方式可以稍微修改一下：用 JavaScript 對象表示 DOM 信息和結構馒吴，當狀態(tài)變更的時候，重新渲染這個 JavaScript 的對象結構瑟曲。當然這樣做其實沒什么卵用饮戳，因為真正的頁面其實沒有改變。

但是可以用新渲染的對象樹去和舊的樹進行對比洞拨，記錄這兩棵樹差異扯罐。記錄下來的不同就是我們需要對頁面真正的 DOM 操作，然后把它們應用在真正的 DOM 樹上烦衣，頁面就變更了歹河。這樣就可以做到：視圖的結構確實是整個全新渲染了齿椅，但是最后操作DOM的時候確實只變更有不同的地方。

這就是所謂的 Virtual DOM 算法启泣。包括幾個步驟：

1. 用 JavaScript 對象結構表示 DOM 樹的結構涣脚；然后用這個樹構建一個真正的 DOM 樹，插到文檔當中
2. 當狀態(tài)變更的時候寥茫，重新構造一棵新的對象樹遣蚀。然后用新的樹和舊的樹進行比較，記錄兩棵樹差異
3. 把2所記錄的差異應用到步驟1所構建的真正的DOM樹上纱耻，視圖就更新了

Virtual DOM 本質上就是在 JS 和 DOM 之間做了一個緩存芭梯。可以類比 CPU 和硬盤弄喘，既然硬盤這么慢玖喘，我們就在它們之間加個緩存：既然 DOM 這么慢，我們就在它們 JS 和 DOM 之間加個緩存蘑志。CPU（JS）只操作內存（Virtual DOM）累奈，最后的時候再把變更寫入硬盤（DOM）。

4 算法實現(xiàn)

4.1 步驟一：用JS對象模擬DOM樹

用 JavaScript 來表示一個 DOM 節(jié)點是很簡單的事情急但，你只需要記錄它的節(jié)點類型澎媒、屬性鸣个，還有子節(jié)點：

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 結構就可以簡單的表示：

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只是一個 JavaScript 對象表示的 DOM 結構咬最，頁面上并沒有這個結構。我們可以根據(jù)這個ul構建真正的<ul>：

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

  for (var propName in props) { // 設置節(jié)點的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é)點也是虛擬DOM肆饶，遞歸構建DOM節(jié)點
      : document.createTextNode(child) // 如果字符串镐躲，只構建文本節(jié)點
    el.appendChild(childEl)
  })

  return el
}

render方法會根據(jù)tagName構建一個真正的DOM節(jié)點储玫，然后設置這個節(jié)點的屬性，最后遞歸地把自己的子節(jié)點也構建起來萤皂。所以只需要：

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

上面的ulRoot是真正的DOM節(jié)點撒穷，把它塞入文檔中，這樣body里面就有了真正的<ul>的DOM結構：

<ul id='list'>
  <li class='item'>Item 1</li>
  <li class='item'>Item 2</li>
  <li class='item'>Item 3</li>
</ul>

完整代碼可見 element.js敌蚜。

4.2 步驟二：比較兩棵虛擬DOM樹的差異

正如你所預料的桥滨，比較兩棵DOM樹的差異是 Virtual DOM 算法最核心的部分，這也是所謂的 Virtual DOM 的 diff 算法弛车。兩個樹的完全的 diff 算法是一個時間復雜度為 O(n^3) 的問題齐媒。但是在前端當中，你很少會跨越層級地移動DOM元素纷跛。所以 Virtual DOM 只會對同一個層級的元素進行對比：

compare-in-level

上面的div只會和同一層級的div對比喻括，第二層級的只會跟第二層級對比。這樣算法復雜度就可以達到 O(n)贫奠。

4.2.1 深度優(yōu)先遍歷唬血，記錄差異

在實際的代碼中望蜡，會對新舊兩棵樹進行一個深度優(yōu)先的遍歷，這樣每個節(jié)點都會有一個唯一的標記：

dfs-walk

在深度優(yōu)先遍歷的時候拷恨，每遍歷到一個節(jié)點就把該節(jié)點和新的的樹進行對比脖律。如果有差異的話就記錄到一個對象里面。

// diff 函數(shù)腕侄，對比兩棵樹
function diff (oldTree, newTree) {
  var index = 0 // 當前節(jié)點的標志
  var patches = {} // 用來記錄每個節(jié)點差異的對象
  dfsWalk(oldTree, newTree, index, patches)
  return patches
}

// 對兩棵樹進行深度優(yōu)先遍歷
function dfsWalk (oldNode, newNode, index, patches) {
  // 對比oldNode和newNode的不同小泉，記錄下來
  patches[index] = [...]

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

// 遍歷子節(jié)點
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) // 計算節(jié)點的標識
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節(jié)點
    leftNode = child
  })
}

例如，上面的div和新的div有差異冕杠，當前的標記是0微姊，那么：

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

同理p是patches[1]，ul是patches[3]分预，類推兢交。

4.2.2 差異類型

上面說的節(jié)點的差異指的是什么呢？對 DOM 操作可能會：

1. 替換掉原來的節(jié)點笼痹，例如把上面的div換成了section
2. 移動配喳、刪除、新增子節(jié)點与倡，例如上面div的子節(jié)點界逛，把p和ul順序互換
3. 修改了節(jié)點的屬性
4. 對于文本節(jié)點昆稿，文本內容可能會改變纺座。例如修改上面的文本節(jié)點2內容為Virtual DOM 2。

所以我們定義了幾種差異類型：

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

對于節(jié)點替換溉潭，很簡單净响。判斷新舊節(jié)點的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é)點畏陕，如上面的文本節(jié)點2配乓，就記錄下：

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

那如果把我div的子節(jié)點重新排序呢？例如p, ul, div的順序換成了div, p, ul惠毁。這個該怎么對比犹芹？如果按照同層級進行順序對比的話，它們都會被替換掉鞠绰。如p和div的tagName不同腰埂，p會被div所替代。最終蜈膨，三個節(jié)點都會被替換屿笼，這樣DOM開銷就非常大牺荠。而實際上是不需要替換節(jié)點，而只需要經(jīng)過節(jié)點移動就可以達到驴一，我們只需知道怎么進行移動休雌。

這牽涉到兩個列表的對比算法，需要另外起一個小節(jié)來討論肝断。

4.2.3 列表對比算法

假設現(xiàn)在可以英文字母唯一地標識每一個子節(jié)點：

舊的節(jié)點順序：

a b c d e f g h i

現(xiàn)在對節(jié)點進行了刪除挑辆、插入、移動的操作孝情。新增j節(jié)點鱼蝉，刪除e節(jié)點，移動h節(jié)點：

新的節(jié)點順序：

a b c h d f g i j

現(xiàn)在知道了新舊的順序箫荡，求最小的插入魁亦、刪除操作（移動可以看成是刪除和插入操作的結合）。這個問題抽象出來其實是字符串的最小編輯距離問題（Edition Distance）羔挡，最常見的解決算法是 Levenshtein Distance洁奈，通過動態(tài)規(guī)劃求解，時間復雜度為 O(M * N)绞灼。但是我們并不需要真的達到最小的操作利术，我們只需要優(yōu)化一些比較常見的移動情況，犧牲一定DOM操作低矮，讓算法時間復雜度達到線性的（O(max(M, N))印叁。具體算法細節(jié)比較多，這里不累述军掂，有興趣可以參考代碼轮蜕。

我們能夠獲取到某個父節(jié)點的子節(jié)點的操作，就可以記錄下來：

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

但是要注意的是蝗锥，因為tagName是可重復的跃洛，不能用這個來進行對比。所以需要給子節(jié)點加上唯一標識key终议，列表對比的時候汇竭，使用key進行對比，這樣才能復用老的 DOM 樹上的節(jié)點穴张。

這樣细燎，我們就可以通過深度優(yōu)先遍歷兩棵樹，每層的節(jié)點進行對比陆馁，記錄下每個節(jié)點的差異了找颓。完整 diff 算法代碼可見 diff.js。

4.3 步驟三：把差異應用到真正的DOM樹上

因為步驟一所構建的 JavaScript 對象樹和render出來真正的DOM樹的信息叮贩、結構是一樣的击狮。所以我們可以對那棵DOM樹也進行深度優(yōu)先的遍歷佛析，遍歷的時候從步驟二生成的patches對象中找出當前遍歷的節(jié)點差異，然后進行 DOM 操作彪蓬。

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

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

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

  if (currentPatches) {
    applyPatches(node, currentPatches) // 對當前節(jié)點進行DOM操作
  }
}

applyPatches寸莫，根據(jù)不同類型的差異對當前節(jié)點進行 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.js。

5 結語

Virtual DOM 算法主要是實現(xiàn)上面步驟的三個函數(shù)：element档冬，diff膘茎，patch。然后就可以實際的進行使用：

// 1\. 構建虛擬DOM
var tree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: blue'}, ['simple virtal dom']),
    el('p', ['Hello, virtual-dom']),
    el('ul', [el('li')])
])

// 2\. 通過虛擬DOM構建真正的DOM
var root = tree.render()
document.body.appendChild(root)

// 3\. 生成新的虛擬DOM
var newTree = el('div', {'id': 'container'}, [
    el('h1', {style: 'color: red'}, ['simple virtal dom']),
    el('p', ['Hello, virtual-dom']),
    el('ul', [el('li'), el('li')])
])

// 4\. 比較兩棵虛擬DOM樹的不同
var patches = diff(tree, newTree)

// 5\. 在真正的DOM元素上應用變更
patch(root, patches)

當然這是非常粗糙的實踐酷誓，實際中還需要處理事件監(jiān)聽等披坏；生成虛擬 DOM 的時候也可以加入 JSX 語法。這些事情都做了的話盐数，就可以構造一個簡單的ReactJS了棒拂。

本文所實現(xiàn)的完整代碼存放在 Github，僅供學習玫氢。