前言

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

過程

假設當前有兩個數組arr1和arr2

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

那么其過程有五步

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的每個元素進行比較

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

如果是在末尾比較成功，那么比較的結束索引-1，當開頭索引大于結束索引時說明比較已經結束

拆解過程

let arr1 = [1,2,3,4,5]let arr2 = [4,3,5,1,2]let oldStartIdx = 0 let oldEndIdx = arr1.lenght -1let newStartIdx = 0let newEndIdx = arr2.length -1let 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和舊數組逐一比較，和索引為3的值相等，說明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和舊數組逐一比較，和索引為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已經從舊數組oldEndIdx位置移動到了newStartIdx位置,newStartIdx++, oldEndIdx-- 5. 第四步比較成功，進入下一輪 //比較成功后,使用u_3表示比較成功的元素 [1,2,u_2,u_1,u_3] //arr1 [u_1,u_2,u_3,1,2] //arr2第四輪： 1. 1和1比較相等,1已經從舊數組oldStartIdx位置移動到newStartIdx位置,oldStartIdx++,newStartIdx++ 2. 第一步比較成功，進入下一輪 3. 第一步比較成功，進入下一輪 4. 第一步比較成功，進入下一輪 5. 第一步比較成功，進入下一輪 //比較成功后,使用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已經從舊數組oldStartIdx位置移動到newStartIdx位置,oldStartIdx++,newStartIdx++ 2. 第一步比較成功，進入下一輪 3. 第一步比較成功，進入下一輪 4. 第一步比較成功，進入下一輪 5. 第一步比較成功，進入下一輪 //比較成功后,使用u_5表示比較成功的元素 [u_4,u_5,u_2,u_1,u_3] //arr1 [u_1,u_2,u_3,u_4,u_5] //arr2

用一個gif圖來表示

上代碼

function diff(prevChildren, nextChildren) { let oldStartIdx = 0 //舊數組起始索引 let oldEndIdx = prevChildren.length - 1 //舊數組結束索引 let newStartIdx = 0 //新數組其實索引 let newEndIdx = nextChildren.length - 1 //新數組結束索引 let oldStartVNode = prevChildren[oldStartIdx] let oldEndVNode = prevChildren[oldEndIdx] let newStartVNode = nextChildren[newStartIdx] let newEndVNode = nextChildren[newEndIdx] while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (!oldStartVNode) { //undefined 時前移一位 oldStartVNode = prevChildren[++oldStartIdx] } else if (!oldEndVNode) { //undefined 時后移一位 oldEndVNode = prevChildren[--oldEndIdx] } else if (oldStartVNode.key === newStartVNode.key ) { //1.開始與開始 oldStartVNode = prevChildren[++oldStartIdx] newStartVNode = nextChildren[++newStartIdx] } else if ( oldEndVNode.key === newEndVNode.key ) { //2.結束與結束 oldEndVNode = prevChildren[--oldEndIdx] newEndVNode = nextChildren[--newEndIdx] } else if (oldStartVNode.key === newEndVNode.key ) { //3.開始與結束 oldStartVNode = prevChildren[++oldStartIdx] newEndVNode = nextChildren[--newEndIdx] } else if (oldEndVNode.key === newStartVNode.key ) { //4.結束與開始 oldEndVNode = prevChildren[--oldEndIdx] newStartVNode = nextChildren[++newStartIdx] } else { //5.新數組開頭元素和舊數組每一個元素對比 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ā)現，上面的算法走完后，如果新舊兩個數組只是順序變化，那么它能完美的diff出差異，但是如果新數組有新增或者刪除的時候就不行了，因此我們在while循環(huán)完成后需要找出新增或者刪除的元素，那怎么知道哪些是新增哪些是刪除的元素呢？

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

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

因為循環(huán)條件的導致，這里會在5次while后就結束了，因此在數組末尾的6和7永遠走不了第五步的插入條件，那如何判斷6和7是新增的呢？我們來觀察一下while循環(huán)結束后的索引

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

我們發(fā)現，新增元素的索引和newStartIdx還有newEndIdx是一一對應的

例子1：newStartIdx小于newEndIdx，并且是5和6，而新增元素6對應在arr2的索引為6,新增元素7對應在arr2的索引為7，此時6和7都已經越界出arr1的長度范圍 例子2：newStartIdx是大于newEndIdx，沒有對應關系 例子3：newStartIdx等于newEndIdx，我們發(fā)現arr2索引為4的元素正是新增元素6，但是6次時沒有越界出arr1的長度范圍,它剛好在數組的最后一個元素 例子4：newStartIdx等于newEndIdx，arr2中索引為6的值正是新增元素6

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

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

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

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

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說明在舊數組中找到了，那么我們將preChildren[idxInOld]設置為undefined，也就是說2,3,5經過diff算法后，它們在arr1中的值已經被替換為了undefined，這里也是就為什么在diff算法開始需要判斷!oldStartVNode和!oldEndVnode的原因了,下面我們完善代碼

function diff(prevChildren, nextChildren) { let oldStartIdx = 0 //舊數組起始索引 let oldEndIdx = prevChildren.length - 1 //舊數組結束索引 let newStartIdx = 0 //新數組其實索引 let newEndIdx = nextChildren.length - 1 //新數組結束索引 let oldStartVNode = prevChildren[oldStartIdx] let oldEndVNode = prevChildren[oldEndIdx] let newStartVNode = nextChildren[newStartIdx] let newEndVNode = nextChildren[newEndIdx] while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (!oldStartVNode) { //undefined 時前移一位 oldStartVNode = prevChildren[++oldStartIdx] } else if (!oldEndVNode) { //undefined 時后移一位 oldEndVNode = prevChildren[--oldEndIdx] } else if (oldStartVNode.key === newStartVNode.key ) { //1.開始與開始 oldStartVNode = prevChildren[++oldStartIdx] newStartVNode = nextChildren[++newStartIdx] } else if ( oldEndVNode.key === newEndVNode.key ) { //2.結束與結束 oldEndVNode = prevChildren[--oldEndIdx] newEndVNode = nextChildren[--newEndIdx] } else if (oldStartVNode.key === newEndVNode.key ) { //3.開始與結束 oldStartVNode = prevChildren[++oldStartIdx] newEndVNode = nextChildren[--newEndIdx] } else if (oldEndVNode.key === newStartVNode.key ) { //4.結束與開始 oldEndVNode = prevChildren[--oldEndIdx] newStartVNode = nextChildren[++newStartIdx] } else { //5.新數組開頭元素和舊數組每一個元素對比 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) { //新增內容 let vnode = nextChildren[newStartIdx] } } else if (newStartIdx > newEndIdx) { for (let i = oldStartIdx; i <= oldEndIdx; i++) { / /刪除內容 } }}diff([1,2,3,4,5],[4,3,5,1,2])

接下來我們使用兩個gif圖來表示一下diff過程

1.新增元素

2.減少元素

以上就是詳解Vue2的diff算法的詳細內容，更多關于Vue2的diff算法的資料請關注好吧啦網其它相關文章！