詳解vue3.0 diff算法的使用(超詳細)

更新時間：2020年07月01日 11:05:15 作者：alien

這篇文章主要介紹了詳解vue3.0 diff算法的使用，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言：隨之vue3.0beta版本的發(fā)布，vue3.0正式版本相信不久就會與我們相遇。尤玉溪在直播中也說了vue3.0的新特性typescript強烈支持，proxy響應(yīng)式原理，重新虛擬dom，優(yōu)化diff算法性能提升等等。小編在這里仔細研究了vue3.0beta版本diff算法的源碼，并希望把其中的細節(jié)和奧妙和大家一起分享。

首先我們來思考一些大中廠面試中，很容易問到的問題：

1 什么時候用到diff算法，diff算法作用域在哪里？

2 diff算法是怎么運作的，到底有什么作用？

3 在v-for 循環(huán)列表 key 的作用是什么

4 用索引index做key真的有用？到底用什么做key才是最佳方案。

如果遇到這些問題，大家是怎么回答的呢？我相信當(dāng)你讀完這篇文章，這些問題也會迎刃而解。

一什么時候用到了diff算法,diff算法作用域？

1.1diff算法的作用域

patch概念引入

在vue update過程中在遍歷子代vnode的過程中，會用不同的patch方法來patch新老vnode，如果找到對應(yīng)的 newVnode 和 oldVnode,就可以復(fù)用利用里面的真實dom節(jié)點。避免了重復(fù)創(chuàng)建元素帶來的性能開銷。畢竟瀏覽器創(chuàng)造真實的dom，操縱真實的dom，性能代價是昂貴的。

patch過程中，如果面對當(dāng)前vnode存在有很多chidren的情況,那么需要分別遍歷patch新的children Vnode和老的 children vnode。

存在chidren的vnode類型

首先思考一下什么類型的vnode會存在children。

①element元素類型vnode

第一中情況就是element類型vnode 會存在 children vode，此時的三個span標(biāo)簽就是chidren vnode情況

<div>
  <span> 蘋果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鴨梨🍐 </span>
</div>

在vue3.0源碼中，patchElement用于處理element類型的vnode ②flagment碎片類型vnode

在Vue3.0中，引入了一個fragment碎片概念。

你可能會問，什么是碎片？如果你創(chuàng)建一個Vue組件，那么它只能有一個根節(jié)點。

<template>
  <span> 蘋果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鴨梨🍐 </span>
</template>

這樣可能會報出警告，原因是代表任何Vue組件的Vue實例需要綁定到一個單一的DOM元素中。唯一可以創(chuàng)建一個具有多個DOM節(jié)點的組件的方法就是創(chuàng)建一個沒有底層Vue實例的功能組件。

flagment出現(xiàn)就是用看起來像一個普通的DOM元素，但它是虛擬的，根本不會在DOM樹中呈現(xiàn)。這樣我們可以將組件功能綁定到一個單一的元素中，而不需要創(chuàng)建一個多余的DOM節(jié)點。

 <Fragment>
  <span> 蘋果🍎 </span> 
  <span> 香蕉🍌 </span>
  <span> 鴨梨🍐 </span>
</Fragment>

在vue3.0源碼中，processFragment用于處理Fragment類型的vnode

1.2 patchChildren

從上文中我們得知了存在children的vnode類型，那么存在children就需要patch每一個

children vnode依次向下遍歷。那么就需要一個patchChildren方法，依次patch子類vnode。

patchChildren

vue3.0中在patchChildren方法中有這么一段源碼

