第深入了解Vue中的雙端diff算法Vue和React都是基于vdom的前端框架，組件渲染會返回vdom，渲染器再把vdom通過增刪改的api同步到dom。

當再次渲染時，會產(chǎn)生新的vdom，渲染器會對比兩棵vdom樹，對有差異的部分通過增刪改的api更新到dom。

這里對比兩棵vdom樹，找到有差異的部分的算法，就叫做diff算法。

diff算法是渲染器中最復雜的部分，也是面試的熱點問題。今天我們就通過Vue的diff算法來探究下diff算法吧。

diff算法

我們知道，兩棵樹做diff，復雜度是O(n^3)的，因為每個節(jié)點都要去和另一棵樹的全部節(jié)點對比一次，這就是n了，如果找到有變化的節(jié)點，執(zhí)行插入、刪除、修改也是n的復雜度。所有的節(jié)點都是這樣，再乘以n，所以是O(n*n*n)的復雜度。

這樣的復雜度對于前端框架來說是不可接受的，這意味著1000個節(jié)點，渲染一次就要處理1000*1000*1000，一共10億次。

所以前端框架的diff約定了兩種處理原則：只做同層的對比，type變了就不再對比子節(jié)點。

因為dom節(jié)點做跨層級移動的情況還是比較少的，一般情況下都是同一層級的dom的增刪改。

這樣只要遍歷一遍，對比一下type就行了，是O(n)的復雜度，而且type變了就不再對比子節(jié)點，能省下一大片節(jié)點的遍歷。另外，因為vdom中記錄了關聯(lián)的dom節(jié)點，執(zhí)行dom的增刪改也不需要遍歷，是O(1)的，整體的diff算法復雜度就是O(n)的復雜度。

1000個節(jié)點渲染一次最多對比1000次，這樣的復雜度就是可接受的范圍了。

但是這樣的算法雖然復雜度低了，卻還是存在問題的。

比如一組節(jié)點，假設有5個，類型是ABCDE，下次渲染出來的是EABCD，這時候逐一對比，發(fā)現(xiàn)type不一樣，就會重新渲染這5個節(jié)點。

而且根據(jù)type不同就不再對比子節(jié)點的原則，如果這些節(jié)點有子節(jié)點，也會重新渲染。

dom操作是比較慢的，這樣雖然diff的算法復雜度是低了，重新渲染的性能也不高。

所以，diff算法除了考慮本身的時間復雜度之外，還要考慮一個因素：dom操作的次數(shù)。

上面那個例子的ABCDE變?yōu)镋ABCD，很明顯只需要移動一下E就行了，根本不用創(chuàng)建新元素。

但是怎么對比出是同個節(jié)點發(fā)生了移動呢？

判斷type么？那不行，同type的節(jié)點可能很多，區(qū)分不出來的。

最好每個節(jié)點都是有唯一的標識。

所以當渲染一組節(jié)點的時候，前端框架會讓開發(fā)者指定key，通過key來判斷是不是有點節(jié)點只是發(fā)生了移動，從而直接復用。

這樣，diff算法處理一組節(jié)點的對比的時候，就要根據(jù)key來再做一次算法的優(yōu)化。

我們會把基于key的兩組節(jié)點的diff算法叫做多節(jié)點diff算法，它是整個vdom的diff算法的一部分。

接下來我們來學習一下多節(jié)點diff算法：

簡單diff

假設渲染ABCD一組節(jié)點，再次渲染是DCAB，這時候怎么處理呢？

多節(jié)點diff算法的目的是為了盡量復用節(jié)點，通過移動節(jié)點代替創(chuàng)建。

所以新vnode數(shù)組的每個節(jié)點我們都要找下在舊vnode數(shù)組中有沒有對應key的，有的話就移動到新的位置，沒有的話再創(chuàng)建新的。

也就是這樣的：

constoldChildren=n1.children

constnewChildren=n2.children

letlastIndex=0

//遍歷新的children

