摘要：但瀏覽器沒這么智能，收到第一個更新請求后，并不知道后續還有次更新操作，因此會馬上執行流程，最終執行次流程。從拿出當前節點的差異深度遍歷子節點對當前節點進行操作，根據不同類型的差異對當前節點進行操作結語算法主要是實現上面步驟的三個函數，，。

大三戰五渣的我，平時也就只能用用別人的輪子，可總用不順心，畢竟不知道原理，最近用vue寫項目，里面涉及到的Virtual DOM雖然已不是什么新概念，但我也只是聽說而已，不知其所以然，既然看到大佬們解析后，那就記錄下吧
參考資料：
戴嘉華：https://github.com/livoras/bl...
張歆琳：https://www.jianshu.com/p/616...
王沛：https://www.infoq.cn/article/...

首先先了解一下加載一個HTML會發生哪些事情

使用HTML分析器生成DOM Tree

使用CSS分析器生成CSSOM

運行JS

結合DOM Tree和CSSOM生成一棵Render Tree

根據render樹，瀏覽器可以計算出網頁中有哪些節點，各節點的CSS以及從屬關系，然后可以計算出每個節點在屏幕中的位置；

繪制出頁面

當你用傳統的源生api或jQuery去操作DOM時，瀏覽器會從構建DOM樹開始從頭到尾執行一遍流程。比如當你在一次操作時，需要更新10個DOM節點，理想狀態是一次性構建完DOM樹，再執行后續操作。但瀏覽器沒這么智能，收到第一個更新DOM請求后，并不知道后續還有9次更新操作，因此會馬上執行流程，最終執行10次流程。顯然例如計算DOM節點的坐標值等都是白白浪費性能，可能這次計算完，緊接著的下一個DOM更新請求，這個節點的坐標值就變了，前面的一次計算是無用功。
DOM是很慢的，我們可以打印一下一個簡單的div元素的屬性

這還只是一層而已，真實的DOM會更加龐大，輕微的觸碰可能就會導致頁面重排，這可是殺死性能的罪魁禍首。而相對于操作DOM對象，原生的JS對象處理起來更快而且簡單

JS表示DOM→構建DOM樹→插圖文檔中

狀態變化→重新構造一顆新的對象樹→新舊樹比較→記錄兩棵樹的差異

把2所記錄的差異應用到步驟1所構建的真正的DOM樹上，從而視圖更新了

在 JS 和 DOM 之間做了一個緩存。可以類比 CPU 和硬盤，既然硬盤這么慢，我們就在它們之間加個緩存：既然 DOM 這么慢，我們就在它們 JS 和 DOM 之間加個緩存。CPU（JS）只操作內存（Virtual DOM），最后的時候再把變更寫入硬盤（DOM）。

用JS記錄節點的類型，屬性和子節點
element.js

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

function el(tagName, props, children){
  return new Element(tagName, props, children)
}

例如上面的 DOM 結構就可以簡單的表示：

let el = require("./element")

let div= el("div", {id: "blue-div"}, [
  el("p", {class: "pink-p"}, [
    el("span", {class: "yellow-sapn"}, ["Virtual sapn"])]),
  el("ul", {class: "green-ul"}, [
    el("li", {class: "red-li"}, ["Virtual li1"]),
    el("li", {class: "red-li"}, ["Virtual li2"]),
    el("li", {class: "red-li"}, ["Virtual li3"])]),
  el("div", {class: "black-div"}, ["Virtual div"])
])

現在的div只是一個JS對象表示的DOM結構，頁面上并沒有這個結構，下面用來構建真正的div

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

    for (let propName in props) { // 設置節點的DOM屬性
        let propValue = props[propName]
        el.setAttribute(propName, propValue)
    }

    let children = this.children || []
    children.forEach(function (child) {
        let childEl = (child instanceof Element)
        ? child.render() // 如果子節點也是虛擬DOM，遞歸構建DOM節點
        : document.createTextNode(child) // 如果字符串，只構建文本節點
        el.appendChild(childEl)
    })
      return el
}

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

let divRoot = div.render()
document.body.appendChild(divRoot)

上面的運行結果:

兩棵樹的完全差異比較的時間復雜度為O(n^3)，這是不好的，又因為前端不會經常進行跨層地移動DOM元素，所以Virtual DOM只對同一層級的元素進行比較，從而時間復雜度降為O(n)

在實際的代碼中，會對新舊兩棵樹進行一個深度優先的遍歷，這樣每個節點都會有一個唯一的標記，在深度優先遍歷的時候，每遍歷到一個節點就把改節點和新的數進行對比，如果有差異就記錄到patches中

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

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

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

// 遍歷子節點
function diffChildren (oldChildren, newChildren, index, patches) {
  let leftNode = null
  let currentNodeIndex = index
  oldChildren.forEach(function (child, i) {
    let newChild = newChildren[i]
    currentNodeIndex = (leftNode && leftNode.count) // 計算節點的標識
      ? currentNodeIndex + leftNode.count + 1
      : currentNodeIndex + 1
    dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍歷子節點
    leftNode = child
  })
}

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

patches[0] = [{difference}, {difference}, ...] // 用數組存儲新舊節點的不同

上面出現了四種新舊樹不同的情況：

REPLACE：節點類型變了，p變成了div，將舊節點卸載并裝載新節點

PROPS：不觸發節點的卸載和裝載，執行節點的更新

TEXT：修改文本內容

REORDER：移動、增加（多了li）、刪除節點，實際操作如圖：

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

let REPLACE = 0
patches[0] = [{
  type: REPALCE,
  node: newNode // el("div", props, children)  p換成div
}]

let PROPS = 1
patches[0] = [{
  type: REPALCE,
  node: newNode // el("p", props, children)
}, {
  type: PROPS,
  props: {//給p新增了id為container
    id: "container"
  }
}]

let TEXT = 2
patches[1] = [{//修改文本節點
  type: TEXT,
  content: "Virtual DOM2"
}]

let REORDER = 3  //重排見王沛的https://www.infoq.cn/article/react-dom-diff

最終Diff出來的結果類型如下：

{
    1: [ {type: REPLACE, node: Element} ],
    4: [ {type: TEXT, content: "after update"} ],
    5: [ {type: PROPS, props: {class: "marginLeft10"}}, {type: REORDER, moves: [{index: 2, type: 0}]} ],
    6: [ {type: REORDER, moves: [{index: 2, type: 0}]} ],
    8: [ {type: REORDER, moves: [{index: 2, type: 0}]} ],
    9: [ {type: TEXT, content: "Item 3"} ],
}

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

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

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

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

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

applyPatches，根據不同類型的差異對當前節點進行 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)
    }
  })
}

Virtual DOM 算法主要是實現上面步驟的三個函數：element，diff，patch。然后就可以實際的進行使用：

// 1. 構建虛擬DOM
let 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
let root = tree.render()
document.body.appendChild(root)

// 3. 生成新的虛擬DOM
let 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樹的不同
let patches = diff(tree, newTree)

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

原理加1，頭發減一堆