前言Vue数据渲染的核心部分就是diff算法的应用。本文从源码入手，结合实例，一步步分析diff算法的整个过程。diff算法简介diff算法是一种比较同级树节点的高效算法，避免了逐层查找和遍历树，所以时间复杂度仅为O(n)。很多场景都会用到diff算法。比如Vue虚拟dom渲染成真实dom时，新旧VNode节点对比更新。使用了这个算法。diff算法有两个显着的特点：1.只会在同一层次进行比较，不会跨层次比较。2.diff比较过程中，循环从两边向中间收集diff过程。基于对diff过程的理解和对vue源码的学习，我们通过对vue源码的解读和实例分析，理清了diff算法的整个过程。下面将整个diff过程分为三步具体分析：第一步是在vue的虚拟dom渲染真实dom的过程中标记新旧VNode的起止位置：oldStartIdx,oldEndIdx,newStartIdx,newEndIdx。letoldStartIdx=0//老节点开始下标letnewStartIdx=0//新节点开始下标letoldEndIdx=oldCh.length-1//老节点结束下标letoldStartVnode=oldCh[0]//老节点开始vnodeletoldEndVnode=oldCh[oldEndIdx]//旧节点结束vnodeletnewEndIdx=newCh.length-1//新节点结束下标letnewStartVnode=newCh[0]//新节点开始vnodeletnewEndVnode=newCh[newEndIdx]//新节点结束vnode经过第一步后，我们初始的新旧VNode节点如下图所示：第二步标记节点位置后，开始进入while循环处理，这里是diff算法的核心流程，根据情况更新，比较旧节点，移动对应的VNode节点。while循环的退出条件是直到旧节点或新节点的起始位置大于结束位置。while(oldStartIdx<=oldEndIdx&&newStartIdx<=newEndIdx){....//处理逻辑}下面详细介绍while循环中的处理逻辑。节点，如果有相同的节点满足sameVnode（可以复用的相同节点），则直接执行patchVnode（该方法进行节点复用处理），并根据具体情况，移动新旧的VNode索引节点从而进入下一个循环处理，总共有2*2=4种情况。下面根据代码进行分析：情况一：当新旧VNode的start遇到sameVnode时，直接patchVnode，同时新旧VNode的start索引加1。如果(sameVnode(oldStartVnode,newStartVnode)){patchVnode(oldStartVnode,newStartVnode,insertedVnodeQueue,newCh,newStartIdx)oldStartVnode=oldCh[++oldStartIdx]newStartVnode=newCh[++newStartIdx]}情况二：当新旧VNode结束时遇到sameVnode，直接patchVnode，同时新旧VNode节点的endindex都减1。elseif(sameVnode(oldEndVnode,newEndVnode)){patchVnode(oldEndVnode,newEndVnode,insertedVnodeQueue,newCh,newEndIdx)oldEndVnode=oldCh[--oldEndIdx]newEndVnode=newCh[--newEndIdx]}情况三：开始时和结束时newVNode遇到sameVnode，说明本次数据更新后oldStartVnode已经移到了oldEndVnode后面。这时候patchVnode之后，需要把当前真正的dom节点移到oldEndVnode后面。同时，旧VNode节点的起始索引加1，新VNode节点的结束索引减1。elseif(sameVnode(oldStartVnode,newEndVnode)){//Vnode右移patchVnode(oldStartVnode,newEndVnode,insertedVnodeQueue,newCh,newEndIdx)canMove&&nodeOps.insertBefore(parentElm,oldStartVnode.elm,nodeOps.nextSibling(oldEndVoldStart.elm)=oldCh[++oldStartIdx]newEndVnode=newCh[--newEndIdx]}情况4：当oldVNode节点的end和newVNode节点的start遇到同一个Vnode，说明本次数据更新后oldEndVnode跑在了oldStartVnode之前。这时候在patchVnode之后，需要把当前真正的dom节点移到oldStartVnode的前面。同时，旧VNode节点的结束索引减1，新VNode节点的起始索引增加1。elseif(sameVnode(oldEndVnode,newStartVnode)){//Vnode左移patchVnode(oldEndVnode,newStartVnode,insertedVnodeQueue,newCh,newStartIdx)canMove&&nodeOps.insertBefore(parentElm,oldEndVnode.elm,oldStartVnode.elm)oldEnd--Vnode=oldCh[oldEndIdx]newStartVnode=newCh[++newStartIdx]}如果以上四种都不是条件满足，就意味着没有相同的节点可以重复使用，所以通过查找预先建立的旧VNode作为键值，对应的索引序列就是value值的哈希表。从此哈希表中找到与newStartVnode具有相同键的旧VNode节点。如果两者都满足sameVnode条件，则在执行patchVnode时将realdom移动到oldStartVnode对应的realdom前面；如果没有找到，则说明当前索引下新的VNode节点在旧的VNode队列中不存在，该节点不能被复用，只能调用createElm创建一个新的dom节点放到当前newStartIdx的位置。else{//如果没有找到相同的可重用节点，则创建一个新节点进行处理/*生成一个哈希表，其key对应于旧VNode的key（只有第一次输入undefined时才会生成,后面还会用到重复检测比如childre是这样的[{xx:xx,key:'key0'},{xx:xx,key:'key1'},{xx:xx,key:'key2'}]beginIdx=0endIdx=2结果生成{key0:0,key1:1,key2:2}*/if(isUndef(oldKeyToIdx))oldKeyToIdx=createKeyToOldIdx(oldCh,oldStartIdx,oldEndIdx)/*IfnewStartVnode新VNode节点存在key和this如果在oldVnode中能找到key，则返回该节点的idxInOld（即节点个数，下标）*/idxInOld=isDef(newStartVnode.key)?oldKeyToIdx[newStartVnode.key]:findIdxInOld(newStartVnode,oldCh,oldStartIdx,oldEndIdx)if(isUndef(idxInOld)){//新元素/*newStartVnode没有key或者旧节点没有找到key，然后创建一个newnode*/createElm(newStartVnode,insertedVnodeQueue,parentElm,oldStartVnode.elm,false,newCh,newStartIdx)}else{/*获取具有相同键的旧节点*/vnodeToMove=oldCh[idxInOld]if(sameVnode(vnodeToMove,newStartVnode)){/*如果新的VNode是with如果得到的key相同的节点是同一个VNode，则patchVnode*/patchVnode(vnodeToMove,newStartVnode,insertedVnodeQueue,newCh,newStartIdx)//因为patchVnode已经进入了，旧节点赋值为undefinedoldCh[idxInOld]=undefined/*有flag时，canMove可以直接插入到oldStartVnode对应的真实Dom节点前面*/canMove&&nodeOps.insertBefore(parentElm,vnodeToMove.elm,oldStartVnode.elm)}else{//相同key不同元素。treatasnewelement/*当新的VNode与找到的具有相同key的VNode不是同一个VNode时（例如标签不同或者输入标签类型不同），创建一个新节点*/createElm(newStartVnode,insertedVnodeQueue,parentElm,oldStartVnode.elm,false,newCh,newStartIdx)}}newStartVnode=newCh[++newStartIdx]}让我们再看看我们的例子。在第一次循环后，我们发现旧节点的结尾与新节点的开头相同（均为D）。所以直接复用D节点作为diff之后创建的第一个真实节点。同时将老节点的endIndex移动到C，新节点的startIndex移动到C。然后开始第二次循环。第二次循环后，旧节点的结尾和新节点的开头（都是C）相同。同理，将diff后创建的C的真实节点插入到第一个创建的节点B的Behind中。同时将老节点的endIndex移动到B，新节点的startIndex移动到E。在接下来的第三个循环中，发现patchVnode的四种情况都不匹配，所以当前在旧节点队列中查找新节点E，发现没有找到。此时只能直接创建一个新的真实节点E，插入到第二个创建的C节点之后。同时将新节点的startIndex移动到A，老节点的startIndex和endIndex保持不变。![]第四次循环，发现新旧节点（都是A）的开头是一样的，所以在diff之后创建A的真实节点，插入到上次创建的E节点后面。同时将旧节点的startIndex移动到B，将新节点的startIndex移动到B。第五次循环，情况同第四次循环，所以创建了真正的节点B在diff之后插入到之前创建的A节点后面。同时将旧节点的startIndex移到C，新节点的startIndex移到F，此时发现旧节点的startIndex大于endIndex。不再满足循环的条件。所以结束循环，然后按照后面的逻辑进行。第三步，while循环结束后根据新老节点的个数增加或删除相应的节点。如果新节点的数量大于旧节点的数量，则需要创建额外的节点并将其添加到真实dom中。反之，如果旧节点数大于新节点数，则需要将多余的旧节点从真实dom中删除。至此整个diff过程就完成了。if(oldStartIdx>oldEndIdx){/*所有比较完成后，如果找到oldStartIdx>oldEndIdx，则说明旧节点遍历完毕，新节点多于旧节点，所以需要多出的新节点一个一个创建并添加到真实的InDom*/refElm=isUndef(newCh[newEndIdx+1])?null:newCh[newEndIdx+1].elmaddVnodes(parentElm,refElm,newCh,newStartIdx,newEndIdx,insertedVnodeQueue)//创建newStartIdx-newEndIdx之间的所有节点}elseif(newStartIdx>newEndIdx){/*如果找到newStartIdx>newEndIdx全部比较完成后，表示遍历完新节点，旧节点多于新节点。这时候需要把多余的旧节点从真实的Dom中移走Except*/removeVnodes(oldCh,oldStartIdx,oldEndIdx)//移除oldStartIdx-oldEndIdx之间的所有节点}回头看我们的例子，新节点的数量更大比老节点要大，newStartIdx和newEndIdx之间的所有节点都需要创建。在我们的例子中，是节点F，所以直接创建节点F对应的真实节点，放在节点B的后面。最后，通过上面源码和例子的分析，我们完成了对diff算法的完整解读看。如果你想了解更多Vue源码。欢迎到我们的github查看。Vue源码分析还有其他几篇文章。另外，对Vue项目的每一行源码都做了注释，方便大家理解。~~~~