for(leti=0;inewChildren.length;i++){

constnewVNode=newChildren[i]

letj=0

letfind=false

//遍歷舊的children

for(j;joldChildren.length;j++){

constoldVNode=oldChildren[j]

//如果找到了具有相同key值的兩個節(jié)點，則調(diào)用patch函數(shù)更新

if(newVNode.key===oldVNode.key){

find=true

patch(oldVNode,newVNode,contAIner)

處理移動...

break//跳出循環(huán)，處理下一個節(jié)點

//沒有找到就是新增了

if(!find){

constprevVNode=newChildren[i-1]

letanchor=null

if(prevVNode){

anchor=prevVNode.el.nextSibling

}else{

anchor=container.firstChild

patch(null,newVNode,container,anchor)

}

這里的patch函數(shù)的作用是更新節(jié)點的屬性，重新設置事件監(jiān)聽器。如果沒有對應的舊節(jié)點的話，就是插入節(jié)點，需要傳入一個它之后的節(jié)點作為錨點anchor。

我們遍歷處理新的vnode：

先從舊的vnode數(shù)組中查找對應的節(jié)點，如果找到了就代表可以復用，接下來只要移動就好了。

如果沒找到，那就執(zhí)行插入，錨點是上一個節(jié)點的nextSibling。

那如果找到了可復用的節(jié)點之后，那移動到哪里呢？

其實新的vnode數(shù)組中記錄的順序就是目標的順序。所以把對應的節(jié)點按照新vnode數(shù)組的順序來移動就好了。

constprevVNode=newChildren[i-1]

if(prevVNode){

constanchor=prevVNode.el.nextSibling

insert(newVNode.el,container,anchor)

}

要插入到i的位置，那就要取i-1位置的節(jié)點的nextSibling做為錨點來插入當前節(jié)點。

但是并不是所有的節(jié)點都需要移動，比如處理到第二個新的vnode，發(fā)現(xiàn)它在舊的vnode數(shù)組中的下標為4，說明本來就是在后面了，那就不需要移動了。反之，如果是vnode查找到的對應的舊的vnode在當前index之前才需要移動。

也就是這樣：

letj=0

letfind=false

//遍歷舊的children

for(j;joldChildren.length;j++){

constoldVNode=oldChildren[j]

//如果找到了具有相同key值的兩個節(jié)點，則調(diào)用patch函數(shù)更新之

if(newVNode.key===oldVNode.key){

find=true

patch(oldVNode,newVNode,container)

if(jlastIndex){//舊的vnode數(shù)組的下標在上一個index之前，需要移動

constprevVNode=newChildren[i-1]

if(prevVNode){

constanchor=prevVNode.el.nextSibling

insert(newVNode.el,container,anchor)

}else{//不需要移動

//更新lastIndex

lastIndex=j

break

}

查找新的vnode在舊的vnode數(shù)組中的下標，如果找到了的話，說明對應的dom就是可以復用的，先patch一下，然后移動。

移動的話判斷下下標是否在lastIndex之后，如果本來就在后面，那就不用移動，更新下lastIndex就行。

如果下標在lastIndex之前，說明需要移動，移動到的位置前面分析過了，就是就是新vnode數(shù)組i-1的后面。

這樣，我們就完成了dom節(jié)點的復用和移動。

新的vnode數(shù)組全部處理完后，舊的vnode數(shù)組可能還剩下一些不再需要的，那就刪除它們：

//遍歷舊的節(jié)點

for(leti=0;ioldChildren.length;i++){

constoldVNode=oldChildren[i]

//拿著舊VNode去新children中尋找相同的節(jié)點

consthas=newChildren.find(

vnode=vnode.key===oldVNode.key

if(!has){

//如果沒有找到相同的節(jié)點，則移除

unmount(oldVNode)

}

這樣，我們就完成了兩組vnode的diff和對應dom的增刪改。

小結一下：

diff算法的目的是根據(jù)key復用dom節(jié)點，通過移動節(jié)點而不是創(chuàng)建新節(jié)點來減少dom操作。

對于每個新的vnode，在舊的vnode中根據(jù)key查找一下，如果沒查找到，那就新增dom節(jié)點，如果查找到了，那就可以復用。

復用的話要不要移動要判斷下下標，如果下標在lastIndex之后，就不需要移動，因為本來就在后面，反之就需要移動。

最后，把舊的vnode中在新vnode中沒有的節(jié)點從dom樹中刪除。

這就是一個完整的diff算法的實現(xiàn)。

這個diff算法我們是從一端逐個處理的，叫做簡單diff算法。

簡單diff算法其實性能不是最好的，比如舊的vnode數(shù)組是ABCD，新的vnode數(shù)組是DABC，按照簡單diff算法，A、B、C都需要移動。

那怎么優(yōu)化這個算法呢？

從一個方向順序處理會有這個問題，那從兩個方向同時對比呢？

這就是雙端diff算法：

雙端diff

簡單diff算法能夠實現(xiàn)dom節(jié)點的復用，但有的時候會做一些沒必要的移動。雙端diff算法解決了這個問題，它是從兩端進行對比。

我們需要4個指針，分別指向新舊兩個vnode數(shù)組的頭尾：

頭和尾的指針向中間移動，直到oldStartIdx=oldEndIdx并且newStartIdx=newEndIdx，說明就處理完了全部的節(jié)點。

每次對比下兩個頭指針指向的節(jié)點、兩個尾指針指向的節(jié)點，頭和尾指向的節(jié)點，是不是key是一樣的，也就是可復用的。

如果是可復用的話就直接用，調(diào)用patch更新一下，如果是頭尾這種，還要移動下位置。

也就是這樣的：

while(oldStartIdx=oldEndIdxnewStartIdx=newEndIdx){

if(oldStartVNode.key===newStartVNode.key){//頭頭

patch(oldStartVNode,newStartVNode,container)

oldStartVNode=oldChildren[++oldStartIdx]

newStartVNode=newChildren[++newStartIdx]

}elseif(oldEndVNode.key===newEndVNode.key){//尾尾

patch(oldEndVNode,newEndVNode,container)

oldEndVNode=oldChildren[--oldEndIdx]

newEndVNode=newChildren[--newEndIdx]

}elseif(oldStartVNode.key===newEndVNode.key){//頭尾，需要移動

patch(oldStartVNode,newEndVNode,container)

insert(oldStartVNode.el,container,oldEndVNode.el.nextSibling)

oldStartVNode=oldChildren[++oldStartIdx]

newEndVNode=newChildren[--newEndIdx]

}elseif(oldEndVNode.key===newStartVNode.key){//尾頭，需要移動

patch(oldEndVNode,newStartVNode,container)

insert(oldEndVNode.el,container,oldStartVNode.el)

oldEndVNode=oldChildren[--oldEndIdx]

newStartVNode=newChildren[++newStartIdx]

}else{

//頭尾沒有找到可復用的節(jié)點

}

頭頭和尾尾的對比比較簡單，頭尾和尾頭的對比還要移動下節(jié)點。

比如舊vnode的頭節(jié)點是新的vnode的尾節(jié)點，那就要把它移動到舊的vnode的尾節(jié)點的位置。

也就是：

insert(oldStartVNode.el,container,oldEndVNode.el.nextSibling)

插入節(jié)點的錨點節(jié)點是oldEndVNode對應的dom節(jié)點的nextSibling。

如果舊vnode的尾節(jié)點是新vnode的頭結點，那就要把它移動到舊vnode的頭結點的位置。

也就是：

insert(oldEndVNode.el,container,oldStartVNode.el)

插入節(jié)點的錨點節(jié)點是oldStartVNode對應的dom節(jié)點（因為要插在它之前）。

從雙端進行對比，能盡可能的減少節(jié)點移動的次數(shù)。

當然，還要處理下如果雙端都沒有可復用節(jié)點的情況：

如果雙端都沒有可復用節(jié)點，那就在舊節(jié)點數(shù)組中找，找到了就把它移動過來，并且原位置置為undefined。沒找到的話就插入一個新的節(jié)點。

也就是這樣：

constidxInOld=oldChildren.findIndex(

node=node.key===newStartVNode.key

if(idxInOld0){

constvnodeToMove=oldChildren[idxInOld]

patch(vnodeToMove,newStartVNode,container)

insert(vnodeToMove.el,container,oldStartVNode.el)

oldChildren[idxInOld]=undefined

}else{

patch(null,newStartVNode,container,oldStartVNode.el)

}

因為有了一些undefined的節(jié)點，所以要加上空節(jié)點的處理邏輯：

if(!oldStartVNode){

oldStartVNode=oldChildren[++oldStartIdx]

}elseif(!oldEndVNode){

oldEndVNode=newChildren[--oldEndIdx]

}

這樣就完成了節(jié)點的復用和移動的邏輯。

那確實沒有可復用的節(jié)點的那些節(jié)點呢？

經(jīng)過前面的移動之后，剩下的節(jié)點都被移動到了中間，如果新vnode有剩余，那就批量的新增，如果舊vnode有剩余那就批量的刪除。

因為前面一個循環(huán)的判斷條件是oldStartIdx=oldEndIdxnewStartIdx=newEndIdx，這樣如果oldvnode多了，最后newStartIdx會小于newEndIdx。如果newvnode多了，最后oldStartIdx會小于oldEndIdx。

所以判斷條件是這樣的：

if(oldEndIdxoldStartIdxnewStartIdx=newEndIdx){

//添加新節(jié)點

for(leti=newStartIdx;i=newEndIdx;i++){

patch(null,newChildren[i],container,oldStartVNode.el)

}elseif(newEndIdxnewStartIdxoldStartIdx=oldEndIdx){

//移除操作

for(leti=oldStartIdx;i=oldEndIdx;i++){

unmount(oldChildren[i])

}

這樣就是一個完整的diff算法了，包括查找可復用節(jié)點和移動節(jié)點、新增和刪除節(jié)點。

而且因為從兩側查找節(jié)點，會比簡單diff算法性能更好一些。

比如ABCD到DABC，簡單diff算法需要移動ABC三個節(jié)點，而雙端diff算法只需要移動D一個節(jié)點。

小結一下：

雙端diff是頭尾指針向中間移動的同時，對比頭頭、尾尾、頭尾、尾頭是否可以復用，如果可以的話就移動對應的dom節(jié)點。

如果頭尾沒找到可復用節(jié)點就遍歷vnode數(shù)組來