Vue3快速diff算法的处理过程
一、为什么要使用diff算法新旧vnode节点都有一组子节点的情况下，如果不使用diff算法处理则渲染器的做法是，将旧的子节点全部卸载，再挂载新的子节点，并没有考虑到节点的复用情况，比如下面的两组vnode
const newVnode = {
type: 'div',
children: [
{ type: 'p', children: '1' },
{ type: 'p', children: '2' },
{ type: 'p', children: '3' },
]
}
const oldVnode = {
type: 'div',
children: [
{ type: 'p', children: '4' },
{ type: 'p', children: '5' },
{ type: 'p', children: '6' }
]
}实际上并不需要去全部卸载然后挂载新的子节点，只需要替换子节点中p标签中的文本内容即可。 Vue使用diff算法的原因就是为了避免全量更新子节点，尽可能的去复用或者使用较少的操作去完成节点的更新。
二、如何复用子节点
1.判断是否可复用：
观察以下两个新旧节点：他们的类型相同都是p元素，并且其内容其实也没有变化，只是元素的顺序发生了变动，这种情况我们完全可以复用新旧节点：
const newVnode = {
type: 'div',
children: [
{ type: 'p', children: '1' },
{ type: 'p', children: '2' },
{ type: 'p', children: '3' },
]
}
const oldVnode = {
type: 'div',
children: [
{ type: 'p', children: '3' },
{ type: 'p', children: '2' },
{ type: 'p', children: '1' }
]
}为了能够识别出哪些子节点是我们可以复用的，可以给其加上key属性，当新旧节点的key值相同时，则证明他们是同一个子节点，可以复用。
const newVnode = {
type: 'div',
children: [
{ type: 'p', children: '1', key:1 },
{ type: 'p', children: '2', key:2},
{ type: 'p', children: '3', key:3},
]
}
const oldVnode = {
type: 'div',
children: [
{ type: 'p', children: '3', key:3 },
{ type: 'p', children: '2', key:2},
{ type: 'p', children: '1', key:1},
]
}
2.对可复用节点的处理：
节点可复用并不意味着只需要简单的处理新旧子节点的顺序变化，子节点的内容可能也会发生变动，所以在移动之前需要打补丁确保内容更新：我们需要对前面处理子节点更新的patchChildren进行完善，主要处理其中新旧子节点都是多个的情况，此时我们才需要使用diff算法处理,其中再使用patch函数去更新可复用节点,具体的处理过程在下文中进行描述：
function patchChildren(n1, n2, container) {
if (typeof n2.children === 'string') {
//省略代码
} else if (Array.isArray(n2.children)) {
//新子节点是一组节点
if (Array.isArray(n1.children)) {
//旧子节点也是一组节点，应用diff算法处理
//省略diff算法代码
//diff中会使用patch去更新可复用元素
} else if (typeof n1.children === 'string') {
//省略代码
}
}
}
三、Vue3快速diff算法的处理过程
1.预处理:处理两组子节点中首尾节点可复用的情况
比如下面的情况：
有三个节点key值相同，可以复用，并且他们在子节点中的相对顺序也没有发生变化，p-1在最前面，p-2和p-3在最后面。所以他们并不需要移动，只需要处理中间的节点。
处理前置节点：
设置一个索引j从0开始使用while循环寻找相同的前置节点：如果是key相同的节点，调用patch函数打补丁更新其中的内容，直到使用同一个索引取到的新旧子节点key值不同
处理后置节点：
拿到新旧子节点最后一个元素的索引oldEnd和newEnd，使用while从两组节点尾部往上遍历，如果是key相同的节点则调用patch函数打补丁更新其中的内容，知道取不到相同key的节点为止。
我们使用一个patchKeyedChildren函数去实现上述过程：
function patchKeyedChildren(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
//处理前置节点
let j = 0
let oldVNode = oldChildren
let newVNode = newChildren
while (oldVNode.key === newVNode.key) {
patch(oldVNode, newVNode, container)
j++
oldVNode = oldChildren
newVNode = newChildren
}
//处理后置节点
//将新旧节点的索引指向最后一个子节点
let oldEnd = oldChildren.length - 1
let newEnd = newChildren.length - 1
oldVNode = oldChildren
newVNode = newChildren
while (oldVNode.key === newVNode.key) {
patch(oldVNode, newVNode, container)
oldEnd--
newEnd--
oldVNode = oldChildren
newVNode = newChildren
}
}
2、预处理之后的两种情况：需要删除节点、需要新增节点
如何判断存在需要删除或者新增的节点? 在预处理之后我们可以获得的信息有：
[*]处理前置节点的时候获得的索引j
[*]处理后置节点得到的两个索引newEnd、oldEnd 利用以上索引可以做出判断：
需要新增节点的情况：oldEnd < j 以及 newEnd >= j：
需要删除节点的情况：oldEnd >= j 以及 newEnd < j：
在前文:
Vuejs 数据是如何渲染的？渲染器的简单实现
Vue 的渲染器是如何对节点进行挂载和更新的中实现的patch和mountElement方法并不能指定位置去挂载节点，为了能够处理指定节点位置插入节点，我们需要为其增加一个参数anchor，传入锚点元素。
function patch(n1, n2, container, anchor) {
//...省略代码
if (typeof type === 'string') {
if (!n1) {
//在此处传入锚点以支持新节点按位置插入
mountElement(n2, container, anchor)
} else {
patchElement(n1, n2)
}
} else if (type === Text) {
//...省略代码
}
function mountElement(vnode, container, anchor) {
//省略代码
//给insert方法传递锚点元素
insert(el, container, anchor)
}
const renderer = createRenderer({
//...省略代码
insert(el, parent, anchor = null) {
//根据锚点元素插入节点
parent.insertBefore(el, anchor)
}
})接下来我们需要完善patchKeyedChildren去处理上述两种情况：
需要新增节点时：
function patchKeyedChildren(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
//需要插入新节点
if (j > oldEnd && j <= newEnd){
//取得锚点索引
const anchorIndex = newEnd + 1
//取得锚点元素
const anchor = anchorIndex < newChildren.length ? newChildren.el : null
//调用patch挂载新节点
while (j <= newEnd) {
patch(null, newChildren, container, anchor)
}
}
}代码如上，我们首先使用newEnd+1获取锚点索引，并且使用newChildren.el去获取到锚点元素，其中还做了一个判断如果newEnd是尾部节点那不需要提供锚点元素直接处理即可。
需要删除节点时:
function patchKeyedChildren(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
//需要插入新节点
if (j > oldEnd && j <= newEnd){
//...省略新增节点逻辑
}else if (j > newEnd && j <= oldEnd) {
//卸载节点
while (j <= oldEnd) {
unmount(oldChildren)
}
}
}如上所示，当j<=oldEnd时循环使用umount卸载对应的节点即可。
在实际过程中，很少会有像上述简单的预处理即可完成大部分工作的情况，这个时候就需要进行进一步的判断： 比如以下情况：
在经过预处理之后，只有首尾两个节点被正确更新了，仍然会有多数节点没有被更新。
预处理之后后续需要做的是:
[*]判断节点是否需要移动，移动节点；
[*]如果有需要添加或者移除的节点进行处理；
3.判断节点是否需要移动：
1.构建source数组
source数组需要去存储新的子节点对应的旧子节点的位置索引，然后去计算一个最长递增子序列，通过最长递增子序列去完成DOM的移动操作
初始化source数组:
function patchKeyedChildren(n1, n2, container) {
const oldChildren = n1.children
const newChildren = n2.children
//需要插入新节点
if (j > oldEnd && j <= newEnd){
//...省略新增节点逻辑
}else if (j > newEnd && j <= oldEnd) {
//卸载节点
while (j <= oldEnd) {
unmount(oldChildren)
}
//预处理完毕后
} else{
//初始化source数组
const count = newEnd - j + 1
const source = new Array(count)
source.fill(-1)
}
}source数组的长度等于预处理之后剩余节点的长度也就是newEnd - j + 1,我们使用fill将数组中的元素填充为-1初始化其中的值
填充source数组: 使用新子节点在旧子节点中的索引去填充source数组
如上key为p-3的新子节点在旧子节点中的索引为2，所以source数组的第一项需要被填充为2，key为p-4的新子节点在旧子节点为3，所以source数组的第二项的值为3，以此类推。 在这个过程中需要嵌套两个for循环去遍历新旧子节类似下面的过程：
for (let i = oldStart; i <= oldEnd; i++) {
const oldVNode = oldChildren
// 遍历新的一组子节点
for (let k = newStart; k <= newEnd; k++) {
const newVNode = newChildren
// 找到拥有相同 key 值的可复用节点
if (oldVNode.key === newVNode.key) {
// 调用 patch 进行更新
patch(oldVNode, newVNode, container)
// 最后填充 source 数组
source = i
}
}
}以上做法时间复杂度为O(n^2),在子节点数量增加时会存在性能问题。 优化的办法是先遍历新的一组子节点，根据子节点的位置和key生成一张索引表，然后再遍历旧的一组子节点，利用节点的key在索引表中找到对应的新子节点的位置，以此填充source数组。
const oldStart = j
const newStart = j
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
keyIndex.key] = i
}
for(let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren
const k = keyIndex
if (typeof k !== 'undefined') {
newVNode = newChildren
patch(oldVNode, newVNode, container)
source = i
} else {
unmount(oldVNode)
}
}优化后的代码如上所示:
首先将预处理之后的j值作为遍历新旧节点开始时的索引，定义一个对象keyIndex作为索引表，遍历预处理之后剩余的一组新子节点，将新子节点newChildren的key值与其位置索引放入索引表中。 遍历旧子节点，在遍历时，我们可以通过当前节点的key去keyIndex索引表中获取从而拿到当前遍历的旧子节点的oldChildren对应的新节点的位置keyIndex,如果位置存在，说明节点可复用，使用patch打补丁，并且使用当前旧节点的索引i对source数组进行填充。
2.标识是否需要移动节点
需要添加标识有:
[*]是否需要移动moved: 用于标识是否有需要移动的节点，
[*]当前新子节点的位置pos: 用于记录遍历旧子节点中遇到的最大的索引值k，如果此次遍历的k值大于上一次的，说明相对位置正确无需移动,
[*]已经更新过的节点数量patched：当patched大于source数组的长度即newEnd - j + 1时说明所有可复用节点已经处理完毕，还有一些旧子节点需要执行卸载操作， 代码如下，我们在每一次更新节点内容后递增patched++记录处理数量，并对moved和pos的值进行处理。
const count = newEnd - j + 1// 新的一组子节点中剩余未处理节点的数量
const source = new Array(count)
source.fill(-1)
const oldStart = j
const newStart = j
let moved = false
let pos = 0
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
keyIndex.key] = i
}
let patched = 0
for(let i = oldStart; i <= oldEnd; i++) {
oldVNode = oldChildren
if (patched < count) {
const k = keyIndex
if (typeof k !== 'undefined') {
newVNode = newChildren
patch(oldVNode, newVNode, container)
patched++
source = i
// 判断是否需要移动
if (k < pos) {
moved = true
} else {
pos = k
}
} else {
// 没找到
unmount(oldVNode)
}
} else {
unmount(oldVNode)
}
}
4.处理节点的移动：
先前我们使用moved去标记了是否有至少一个子节点需要移动，当moved为true时，我们需要配合source数组中的最长递增子序列去移动节点，否则直接不用再去使用diff。
1.最长递增子序列：
什么是最长递增子序列 递增子序列就是在一个序列中，从左到右依次找出更大的值所构成的序列，在一个序列中可能存在多个递增子序列，最长递增子序列就是其中长度最长的那个。 例如 在上面的例子中我们得到的source数组为,则其最长递增子序列为，我们通过处理得到了对应的旧子节点的索引,即最长递增子序列对应的新子节点的索引。
如上最长递增子序列对应的旧节点为key为p-3、p-4，对应在新子节点的位置为0，1。
最长递增子序列的意义：通过最长递增子序列得到的索引可以提示我们哪些元素的相对位置，在子节点更新后并未发生变化，我们可以保留这些节点的相对位置，然后去处理和移动其他位置。如上p-3和p-4的相对位置在更新之后并未发生变化，即新节点中的索引为0和1的元素不需要移动。这里我们省略求最长递增子序列的方法，直接将其当作函数lis处理source数组的结果
const seq = lis(source)
2.根据最长递增子序列移动节点：
创建两个索引辅助移动:
[*]索引 i 指向新的一组子节点中的最后一个节点。
[*]索引 s 指向最长递增子序列中的最后一个元素。
我们需要去判断以下的情况:
[*]source === -1: 节点不存在，需要挂载新节点
[*]i!==seq：节点需要移动，
[*]i===seq：节点无需移动，将s递减并再次进行比较
完善patchKeyedChildren去处理这几种情况:
function patchKeyedChildren(n1, n2, container) {
//省略预处理和构造source数组代码
if (moved) {
const seq = lis(source)
// s 指向最长递增子序列的最后一个值
let s = seq.length - 1
let i = count - 1
for (i; i >= 0; i--) {
if (source === -1) {
// 说明索引为 i 的节点是全新的节点，应该将其挂载
} else if (i !== seq) {
// 说明该节点需要移动
} else {
// 当 i === seq 时，说明该位置的节点不需要移动
// 并让 s 指向下一个位置
s--
}
}
}
}
}节点不存在情况具体处理
if (source === -1) {
// 该节点在新的一组子节点中的真实位置索引
const pos = i + newStart
const newVNode = newChildren
// 该节点下一个节点的位置索引
const nextPos = pos + 1
// 锚点
const anchor = nextPos < newChildren.length
? newChildren.el
: null
patch(null, newVNode, container, anchor)
}代码如上所示：当新子节点是新节点时直接获取，该节点的位置，即索引，并且加一获得锚点用于挂载元素，如果元素本身就是最后一个元素 nextPos < newChildren.length，则无需锚点。 此时p-7处理完成，继续向上处理p-2
节点需要移动的情况
if (i !== seq) { // 该节点在新的一组子节点中的真实位置索引 const pos = i + newStart const newVNode = newChildren // 该节点下一个节点的位置索引 const nextPos = pos + 1 // 锚点 const anchor = nextPos < newChildren.length ? newChildren.el : null patch(null, newVNode, container, anchor)}逻辑和节点不存在的情况类似，只是移动节点通过insert函数去完成。此时处理的结果如下
节点不需要移动的情况 对于p-3和p-4来说，source !== -1,并且i === seq，即节点无需移动只需更新s的值即可
s--依此类推直到循环结束，子节点全部更新完毕，该过程完整代码如下：
if (moved) { const seq = lis(source) // s 指向最长递增子序列的最后一个值 let s = seq.length - 1 let i = count - 1 for (i; i >= 0; i--) { if (source === -1) { // 说明索引为 i 的节点是全新的节点，应该将其挂载 // 该节点在新 children 中的真实位置索引 const pos = i + newStart const newVNode = newChildren // 该节点下一个节点的位置索引 const nextPos = pos + 1 // 锚点 const anchor = nextPos < newChildren.length ? newChildren.el : null // 挂载 patch(null, newVNode, container, anchor) } else if (i !== seq) { // 说明该节点需要移动 // 该节点在新的一组子节点中的真实位置索引 const pos = i + newStart const newVNode = newChildren // 该节点下一个节点的位置索引 const nextPos = pos + 1 // 锚点 const anchor = nextPos < newChildren.length ? newChildren.el : null // 移动 insert(newVNode.el, container, anchor) } else { // 当 i === seq 时，说明该位置的节点不需要移动 // 并让 s 指向下一个位置 s-- } }}}
总结：
[*]使用 diff 算法的原因：
[*]传统的 DOM 更新方法会在有新旧子节点时卸载旧节点并挂载新节点，这种方法没有考虑到节点的复用可能性。diff 算法通过比较新旧节点的差异来复用节点，从而优化性能。
[*]节点复用依据:key：
[*]节点复用是通过比较节点的 key 和类型来实现的。相同的 key 和类型表明两个节点可以被视为同一个，从而复用以减少 DOM 操作。
[*]Vue 3 diff算法的过程：
[*]预处理阶段：处理首尾节点，找出新旧两种子节点中首尾可复用的节点并更新。
[*]处理理想情况下新增和删除节点：若通过预处理有一组节点已经更新完毕，证明新的一组子节点只需新增或删除部分节点即可完成更新。
[*]构造source数组：通过遍历新旧两组子节点，构造一个source数组,去存储新的子节点对应的旧子节点的位置索引，并在此过程中判断是否需要使用diff算法处理移动。
[*]节点位置移动：根据最长递增子序列判断具体的某个节点是否需要新增或者移动，在需要时移动节点以匹配新的子节点顺序。
[*]diff算法带来的效率提升：
[*]算法避免了全量的 DOM 更新，通过巧妙的方法判断哪些节点需要更新、移动或重新挂载，从而降低了全量更新的成本和时间。
以上就是Vue3快速diff算法的处理过程的详细内容，更多关于Vue3快速diff算法的资料请关注脚本之家其它相关文章！
来源:https://www.jb51.net/javascript/321003qlr.htm
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]