Vue中的Diff算法

发布于:2021-06-19 03:50:21

Vue中的Diff算法

本篇文章主要介绍Diff算法的思想和Vue中对Diff算法的基本实现。


1. 为什么要用Diff算法

由于在浏览器中操作DOM的代价是非常“昂贵”的,所以才在Vue引入了Virtual DOM,Virtual DOM是对真实DOM的一种抽象描述,不懂的朋友可以自行查阅相关资料。


即使使用了Virtual DOM来进行真实DOM的渲染,在页面更新的时候,也不能全量地将整颗Virtual DOM进行渲染,而是去渲染改变的部分,这时候就需要一个计算Virtual DOM树改变部分的算法了,这个算法就是Diff算法。


2. 传统的Diff算法

传统的Diff算法通过循环递归对节点进行比较,然后判断每个节点的状态以及要做的操作(add,remove,change),最后 根据Virtual DOM进行DOM的渲染。大体流程如下图(图来源):


传统Diff算法的复杂度为O(n^3),这个复杂度相对来说还是较高的。后来React开发者提供了一种复杂度仅为O(n) 的Diff算法。下面就来看一下O(n)复杂度的Diff算法是如何实现的。


3. 更高效的Diff算法

React的开发者结合Web界面的特点做出了两个大胆的假设,使得Diff算法复杂度直接从O(n^3)降低到O(n),假设如下:


两个相同组件产生类似的DOM结构,不同的组件产生不同的DOM结构;对于同一层次的一组子节点,它们可以通过唯一的id进行区分。

通过这两个假设,他们提供了下面的Diff算法思路。


同层比较

新的Diff算法是逐层进行比较,只比较同一层次的节点,大大降低了复杂度,具体如下图。在后面的内容中也会介绍Vue中同层节点比较的具体实现。


不同类型节点的比较

如果发现新旧两个节点类型不同时,Diff算法会直接删除旧的节点及其子节点并插入新的节点,这是由于前面提出的不同组件产生的DOM结构一般是不同的,所以可以不用浪费时间去比较。注意的是,删除节点意味着彻底销毁该节点,并不会将该节点去与后面的节点相比较。


相同类型节点的比较

若是两个节点类型相同时,Diff算法会更新节点的属性实现转换。


列表节点的比较

列表节点的操作一般包括添加、删除和排序,列表节点需要我们给它一个key才能进行高效的比较。


4.Vue Diff算法的实现

了解了Diff算法的大体思路后,我们回过头来看下Vue中的Diff算法是如何实现的。


Vue的Diff算法与上面的思路大体相似,只比较同级的节点,若找不到与新节点类型相同的节点,则插入一个新节点,若有相同类型的节点则进行节点属性的更新,最后删除新节点列表中不包含的旧节点。具体的实现在vue源码的src/core/vdom/patch.js中的updateChildren方法中,由于代码较长,下面简单说一下整个的比较流程。


初始化


如上图,有一组新旧节点数组before:[A, B, C, D]、after:[E, C, F, G],我们设置了四个哨兵节点,oldStartIdx、newStartIdx、oldEndIdx、newEndIdx分别指向新旧节点数组的起始下标和开始下标,值为0,0,3,3;oldStartVnode,newStartVnode,oldEndVnode,newEndVnode则分别指向了before和after节点列表中对应哨兵节点下标的值,值为before[oldStartVnode],after[newStartIdx],before[oldEndIdx],after[newEndIdx]。


Diff

当哨兵满足oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx的条件的时候,我们会循环进行一系列节点之间的比较。


优先判断

我们首先对上面声明的各个节点进行一些优先级较高的判断。


判断1:oldStartVnode是否为空,若为true则oldStartIdx向后移动,继续下一个节点的判断。判断代码如下:

if (isUndef(oldStartVnode)) {
// 更新哨兵
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
}

判断2:oldEndVnode是否为空,若为true则oldEndIdx向前移动。判断代码如下:

else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
}

判断3:使用 sameVnode判断before和after未判断的头节点是否为相同节点,若为true,则按照上面思路说的,对相同类型节点进行节点的属性的更新并修改哨兵位置。

// sameVnode为判断节点是否相等的方法,包括key、tag、isComment等各个属性的相等才能算作相同节点
else if (sameVnode(oldStartVnode, newStartVnode)) {
// 更新节点内容
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
// 更新哨兵
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}

判断4:使用上一步相同的方法对oldEndVnode和newEndVnode进行判断。并执行相同的更新操作。

