詳解Vue2的diff算法

更新時(shí)間：2021年01月06日 09:03:42 作者：啥都不會(huì)的前端CV獅

這篇文章主要介紹了Vue2的diff算法的相關(guān)資料，幫助大家更好的理解和使用vue框架，感興趣的朋友可以了解下

前言

雙端比較算法是vue2.x采用的diff算法，本篇文章只是對(duì)雙端比較算法粗略的過(guò)程進(jìn)行了一下分析，具體細(xì)節(jié)還是得Vue源碼，Vue的源碼在這

過(guò)程

假設(shè)當(dāng)前有兩個(gè)數(shù)組arr1和arr2

let arr1 = [1,2,3,4,5]
let arr2 = [4,3,5,1,2]

那么其過(guò)程有五步

arr1[0] 和 arr2[0]比較
arr1[ arr1.length-1 ] 和 arr2[ arr2.length-1 ] 比較
arr1[0] 和 arr2[ arr2.length-1 ] 比較
arr1[ arr1.length-1 ] 和 arr2[0] 比較
arr2[0] 和 arr1的每個(gè)元素進(jìn)行比較

每次比較都是從數(shù)組的兩端開(kāi)始比較，如果是首位比較相等，那么比較的開(kāi)頭索引+1

如果是在末尾比較成功，那么比較的結(jié)束索引-1，當(dāng)開(kāi)頭索引大于結(jié)束索引時(shí)說(shuō)明比較已經(jīng)結(jié)束

拆解過(guò)程

let arr1 = [1,2,3,4,5]
let arr2 = [4,3,5,1,2]

let oldStartIdx = 0 
let oldEndIdx = arr1.lenght -1
let newStartIdx = 0
let newEndIdx = arr2.length -1

let oldStartVNode = arr1[oldStartIdx]   
let oldEndVNode = arr1[oldEndIdx]  
let newStartVNode = arr2[newStartIdx]  
let newEndVNode = arr2[newEndIdx]

第一輪：
 1. 1和4比較不相等
 2. 5和2比較不相等
 3. 1和2比較不相等
 4. 5和4比較不相等
 5. 4和舊數(shù)組逐一比較，和索引為3的值相等，說(shuō)明4由索引3變換位置為了0， newStartIdx++
 //比較完后,使用u_1表示比較成功的元素
 [1,2,3,u_1,5] //arr1
 [u_1,3,5,1,2] //arr2

第二輪：
 1. 1和3比較不相等
 2. 5和2比較不相等
 3. 1和2比較不相等
 4. 5和3比較不相等
 5. 3和舊數(shù)組逐一比較，和索引為2的值相等，3由索引2變換位置為了0， newStartIdx++
 //比較成功后,使用u_2表示比較成功的元素
 [1,2,u_2,u_1,5] //arr1
 [u_1,u_2,5,1,2] //arr2

第三輪： 
 1. 1和5比較不相等 
 2. 5和2比較不相等 
 3. 1和2比較不相等 
 4. 5和5比較相等,5已經(jīng)從舊數(shù)組oldEndIdx位置移動(dòng)到了newStartIdx位置,newStartIdx++, oldEndIdx-- 
 5. 第四步比較成功，進(jìn)入下一輪 
 //比較成功后,使用u_3表示比較成功的元素 
 [1,2,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,1,2] //arr2

第四輪： 
 1. 1和1比較相等,1已經(jīng)從舊數(shù)組oldStartIdx位置移動(dòng)到newStartIdx位置,oldStartIdx++,newStartIdx++ 
 2. 第一步比較成功，進(jìn)入下一輪 3. 第一步比較成功，進(jìn)入下一輪 
 4. 第一步比較成功，進(jìn)入下一輪 5. 第一步比較成功，進(jìn)入下一輪 
 //比較成功后,使用u_4表示比較成功的元素 
 [u_4,2,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,u_4,2] //arr2