if (patchFlag > 0) {
   if (patchFlag & PatchFlags.KEYED_FRAGMENT) { 
     /* 對于存在key的情況用于diff算法 */
    patchKeyedChildren(
     c1 as VNode[],
     c2 as VNodeArrayChildren,
     container,
     anchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
    return
   } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
     /* 對于不存在key的情況,直接patch */
    patchUnkeyedChildren( 
     c1 as VNode[],
     c2 as VNodeArrayChildren,
     container,
     anchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
    return
   }
  }

patchChildren根據(jù)是否存在key進行真正的diff或者直接patch。既然diff算法存在patchChildren方法中，而patchChildren方法用在Fragment類型和element類型的vnode中，這樣也就解釋了diff算法的作用域是什么。 1.3 diff算法作用？

通過前言我們知道，存在這children的情況的vnode，需要通過patchChildren遍歷children依次進行patch操作，如果在patch期間，再發(fā)現(xiàn)存在vnode情況，那么會遞歸的方式依次向下patch，那么找到與新的vnode對應(yīng)的vnode顯的如此重要。

我們用兩幅圖來向大家展示vnode變化。

如上兩幅圖表示在一次更新中新老dom樹變化情況。

假設(shè)不存在diff算法，依次按照先后順序patch會發(fā)生什么

如果 不存在diff算法 ，而是直接patchchildren 就會出現(xiàn)如下圖的邏輯。

第一次patchChidren

第二次patchChidren

第三次patchChidren‘

第四次patchChidren

如果沒有用到diff算法，而是依次patch虛擬dom樹，那么如上稍微 修改dom順序 ，就會在patch過程中沒有一對正確的新老vnode，所以老vnode的節(jié)點沒有一個可以復(fù)用，這樣就需要重新創(chuàng)造新的節(jié)點，浪費了性能開銷，這顯然不是我們需要的。

那么diff算法的作用就來了。

diff作用就是在patch子vnode過程中，找到與新vnode對應(yīng)的老vnode，復(fù)用真實的dom節(jié)點，避免不必要的性能開銷

二 diff算法具體做了什么(重點)？

在正式講diff算法之前，在patchChildren的過程中，存在 patchKeyedChildren

patchUnkeyedChildren

patchKeyedChildren 是正式的開啟diff的流程，那么patchUnkeyedChildren的作用是什么呢？我們來看看針對沒有key的情況patchUnkeyedChildren會做什么。

c1 = c1 || EMPTY_ARR
  c2 = c2 || EMPTY_ARR
  const oldLength = c1.length
  const newLength = c2.length
  const commonLength = Math.min(oldLength, newLength)
  let i
  for (i = 0; i < commonLength; i++) { /* 依次遍歷新老vnode進行patch */
   const nextChild = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
   patch(
    c1[i],
    nextChild,
    container,
    null,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized
   )
  }
  if (oldLength > newLength) { /* 老vnode 數(shù)量大于新的vnode，刪除多余的節(jié)點 */
   unmountChildren(c1, parentComponent, parentSuspense, true, commonLength)
  } else { /* /* 老vnode 數(shù)量小于于新的vnode，創(chuàng)造新的即誒安 */
   mountChildren(
    c2,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    isSVG,
    optimized,
    commonLength
   )
  }

我們可以得到結(jié)論，對于不存在key情況

① 比較新老children的length獲取最小值然后對于公共部分，進行從新patch工作。

② 如果老節(jié)點數(shù)量大于新的節(jié)點數(shù)量，移除多出來的節(jié)點。

③ 如果新的節(jié)點數(shù)量大于老節(jié)點的數(shù)量，從新 mountChildren新增的節(jié)點。

那么對于存在key情況呢？會用到diff算法， diff算法做了什么呢？

patchKeyedChildren方法究竟做了什么？

我們先來看看一些聲明的變量。

  /* c1 老的vnode c2 新的vnode */
  let i = 0       /* 記錄索引 */
  const l2 = c2.length  /* 新vnode的數(shù)量 */
  let e1 = c1.length - 1 /* 老vnode 最后一個節(jié)點的索引 */
  let e2 = l2 - 1    /* 新節(jié)點最后一個節(jié)點的索引 */

①第一步從頭開始向尾尋找

(a b) c

(a b) d e

 /* 從頭對比找到有相同的節(jié)點 patch ，發(fā)現(xiàn)不同，立即跳出*/
  while (i <= e1 && i <= e2) {
   const n1 = c1[i]
   const n2 = (c2[i] = optimized
    ? cloneIfMounted(c2[i] as VNode)
    : normalizeVNode(c2[i]))
    /* 判斷key ，type是否相等 */
   if (isSameVNodeType(n1, n2)) {
    patch(
     n1,
     n2,
     container, 
     parentAnchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
   } else {
    break
   }
   i++
  }

第一步的事情就是從頭開始尋找相同的vnode，然后進行patch,如果發(fā)現(xiàn)不是相同的節(jié)點，那么立即跳出循環(huán)。

具體流程如圖所示

isSameVNodeType

export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
 return n1.type === n2.type && n1.key === n2.key
}

isSameVNodeType 作用就是判斷當(dāng)前vnode類型和 vnode的 key是否相等

②第二步從尾開始同前diff

a (b c)

d e (b c)

/* 如果第一步?jīng)]有patch完，立即，從后往前開始patch ,如果發(fā)現(xiàn)不同立即跳出循環(huán) */
  while (i <= e1 && i <= e2) {
   const n1 = c1[e1]
   const n2 = (c2[e2] = optimized
    ? cloneIfMounted(c2[e2] as VNode)
    : normalizeVNode(c2[e2]))
   if (isSameVNodeType(n1, n2)) {
    patch(
     n1,
     n2,
     container,
     parentAnchor,
     parentComponent,
     parentSuspense,
     isSVG,
     optimized
    )
   } else {
    break
   }
   e1--
   e2--
  }

經(jīng)歷第一步操作之后，如果發(fā)現(xiàn)沒有patch完，那么立即進行第二部，從尾部開始遍歷依次向前diff。

如果發(fā)現(xiàn)不是相同的節(jié)點，那么立即跳出循環(huán)。

具體流程如圖所示

③④主要針對新增和刪除元素的情況，前提是元素沒有發(fā)生移動，如果有元素發(fā)生移動就要走⑤邏輯。 ③ 如果老節(jié)點是否全部patch，新節(jié)點沒有被patch完,創(chuàng)建新的vnode

(a b)

(a b) c

i = 2, e1 = 1, e2 = 2

(a b)

c (a b)

i = 0, e1 = -1, e2 = 0

/* 如果新的節(jié)點大于老的節(jié)點數(shù) ，對于剩下的節(jié)點全部以新的vnode處理（ 這種情況說明已經(jīng)patch完相同的vnode ） */
  if (i > e1) {
   if (i <= e2) {
    const nextPos = e2 + 1
    const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
    while (i <= e2) {
     patch( /* 創(chuàng)建新的節(jié)點*/
      null,
      (c2[i] = optimized
       ? cloneIfMounted(c2[i] as VNode)
       : normalizeVNode(c2[i])),
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG
     )
     i++
    }
   }
  }

i > e1

如果新的節(jié)點大于老的節(jié)點數(shù) ，對于剩下的節(jié)點全部以新的vnode處理（這種情況說明已經(jīng)patch完相同的vnode ），也就是要全部create新的vnode.

具體邏輯如圖所示

④ 如果新節(jié)點全部被patch，老節(jié)點有剩余，那么卸載所有老節(jié)點

i > e2

(a b) c

(a b)

i = 2, e1 = 2, e2 = 1

a (b c)

(b c)

i = 0, e1 = 0, e2 = -1

else if (i > e2) {
  while (i <= e1) {
   unmount(c1[i], parentComponent, parentSuspense, true)
   i++
  }
}

對于老的節(jié)點大于新的節(jié)點的情況，對于超出的節(jié)點全部卸載（這種情況說明已經(jīng)patch完相同的vnode ）

具體邏輯如圖所示

⑤ 不確定的元素（這種情況說明沒有patch完相同的vnode ），我們可以接著①②的邏輯繼續(xù)往下看 diff核心

在①②情況下沒有遍歷完的節(jié)點如下圖所示。

剩下的節(jié)點。

 const s1 = i //第一步遍歷到的index
   const s2 = i 
   const keyToNewIndexMap: Map<string | number, number> = new Map()
   /* 把沒有比較過的新的vnode節(jié)點,通過map保存 */
   for (i = s2; i <= e2; i++) {
    if (nextChild.key != null) {
     keyToNewIndexMap.set(nextChild.key, i)
    }
   }
   let j
   let patched = 0 
   const toBePatched = e2 - s2 + 1 /* 沒有經(jīng)過 path 新的節(jié)點的數(shù)量 */
   let moved = false /* 證明是否 */
   let maxNewIndexSoFar = 0 
   const newIndexToOldIndexMap = new Array(toBePatched)
    for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
   /* 建立一個數(shù)組，每個子元素都是0 [ 0, 0, 0, 0, 0, 0, ] */

遍歷所有新節(jié)點把索引和對應(yīng)的key,存入map keyToNewIndexMap中

keyToNewIndexMap存放 key -> index 的map

D : 2

E : 3

C : 4

I : 5

接下來聲明一個新的指針 j ,記錄剩下新的節(jié)點的索引。

patched,記錄在第⑤步patched新節(jié)點過的數(shù)量

toBePatched記錄⑤步之前，沒有經(jīng)過patched 新的節(jié)點的數(shù)量。

moved代表是否發(fā)生過移動，咱們的demo是已經(jīng)發(fā)生過移動的。

newIndexToOldIndexMap用來存放新節(jié)點索引和老節(jié)點索引的數(shù)組。

newIndexToOldIndexMap 數(shù)組的index是新vnode的索引， value是老vnode的索引。

接下來

 for (i = s1; i <= e1; i++) { /* 開始遍歷老節(jié)點 */
    const prevChild = c1[i]
    if (patched >= toBePatched) { /* 已經(jīng)patch數(shù)量大于等于， */
     /* ① 如果 toBePatched新的節(jié)點數(shù)量為0 ，那么統(tǒng)一卸載老的節(jié)點 */
     unmount(prevChild, parentComponent, parentSuspense, true)
     continue
    }
    let newIndex
     /* ② 如果,老節(jié)點的key存在 ，通過key找到對應(yīng)的index */
    if (prevChild.key != null) {
     newIndex = keyToNewIndexMap.get(prevChild.key)
    } else { /* ③ 如果,老節(jié)點的key不存在 */
     for (j = s2; j <= e2; j++) { /* 遍歷剩下的所有新節(jié)點 */
      if (
       newIndexToOldIndexMap[j - s2] === 0 && /* newIndexToOldIndexMap[j - s2] === 0 新節(jié)點沒有被patch */
       isSameVNodeType(prevChild, c2[j] as VNode)
      ) { /* 如果找到與當(dāng)前老節(jié)點對應(yīng)的新節(jié)點那么 ，將新節(jié)點的索引，賦值給newIndex */
       newIndex = j
       break
      }
     }
    }
    if (newIndex === undefined) { /* ①沒有找到與老節(jié)點對應(yīng)的新節(jié)點，刪除當(dāng)前節(jié)點，卸載所有的節(jié)點 */
     unmount(prevChild, parentComponent, parentSuspense, true)
    } else {
     /* ②把老節(jié)點的索引，記錄在存放新節(jié)點的數(shù)組中， */
     newIndexToOldIndexMap[newIndex - s2] = i + 1
     if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
     } else {
      /* 證明有節(jié)點已經(jīng)移動了  */
      moved = true
     }
     /* 找到新的節(jié)點進行patch節(jié)點 */
     patch(
      prevChild,
      c2[newIndex] as VNode,
      container,
      null,
      parentComponent,
      parentSuspense,
      isSVG,
      optimized
     )
     patched++
    }
 }

