虚拟DOM和diff算法
虚拟DOM和diff算法
面试中我们经常会考到 虚拟 DOM 和 diff 算法，这涉及到 Vue 作为一个声明式的框架如何进行 DOM 挂载和更新，是非常重要的知识点。
声明式框架和命令式框架的比较
在深度介绍 虚拟DOM 和 diff 算法之前，我们怎么也得先讲一下为什么 Vue 要选择声明式框架，然后 虚拟DOM 在声明式框架中有什么作用。
首先，什么是命令式框架呢，早年间的jQuery就是，举个简单例子大家看一下。
// jquery
$('#app') // 获取 div
.text('hello world') // 设置文本内容
.on('click', () => { alert('ok') }) // 绑定点击事件
// 原生js
const div = document.querySelector('#app') // 获取 div
div.innerText = 'hello world' // 设置文本内容
div.addEventListener('click', () => { alert('ok') }) // 绑定点击事 件大家可以发现，命令式框架注重过程，通过上述的代码我们可以很明显的看出自然语言和代码一一对应的关系。
那么，什么是声明式框架呢?与命令式框架更加关注过程不同，声明式框架更加注重结果。结合 Vue.js，我们来看看如何实现上面自然语言描述的功能:
<div @click="() => alert('ok')">hello world</div>这段类 HTML 的模板就是 Vue.js 实现如上功能的方式。可以看到，我们提供的是一个“结果”，至于如何实现这个“结果”，我们并不关心，至于怎么实现这个结果，肯定是由 Vue 帮我们封装了，所以我们可以知道 Vue 内部实现一定是命令式，而暴露给我们的却是声明式。
命令式和声明式框架各有优缺点，我们这里着重讲的话就是体现在性能和可维护性上。
拿上面的代码来说，如果我们要将 div 标签文本修改为 "hello,world!"，我们该怎么做呢，很简单：
div.textContent = 'hello world!' // 设置文本内容现在思考一下，还有没有其他办法比上面这句代码的性能更好? 答案是“没有”。可以看到，理论上命令式代码可以做到极致的性能优 化，因为我们明确知道哪些发生了变更，只做必要的修改就行了。但 是声明式代码不一定能做到这一点，因为它描述的是结果:
<!-- 之前: -->
<div @click="() => alert('ok')">hello world</div>
<!-- 之后: -->
<div @click="() => alert('ok')">hello Vue3</div>对于框架来说，为了实现最优的更新性能，它需要找到前后的差异并只更新变化的地方，（ 这个过程就是通过 diff 算法找到 虚拟DOM 不同并更新 ）但是最终完成这次更新的代码仍然是:
div.textContent = 'hello world!' // 设置文本内容如果我们把直接修改的性能消耗定义为 A，把找出差异的性能消耗定义为 B，那么有:
- 命令式代码的更新性能消耗 = A
- 声明式代码的更新性能消耗 = B + A
可以看到，声明式代码会比命令式代码多出找出差异的性能消耗，因此最理想的情况是，当找出差异的性能消耗为 0 时，这时候命令式代码和声明式代码性能消耗才会相同，所以我们可以得出结论：声明式代码的性能不优于命令式代码。
那么为什么 Vue.js 要选择声明式的设计方案呢？原因就在于声明式代码的可维护性更强。从上面例子的代码中我们也可以感受到，在采用命令式代码开发的时候，我们需要维护实现目标的整个过程，包括要手动完成 DOM 元素的创建、更新和删除等。而声明式代码展示等就是我们的要的结果至于怎么实现，我们并不关心。
通过上面的介绍，我们就知道，为了提高声明式代码的效率，我们就要减少找出差异的性能消耗，虚拟DOM 就是为了最小化这个过程的性能消耗，当然 虚拟DOM 理论上不可能比原生的性能更好。不过请注意，是“理论上”，为什么呢？当业务复杂时，因为我们很难写出极致优化的代码逻辑，就算写出了，也一定投入了大量的精力成本。虚拟DOM 就可以帮助我们在不耗费太多努力，也能保证程序的性能下限。
最后，在结束介绍时候，我们再做一个比较，使用 innerHTML 操作页面和虚拟 DOM 相比性能如何？innerHTML 和 document.createElement 等 DOM 操作方法有何差异。
先来看第一个问题，为了比较 innerHTML 和虚拟 DOM 的性能，我们需要了解它们创建、更新页面的过程。对于 innerHTML 来说， 为了创建页面，我们需要构造一段 HTML 字符串:
const html = `
<div><span>...</span></div>
`接着将该字符串赋值给 DOM 元素的 innerHTML 属性:
div.innerHTML = html然而这句话远没有看上去那么简单。为了渲染出页面，首先要把 字符串解析成 DOM 树，这是一个 DOM 层面的计算。我们知道，涉及 DOM 的运算要远比 JavaScript 层面的计算性能差，这有一个跑分结果 可供参考，如图所示。
在图中，上边是纯 JavaScript 层面的计算，循环 10 000 次，每次创建一个 JavaScript 对象并将其添加到数组中；下边是 DOM 操作，每次创建一个 DOM 元素并将其添加到页面中。跑分结果显示，纯 JavaScript 层面的操作要比 DOM 操作快得多，它们不在一个数量级 上。基于这个背景，我们可以用一个公式来表达通过 innerHTML 创建页面的性能: HTML字符串拼接计算量 + innerHTML 的DOM计算量。
接下来，我们讨论虚拟 DOM 在创建页面时的性能。虚拟 DOM 创建页面的过程分为两步:第一步是创建 JavaScript 对象，这个对象可以理解为真实 DOM 的描述;第二步是递归地遍历虚拟 DOM 树并创建真实 DOM。我们同样可以用一个公式来表达: JavaScript对象的计算量 + 创建真实 DOM 的计算量。
可以看到，无论是纯 JavaScript 层面的计算，还是 DOM 层面的计 算，其实两者差距不大。这里我们从宏观的角度只看数量级上的差 异。如果在同一个数量级，则认为没有差异。在创建页面的时候，都 需要新建所有 DOM 元素。
刚刚我们讨论了创建页面时的性能情况，大家可能会觉得虚拟 DOM 相比 innerHTML 没有优势可言，甚至细究的话性能可能会更差（ 构建对象。别着急，接下来我们看看它们在更新页面时的性能。
使用 innerHTML 更新界面时是全量更新，需要重新设置 innerHTML 的属性，而重新设置的代价就是销毁旧的，新建新的，而 虚拟DOM 只需要比较差异，做必要的操作。
当更新页面时，影响 虚拟DOM 的性能因素与影响 innerHTML 的性能因素不同。对于 虚拟DOM来说，无论页面多大，都只会更新变化的内容，而对于 innerHTML 来说，页面越大，就意味着更新时的性能消耗越大。如果加上性能因素，那么最终它们在更新页面时的性能如图所示。
基于此，我们可以粗略地总结一下 innerHTML、虚拟DOM 以及 原生 JavaScript(指 createElement 等方法)在更新页面时的性能，
Vue 的渲染过程
根据上面我们可以知道 Vue.js 的渲染是基于 虚拟DOM，在具体介绍 虚拟DOM 和 diff 算法之前，我们需要先大致了解一下 Vue 的渲染过程：
- 解析模板：Vue首先会解析模板，并生成一个抽象语法树（AST）。
- 生成渲染函数：Vue根据AST生成一个渲染函数，该函数用于生成Virtual DOM树。
- 执行渲染函数：当组件的状态发生变化时，Vue会重新执行渲染函数，生成一个新的Virtual DOM树。
- 对比新旧Virtual DOM树：Vue会对比新旧Virtual DOM树的差异，找出需要更新的部分。
- 更新DOM：Vue会根据差异更新真实的DOM树
图解如下：
在这图中，把解析模版到生成抽象语法树这个过程我们称之为编译器的工作，把抽象语法树变为 虚拟DOM 并且与真实的 DOM 相关这一步称为渲染器的工作，而 diff 算法就是其更新核心，用于精确地找到 vnode 对象的变更点并且只更新变更的内容。
这里不细究二者的编译器和渲染器的源码，相对比较复杂，后续如果有机会可能会再出文章细讲，这里只需要知道两个的作用就好，一个是将我们 Vue 的 template 中的内容变为抽象语法树，另一个是将抽象语法树生成 虚拟DOM 并与真实的 DOM 相关联，并且比较新旧 DOM 区别来更新。
虚拟DOM
根据上面的讲解，我相信大家已经对 虚拟DOM 是什么已经有了基本的想法，其实本质就是使用 JavaScript 对象来描述 UI 的方式。
虚拟 DOM 通常用英文 virtual DOM 来表达，有时会简写成 vdom。虚拟 DOM 和真实 DOM 的结构一样，都是由一个个节点组成 的树型结构。所以，我们经常能听到“虚拟节点”这样的词，即 virtual node，有时会简写成 vnode。虚拟 DOM 是树型结构，这棵树中的任 何一个 vnode 节点都可以是一棵子树，因此 vnode 和 vdom 有时可 以替换使用。
举个例子
<div id="app">
<p class="text">hello world!!!</p>
</div>这个用 虚拟DOM 表示就是：
{
tag: 'div',
props: {
id: 'app'
},
chidren: [
{
tag: 'p',
props: {
className: 'text'
},
chidren: [
'hello world!!!'
]
}
]
}看到这，大家就知道 虚拟DOM 其实并没有什么神秘的，这里顺带提一下，其实 Vue.js 3 除了支持使用模板描述 UI 外，还支持使用虚拟 DOM 描述 UI。其实我 们在 Vue.js 组件中手写的渲染函数就是使用虚拟 DOM 来描述 UI 的， 如以下代码所示:
import { h } from 'vue'
export default {
render() {
return h('h1', { onClick: handler }) // 虚拟 DOM
}
}这里的 h 函数本质上就是返回一个 js 对象，如果展开的话，大概就是：
export default {
render() {
return {
tag: 'h1',
props: { onClick: handler }
}
}
}diff算法
按道理来说，介绍 diff 算法怎么也得把源码拿出来解析一下，但是如果要解析源码就不得不讲解把整个渲染器拿出来解析，这又是个很复杂的东西，等后续有时间再做一期专门的讲解，所以我们这边源码不会细究其每个函数的实现方式，只需要了解会出现的方法的大概作用。
diff 算法呢有两次更新，所以我们本篇文章会介绍三种 diff 算法，即：简单 diff 算法，双端 diff 算法和快速 diff 算法，分别对应着React、Vue2、Vue3
下面的diff算法中会出现几个方法和属性，在这里进行罗列，并说明其功能
mount(vnode, parent, [refNode]): 挂载节点，通过 vnode 生成真实的 DOM 节点。parent 为其父级的真实DOM节点，refNode 为真实的 DOM 节点，其父级节点为 parent。如果 refNode 不为空，vnode 生成的DOM节点就会插入到 refNode 之前；如果 refNode 为空，那么 vnode 生成的 DOM 节点就作为最后一个子节点插入到 parent 中
patch(prevNode, nextNode, parent): 可以简单的理解为给当前 DOM 节点进行更新，并且调用diff算法对比自身的子节点;
el代表着真实的DOM
unMount(vnode): 卸载节点，即将 vnode对应的真实 DOM 节点删除。
简单diff算法
核心逻辑
拿新的一组子节点中的节点去旧的一组子节点中寻找可复用的节点（ 通过 key，这也就是为什么不建议用 index 作为 key ）。如果找到了，则记录该节点的位置索引。把这个位置索引称为最大索引 (lastIndex) 。在整个更新过程中，如果一个节点的索引值小于最大索引，则说明该节点对应的真实 DOM 元素需要移动。
实现思路
- 依次遍历新 children，去旧 children 中查找就具有相同 key 的可复用节点。如果找到对应旧节点的索引 `< lastIndex(最大索引)，则说明该节点需要移动，反之更新 lastIndex。
- 若新节点没在旧 children 中找到可复用节点，则在当前新节点的上一个节点之后插入新节点。
- 遍历旧 children，查找是否有不存在新 children 中的节点，如果有则卸载改节点。
实现代码
function reactDiff(prevChildren, nextChildren, parent) {
// 记录索引
let lastIndex = 0
for (let i = 0; i < nextChildren.length; i++) {
let nextChild = nextChildren[i],
find = false; // 用来记录节点是新插入的节点还是旧节点修改
for (let j = 0; j < prevChildren.length; j++) {
let prevChild = prevChildren[j]
if (nextChild.key === prevChild.key) {
find = true
patch(prevChild, nextChild, parent) // 更新节点
if (j < lastIndex) {
// 移动到前一个节点的后面
let refNode = nextChildren[i - 1].el.nextSibling;
parent.insertBefore(nextChild.el, refNode)
} else {
// 不需要移动节点，记录当前位置，与之后的节点进行对比
lastIndex = j
}
break
}
}
if (!find) {
// 如果没有找到，则代表这是新的节点，需要插入新节点
let refNode = i <= 0
? prevChildren[0].el
: nextChildren[i - 1].el.nextSibling
mount(nextChild, parent, refNode); // 挂载新节点
}
}
// 当旧的节点不在新列表中时，我们就将其对应的DOM节点移除。
for (let i = 0; i < prevChildren.length; i++) {
let prevChild = prevChildren[i],
key = prevChild.key,
has = nextChildren.find(item =>` item.key === key);
if (!has) unMount(preChild)
}
}图解
缺点和优化
目前的reactDiff的时间复杂度为O(m*n)，我们可以用空间换时间，把key与index的关系维护成一个Map，从而将时间复杂度降低为O(n)。
根据图解我们可以发现，这种算法下我们需要移动两次 DOM 元素，即：先将 p-1 移动到 p-3 之后，然后再将 p-2 移动到 p-1 之后，完成Diff。但是我们通过观察可以发现，只要将 p-3 移动到 p-1 之前就可以完成Diff
所以接下来我们继续介绍 Vue2 使用的双端 diff 算法
双端diff算法
所谓双端比较就是新列表和旧列表两个列表的头与尾互相对比，在对比的过程中指针会逐渐向内靠拢，直到某一个列表的节点全部遍历过，对比停止。
核心逻辑
在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单 Diff 算法，双端 Diff 算法的优势在于，对于同样的更新场景，执行的DOM 移动操作次数更少。
实现思路
- 首先，双端比较分四个步骤比较，如果找到可复用节点，进行 patch，移动节点。
- 旧的一组子节点中的第一个子节点与新的一组节点中的第一个子节点比较
- 旧的一组子节点中的最后一个子节点与新的一组子节点中的最后一个子节点比较
- 旧的一组子节点中的第一个子节点与新的一组子节点中的最后一个子节点比较
- 旧的一组子节点的最后一个子节点与新的一组子节点中的第一个子节点比较
- 以上对比都不满足，则遍历旧的一组子节点，寻找与 newStartVNode 拥有相同 key 值的元素
- 找到了可复用节点，进行 patch，然后将该节点插入到 oldStartVNode 之前，newStartIdx 索引继续移动
- 未找到可复用节点，创建和挂载新节点
- 循环结束检查索引值情况，处理剩余节点，新增或删除节点
实现代码
function vue2diff(prevChildren, nextChildren, parent) {
// 使用四个指针指向两个列表的头尾
let oldStartIndex = 0,
newStartIndex = 0,
oldEndIndex = prevChildren.length - 1,
newEndIndex = nextChildren.length - 1,
// 分别指向两个列表的头尾节点
oldStartNode = prevChildren[oldStartIndex],
oldEndNode = prevChildren[oldEndIndex],
newStartNode = nextChildren[newStartIndex],
newEndNode = nextChildren[newEndIndex];
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
/*
* 当旧节点已经被处理过，直接跳过到下一个（ 原因下面有讲 ）
*/
if (oldStartNode === undefined) {
oldStartNode = prevChildren[++oldStartIndex]
} else if (oldEndNode === undefined) {
oldEndNode = prevChildren[--oldEndIndex]
} else if (oldStartNode.key === newStartNode.key) {
/*
* 当旧列表的头一个节点 oldStartNode 与新列表的头一个节点 newStartNode 对比时 key 相同。
* 那么对新旧节点进行对比更新
* 旧列表的头指针 oldStartIndex 与新列表的头指针 newStartIndex 同时向后移动一位。
*/
patch(oldStartNode, newStartNode, parent)
oldStartIndex++
newStartIndex++
oldStartNode = prevChildren[oldStartIndex]
newStartNode = nextChildren[newStartIndex]
} else if (oldEndNode.key === newEndNode.key) {
/*
* 当旧列表的最后一个节点 oldEndNode 与新列表的最后一个节点 newEndNode 对比时 key 相同。
* 那么对新旧节点进行对比更新
* 旧列表的尾指针 oldEndIndex 与新列表的尾指针 newEndndex 同时向前移动一位。
*/
patch(oldEndNode, newEndNode, parent)
oldEndIndex--
newEndIndex--
oldEndNode = prevChildren[oldEndIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldStartNode.key === newEndNode.key) {
/*
* 当旧列表的第一个节点 oldStartNode 与新列表的最后一个节点 newEndNode 对比时 key 相同。
* 那么对新旧节点进行对比更新
* 将该节点插入到末尾
* 旧列表的头指针 oldStartIndex 向后移动一位。
* 新列表的尾指针 newEndndex 向前移动一位
*/
patch(oldStartNode, newEndNode, parent)
parent.insertBefore(oldStartNode.el, oldEndNode.el.nextSibling)
oldStartIndex++
newEndIndex--
oldStartNode = prevChildren[oldStartIndex]
newEndNode = nextChildren[newEndIndex]
} else if (oldEndNode.key === newStartNode.key) {
/*
* 当旧列表的最后一个节点 oldEndNode 与新列表的第一个节点 newStartNode 对比时 key 相同。
* 那么对新旧节点进行对比更新
* 将该节点插入到开头
* 旧列表的尾指针 oldEndIndex 向前移动一位。
* 新列表的头指针 newStartndex 向后移动一位
*/
patch(oldEndNode, newStartNode, parent)
parent.insertBefore(oldEndNode.el, oldStartNode.el)
oldEndIndex--
newStartIndex++
oldEndNode = prevChildren[oldEndIndex]
newStartNode = nextChildren[newStartIndex]
} else {
/*
* 当四次比较都没找到时，拿新列表的第一个节点去旧列表中找与其 key 相同的节点。
*/
let newKey = newStartNode.key,
oldIndex = prevChildren.findIndex(child => child && (child.key === newKey));
if (oldIndex === -1) {
/*
* 如果没找到 key 值相同，说明是新建立的节点，直接创建一个新的节点放到最前面就可以了
*/
mount(newStartNode, parent, oldStartNode.el)
} else {
/*
* 如果找到 key 值相同
* 直接进行新旧节点比较更新，并且将其移动到最前面
* 将其设置为 undefined 证明已经被处理过了
*/
let prevNode = prevChildren[oldIndex]
patch(prevNode, newStartNode, parent)
parent.insertBefore(prevNode.el, oldStartNode.el)
prevChildren[oldIndex] = undefined
}
/*
* 无论是否在旧列表中找到，我们都需要将新列表的头指针 newStartndex 向后移动一位，证明处理过了
*/
newStartIndex++
newStartNode = nextChildren[newStartIndex]
}
}
if (newStartIndex > newEndIndex) {
/*
* 如果新列表遍历完了但是旧列表还没遍历完
* 说明旧列表中剩余的节点需要卸载
*/
while (oldStartIndex <= oldStartIndex) {
if (!prevChildren[oldStartIndex]) {
oldStartIndex++
continue
}
unMount(prevChildren[oldStartIndex++].el)
}
} else if (oldStartIndex > oldStartIndex) {
/*
* 如果旧列表遍历完了但是新列表还没遍历完
* 说明新列表中的节点都是新加的，挂载即可
*/
while (newStartIndex `<= newStartIndex) {
mount(nextChildren[newStartIndex++], parent, oldStartNode.el)
}
}
}图解
快速Diff算法 —— 最长递增子序列
Vue3 的 diff 借鉴于inferno，该算法其中有两个理念。第一个是相同的前置与后置元素的预处理；第二个则是最长递增子序列，此思想与 React 的 diff 类似又不尽相同。下面我们来一一介绍。所以其核心流程和思路基本和双端差不多，只是加了预处理和最长递增子序列。
前置与后置的预处理
我们看这两段文字
- TEXT1: I use vue for app development
- TEXT2: I use react for app development
其实就简单的看一眼我们就能发现，这两段文字是有一部分是相同的，这些文字是不需要修改也不需要移动的，真正需要进行修改中间的几个字母。
Vue3 的 diff 算法就是借鉴了上面的文本处理
情况1：新增节点
通过观察可以发现，两组子节点具有相同的前置节点p-1，以及相同的后置节点p-3和p-4。索引j、newEnd和oldEnd之间的关系
- 条件一 j > oldEnd 成立：说明在预处理过程中，所有的旧节点都处理完毕了。
- 条件二 j `<= newEnd 成立：说明在预处理过后，在新的一组子节点中，仍然有未被处理的子节点，而这些遗留的节点将被视作新增节点。
情况1：新增节点
通过观察可以发现，两组子节点具有相同的前置节点p-1，以及相同的后置节点p-3。索引j、newEnd和oldEnd之间的关系
- 条件一 j > newEnd 成立：说明在预处理过程中，所有的新节点都处理完毕了。
- 条件二 j `<= oldEnd 成立：说明在预处理过后，在旧的一组子节点中，仍然有未被处理的子节点，而这些遗留的节点将被视作删除节点。
对于相同的前置节点和后置节点，由于它们在新旧两组子节点中的相对位置不变，所以我们无须移动它们，但仍然需要在它们之间打补丁。根据上面的分析，我们可实现如下预处理的代码：
function vue3diff(prevChildren, nextChildren, parent) {
// 更新相同的前缀节点
// 索引 j 指向新旧两组子节点的开头
let j = 0
let oldVNode = prevChildren[j]
let newVNode = nextChildren[j]
// while 循环向后遍历，直到遇到拥有不同 key 值的节点为止
while (oldVNode.key === newVNode.key) {
// 调用 patch 函数更新
patch(oldVNode, newVNode, parent)
j++
oldVNode = prevChildren[j]
newVNode = nextChildren[j]
}
// 更新相同的后缀节点
// 索引 oldEnd 指向旧的一组子节点的最后一个节点
let oldEnd = prevChildren.length - 1
// 索引 newEnd 指向新的一组子节点的最后一个节点
let newEnd = nextChildren.length - 1
oldVNode = prevChildren[oldEnd]
newVNode = nextChildren[newEnd]
// while 循环向前遍历，直到遇到拥有不同 key 值的节点为止
while (oldVNode.key === newVNode.key) {
// 调用 patch 函数更新
patch(oldVNode, newVNode, parent)
oldEnd--
newEnd--
oldVNode = prevChildren[oldEnd]
newVNode = nextChildren[newEnd]
}
// 满足条件，则说明从 j ->` newEnd 之间的节点应作为新节点插入
if (j > oldEnd && j <= newEnd) {
// 锚点的索引
const anchorIndex = newEnd + 1
// 锚点元素
const anchor = anchorIndex < nextChildren.length ? nextChildren[anchorIndex].el : null
// 采用 while 循环，调用 mount 函数逐个挂载新增的节点
while (j <= newEnd) {
mount(nextChildren[j++], parent, anchor)
}
} else if (j > newEnd && j <= oldEnd) {
// j -> oldEnd 之间的节点应该被卸载
while (j `<= oldEnd) {
unMount(prevChildren[j++])
}
}
}判断是否需要进行DOM移动操作
上面预处理过程是处理比较理想化的情况，当处理完相同的前置节点和后置节点后，新旧两组子节点中总会有一组子节点全部被处理完毕。在这种情况下，只需要简单地挂载、卸载节点即可。但有时情况会比较复杂。如下图
经过预处理后，新旧两组子节点中都有部分节点未被处理，这时就需要进一步处理。怎么处理呢？
- 判断是否有节点需要移动，以及应该如何移动；
- 找出那些需要被添加或移除的节点。
代码实现上，预处理过程中处理了理想的新增和删除情况，我们需要增加一个 else 分支来处理非理想情况，如下：
function vue3diff(prevChildren, nextChildren, parent) {
let j = 0
let oldVNode = prevChildren[j]
let newVNode = nextChildren[j]
// 更新相同的前缀节点
// 省略部分代码
// 更新相同的后缀节点
// 省略部分代码
// 满足条件，则说明从 j -> newEnd 之间的节点应作为新节点插入
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j <= oldEnd) {
// j -> oldEnd 之间的节点应该被卸载
// 省略部分代码
} else {
// 增加 else 分支来处理非理性情况
}
}一、 构造一个数组source
构造一个数组 source，它的长度等于新的一组子节点在经过预处理之后剩余未处理节点数量，数组 source 中每个元素分别与新的一组子节点中剩余未处理节点对应，并且 source 中每个元素的初始值都是 -1。
数组 source 有什么作用呢？
source 数组将用来存储新的一组子节点中的节点在旧的一组子节点的位置索引，后面将会使用它计算出一个最长递增子序列，并用于辅助完成 DOM 移动的操作。
if (j > oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j `<= oldEnd) {
// 省略部分代码
} else {
// 处理非理性情况
// 构造 source 数组
const count = newEnd - j + 1 // 新的一组子节点中剩余未处理节点的数量
const source = new Array(count)
source.fill(-1)
// oldStart 和 newStart 分别为起始索引，即 j
const oldStart = j
const newStart = j
// 遍历旧的一组子节点
for (let i = oldStart; i `< oldEnd; i++) {
const oldVNOde = prevChildren[i]
// 遍历新的一组子节点
for (let k = newStart; k `< newEnd; k++) {
const newVNode = nextChildren[k]
// 找到拥有相同key值的可复用节点
if (oldVNode.key === newVNode.key) {
// 调用patch进行更新
patch(oldVNOde, newVNode, parent)
// 最后填充 source 数组
source[k - newStart] = i
}
}
}
}上面用于填充 source 数组的代码存在怎样的问题？
这段代码采用了两层嵌套的循环，其时间复杂度为 O(n^2)，当新旧两组子节点数量较多时两层嵌套的循环会带来性能问题。
怎样优化构造 source 数组的代码
为新的一组子节点构建一张索引表，用来存储节点的 key 和节点位置索引之间的映射。利用它可以快速地填充 source 数组。时间复杂度降至 O(n)。优化后代码实现如下:
if (j >``` oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j `<= oldEnd) {
// 省略部分代码
} else {
// 处理非理性情况
// 构造 source 数组
const count = newEnd - j + 1 // 新的一组子节点中剩余未处理节点的数量
const source = new Array(count)
source.fill(-1)
// oldStart 和 newStart 分别为起始索引，即 j
const oldStart = j
const newStart = j
//构建索引表
const keyIndex = {}
for(let i = newStart; i `<= newEnd; i++) {
keyIndex[nextChildren[i].key] = i
}
// 遍历旧的一组子节点中剩余未处理的节点
for(let i = oldStart; i `<= oldEnd; i++) {
oldVNode = prevChildren[i]
// 通过索引表快速找到新的一组子节点中具有相同 key 的节点位置
const k = keyIndex[oldVNode.key]
if (typeof k !== 'undefined') {
newVNode = nextChildren[k]
// 调用 patch 函数完成更新
patch(oldVNode, newVNode, parent)
// 填充 source 数组
source[k - newStart] = i
} else {
// 没找到
unMount(oldVNode)
}
}
}二、如何判断节点是否需要移动
如果在子节点遍历过程中遇到的索引值程序递增趋势，则说明不需要移动节点，反之则需要。
此处需新增三个变量 moved、pos 和 patched。
- moved 初始值 false，代表是否需要移动节点；
- pos 初始值 0，代表遍历旧的一组子节点的过程中遇到的最大索引值 k。
- patched 初始值 0，代表已经更新过的节点数量。已经更新过的节点数量应该小于新的一组子节点中需要更新的节点数量。一旦前者超过后者，则说明有多余的节点，我们应该将他们卸载。
在第二个 for 循环内，通过比较变量 k 与变量 pos 的值来判断是否需要移动节点。
if (j >``` oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j `<= oldEnd) {
// 省略部分代码
} else {
// 处理非理性情况
// 构造 source 数组
const count = newEnd - j + 1 // 新的一组子节点中剩余未处理节点的数量
const source = new Array(count)
source.fill(-1)
// oldStart 和 newStart 分别为起始索引，即 j
const oldStart = j
const newStart = j
// 新增两个变量 moved 和 pos
let moved = false
let pos = 0
const keyIndex = {}
for(let i = newStart; i `<= newEnd; i++) {
keyIndex[nextChildren[i].key] = i
}
// 新增 patched 变量，代表更新过的节点数量
let patched = 0
for(let i = oldStart; i `<= oldEnd; i++) {
oldVNode = prevChildren[i]
// 如果更新过的节点数量小于等于需要更新的节点数量，则执行更新
if (patched < count) {
const k = keyIndex[oldVNode.key]
if (typeof k !== 'undefined') {
newVNode = nextChildren[k]
patch(oldVNode, newVNode, parent)
// 每更新一个节点，都将 patched 变量 +1
patched++
source[k - newStart] = i
// 判断节点是否需要移动
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 没找到
unMount(oldVNode)
}
} else {
// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
unMount(oldVNode)
}
}
}如何移动节点
通过上面的处理，我们可以得到 moved 的值，如果 moved 为 true 说明需要移动节点。因此，需要增加个 if 判断分支来处理 DOM 移动的逻辑，如下：
if (j >``` oldEnd && j <= newEnd) {
// 省略部分代码
} else if (j > newEnd && j `<= oldEnd) {
// 省略部分代码
} else {
// 省略部分代码
for(let i = oldStart; i `<= oldEnd; i++) {
// 省略部分代码
}
if (moved){
// 如果 moved 为真， 则需要进行 DOM 移动操作
}
}计算 suorce 最长递增子序列
什么是最长递增子序列？
给定一个数值序列，找到它的一个子序列，并且该子序列中的值是递增的，子序列中的元素在原序列中不一定连续。一个序列可能有很多个递增子序列，其中最长的那个就称为最长递增子序列，例如：
[0, 8, 4, 12]
// 上面的最长递增子序列如下：
[0, 4, 12]
// 或
[0, 8, 12]如图所示，子序列 seq 的值为 [0, 1]，说明在新的一组子节点中， 重新编号后，索引值为 0 和 1的这两个节点在更新前后顺序没有发生变化，不需要移动。
之后我们只需要在这个基础上移动不在最长递增子序列的节点，方法如下：
- 创建两个索引值 i 和 s，分析 source，seq，i 和 s 的关系
- i 指向新的一组子节点中最后一个节点；
- s 指向最长递增子序列中的最后一个元素。
我们可以知道source，seq，i 和 s 存在下面三种情况：
- 情况一：source[i] === -1，说明索引为 i 的节点是全新的节点，应该将其挂载
- 情况二：i !== seq[s]，说明该节点需要移动
- 情况三： i === seq[s] 时，说明该位置的节点不需要移动
if (moved) {
// 获取最长递增子序列，算法可以去了解一下
const seq = getSequence(source)
// s 指向最长递增子序列的最后一个值，count是剩余未处理的新列表中的节点数
let s = seq.length - 1
let i = count - 1
// for 循环使得 i 递减
for (i; i >= 0; i--) {
if (source[i] === -1) {
// 说明索引为 i 的节点是全新的节点，应该将其挂载
// 该节点在新 children 中的真实位置索引
const pos = i + newStart
const newVNode = nextChildren[pos]
// 该节点下一个节点的位置索引
const nextPos = pos + 1
// 锚点
const anchor = nextPos < nextChildren.length
? nextChildren[nextPos].el
: null
// 挂载
mount(null, newVNode, parent)
} else if (i !== seq[s]) {
// 说明该节点需要移动
// 该节点在新的一组子节点中的真实位置索引
const pos = i + newStart
const newVNode = nextChildren[pos]
// 该节点下一个节点的位置索引
const nextPos = pos + 1
// 锚点
const anchor = nextPos < nextChildren.length
? nextChildren[nextPos].el
: null
// 移动
insert(newVNode.el, parent, anchor)
} else {
// 当 i === seq[s] 时，说明该位置的节点不需要移动
// 并让 s
s--
}
}总结
这就是我们今天全部讲的了，首先我们介绍了声明式框架和命令式框架，讲解了二者的区别，我们可以确定的是从理论上命令式框架比声明式框架效率更高，因为声明式框架需要一个寻找新旧 DOM 区别的时间，这也是 虚拟DOM 产生的原因，但是声明式框架可维护性更高。
接下来我们介绍了 Vue 的渲染，我们需要解析器把模板转化为 AST，这个过程中会打一些补丁来帮助提高渲染器的效率，然后通过渲染器把 AST 转为 虚拟DOM 并且将 虚拟DOM 与真实的 DOM 相关联，并且其核心是 Diff 算法，可以高效的找出新旧 DOM 的区别并更新。
最后，我们介绍了三种 Diff 算法，第一个是简单 diff 算法，就是单向比较，寻找最大索引，比最大索引小的都要移动，如果比他大则更新索引，不需要移动；第二个是双端 diff 算法，通过比较新旧列表的首尾四个指针来进行更新；最后是快速 diff 算法，使用的是前后预处理以及最长递增子序列，最长递增子序列其实也是对一个简单 diff 算法的方法的一种改进。