第五輪： 
 1. 2和2比較相等,1已經(jīng)從舊數(shù)組oldStartIdx位置移動(dòng)到newStartIdx位置,oldStartIdx++,newStartIdx++ 
 2. 第一步比較成功，進(jìn)入下一輪 
 3. 第一步比較成功，進(jìn)入下一輪 
 4. 第一步比較成功，進(jìn)入下一輪 
 5. 第一步比較成功，進(jìn)入下一輪 
 //比較成功后,使用u_5表示比較成功的元素 
 [u_4,u_5,u_2,u_1,u_3] //arr1 
 [u_1,u_2,u_3,u_4,u_5] //arr2

用一個(gè)gif圖來(lái)表示

上代碼

function diff(prevChildren, nextChildren) {  
 let oldStartIdx = 0 //舊數(shù)組起始索引  
 let oldEndIdx = prevChildren.length - 1 //舊數(shù)組結(jié)束索引  
 let newStartIdx = 0 //新數(shù)組其實(shí)索引  
 let newEndIdx = nextChildren.length - 1 //新數(shù)組結(jié)束索引  
 
 let oldStartVNode = prevChildren[oldStartIdx]   
 let oldEndVNode = prevChildren[oldEndIdx]  
 let newStartVNode = nextChildren[newStartIdx]  
 let newEndVNode = nextChildren[newEndIdx]  
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {   
  if (!oldStartVNode) { 
  //undefined 時(shí)前移一位    
  oldStartVNode = prevChildren[++oldStartIdx]   
 } else if (!oldEndVNode) { 
  //undefined 時(shí)后移一位    
  oldEndVNode = prevChildren[--oldEndIdx]   
 } else if (oldStartVNode.key === newStartVNode.key ) { //1.開(kāi)始與開(kāi)始    
  oldStartVNode = prevChildren[++oldStartIdx]    
  newStartVNode = nextChildren[++newStartIdx]   
 } else if ( oldEndVNode.key === newEndVNode.key ) { //2.結(jié)束與結(jié)束     
  oldEndVNode = prevChildren[--oldEndIdx]    
  newEndVNode = nextChildren[--newEndIdx]   
 } else if (oldStartVNode.key === newEndVNode.key ) { //3.開(kāi)始與結(jié)束    
  oldStartVNode = prevChildren[++oldStartIdx]    
  newEndVNode = nextChildren[--newEndIdx]   
 } else if (oldEndVNode.key === newStartVNode.key ) { //4.結(jié)束與開(kāi)始     
  oldEndVNode = prevChildren[--oldEndIdx]    
  newStartVNode = nextChildren[++newStartIdx]   
 } else {
  //5.新數(shù)組開(kāi)頭元素和舊數(shù)組每一個(gè)元素對(duì)比    
  const idxInOld = prevChildren.findIndex((node) => {     
   if (node && node.key === newStartVNode.key) {      
   return true     
   }     
  })    
  if (idxInOld >= 0) {     
   prevChildren[idxInOld] = undefined    
  } else {     
   //newStartVNode是新元素    
  }    
  newStartVNode = nextChildren[++newStartIdx]   
 }  
 } 
}


diff([1,2,3,4,5],[4,3,5,1,2])

我們發(fā)現(xiàn)，上面的算法走完后，如果新舊兩個(gè)數(shù)組只是順序變化，那么它能完美的diff出差異，但是如果新數(shù)組有新增或者刪除的時(shí)候就不行了，因此我們?cè)趙hile循環(huán)完成后需要找出新增或者刪除的元素，那怎么知道哪些是新增哪些是刪除的元素呢？

在比較的第五步，選取的新數(shù)組的第一個(gè)元素和舊數(shù)組的所有元素逐一對(duì)比，這里我們就可以得出了這個(gè)數(shù)組是否是新增，如果對(duì)比相等，那就是位置變換，否則當(dāng)前元素就是新增的，但是，while循環(huán)的條件是oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx，如果是以下情況