else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
// 更新哨兵
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}

判断5:使用sameVNode判断旧列表的头节点和新列表的尾节点进行判断,
sameVnode(oldStartVnode, newEndVnode),若为true,更新相同节点,若该节点可以移动在真实DOM中将oldStartVnode,放到真实节点列表的最后。

else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
// 真实DOM移动到真实节点列表的最后面
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
// 更新哨兵
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}

判断6:使用sameVnode比较旧列表的尾节点和新列表的头节点,若为true,和上面一样,更新相同节点,将oldEndVnode放到真实节点列表的最开始。

else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
// 真实DOM移动到真实节点列表最前面
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}

通过这一系列的优先判断条件,一方面对于一些不需要做移动的DOM可以得到快速处理,另一方面使待处理节点变少,缩小了后续操作的处理范围,可以更快地完成同级节点的对比。


若节点不满足上面的所有判断,则会进入到最后一个条件分支,判断7:。


else {
// oldKeyToIdx为after列表中key和index的映射,可以加快查找速度
if (isUndef(oldKeyToIdx)) {
// 若不存在该映射则去初始化映射
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// 若newStartVnode存在key的情况,则去映射中查找,若无则从oldStartIdx到oldEndIdx遍历after列表查找新节点是否存在
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
// 若新节点不存在于旧节点数组中,新建一个元素并插入真实DOM节点列表中
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
// 若在旧列表中查找到新节点,则去判断两个节点是否相等
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
// 更新节点内容和哨兵并进行节点的移动
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue)
oldCh[idxInOld] = undefined
canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
} else {
// same key but different element. treat as new element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
}
}
newStartVnode = newCh[++newStartIdx]
}

循环结束

最后当oldStartIdx > oldEndIdx || newStartIdx > newEndIdx,也就是新或旧节点数组有一个被查找完之后则退出判断循环。当循环结束时,旧节点数组中剩下的节点即为要删除的节点,新节点数组中剩下的即为要新增的节点。只需要进行简单的新增和删除操作即可,代码如下:


if (oldStartIdx > oldEndIdx) {
// 新节点数组中有剩余,新增新节点
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
} else if (newStartIdx > newEndIdx) {
// 旧节点数组中有剩余,删除旧节点
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
}

经历过了这么多的判断之后,就完成了同级节点之间的Diff比较。


就地复用

在Diff中会使用到一种就地复用的策略。就地复用是指Vue会尽可能复用之前的DOM,尽可能不发生DOM的移动。


Vue判断新旧节点是否为相同节点(也就是上面的sameVnode方法),这个相同节点的意思并不是两个完全相同的节点,实际上它仅判断是否为同类节点(同类节点为类型相同且节点数据一致,如前后两个span,span标签上的属性没有改变,但是里面的内容变了,这样就算作同类节点),如果是同类节点,那么Vue会直接复用旧DOM节点,只要更新节点中的内容即可。这样可以大大减少列表中节点的移动操作。


图解Diff

下面通过之前的初始化的节点图,进行一步一步的图解。


(1)在初始化并设置了哨兵之后,进入了条件判断循环。第一步发现了旧数组的头和新数组的尾都是A节点,这时候进入了上面的判断5。oldStartIdx向后移动,newEndIdx向前移动。更新A节点内容并在真实DOM中将A移动到队伍最后


(2)第二次循环,进入判断7,发现新节点E并不存在于旧节点列表中,只能新建E节点,并插入真实DOM中。哨兵newStartIdx向后移动。


(3)第三次循环,进入判断7,根据key map获取遍历旧节点数组发现C节点存在旧节点数组中,获取C节点在旧节点数组中的位置,在真实DOM中将C节点插入到oldStartNode(B节点)前面,将旧节点数组中的该元素(before[idxInOld])置为undefined,newStartIdx向后移动。


(4)第四次循环,同第二次循环,新节点F并不存在旧节点数组中,新建F节点,并插入节点C后。newStartIdx向后移动。

(5)newStartIdx > newEndIdx,不满足循环条件,即新节点数组已处理完成。接下来进入退出循环后的条件处理,所以从oldStartIdx到oldEndIdx遍历旧节点数组,依次删除B,D两个节点。完成节点比较



总结

Vue中的Diff算法采用了React相似的思路,都是同层节点进行比较,在比较的过程中,使用了一些优先判断和就地复用策略,提高了Diff算法的效率。

相关推荐

最新更新

猜你喜欢