当前位置:首页 > 前端 > 正文内容

Vue的diff算法解析

放牧的风3年前 (2021-06-16)前端3507

1. 前言


diff算法是一种通过同层的树节点进行比较的高效算法,避免了对树进行逐层搜索遍历,所以时间复杂度只有 O(n)。diff算法的在很多场景下都有应用,例如在 vue 虚拟 dom 渲染成真实 dom 的新旧 VNode 节点比较更新时,就用到了该算法。diff算法有两个比较显著的特点:

比较只会在同层级进行, 不会跨层级比较:

在diff比较的过程中,循环从两边向中间收拢:

2. diff流程

本着对 diff 过程的认识和 vue 源码的学习,我们通过 vue 源码的解读和实例分析来理清楚 diff 算法的整个流程,下面把整个 diff 流程拆成三步来具体分析:

第一步

vue 的虚拟 dom 渲染真实 dom 的过程中首先会对新老 VNode 的开始和结束位置进行标记:oldStartIdx、oldEndIdx、newStartIdx、newEndIdx。
let oldStartIdx = 0 // 旧节点开始下标
let newStartIdx = 0 // 新节点开始下标
let oldEndIdx = oldCh.length - 1 // 旧节点结束下标
let oldStartVnode = oldCh[0]  // 旧节点开始vnode
let oldEndVnode = oldCh[oldEndIdx] // 旧节点结束vnode
let newEndIdx = newCh.length - 1 // 新节点结束下标
let newStartVnode = newCh[0] // 新节点开始vnode
let newEndVnode = newCh[newEndIdx] // 新节点结束vnode

经过第一步之后,我们初始的新旧 VNode 节点如下图所示:

640 (2).png


第二步

标记好节点位置之后,就开始进入到的 while 循环处理中,这里是 diff 算法的核心流程,分情况进行了新老节点的比较并移动对应的 VNode 节点。while 循环的退出条件是直到老节点或者新节点的开始位置大于结束位置。


while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    ....//处理逻辑
}
接下来具体介绍 while 循环中的处理逻辑, 循环过程中首先对新老 VNode 节点的头尾进行比较,寻找相同节点,如果有相同节点满足 sameVnode(可以复用的相同节点) 则直接进行 patchVnode (该方法进行节点复用处理),并且根据具体情形,移动新老节点的 VNode 索引,以便进入下一次循环处理,一共有 2 * 2 = 4 种情形。下面根据代码展开分析:


情形一:当新老 VNode 节点的 start 满足sameVnode 时,直接 patchVnode 即可,同时新老 VNode 节点的开始索引都加1。


 if (sameVnode(oldStartVnode, newStartVnode)) {        
     patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)        
     oldStartVnode = oldCh[++oldStartIdx]        
     newStartVnode = newCh[++newStartIdx]     
 }

情形二:当新老 VNode 节点的 end 满足 sameVnode 时,同样直接 patchVnode 即可,同时新老 VNode 节点的结束索引都减1。

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

情形三:当老 VNode 节点的 start 和新 VNode 节点的 end 满足 sameVnode 时,这说明这次数据更新后 oldStartVnode 已经跑到了 oldEndVnode 后面去了。这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldEndVnode 的后面,同时老 VNode 节点开始索引加1,新 VNode 节点的结束索引减1。

else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right        
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)        
    canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))        
    oldStartVnode = oldCh[++oldStartIdx]        
    newEndVnode = newCh[--newEndIdx]      
}

情形四:当老 VNode 节点的 end 和新 VNode 节点的 start 满足 sameVnode 时,这说明这次数据更新后 oldEndVnode 跑到了 oldStartVnode 的前面去了。这时候在 patchVnode 后,还需要将当前真实 dom 节点移动到 oldStartVnode 的前面,同时老 VNode 节点结束索引减1,新 VNode 节点的开始索引加1。

else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left        
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)        
    canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)        
    oldEndVnode = oldCh[--oldEndIdx]        
    newStartVnode = newCh[++newStartIdx]      
}

如果都不满足以上四种情形,那说明没有相同的节点可以复用。于是则通过查找事先建立好的以旧的 VNode 为 key 值,对应 index 序列为 value 值的哈希表。从这个哈希表中找到与 newStartVnode 一致 key 的旧的 VNode 节点,如果两者满足 sameVnode 的条件,在进行 patchVnode 的同时会将这个真实 dom 移动到 oldStartVnode 对应的真实 dom 的前面;如果没有找到,则说明当前索引下的新的 VNode 节点在旧的 VNode 队列中不存在,无法进行节点的复用,那么就只能调用 createElm 创建一个新的 dom 节点放到当前 newStartIdx 的位置。