let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7]

因?yàn)檠h(huán)條件的導(dǎo)致，這里會(huì)在5次while后就結(jié)束了，因此在數(shù)組末尾的6和7永遠(yuǎn)走不了第五步的插入條件，那如何判斷6和7是新增的呢？我們來(lái)觀察一下while循環(huán)結(jié)束后的索引

//例子1
let arr1 = [1,2,3,4,5]
let arr2 = [1,2,3,4,5,6,7]
//diff后它們的索引為
oldStartIdx = 5, oldEndIdx = 4
newStartIdx = 5, newEndIdx = 6

//例子2
let arr1 = [1,2,3,4,5]
let arr2 = [4,5,6,7,1,3,2]
//diff后它們的索引為
oldStartIdx = 3, oldEndIdx = 2
newStartIdx = 6, newEndIdx = 5

//例子3
let arr1 = [1,2,3,4,5]
let arr2 = [7,1,3,5,6,4,2]
//diff后它們的索引為
oldStartIdx = 5, oldEndIdx = 4
newStartIdx = 4, newEndIdx = 4

//例子4
let arr1 = [1,2,3,4,5]
let arr2 = [2,4,1,5,7,3,6]
//diff后它們的索引為
oldStartIdx = 3, oldEndIdx = 2
newStartIdx = 6, newEndIdx = 6

我們發(fā)現(xiàn)，新增元素的索引和newStartIdx還有newEndIdx是一一對(duì)應(yīng)的

例子1：newStartIdx小于newEndIdx，并且是5和6，而新增元素6對(duì)應(yīng)在arr2的索引為6,新增元素7對(duì)應(yīng)在arr2的索引為7，此時(shí)6和7都已經(jīng)越界出arr1的長(zhǎng)度范圍
例子2：newStartIdx是大于newEndIdx，沒(méi)有對(duì)應(yīng)關(guān)系
例子3：newStartIdx等于newEndIdx，我們發(fā)現(xiàn)arr2索引為4的元素正是新增元素6，但是6次時(shí)沒(méi)有越界出arr1的長(zhǎng)度范圍,它剛好在數(shù)組的最后一個(gè)元素
例子4：newStartIdx等于newEndIdx，arr2中索引為6的值正是新增元素6

那么得出的結(jié)論就是，如果在while循環(huán)結(jié)束后，如果newStartIdx是小于或者等于newEndIdx，那么在newStartIdx和newEndIdx索引之間對(duì)應(yīng)的元素就是新增的元素，并且oldStartIdx總是比oldEndIdx大

上面說(shuō)完了新增，那如果是刪除元素呢?看例子

//例子1
let arr1 = [4,3,5,6,7,2,1]
let arr2 = [1,3,5,4,2]
//diff后它們的索引為
oldStartIdx = 3, oldEndIdx = 4
newStartIdx = 3, newStartIdx = 2

//例子2
let arr1 = [7,2,3,5,6,1,4]
let arr2 = [5,1,2,3,4]
//diff后它們的索引為
oldStartIdx = 0, oldEndIdx = 4
newStartIdx = 4, newStartIdx = 3

//例子3
let arr1 = [1,5,4,2,6,7,3]
let arr2 = [4,5,1,2,3]
//diff后它們的索引為
oldStartIdx = 4, oldEndIdx = 5
newStartIdx = 4, newStartIdx = 3

同理新增的觀察套路，發(fā)現(xiàn)newStartIdx總是比newStartIdx大，并且需要?jiǎng)h除的元素總是在oldStartIdx和oldEndIdx對(duì)應(yīng)的索引之間，那么我們只需要把oldStartIdx和oldEndIdx的元素刪除即可，那問(wèn)題來(lái)了，像例子2 中oldStartIdx和oldEndIdx索引之間的元素有7,2,3,5,6其中真正需要?jiǎng)h除的只有7和6，這樣子不就誤刪了2,3,5么？關(guān)鍵的來(lái)了，我們看例子2的2,3,5發(fā)現(xiàn)它們走的都是雙端比較算法的第五步，第五步寫(xiě)的代碼是

 const idxInOld = prevChildren.findIndex((node) => {     
  if (node && node.key === newStartVNode.key) {      
   return true     
  }     
 })    
 if (idxInOld >= 0) {     
  prevChildren[idxInOld] = undefined    
 } else {     
 //newStartVNode是新元素    
 }    
 newStartVNode = nextChildren[++newStartIdx]