這段代碼算是diff算法的核心。

第一步：通過老節(jié)點的key找到對應(yīng)新節(jié)點的index:開始遍歷老的節(jié)點，判斷有沒有key，如果存在key通過新節(jié)點的keyToNewIndexMap找到與新節(jié)點index,如果不存在key那么會遍歷剩下來的新節(jié)點試圖找到對應(yīng)index。第二步：如果存在index證明有對應(yīng)的老節(jié)點，那么直接復(fù)用老節(jié)點進行patch，沒有找到與老節(jié)點對應(yīng)的新節(jié)點，刪除當(dāng)前老節(jié)點。第三步：newIndexToOldIndexMap找到對應(yīng)新老節(jié)點關(guān)系。

到這里，我們patch了一遍，把所有的老vnode都patch了一遍。

如圖所示

但是接下來的問題。

1 雖然已經(jīng)patch過所有的老節(jié)點。可以對于已經(jīng)發(fā)生移動的節(jié)點，要怎么真正移動dom元素。

2 對于新增的節(jié)點，（圖中節(jié)點I）并沒有處理，應(yīng)該怎么處理。

  /*移動老節(jié)點創(chuàng)建新節(jié)點*/
   /* 根據(jù)最長穩(wěn)定序列移動相對應(yīng)的節(jié)點 */
   const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR
   j = increasingNewIndexSequence.length - 1
   for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex] as VNode
    const anchor =
     nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) { /* 沒有老的節(jié)點與新的節(jié)點對應(yīng)，則創(chuàng)建一個新的vnode */
     patch(
      null,
      nextChild,
      container,
      anchor,
      parentComponent,
      parentSuspense,
      isSVG
     )
    } else if (moved) {
     if (j < 0 || i !== increasingNewIndexSequence[j]) { /*如果沒有在長*/
      /* 需要移動的vnode */
      move(nextChild, container, anchor, MoveType.REORDER)
     } else {
      j--
     }

⑥最長穩(wěn)定序列

首選通過getSequence得到一個最長穩(wěn)定序列，對于index === 0 的情況也就是 新增節(jié)點（圖中I） 需要從新mount一個新的vnode,然后對于發(fā)生移動的節(jié)點進行統(tǒng)一的移動操作

什么叫做最長穩(wěn)定序列

對于以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最長遞增子序列為

0, 2, 6, 9, 11, 15.

為什么要得到最長穩(wěn)定序列

因為我們需要一個序列作為基礎(chǔ)的參照序列，其他未在穩(wěn)定序列的節(jié)點，進行移動。

總結(jié)

經(jīng)過上述我們大致知道了diff算法的流程

1 從頭對比找到有相同的節(jié)點 patch ，發(fā)現(xiàn)不同，立即跳出。

2如果第一步?jīng)]有patch完，立即，從后往前開始patch ,如果發(fā)現(xiàn)不同立即跳出循環(huán)。 3如果新的節(jié)點大于老的節(jié)點數(shù) ，對于剩下的節(jié)點全部以新的vnode處理（這種情況說明已經(jīng)patch完相同的vnode ）。 4 對于老的節(jié)點大于新的節(jié)點的情況，對于超出的節(jié)點全部卸載（這種情況說明已經(jīng)patch完相同的vnode ）。 5不確定的元素（這種情況說明沒有patch完相同的vnode ）與 3 ，4對立關(guān)系。

1 把沒有比較過的新的vnode節(jié)點,通過map保存

記錄已經(jīng)patch的新節(jié)點的數(shù)量 patched

沒有經(jīng)過 path 新的節(jié)點的數(shù)量 toBePatched

建立一個數(shù)組newIndexToOldIndexMap，每個子元素都是[ 0, 0, 0, 0, 0, 0, ] 里面的數(shù)字記錄老節(jié)點的索引，數(shù)組索引就是新節(jié)點的索引

開始遍歷老節(jié)點

① 如果 toBePatched新的節(jié)點數(shù)量為0 ，那么統(tǒng)一卸載老的節(jié)點

② 如果,老節(jié)點的key存在，通過key找到對應(yīng)的index

③ 如果,老節(jié)點的key不存在

1 遍歷剩下的所有新節(jié)點

2 如果找到與當(dāng)前老節(jié)點對應(yīng)的新節(jié)點那么，將新節(jié)點的索引，賦值給newIndex

④ 沒有找到與老節(jié)點對應(yīng)的新節(jié)點，卸載當(dāng)前老節(jié)點。

⑤ 如果找到與老節(jié)點對應(yīng)的新節(jié)點，把老節(jié)點的索引，記錄在存放新節(jié)點的數(shù)組中，