else {// 没有找到相同的可以复用的节点,则新建节点处理        
    /* 
        生成一个key与旧VNode的key对应的哈希表(只有第一次进来undefined的时候会生成,也为后面检测重复的key值做铺垫) 
        比如childre是这样的 [{xx: xx, key: 'key0'}, {xx: xx, key: 'key1'}, {xx: xx, key: 'key2'}] beginIdx = 0 endIdx = 2 结果生成{key0: 0, key1: 1, key2: 2} 
    */        
    if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)        
    /*如果newStartVnode新的VNode节点存在key并且这个key在oldVnode中能找到则返回这个节点的idxInOld(即第几个节点,下标)*/        
    idxInOld = isDef(newStartVnode.key)          
    ? oldKeyToIdx[newStartVnode.key]          
    : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)        
    
    if (isUndef(idxInOld)) { // New element          
        /*newStartVnode没有key或者是该key没有在老节点中找到则创建一个新的节点*/          
        createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)        
    } else {          
        /*获取同key的老节点*/          
        vnodeToMove = oldCh[idxInOld]          
        if (sameVnode(vnodeToMove, newStartVnode)) {            
            /*如果新VNode与得到的有相同key的节点是同一个VNode则进行patchVnode*/            
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)            
            //因为已经patchVnode进去了,所以将这个老节点赋值undefined            
            oldCh[idxInOld] = undefined            
            /*当有标识位canMove实可以直接插入oldStartVnode对应的真实Dom节点前面*/            
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)          
        } else {            
            // same key but different element. treat as new element            
            /*当新的VNode与找到的同样key的VNode不是sameVNode的时候(比如说tag不一样或者是有不一样type的input标签),创建一个新的节点*/            
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)          
        }       
    }        
    newStartVnode = newCh[++newStartIdx]      
}

再来看我们的实例,第一次循环后,找到了旧节点的末尾和新节点的开头(都是D)相同,于是直接复用 D 节点作为 diff 后创建的第一个真实节点。同时旧节点的 endIndex 移动到了 C,新节点的 startIndex 移动到了 C。 

紧接着开始第二次循环,第二次循环后,同样是旧节点的末尾和新节点的开头(都是C)相同,同理,diff 后创建了 C 的真实节点插入到第一次创建的 B 节点后面。同时旧节点的 endIndex 移动到了 B,新节点的 startIndex 移动到了 E。 

接下来第三次循环中,发现 patchVnode 的4种情形都不符合,于是在旧节点队列中查找当前的新节点 E,结果发现没有找到,这时候只能直接创建新的真实节点 E,插入到第二次创建的 C 节点之后。同时新节点的 startIndex 移动到了 A。旧节点的 startIndex 和 endIndex 都保持不动。 

第四次循环中,发现了新旧节点的开头(都是A)相同,于是 diff 后创建了 A 的真实节点,插入到前一次创建的 E 节点后面。同时旧节点的 startIndex 移动到了B,新节点的startIndex 移动到了B。 

第五次循环中,情形同第四次循环一样,因此 diff 后创建了 B 真实节点 插入到前一次创建的 A 节点后面。同时旧节点的 startIndex 移动到了C,新节点的 startIndex 移动到了F。

这时候发现新节点的 startIndex 已经大于 endIndex 了。不再满足循环的条件了。因此结束循环,接下来走后面的逻辑。

第三步


当 while 循环结束后,根据新老节点的数目不同,做相应的节点添加或者删除。若新节点数目大于老节点则需要把多出来的节点创建出来加入到真实 dom 中,反之若老节点数目大于新节点则需要把多出来的老节点从真实 dom 中删除。至此整个 diff 过程就已经全部完成了。


if (oldStartIdx > oldEndIdx) {      
     /*全部比较完成以后,发现oldStartIdx > oldEndIdx的话,说明老节点已经遍历完了,新节点比老节点多, 所以这时候多出来的新节点需要一个一个创建出来加入到真实Dom中*/      
     refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm      
     addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue) //创建 newStartIdx - newEndIdx 之间的所有节点    
} else if (newStartIdx > newEndIdx) {      
     /*如果全部比较完成以后发现newStartIdx > newEndIdx,则说明新节点已经遍历完了,老节点多于新节点,这个时候需要将多余的老节点从真实Dom中移除*/      
     removeVnodes(oldCh, oldStartIdx, oldEndIdx) //移除 oldStartIdx - oldEndIdx 之间的所有节点    
}

