React虚拟DOM和Diff算法解析

前言

React 中最值得称道的部分莫过于 Virtual DOM 与 diff 的完美结合,特别是其高效的 diff 算法,让用户可以无需顾忌性能问题而”任性自由”的刷新页面,让开发者也可以无需关心 Virtual DOM 背后的运作原理,因为 React diff 会帮助我们计算出 Virtual DOM 中真正变化的部分,并只针对该部分进行实际 DOM 操作,而非重新渲染整个页面,从而保证了每次操作更新后页面的高效渲染,因此 Virtual DOM 与 diff 是保证 React 性能口碑的幕后推手。

行文至此,可能会有读者质疑:React 无非就是引入 diff 这一概念,且 diff 算法也并非其首创,何必吹嘘的如此天花乱坠呢?

其实,正是因为 diff 算法的普识度高,就更应该认可 React 针对 diff 算法优化所做的努力与贡献,更能体现 React 开发者们的魅力与智慧!

传统 diff 算法

计算一棵树形结构转换成另一棵树形结构的最少操作,是一个复杂且值得研究的问题。传统 diff 算法通过循环递归对节点进行依次对比,效率低下,算法复杂度达到 O(n^3),其中 n 是树中节点的总数。O(n^3) 到底有多可怕,这意味着如果要展示1000个节点,就要依次执行上十亿次的比较。这种指数型的性能消耗对于前端渲染场景来说代价太高了!现今的 CPU 每秒钟能执行大约30亿条指令,即便是最高效的实现,也不可能在一秒内计算出差异情况。

如果 React 只是单纯的引入 diff 算法而没有任何的优化改进,那么其效率是远远无法满足前端渲染所要求的性能。

因此,想要将 diff 思想引入 Virtual DOM,就需要设计一种稳定高效的 diff 算法,而 React 做到了!

那么,React diff 到底是如何实现的呢?


React Diff算法以及虚拟DOM解析

1. 虚拟DOM

1.1用JS对象模拟DOM树

用 JavaScript 来表示一个 DOM 节点是很简单的事情,你只需要记录它的节点类型、属性,还有子节点:

1
2
3
4
5
6
7
8
9
10
// a.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 结构就可以简单的表示:

1
2
3
4
5
6
7
var el = require('./a.js')

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

现在ul只是一个 JavaScript 对象表示的 DOM 结构,页面上并没有这个结构。我们可以根据这个ul构建真正的<ul>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Element.prototype.render = function () {
var el = document.createElement(this.tagName) // 根据tagName构建
var props = this.props

for (var propName in props) { // 设置节点的DOM属性
var propValue = props[propName]
el.setAttribute(propName, propValue)
}

var children = this.children || []

children.forEach(function (child) {
var childEl = (child instanceof Element)
? child.render() // 如果子节点也是虚拟DOM,递归构建DOM节点
: document.createTextNode(child) // 如果字符串,只构建文本节点
el.appendChild(childEl)
})

return el
}

render方法会根据tagName构建一个真正的DOM节点,然后设置这个节点的属性,最后递归地把自己的子节点也构建起来。所以只需要:

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

上面的ulRoot是真正的DOM节点,把它塞入文档中,这样body里面就有了真正的<ul>的DOM结构:

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

2. diff 策略

传统 diff 算法的复杂度为 O(n^3),显然这是无法满足性能要求的。React 通过制定大胆的策略,将 O(n^3) 复杂度的问题转换成 O(n) 复杂度的问题。

  1. Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计。

  2. 拥有相同类的两个组件将会生成相似的树形结构,拥有不同类的两个组件将会生成不同的树形结构。

  3. 对于同一层级的一组子节点,它们可以通过唯一 id 进行区分。

这里写图片描述

简单来说就是上面的div只会和同一层级的div对比,第二层级的只会跟第二层级对比。这样算法复杂度就可以达到 O(n)。

2.1 深度优先遍历,记录差异

在实际的代码中,会对新旧两棵树进行一个深度优先的遍历,这样每个节点都会有一个唯一的标记:

这里写图片描述

在深度优先遍历的时候,每遍历到一个节点就把该节点和新的的树进行对比。如果有差异的话就记录到一个对象里面。

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
// diff 函数,对比两棵树
function diff (oldTree, newTree) {
var index = 0 // 当前节点的标志
var 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) {
var leftNode = null
var currentNodeIndex = index
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i]
currentNodeIndex = (leftNode && leftNode.count) // 计算节点的标识
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1
dfsWalk(child, newChild, currentNodeIndex, patches) // 深度遍历子节点
leftNode = child
})
}

例如,上面的div和新的div有差异,当前的标记是0,那么:

1
patches[0] = [{difference}, {difference}, ...] // 用数组存储新旧节点的不同

同理p是patches[1],ul是patches[3],类推。

2.2 差异类型

上面说的节点的差异指的是什么呢?
对 DOM 操作可能会:

  1. 替换掉原来的节点,例如把上面的div换成了section
  2. 移动、删除、新增子节点,例如上面div的子节点,把p和ul顺序互换
  3. 修改了节点的属性
  4. 对于文本节点,文本内容可能会改变。例如修改上面的文本节点2内容为Virtual DOM 2。

所以我们定义了几种差异类型:

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

对于节点替换,很简单。判断新旧节点的tagName和是不是一样的,如果不一样的说明需要替换掉。如div换成section,就记录下:

1
2
3
4
patches[0] = [{
type: REPALCE,
node: newNode // el('section', props, children)
}]

如果给div新增了属性id为container,就记录下:

1
2
3
4
5
6
7
8
9
patches[0] = [{
type: REPALCE,
node: newNode // el('section', props, children)
}, {
type: PROPS,
props: {
id: "container"
}
}]