如果idxInOld>0說(shuō)明在舊數(shù)組中找到了，那么我們將preChildren[idxInOld]設(shè)置為undefined，也就是說(shuō)2,3,5經(jīng)過(guò)diff算法后，它們?cè)赼rr1中的值已經(jīng)被替換為了undefined，這里也是就為什么在diff算法開(kāi)始需要判斷!oldStartVNode和!oldEndVnode的原因了,下面我們完善代碼

function diff(prevChildren, nextChildren) { 
 let oldStartIdx = 0 //舊數(shù)組起始索引 
 let oldEndIdx = prevChildren.length - 1 //舊數(shù)組結(jié)束索引 
 let newStartIdx = 0 //新數(shù)組其實(shí)索引 
 let newEndIdx = nextChildren.length - 1 //新數(shù)組結(jié)束索引 

 let oldStartVNode = prevChildren[oldStartIdx]  
 let oldEndVNode = prevChildren[oldEndIdx] 
 let newStartVNode = nextChildren[newStartIdx] 
 let newEndVNode = nextChildren[newEndIdx] 
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {  
  if (!oldStartVNode) { //undefined 時(shí)前移一位   
   oldStartVNode = prevChildren[++oldStartIdx]  
  } else if (!oldEndVNode) { 
   //undefined 時(shí)后移一位   
   oldEndVNode = prevChildren[--oldEndIdx]  
  } else if (oldStartVNode.key === newStartVNode.key ) { //1.開(kāi)始與開(kāi)始   
   oldStartVNode = prevChildren[++oldStartIdx]   
   newStartVNode = nextChildren[++newStartIdx]  
  } else if ( oldEndVNode.key === newEndVNode.key ) { //2.結(jié)束與結(jié)束    
   oldEndVNode = prevChildren[--oldEndIdx]   
   newEndVNode = nextChildren[--newEndIdx]  
  } else if (oldStartVNode.key === newEndVNode.key ) { //3.開(kāi)始與結(jié)束   
   oldStartVNode = prevChildren[++oldStartIdx]   
   newEndVNode = nextChildren[--newEndIdx]  
  } else if (oldEndVNode.key === newStartVNode.key ) { //4.結(jié)束與開(kāi)始    
   oldEndVNode = prevChildren[--oldEndIdx]   
   newStartVNode = nextChildren[++newStartIdx]  
  } else {   
    //5.新數(shù)組開(kāi)頭元素和舊數(shù)組每一個(gè)元素對(duì)比   
   const idxInOld = prevChildren.findIndex((node) => {    
    if (node && node.key === newStartVNode.key) {     
     return true    
    }    
   })   
   if (idxInOld >= 0) {    
    prevChildren[idxInOld] = undefined   
   } else {    
    //newStartVNode是新元素   
   }   
   newStartVNode = nextChildren[++newStartIdx]  
  } 
 } 
 if (oldStartIdx > oldEndIdx) {    
 for (; newStartIdx <= newEndIdx; ++newStartIdx) {   
 //新增內(nèi)容   
 let vnode = nextChildren[newStartIdx]   
 } 
 } else if (newStartIdx > newEndIdx) {  
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {   /
   /刪除內(nèi)容  
 } 
 }
}

diff([1,2,3,4,5],[4,3,5,1,2])

接下來(lái)我們使用兩個(gè)gif圖來(lái)表示一下diff過(guò)程

1.新增元素