再回过头看我们的实例,新节点的数目大于旧节点,需要创建 newStartIdx 和 newEndIdx 之间的所有节点。在我们的实例中就是节点 F,因此直接创建 F 节点对应的真实节点放到 B 节点后面即可。 

640 (4).png

结尾


最后通过上述的源码和实例的分析,我们完成了 Vue 中 diff 算法的完整解读。如果想要了解更多的 Vue 源码。欢迎进入我们的 github地址(https://github.com/DQFE/vue)进行查看,里面对每一行 Vue 源码都做了注释,方便大家的理解。


扫描二维码推送至手机访问。

版权声明:本文由放牧的风发布,如需转载请注明出处。

本文链接:https://grazingwind.com/post/70.html

标签: VUEdiff
分享给朋友:

相关文章

webstorm中用npm运行任务(即显示npm面板)

webstorm中用npm运行任务(即显示npm面板)

第一步右击package.json文件,点击show npm Scripts第二步出现npm面板第三步点击即可运行任务  ...

如何理解HTTP响应的状态码?

如何理解HTTP响应的状态码?

我们知道HTTP协议是通过HTTP请求和HTTP响应来实现双向通信的。 HTTP状态码(HTTP Status Code)是用以表示Web服务器HTTP响应状态的3位数字代码,由RFC 2616规范定义。 合理的状态码不仅可以让用...

跨域资源共享 CORS 详解

跨域资源共享 CORS 详解

CORS是一个W3C标准,全称是"跨域资源共享"(Cross-origin resource sharing)。它允许浏览器向跨源服务器,发出XMLHttpRequest请求,从而克服了AJAX只能同源使用的限制。本文详...

经得住拷问的HTTPS原理解析

经得住拷问的HTTPS原理解析

此文涵盖的大致内容:理解HTTPS原理的概念什么是对称加密和非对称加密?什么是数字签名?怎么生成?怎么校验?啥时候是对称加密?啥时候是非对称加密?啥时候进行算法加密?什么算法?第三方机构包含哪些?HTTPS 是什么?具体流程HTTPS和HT...

彻底理解浏览器的缓存机制

彻底理解浏览器的缓存机制

概述浏览器的缓存机制也就是我们说的HTTP缓存机制,其机制是根据HTTP报文的缓存标识进行的,所以在分析浏览器缓存机制之前,我们先使用图文简单介绍一下HTTP报文,HTTP报文分为两种:HTTP请求(Request)报文,报文格式为:请求行...

前端性能优化的知识(上)

前端性能优化的知识(上)

前言引言反复看下以下三个问题。有木有不同的人问过你:什么是前端性能优化?有木有不同的面试官问过你:你为前端性能优化做过什么?有木有哪一次,你问过自己:别人问我前端性能优化到底应该如何答复?你有木有一套自己的关于性能优化的答案,能让技术大牛和...

评论列表

游客
6分钟前

我只是来赚积分的!http://zohl.wxsljd.net/test/353000104.html

游客
6分钟前

哥回复的不是帖子,是寂寞!http://sisy.cableshow.net/test/757137000.html

游客
6分钟前

东方不败还是灭绝师太啊?http://goby.cableshow.net/test/225938956.html

游客
11分钟前

这么好的帖子,应该加精华!https://sdceda.com/fei/772421623/

游客
13分钟前

大神好强大!https://sdceda.com/shi/305810539/

游客
15分钟前

这个帖子会火的,鉴定完毕!http://ymqd.gmpedu.net/test/162491299.html

游客
15分钟前

今天怎么了,什么人都出来了!http://qhfr.gmpedu.net/test/704819657.html

游客
17分钟前

收藏了,改天让朋友看看!http://lklm.cableshow.net/test/690537136.html

访客
21分钟前

58档口最新地址 https://b0594.com

游客
30分钟前

网页的加载速度非常快,不会影响用户体验。https://sdceda.com/shi/913118314/

游客
36分钟前

突然觉得楼主说的很有道理,赞一个!http://wocx.cableshow.net/test/825558520.html

游客
42分钟前

楼主发几张靓照啊!https://sdceda.com/fei/412407921/

游客
43分钟前

好帖子!http://ktez.xiehailong.net/test/833373849.html

游客
45分钟前

楼主很有激情啊!http://tmqw.cableshow.net/test/185413931.html

游客
50分钟前

白富美?高富帅?https://sdceda.com/shi/648883718/

游客
52分钟前

楼主的文笔不错!https://sdceda.com/lao/435457815/

游客
55分钟前

东方不败外加灭绝师太啊!http://pskc.zhujiajia.net/test/762556353.html

游客
55分钟前

无图无真相!http://vwml.zhujiajia.net/test/454485786.html

游客
1小时前

这个帖子好无聊啊!http://apur.zzshiyuan.net/test/423194177.html

游客
1小时前

收藏了,以后可能会用到!http://zjyx.ydhealthy.net/test/485782403.html

游客
1小时前

楼主的帖子实在是写得太好了。文笔流畅,修辞得体!https://sdceda.com/shi/420697944/

游客
1小时前

好无聊啊!https://sdceda.com/shi/356594552/

游客
1小时前

经典!https://sdceda.com/lao/099058237/

游客
1小时前

无图无真相!http://zerl.cableshow.net/test/520537716.html

游客
1小时前

楼主的帖子实在是写得太好了。文笔流畅,修辞得体!http://cfqx.cableshow.net/test/799522902.html

游客
1小时前

看了这么多帖子,第一次看到这么有深度了!http://qnpj.zhujiajia.net/test/136054751.html

游客
2小时前

顶顶更健康!https://sdceda.com/seo/044182239/

游客
2小时前

楼上的很有激情啊!http://qefr.xiehailong.net/test/985150124.html

游客
2小时前

楼主是在找骂么?http://syoz.zhujiajia.net/test/365510372.html

游客
2小时前

看了这么多帖子,第一次看到这么有深度了!http://vnwy.cableshow.net/test/841635398.html

游客
2小时前

看了这么多帖子,第一次看到这么高质量内容!http://udfk.zhiwuzubai.net/test/030620678.html

游客
2小时前

态度决定一切,不错!http://ziwe.cableshow.net/test/697789172.html

游客
2小时前

楼主主机很热情啊!http://obsy.cableshow.net/test/279894104.html

游客
2小时前

缺乏激情了!http://stlt.xiehailong.net/test/190549707.html

游客
2小时前

好东西,学习学习!http://pojp.xiehailong.net/test/472878672.html

游客
2小时前

支持楼上的!http://bcho.zhujiajia.net/test/546439979.html

游客
2小时前

太高深了,理解力不够用了!https://sdceda.com/seo/595978625/

游客
2小时前

这么经典的话只有楼主能想到!https://sdceda.com/shi/095271032/

游客
2小时前

楼主最近很消极啊!https://sdceda.com/laoliu/693257/

游客
2小时前

以后就跟楼主混了!https://sdceda.com/seo/490249291/

游客
2小时前

在这个版块混了这么久了,第一次看见这么给你的帖子!http://otpu.cableshow.net/test/118421549.html

游客
2小时前

收藏了,楼主加油!https://sdceda.com/shi/614137513/

游客
2小时前

有内涵!https://sdceda.com/shi/698555209/

游客
2小时前

收藏了,怕楼主删了!http://qezz.zhujiajia.net/test/724649958.html

游客
2小时前

鉴定完毕!https://sdceda.com/fei/225532907/

游客
2小时前

怪事年年有,今年特别多!http://wbtd.zhujiajia.net/test/745562247.html

游客
2小时前

有机会找楼主好好聊聊!http://whxn.wxpwlw.net/test/473384356.html

访客
2小时前

安福货源网58档口最新地址 https://www.z11.cn

游客
2小时前

楼主练了葵花宝典吧?http://fzfw.wxsljd.net/test/279653320.html

游客
2小时前

今天怎么了,什么人都出来了!http://bofx.yntvexp.net/test/835617664.html

游客
2小时前

楼上的真不讲道理!http://xbls.huilingtong.net/test/872359542.html

游客
2小时前

楼主的帖子越来越有深度了!http://wbbs.cableshow.net/test/630426696.html

游客
2小时前

吹牛的人越来越多了!http://pwwi.xiehailong.net/test/665165710.html

游客
2小时前

读了楼主的帖子,顿时马桶就通了。。。https://sdceda.com/fei/633179590/

游客
2小时前

楼主是一个典型的文艺青年啊!http://sbya.xiehailong.net/test/395944827.html

游客
2小时前

每次看到楼主的帖子都有惊吓!https://sdceda.com/shi/917687829/

游客
2小时前

楼上的别说的那么悲观好吧!https://sdceda.com/fei/972215574/

游客
3小时前

最近压力山大啊!http://imhp.cableshow.net/test/177076558.html

游客
3小时前

楼主练了葵花宝典吧?https://sdceda.com/fei/942430681/

游客
3小时前

楼主加油,看好你哦!http://v3hoc.ncsxzs.com/07/5.html

游客
3小时前

祖国尚未统一,我却天天灌水,好内疚!https://sdceda.com/lao/740435586/

游客
3小时前

收藏了,很不错的内容!http://cfvd.zlgas.net/test/227618641.html

访客
3小时前

福安图片 https://www.b0594.com

游客
3小时前

内容很有深度!https://sdceda.com/lao/901256147/

游客
3小时前

灌水不是我的目的!https://sdceda.com/lao/237264537/

游客
3小时前

今天是个特别的日子,值得纪念!http://puam.cableshow.net/test/238819231.html

游客
3小时前

勤奋灌水,天天向上!http://mycc.xiehailong.net/test/884629197.html

游客
3小时前

这个帖子好无聊啊!http://tlao.foxcup.net/test/390593487.html

游客
3小时前

楼主最近很消极啊!http://unzj.zlgas.net/test/514781213.html

游客
3小时前

看了这么多帖子,第一次看到这么经典的!http://1it.huibolt.com

游客
3小时前

大神就是大神,这么经典!http://xrif.xiehailong.net/test/341210726.html

游客
3小时前

以后就跟楼主混了!https://sdceda.com/fei/623602277/

游客
3小时前

这么好的帖子,应该加精华!http://txsd.zhujiajia.net/test/125077635.html

游客
3小时前

楼主发几张靓照啊!http://lttl.ezytkt.net/test/733806894.html

游客
4小时前

在这个版块混了这么久了,第一次看见这么给你的帖子!https://sdceda.com/fei/850573904/

游客
4小时前

有钱、有房、有车,人人都想!https://sdceda.com/shi/240142736/

游客
4小时前

看了这么多帖子,第一次看到这么高质量内容!http://akpk.cableshow.net/test/941052534.html

游客
4小时前

好好学习楼主的帖子!http://fqsv.xinroo.net/test/295406956.html

游客
4小时前

网页的加载速度非常快,不会影响用户体验。https://sdceda.com/fei/628108337/

游客
4小时前

看了这么多帖子,第一次看到这么有深度了!https://sdceda.com/shi/539072240/

游客
4小时前

一口气看完了,我要下去回味回味了!http://kibu.ewmo.net/test/660795558.html

游客
4小时前

楼主就是我的榜样哦http://awsc.scifine.net/test/253152392.html

游客
4小时前

楼上的说的很多!http://mksx.zfgbw.net/test/353338780.html

游客
4小时前

感觉不错!https://sdceda.com/fei/038918205/

游客
4小时前

楼主很有激情啊!http://xkiw.cableshow.net/test/715976685.html

游客
4小时前

论坛的帖子越来越有深度了!https://sdceda.com/seo/552828962/

游客
4小时前

林子大了,什么鸟都有了啊!http://vheb.ifccom.net/test/683360348.html

游客
4小时前

楼主发几张靓照啊!http://exbg.zhujiajia.net/test/114472261.html

游客
4小时前

楼主的头像能辟邪啊!https://sdceda.com/shi/453900126/

游客
4小时前

赞一个!http://bbtr.zhujiajia.net/test/740131560.html

游客
4小时前

楼上的真不讲道理!https://sdceda.com/laoliu/598868/

游客
4小时前

顶顶更健康!https://sdceda.com/seo/152027218/

游客
4小时前

今天过得很不爽!http://xpjg.xiehailong.net/test/760236698.html

游客
5小时前

刚分手,心情不好!http://yatl.zhujiajia.net/test/771865091.html

游客
5小时前

最近回了很多帖子,都没人理我!http://zeat.fiuedu.net/test/813400332.html

游客
5小时前

鉴定完毕!http://krta.ezytkt.net/test/886775048.html

游客
5小时前

楼主很有经验啊!https://sdceda.com/seo/785236883/

游客
5小时前

楼主主机很热情啊!http://avpx.huilingtong.net/test/906767905.html

游客
5小时前

支持一下,下面的保持队形!http://lpba.ezytkt.net/test/130457836.html

游客
5小时前

有钱、有房、有车,人人都想!http://tqxs.xiehailong.net/test/052306913.html

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。