为什么需要 Virtual Dom

众所周知，操作 DOM 是很耗费性能的一件事情，既然如此，我们可以考虑通过 JS 对象来模拟 DOM 对象，毕竟操作 JS 对象比操作 DOM 省时的多。

举个例子

1 2 3 4

// 假设这里模拟一个 ul，其中包含了 5 个 li [1, 2, 3, 4, 5] // 这里替换上面的 li [1, 2, 5, 4]

 

从上述例子中，我们一眼就可以看出先前的 ul 中的第三个 li 被移除了，四五替换了位置。

如果以上操作对应到 DOM 中，那么就是以下代码

1 2 3 4 5 6 7 8 9

// 删除第三个 li ul.childNodes[2].remove() // 将第四个 li 和第五个交换位置 var fromNode = ul.childNodes[4] var toNode = node.childNodes[3] var cloneFromNode = fromNode.cloneNode(true) var cloenToNode = toNode.cloneNode(true) ul.replaceChild(cloneFromNode, toNode) ul.replaceChild(cloenToNode, fromNode)

 

当然在实际操作中，我们还需要给每个节点一个标识，作为判断是同一个节点的依据。所以这也是 Vue 和 React 中官方推荐列表里的节点使用唯一的 key 来保证性能。

那么既然 DOM 对象可以通过 JS 对象来模拟，反之也可以通过 JS 对象来渲染出对应的 DOM

以下是一个 JS 对象模拟 DOM 对象的简单实现

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