如果是文本节点,如上面的文本节点2,就记录下:

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

那如果把我div的子节点重新排序呢?例如p, ul, div的顺序换成了div, p, ul。这个该怎么对比?如果按照同层级进行顺序对比的话,它们都会被替换掉。如p和div的tagName不同,p会被div所替代。最终,三个节点都会被替换,这样DOM开销就非常大。而实际上是不需要替换节点,而只需要经过节点移动就可以达到,我们只需知道怎么进行移动。

2.3 列表对比算法

例子:

这里写图片描述

新老集合所包含的节点,如上图图所示,新老集合进行 diff 差异化对比,通过 key 发现新老集合中的节点都是相同的节点,因此无需进行节点删除和创建,只需要将老集合中节点的位置进行移动,更新为新集合中节点的位置,此时 React 给出的 diff 结果为:B、D 不做任何操作,A、C 进行移动操作,即可。

那么,如此高效的 diff 到底是如何运作的呢?让我们通过源码进行详细分析。

首先对新集合的节点进行循环遍历,for (name in nextChildren),通过唯一 key 可以判断新老集合中是否存在相同的节点,if (prevChild === nextChild),如果存在相同节点,则进行移动操作,但在移动前需要将当前节点在老集合中的位置与 lastIndex 进行比较,if (child._mountIndex < lastIndex),则进行节点移动操作,否则不执行该操作。这是一种顺序优化手段,lastIndex 一直在更新,表示访问过的节点在老集合中最右的位置(即最大的位置),如果新集合中当前访问的节点比 lastIndex 大,说明当前访问节点在老集合中就比上一个节点位置靠后,则该节点不会影响其他节点的位置,因此不用添加到差异队列中,即不执行移动操作,只有当访问的节点比 lastIndex 小时,才需要进行移动操作。

以上图为例,可以更为清晰直观的描述 diff 的差异对比过程:

  • 从新集合中取得 B,判断老集合中存在相同节点 B,通过对比节点位置判断是否进行移动操作,B 在老集合中的位置 B._mountIndex = 1,此时 lastIndex = 0,不满足 child._mountIndex < lastIndex 的条件,因此不对 B 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),其中 prevChild._mountIndex 表示 B 在老集合中的位置,则 lastIndex = 1,并将 B 的位置更新为新集合中的位置prevChild._mountIndex = nextIndex,此时新集合中 B._mountIndex = 0,nextIndex++ 进入下一个节点的判断。
  • 从新集合中取得 A,判断老集合中存在相同节点 A,通过对比节点位置判断是否进行移动操作,A 在老集合中的位置 A._mountIndex = 0,此时 lastIndex = 1,满足 child._mountIndex < lastIndex的条件,因此对 A 进行移动操作enqueueMove(this, child._mountIndex, toIndex),其中 toIndex 其实就是 nextIndex,表示 A 需要移动到的位置;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 1,并将 A 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中A._mountIndex = 1nextIndex++ 进入下一个节点的判断。
  • 从新集合中取得 D,判断老集合中存在相同节点 D,通过对比节点位置判断是否进行移动操作,D 在老集合中的位置 D._mountIndex = 3,此时 lastIndex = 1,不满足 child._mountIndex < lastIndex的条件,因此不对 D 进行移动操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 D 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中D._mountIndex = 2nextIndex++ 进入下一个节点的判断。
  • 从新集合中取得 C,判断老集合中存在相同节点 C,通过对比节点位置判断是否进行移动操作,C 在老集合中的位置 C._mountIndex = 2,此时 lastIndex = 3,满足 child._mountIndex < lastIndex 的条件,因此对 C 进行移动操作 enqueueMove(this, child._mountIndex, toIndex);更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),则 lastIndex = 3,并将 C 的位置更新为新集合中的位置 prevChild._mountIndex = nextIndex,此时新集合中 C._mountIndex = 3nextIndex++ 进入下一个节点的判断,由于 C 已经是最后一个节点,因此 diff 到此完成。

以上主要分析新老集合中存在相同节点但位置不同时,对节点进行位置移动的情况,如果新集合中有新加入的节点且老集合存在需要删除的节点,那么 React diff 又是如何对比运作的呢?

这里写图片描述

B,E,C,A和上面的步骤一样, 只不过当完成新集合中所有节点 diff 时,最后还需要对老集合进行循环遍历,判断是否存在新集合中没有但老集合中仍存在的节点,发现存在这样的节点 D,因此删除节点 D,到此 diff 全部完成。

2.3 把差异应用到真正的DOM树上

因为1.1虚拟dom那一小节所构建的 JavaScript 对象树和render出来真正的DOM树的信息、结构是一样的。所以我们可以对那棵DOM树也进行深度优先的遍历,遍历的时候从2.1 深度优先遍历,记录差异那一节生成的patches对象中找出当前遍历的节点差异,然后进行 DOM 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function patch (node, patches) {
var walker = {index: 0}
dfsWalk(node, walker, patches)
}

function dfsWalk (node, walker, patches) {
var currentPatches = patches[walker.index] // 从patches拿出当前节点的差异

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

if (currentPatches) {
applyPatches(node, currentPatches) // 对当前节点进行DOM操作
}
}

applyPatches,根据不同类型的差异对当前节点进行 DOM 操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 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)

当然这是非常粗糙的实践,实际中还需要处理事件监听等;生成虚拟 DOM 的时候也可以加入 JSX 语法。这些事情都做了的话,就可以构造一个简单的ReactJS了。

参考链接:
https://www.zhihu.com/question/29504639
https://zhuanlan.zhihu.com/p/20346379

越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!