共计 5362 个字符，预计需要花费 14 分钟才能阅读完成。
大三战五渣的我，平时也就只能用用别人的轮子，可总用不顺心，毕竟不知道原理，最近用 vue 写项目，里面涉及到的 Virtual DOM 虽然已不是什么新概念，但我也只是听说而已，不知其所以然，既然看到大佬们解析后，那就记录下吧参考资料：戴嘉华：https://github.com/livoras/bl… 张歆琳：https://www.jianshu.com/p/616… 王沛：https://www.infoq.cn/article/…
为啥要 Virtual DOM
首先先了解一下加载一个 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 树上，从而视图更新了
Virtual DOM 的本质
在 JS 和 DOM 之间做了一个缓存。可以类比 CPU 和硬盘，既然硬盘这么慢，我们就在它们之间加个缓存：既然 DOM 这么慢，我们就在它们 JS 和 DOM 之间加个缓存。CPU（JS）只操作内存（Virtual DOM），最后的时候再把变更写入硬盘（DOM）。
算法实现
步骤一：用 JS 对象模拟 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)
上面的运行结果:
步骤二：比较两棵虚拟 DOM 树的差异 (diff 算法)
两棵树的完全差异比较的时间复杂度为 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”} ],
}
步骤三：把差异应用到真正的 DOM 树上
因为步骤一所构建的 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，头发减一堆