export default class Element { /** * @param {String} tag 'div' * @param {Object} props { class: 'item' } * @param {Array} children [ Element1, 'text'] * @param {String} key option */ constructor(tag, props, children, key) { this.tag = tag this.props = props if (Array.isArray(children)) { this.children = children } else if (isString(children)) { this.key = children this.children = null } if (key) this.key = key } // 渲染 render() { var root = this._createElement( this.tag, this.props, this.children, this.key ) document.body.appendChild(root) return root } create() { return this._createElement(this.tag, this.props, this.children, this.key) } // 创建节点 _createElement(tag, props, child, key) { // 通过 tag 创建节点 var el = document.createElement(tag) // 设置节点属性 for (const key in props) { if (props.hasOwnProperty(key)) { const value = props[key] el.setAttribute(key, value) } } if (key) { el.setAttribute('key', key) } // 递归添加子节点 if (child) { child.forEach(element => { var child if (element instanceof Element) { child = this._createElement( element.tag, element.props, element.children, element.key ) } else { child = document.createTextNode(element) } el.appendChild(child) }) } return el } }

Virtual Dom 算法简述

既然我们已经通过 JS 来模拟实现了 DOM，那么接下来的难点就在于如何判断旧的对象和新的对象之间的差异。

DOM 是多叉树的结构，如果需要完整的对比两颗树的差异，那么需要的时间复杂度会是 O(n ^ 3)，这个复杂度肯定是不能接受的。于是 React 团队优化了算法，实现了 O(n) 的复杂度来对比差异。

实现 O(n) 复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动 DOM 元素。

所以判断差异的算法就分为了两步

• 首先从上至下，从左往右遍历对象，也就是树的深度遍历，这一步中会给每个节点添加索引，便于最后渲染差异
• 一旦节点有子元素，就去判断子元素是否有不同

Virtual Dom 算法实现

树的递归

首先我们来实现树的递归算法，在实现该算法前，先来考虑下两个节点对比会有几种情况

1. 新的节点的 tagName 或者 key 和旧的不同，这种情况代表需要替换旧的节点，并且也不再需要遍历新旧节点的子元素了，因为整个旧节点都被删掉了
2. 新的节点的 tagName 和 key（可能都没有）和旧的相同，开始遍历子树
3. 没有新的节点，那么什么都不用做

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import { StateEnums, isString, move } from './util' import Element from './element' export default function diff(oldDomTree, newDomTree) { // 用于记录差异 var pathchs = {} // 一开始的索引为 0 dfs(oldDomTree, newDomTree, 0, pathchs) return pathchs } function dfs(oldNode, newNode, index, patches) { // 用于保存子树的更改 var curPatches = [] // 需要判断三种情况 // 1.没有新的节点，那么什么都不用做 // 2.新的节点的 tagName 和 `key` 和旧的不同，就替换 // 3.新的节点的 tagName 和 key（可能都没有） 和旧的相同，开始遍历子树 if (!newNode) { } else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) { // 判断属性是否变更 var props = diffProps(oldNode.props, newNode.props) if (props.length) curPatches.push({ type: StateEnums.ChangeProps, props }) // 遍历子树 diffChildren(oldNode.children, newNode.children, index, patches) } else { // 节点不同，需要替换 curPatches.push({ type: StateEnums.Replace, node: newNode }) } if (curPatches.length) { if (patches[index]) { patches[index] = patches[index].concat(curPatches) } else { patches[index] = curPatches } } }

判断属性的更改

判断属性的更改也分三个步骤

1. 遍历旧的属性列表，查看每个属性是否还存在于新的属性列表中
2. 遍历新的属性列表，判断两个列表中都存在的属性的值是否有变化
3. 在第二步中同时查看是否有属性不存在与旧的属性列列表中

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

function diffProps(oldProps, newProps) { // 判断 Props 分以下三步骤 // 先遍历 oldProps 查看是否存在删除的属性 // 然后遍历 newProps 查看是否有属性值被修改 // 最后查看是否有属性新增 var change = [] for (const key in oldProps) { if (oldProps.hasOwnProperty(key) && !newProps[key]) { change.push({ prop: key }) } } for (const key in newProps) { if (newProps.hasOwnProperty(key)) { const prop = newProps[key] if (oldProps[key] && oldProps[key] !== newProps[key]) { change.push({ prop: key, value: newProps[key] }) } else if (!oldProps[key]) { change.push({ prop: key, value: newProps[key] }) } } } return change }

判断列表差异算法实现

这个算法是整个 Virtual Dom 中最核心的算法，且让我一一为你道来。

这里的主要步骤其实和判断属性差异是类似的，也是分为三步

1. 遍历旧的节点列表，查看每个节点是否还存在于新的节点列表中
2. 遍历新的节点列表，判断是否有新的节点
3. 在第二步中同时判断节点是否有移动

PS：该算法只对有 key 的节点做处理

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

function listDiff(oldList, newList, index, patches) { // 为了遍历方便，先取出两个 list 的所有 keys var oldKeys = getKeys(oldList) var newKeys = getKeys(newList) var changes = [] // 用于保存变更后的节点数据 // 使用该数组保存有以下好处 // 1.可以正确获得被删除节点索引 // 2.交换节点位置只需要操作一遍 DOM // 3.用于 `diffChildren` 函数中的判断，只需要遍历 // 两个树中都存在的节点，而对于新增或者删除的节点来说，完全没必要 // 再去判断一遍 var list = [] oldList && oldList.forEach(item => { var key = item.key if (isString(item)) { key = item } // 寻找新的 children 中是否含有当前节点 // 没有的话需要删除 var index = newKeys.indexOf(key) if (index === -1) { list.push(null) } else list.push(key) }) // 遍历变更后的数组 var length = list.length // 因为删除数组元素是会更改索引的 // 所有从后往前删可以保证索引不变 for (var i = length - 1; i >= 0; i--) { // 判断当前元素是否为空，为空表示需要删除 if (!list[i]) { list.splice(i, 1) changes.push({ type: StateEnums.Remove, index: i }) } } // 遍历新的 list，判断是否有节点新增或移动 // 同时也对 `list` 做节点新增和移动节点的操作 newList && newList.forEach((item, i) => { var key = item.key if (isString(item)) { key = item } // 寻找旧的 children 中是否含有当前节点 var index = list.indexOf(key) // 没找到代表新节点，需要插入 if (index === -1 || key == null) { changes.push({ type: StateEnums.Insert, node: item, index: i }) list.splice(i, 0, key) } else { // 找到了，需要判断是否需要移动 if (index !== i) { changes.push({ type: StateEnums.Move, from: index, to: i }) move(list, index, i) } } }) return { changes, list } } function getKeys(list) { var keys = [] var text list && list.forEach(item => { var key if (isString(item)) { key = [item] } else if (item instanceof Element) { key = item.key } keys.push(key) }) return keys }

 

遍历子元素打标识

对于这个函数来说，主要功能就两个

1. 判断两个列表差异
2. 给节点打上标记

总体来说，该函数实现的功能很简单

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

function diffChildren(oldChild, newChild, index, patches) { var { changes, list } = listDiff(oldChild, newChild, index, patches) if (changes.length) { if (patches[index]) { patches[index] = patches[index].concat(changes) } else { patches[index] = changes } } // 记录上一个遍历过的节点 var last = null oldChild && oldChild.forEach((item, i) => { var child = item && item.children if (child) { index = last && last.children ? index + last.children.length + 1 : index + 1 var keyIndex = list.indexOf(item.key) var node = newChild[keyIndex] // 只遍历新旧中都存在的节点，其他新增或者删除的没必要遍历 if (node) { dfs(item, node, index, patches) } } else index += 1 last = item }) }

 

渲染差异

通过之前的算法，我们已经可以得出两个树的差异了。既然知道了差异，就需要局部去更新 DOM 了，下面就让我们来看看 Virtual Dom 算法的最后一步骤

这个函数主要两个功能

1. 深度遍历树，将需要做变更操作的取出来
2. 局部更新 DOM

整体来说这部分代码还是很好理解的

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

var index = 0 export default function patch(node, patchs) { var changes = patchs[index] var childNodes = node && node.childNodes // 这里的深度遍历和 diff 中是一样的 if (!childNodes) index += 1 if (changes && changes.length && patchs[index]) { changeDom(node, changes) } var last = null if (childNodes && childNodes.length) { childNodes.forEach((item, i) => { index = last && last.children ? index + last.children.length + 1 : index + 1 patch(item, patchs) last = item }) } } function changeDom(node, changes, noChild) { changes && changes.forEach(change => { var { type } = change switch (type) { case StateEnums.ChangeProps: var { props } = change props.forEach(item => { if (item.value) { node.setAttribute(item.prop, item.value) } else { node.removeAttribute(item.prop) } }) break case StateEnums.Remove: node.childNodes[change.index].remove() break case StateEnums.Insert: var dom if (isString(change.node)) { dom = document.createTextNode(change.node) } else if (change.node instanceof Element) { dom = change.node.create() } node.insertBefore(dom, node.childNodes[change.index]) break case StateEnums.Replace: node.parentNode.replaceChild(change.node.create(), node) break case StateEnums.Move: var fromNode = node.childNodes[change.from] var toNode = node.childNodes[change.to] var cloneFromNode = fromNode.cloneNode(true) var cloenToNode = toNode.cloneNode(true) node.replaceChild(cloneFromNode, toNode) node.replaceChild(cloenToNode, fromNode) break default: break } }) }

 

最后

Virtual Dom 算法的实现也就是以下三步

1. 通过 JS 来模拟创建 DOM 对象
2. 判断两个对象的差异
3. 渲染差异

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

var test4 = new Element('div', { class: 'my-div' }, ['test4']) var test5 = new Element('ul', { class: 'my-div' }, ['test5']) var test1 = new Element('div', { class: 'my-div' }, [test4]) var test2 = new Element('div', { id: '11' }, [test5, test4]) var root = test1.render() var pathchs = diff(test1, test2) console.log(pathchs) setTimeout(() => { console.log('开始更新') patch(root, pathchs) console.log('结束更新') }, 1000)