Vue3組件更新中的DOM?diff算法示例詳解

更新時(shí)間：2022年04月11日 16:13:13 作者：風(fēng)度前端

虛擬dom是當(dāng)前前端最流行的兩個(gè)框架（vue和react）都用到的一種技術(shù),都說(shuō)他能幫助vue和react提升渲染性能,提升用戶體驗(yàn),下面這篇文章主要給大家介紹了關(guān)于Vue3組件更新中的DOM?diff算法的相關(guān)資料,需要的朋友可以參考下

在vue的組件更新過(guò)程中，新子節(jié)點(diǎn)數(shù)組相對(duì)于舊子節(jié)點(diǎn)數(shù)組的變化，無(wú)非是通過(guò)更新、刪除、添加和移動(dòng)節(jié)點(diǎn)來(lái)完成，而核心 diff 算法，就是在已知舊子節(jié)點(diǎn)的 DOM 結(jié)構(gòu)、vnode 和新子節(jié)點(diǎn)的 vnode 情況下，以較低的成本完成子節(jié)點(diǎn)的更新為目的，求解生成新子節(jié)點(diǎn) DOM 的系列操作。

舉例來(lái)說(shuō)，假說(shuō)我們有一個(gè)如下的列表

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

然后我們?cè)谥虚g插入一行，得到一個(gè)新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="d">e</li>
  <li key="c">c</li>
  <li key="d">d</li>
</ul>

在插入操作的前后，它們對(duì)應(yīng)渲染生成的 vnode 可以用一張圖表示：

從圖中我們可以直觀地感受到，差異主要在新子節(jié)點(diǎn)中的 b 節(jié)點(diǎn)后面多了一個(gè) e 節(jié)點(diǎn)。

我們?cè)侔堰@個(gè)例子稍微修改一下，多添加一個(gè) e 節(jié)點(diǎn)：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

然后我們刪除中間一項(xiàng)，得到一個(gè)新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="d">d</li>
  <li key="e">e</li>
</ul>

在刪除操作的前后，它們對(duì)應(yīng)渲染生成的 vnode 可以用一張圖表示：

我們可以看到，這時(shí)差異主要在新子節(jié)點(diǎn)中的 b 節(jié)點(diǎn)后面少了一個(gè) c 節(jié)點(diǎn)。

綜合這兩個(gè)例子，我們很容易發(fā)現(xiàn)新舊 children 擁有相同的頭尾節(jié)點(diǎn)。對(duì)于相同的節(jié)點(diǎn)，我們只需要做對(duì)比更新即可，所以 diff 算法的第一步從頭部開(kāi)始同步。

同步頭部節(jié)點(diǎn)

我們先來(lái)看一下頭部節(jié)點(diǎn)同步的實(shí)現(xiàn)代碼：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  while (i <= e1 && i <= e2) {
    const n1 = c1[i]
    const n2 = c2[i]
    if (isSameVNodeType(n1, n2)) {
      // 相同的節(jié)點(diǎn)，遞歸執(zhí)行 patch 更新節(jié)點(diǎn)
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    i++
  }
}

在整個(gè) diff 的過(guò)程，我們需要維護(hù)幾個(gè)變量：頭部的索引 i、舊子節(jié)點(diǎn)的尾部索引 e1和新子節(jié)點(diǎn)的尾部索引 e2。

同步頭部節(jié)點(diǎn)就是從頭部開(kāi)始，依次對(duì)比新節(jié)點(diǎn)和舊節(jié)點(diǎn)，如果它們相同的則執(zhí)行 patch 更新節(jié)點(diǎn)；如果不同或者索引 i 大于索引 e1 或者 e2，則同步過(guò)程結(jié)束。

我們拿第一個(gè)例子來(lái)說(shuō)，通過(guò)下圖看一下同步頭部節(jié)點(diǎn)后的結(jié)果：

可以看到，完成頭部節(jié)點(diǎn)同步后：i 是 2，e1 是 3，e2 是 4。

同步尾部節(jié)點(diǎn)

接著從尾部開(kāi)始同步尾部節(jié)點(diǎn)，實(shí)現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  while (i <= e1 && i <= e2) {
    const n1 = c1[e1]
    const n2 = c2[e2]
    if (isSameVNodeType(n1, n2)) {
      patch(n1, n2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized)
    }
    else {
      break
    }
    e1--
    e2--
  }
}

同步尾部節(jié)點(diǎn)就是從尾部開(kāi)始，依次對(duì)比新節(jié)點(diǎn)和舊節(jié)點(diǎn)，如果相同的則執(zhí)行 patch 更新節(jié)點(diǎn)；如果不同或者索引 i 大于索引 e1 或者 e2，則同步過(guò)程結(jié)束。

我們來(lái)通過(guò)下圖看一下同步尾部節(jié)點(diǎn)后的結(jié)果：

可以看到，完成尾部節(jié)點(diǎn)同步后：i 是 2，e1 是 1，e2 是 2。

接下來(lái)只有 3 種情況要處理：

新子節(jié)點(diǎn)有剩余要添加的新節(jié)點(diǎn)；
舊子節(jié)點(diǎn)有剩余要?jiǎng)h除的多余節(jié)點(diǎn)；
未知子序列

我們繼續(xù)看一下具體是怎樣操作的。

添加新的節(jié)點(diǎn)

首先要判斷新子節(jié)點(diǎn)是否有剩余的情況，如果滿足則添加新子節(jié)點(diǎn)，實(shí)現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 3, e2 = 4
  // (a b) c d
  // (a b) e c d
  // ...
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 3, e2 = 4
  // (a b) (c d)
  // (a b) e (c d)
  // 3. 掛載剩余的新節(jié)點(diǎn)
  // i = 2, e1 = 1, e2 = 2
  if (i > e1) {
    if (i <= e2) {
      const nextPos = e2 + 1
      const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor
      while (i <= e2) {
        // 掛載新節(jié)點(diǎn)
        patch(null, c2[i], container, anchor, parentComponent, parentSuspense, isSVG)
        i++
      }
    }
  }
}

如果索引 i 大于尾部索引 e1 且 i 小于 e2，那么從索引 i 開(kāi)始到索引 e2 之間，我們直接掛載新子樹(shù)這部分的節(jié)點(diǎn)。

對(duì)我們的例子而言，同步完尾部節(jié)點(diǎn)后 i 是 2，e1 是 1，e2 是 2，此時(shí)滿足條件需要添加新的節(jié)點(diǎn)，我們來(lái)通過(guò)下圖看一下添加后的結(jié)果：

添加完 e 節(jié)點(diǎn)后，舊子節(jié)點(diǎn)的 DOM 和新子節(jié)點(diǎn)對(duì)應(yīng)的 vnode 映射一致，也就完成了更新。

刪除多余節(jié)點(diǎn)

如果不滿足添加新節(jié)點(diǎn)的情況，我就要接著判斷舊子節(jié)點(diǎn)是否有剩余，如果滿足則刪除舊子節(jié)點(diǎn)，實(shí)現(xiàn)代碼如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 4, e2 = 3
  // (a b) c d e
  // (a b) d e
  // ...
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 4, e2 = 3
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點(diǎn)
  // i = 2, e1 = 2, e2 = 1
  // 不滿足
  if (i > e1) {
  }
  // 4. 普通序列刪除多余的舊節(jié)點(diǎn)
  // i = 2, e1 = 2, e2 = 1
  else if (i > e2) {
    while (i <= e1) {
      // 刪除節(jié)點(diǎn)
      unmount(c1[i], parentComponent, parentSuspense, true)
      i++
    }
  }
}

如果索引 i 大于尾部索引 e2，那么從索引 i 開(kāi)始到索引 e1 之間，我們直接刪除舊子樹(shù)這部分的節(jié)點(diǎn)。

第二個(gè)例子是就刪除節(jié)點(diǎn)的情況，我們從同步頭部節(jié)點(diǎn)開(kāi)始，用圖的方式演示這一過(guò)程。

首先從頭部同步節(jié)點(diǎn)：

此時(shí)的結(jié)果：i 是 2，e1 是 4，e2 是 3。

接著從尾部同步節(jié)點(diǎn)：

此時(shí)的結(jié)果：i 是 2，e1 是 2，e2 是 1，滿足刪除條件，因此刪除子節(jié)點(diǎn)中的多余節(jié)點(diǎn)：

刪除完 c 節(jié)點(diǎn)后，舊子節(jié)點(diǎn)的 DOM 和新子節(jié)點(diǎn)對(duì)應(yīng)的 vnode 映射一致，也就完成了更新。

處理未知子序列

單純的添加和刪除節(jié)點(diǎn)都是比較理想的情況，操作起來(lái)也很容易，但是有些時(shí)候并非這么幸運(yùn)，我們會(huì)遇到比較復(fù)雜的未知子序列，這時(shí)候 diff 算法會(huì)怎么做呢？

我們?cè)偻ㄟ^(guò)例子來(lái)演示存在未知子序列的情況，假設(shè)一個(gè)按照字母表排列的列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="c">c</li>
  <li key="d">d</li>
  <li key="e">e</li>
  <li key="f">f</li>
  <li key="g">g</li>
  <li key="h">h</li>
</ul>

然后我們打亂之前的順序得到一個(gè)新列表：

<ul>
  <li key="a">a</li>
  <li key="b">b</li>
  <li key="e">e</li>
  <li key="d">c</li>
  <li key="c">d</li>
  <li key="i">i</li>
  <li key="g">g</li>
  <li key="h">h</li>
</ul>

在操作前，它們對(duì)應(yīng)渲染生成的 vnode 可以用一張圖表示：

我們還是從同步頭部節(jié)點(diǎn)開(kāi)始，用圖的方式演示這一過(guò)程。

首先從頭部同步節(jié)點(diǎn)：

同步頭部節(jié)點(diǎn)后的結(jié)果：i 是 2，e1 是 7，e2 是 7。

接著從尾部同步節(jié)點(diǎn)：

同步尾部節(jié)點(diǎn)后的結(jié)果：i 是 2，e1 是 5，e2 是 5?？梢钥吹剿炔粷M足添加新節(jié)點(diǎn)的條件，也不滿足刪除舊節(jié)點(diǎn)的條件。那么對(duì)于這種情況，我們應(yīng)該怎么處理呢？

結(jié)合上圖可以知道，要把舊子節(jié)點(diǎn)的 c、d、e、f 轉(zhuǎn)變成新子節(jié)點(diǎn)的 e、c、d、i。從直觀上看，我們把 e 節(jié)點(diǎn)移動(dòng)到 c 節(jié)點(diǎn)前面，刪除 f 節(jié)點(diǎn)，然后在 d 節(jié)點(diǎn)后面添加 i 節(jié)點(diǎn)即可。

其實(shí)無(wú)論多復(fù)雜的情況，最終無(wú)非都是通過(guò)更新、刪除、添加、移動(dòng)這些動(dòng)作來(lái)操作節(jié)點(diǎn)，而我們要做的就是找到相對(duì)優(yōu)的解。

當(dāng)兩個(gè)節(jié)點(diǎn)類型相同時(shí)，我們執(zhí)行更新操作；當(dāng)新子節(jié)點(diǎn)中沒(méi)有舊子節(jié)點(diǎn)中的某些節(jié)點(diǎn)時(shí)，我們執(zhí)行刪除操作；當(dāng)新子節(jié)點(diǎn)中多了舊子節(jié)點(diǎn)中沒(méi)有的節(jié)點(diǎn)時(shí)，我們執(zhí)行添加操作，這些操作我們?cè)谇懊嬉呀?jīng)闡述清楚了。相對(duì)來(lái)說(shuō)這些操作中最麻煩的就是移動(dòng)，我們既要判斷哪些節(jié)點(diǎn)需要移動(dòng)也要清楚如何移動(dòng)。

移動(dòng)子節(jié)點(diǎn)

那么什么時(shí)候需要移動(dòng)呢，就是當(dāng)子節(jié)點(diǎn)排列順序發(fā)生變化的時(shí)候，舉個(gè)簡(jiǎn)單的例子具體看一下：

var prev = [1, 2, 3, 4, 5, 6]
var next = [1, 3, 2, 6, 4, 5]

可以看到，從 prev 變成 next，數(shù)組里的一些元素的順序發(fā)生了變化，我們可以把子節(jié)點(diǎn)類比為元素，現(xiàn)在問(wèn)題就簡(jiǎn)化為我們?nèi)绾斡米钌俚囊苿?dòng)使元素順序從 prev 變化為 next 。

一種思路是在 next 中找到一個(gè)遞增子序列，比如 [1, 3, 6] 、[1, 2, 4, 5]。之后對(duì) next 數(shù)組進(jìn)行倒序遍歷，移動(dòng)所有不在遞增序列中的元素即可。

如果選擇了 [1, 3, 6] 作為遞增子序列，那么在倒序遍歷的過(guò)程中，遇到 6、3、1 不動(dòng)，遇到 5、4、2 移動(dòng)即可，如下圖所示：

如果選擇了 [1, 2, 4, 5] 作為遞增子序列，那么在倒序遍歷的過(guò)程中，遇到 5、4、2、1 不動(dòng)，遇到 6、3 移動(dòng)即可，如下圖所示：

可以看到第一種移動(dòng)了三次，而第二種只移動(dòng)了兩次，遞增子序列越長(zhǎng)，所需要移動(dòng)元素的次數(shù)越少，所以如何移動(dòng)的問(wèn)題就回到了求解最長(zhǎng)遞增子序列的問(wèn)題。我們稍后會(huì)詳細(xì)講求解最長(zhǎng)遞增子序列的算法，所以先回到我們這里的問(wèn)題，對(duì)未知子序列的處理。

我們現(xiàn)在要做的是在新舊子節(jié)點(diǎn)序列中找出相同節(jié)點(diǎn)并更新，找出多余的節(jié)點(diǎn)刪除，找出新的節(jié)點(diǎn)添加，找出是否有需要移動(dòng)的節(jié)點(diǎn)，如果有該如何移動(dòng)。

在查找過(guò)程中需要對(duì)比新舊子序列，那么我們就要遍歷某個(gè)序列，如果在遍歷舊子序列的過(guò)程中需要判斷某個(gè)節(jié)點(diǎn)是否在新子序列中存在，這就需要雙重循環(huán)，而雙重循環(huán)的復(fù)雜度是 O(n2) ，為了優(yōu)化這個(gè)復(fù)雜度，我們可以用一種空間換時(shí)間的思路，建立索引圖，把時(shí)間復(fù)雜度降低到 O(n)。

建立索引圖

所以處理未知子序列的第一步，就是建立索引圖。

通常我們?cè)陂_(kāi)發(fā)過(guò)程中，會(huì)給 v-for 生成的列表中的每一項(xiàng)分配唯一 key 作為項(xiàng)的唯一 ID，這個(gè) key 在 diff 過(guò)程中起到很關(guān)鍵的作用。對(duì)于新舊子序列中的節(jié)點(diǎn)，我們認(rèn)為 key 相同的就是同一個(gè)節(jié)點(diǎn)，直接執(zhí)行 patch 更新即可。

我們根據(jù) key 建立新子序列的索引圖，實(shí)現(xiàn)如下：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點(diǎn)， 不滿足
  // 4. 普通序列刪除多余的舊節(jié)點(diǎn)，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開(kāi)始索引，從 i 開(kāi)始記錄
  const s1 = i
  // 新子序列開(kāi)始索引，從 i 開(kāi)始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  const keyToNewIndexMap = new Map()
  for (i = s2; i <= e2; i++) {
    const nextChild = c2[i]
    keyToNewIndexMap.set(nextChild.key, i)
  }
}

新舊子序列是從 i 開(kāi)始的，所以我們先用 s1、s2 分別作為新舊子序列的開(kāi)始索引，接著建立一個(gè) keyToNewIndexMap 的 Map<key, index> 結(jié)構(gòu)，遍歷新子序列，把節(jié)點(diǎn)的 key 和 index 添加到這個(gè) Map 中，注意我們這里假設(shè)所有節(jié)點(diǎn)都是有 key 標(biāo)識(shí)的。

keyToNewIndexMap 存儲(chǔ)的就是新子序列中每個(gè)節(jié)點(diǎn)在新子序列中的索引，我們來(lái)看一下示例處理后的結(jié)果，如下圖所示：

我們得到了一個(gè)值為 {e:2,c:3,d:4,i:5} 的新子序列索引圖。

更新和移除舊節(jié)點(diǎn)

接下來(lái)，我們就需要遍歷舊子序列，有相同的節(jié)點(diǎn)就通過(guò) patch 更新，并且移除那些不在新子序列中的節(jié)點(diǎn)，同時(shí)找出是否有需要移動(dòng)的節(jié)點(diǎn)，我們來(lái)看一下這部分邏輯的實(shí)現(xiàn)：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 7, e2 = 7
  // (a b) c d e f g h
  // (a b) e c d i g h
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 7, e2 = 7
  // (a b) c d e f (g h)
  // (a b) e c d i (g h)
  // 3. 普通序列掛載剩余的新節(jié)點(diǎn)，不滿足
  // 4. 普通序列刪除多余的舊節(jié)點(diǎn)，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子序列開(kāi)始索引，從 i 開(kāi)始記錄
  const s1 = i
  // 新子序列開(kāi)始索引，從 i 開(kāi)始記錄
  const s2 = i
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點(diǎn)更新，刪除不在新子序列中的節(jié)點(diǎn)，判斷是否有移動(dòng)節(jié)點(diǎn)
  // 新子序列已更新節(jié)點(diǎn)的數(shù)量
  let patched = 0
  // 新子序列待更新節(jié)點(diǎn)的數(shù)量，等于新子序列的長(zhǎng)度
  const toBePatched = e2 - s2 + 1
  // 是否存在要移動(dòng)的節(jié)點(diǎn)
  let moved = false
  // 用于跟蹤判斷是否有節(jié)點(diǎn)移動(dòng)
  let maxNewIndexSoFar = 0
  // 這個(gè)數(shù)組存儲(chǔ)新子序列中的元素在舊子序列節(jié)點(diǎn)的索引，用于確定最長(zhǎng)遞增子序列
  const newIndexToOldIndexMap = new Array(toBePatched)
  // 初始化數(shù)組，每個(gè)元素的值都是 0
  // 0 是一個(gè)特殊的值，如果遍歷完了仍有元素的值為 0，則說(shuō)明這個(gè)新節(jié)點(diǎn)沒(méi)有對(duì)應(yīng)的舊節(jié)點(diǎn)
  for (i = 0; i < toBePatched; i++)
    newIndexToOldIndexMap[i] = 0
  // 正序遍歷舊子序列
  for (i = s1; i <= e1; i++) {
    // 拿到每一個(gè)舊子序列節(jié)點(diǎn)
    const prevChild = c1[i]
    if (patched >= toBePatched) {
      // 所有新的子序列節(jié)點(diǎn)都已經(jīng)更新，剩余的節(jié)點(diǎn)刪除
      unmount(prevChild, parentComponent, parentSuspense, true)
      continue
    }
    // 查找舊子序列中的節(jié)點(diǎn)在新子序列中的索引
    let newIndex = keyToNewIndexMap.get(prevChild.key)
    if (newIndex === undefined) {
      // 找不到說(shuō)明舊子序列已經(jīng)不存在于新子序列中，則刪除該節(jié)點(diǎn)
      unmount(prevChild, parentComponent, parentSuspense, true)
    }
    else {
      // 更新新子序列中的元素在舊子序列中的索引，這里加 1 偏移，是為了避免 i 為 0 的特殊情況，影響對(duì)后續(xù)最長(zhǎng)遞增子序列的求解
      newIndexToOldIndexMap[newIndex - s2] = i + 1
      // maxNewIndexSoFar 始終存儲(chǔ)的是上次求值的 newIndex，如果不是一直遞增，則說(shuō)明有移動(dòng)
      if (newIndex >= maxNewIndexSoFar) {
        maxNewIndexSoFar = newIndex
      }
      else {
        moved = true
      }
      // 更新新舊子序列中匹配的節(jié)點(diǎn)
      patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, optimized)
      patched++
    }
  }
}

我們建立了一個(gè) newIndexToOldIndexMap 的數(shù)組，來(lái)存儲(chǔ)新子序列節(jié)點(diǎn)的索引和舊子序列節(jié)點(diǎn)的索引之間的映射關(guān)系，用于確定最長(zhǎng)遞增子序列，這個(gè)數(shù)組的長(zhǎng)度為新子序列的長(zhǎng)度，每個(gè)元素的初始值設(shè)為 0，它是一個(gè)特殊的值，如果遍歷完了仍有元素的值為 0，則說(shuō)明遍歷舊子序列的過(guò)程中沒(méi)有處理過(guò)這個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)是新添加的。

下面我們說(shuō)說(shuō)具體的操作過(guò)程：正序遍歷舊子序列，根據(jù)前面建立的 keyToNewIndexMap 查找舊子序列中的節(jié)點(diǎn)在新子序列中的索引，如果找不到就說(shuō)明新子序列中沒(méi)有該節(jié)點(diǎn)，就刪除它；如果找得到則將它在舊子序列中的索引更新到 newIndexToOldIndexMap 中。

注意這里索引加了長(zhǎng)度為 1 的偏移，是為了應(yīng)對(duì) i 為 0 的特殊情況，如果不這樣處理就會(huì)影響后續(xù)求解最長(zhǎng)遞增子序列。

遍歷過(guò)程中，我們用變量 maxNewIndexSoFar 跟蹤判斷節(jié)點(diǎn)是否移動(dòng)，maxNewIndexSoFar 始終存儲(chǔ)的是上次求值的 newIndex，一旦本次求值的 newIndex 小于 maxNewIndexSoFar，這說(shuō)明順序遍歷舊子序列的節(jié)點(diǎn)在新子序列中的索引并不是一直遞增的，也就說(shuō)明存在移動(dòng)的情況。

除此之外，這個(gè)過(guò)程中我們也會(huì)更新新舊子序列中匹配的節(jié)點(diǎn)，另外如果所有新的子序列節(jié)點(diǎn)都已經(jīng)更新，而對(duì)舊子序列遍歷還未結(jié)束，說(shuō)明剩余的節(jié)點(diǎn)就是多余的，刪除即可。

至此，我們完成了新舊子序列節(jié)點(diǎn)的更新、多余舊節(jié)點(diǎn)的刪除，并且建立了一個(gè) newIndexToOldIndexMap 存儲(chǔ)新子序列節(jié)點(diǎn)的索引和舊子序列節(jié)點(diǎn)的索引之間的映射關(guān)系，并確定是否有移動(dòng)。

我們來(lái)看一下示例處理后的結(jié)果，如下圖所示：

可以看到， c、d、e 節(jié)點(diǎn)被更新，f 節(jié)點(diǎn)被刪除，newIndexToOldIndexMap 的值為 [5, 3, 4 ,0]，此時(shí) moved 也為 true，也就是存在節(jié)點(diǎn)移動(dòng)的情況。

移動(dòng)和掛載新節(jié)點(diǎn)

接下來(lái)，就到了處理未知子序列的最后一個(gè)流程，移動(dòng)和掛載新節(jié)點(diǎn)，我們來(lái)看一下這部分邏輯的實(shí)現(xiàn)：

const patchKeyedChildren = (c1, c2, container, parentAnchor, parentComponent, parentSuspense, isSVG, optimized) => {
  let i = 0
  const l2 = c2.length
  // 舊子節(jié)點(diǎn)的尾部索引
  let e1 = c1.length - 1
  // 新子節(jié)點(diǎn)的尾部索引
  let e2 = l2 - 1
  // 1. 從頭部開(kāi)始同步
  // i = 0, e1 = 6, e2 = 7
  // (a b) c d e f g
  // (a b) e c d h f g
  // 2. 從尾部開(kāi)始同步
  // i = 2, e1 = 6, e2 = 7
  // (a b) c (d e)
  // (a b) (d e)
  // 3. 普通序列掛載剩余的新節(jié)點(diǎn)， 不滿足
  // 4. 普通序列刪除多余的節(jié)點(diǎn)，不滿足
  // i = 2, e1 = 4, e2 = 5
  // 舊子節(jié)點(diǎn)開(kāi)始索引，從 i 開(kāi)始記錄
  const s1 = i
  // 新子節(jié)點(diǎn)開(kāi)始索引，從 i 開(kāi)始記錄
  const s2 = i //
  // 5.1 根據(jù) key 建立新子序列的索引圖
  // 5.2 正序遍歷舊子序列，找到匹配的節(jié)點(diǎn)更新，刪除不在新子序列中的節(jié)點(diǎn)，判斷是否有移動(dòng)節(jié)點(diǎn)
  // 5.3 移動(dòng)和掛載新節(jié)點(diǎn)
  // 僅當(dāng)節(jié)點(diǎn)移動(dòng)時(shí)生成最長(zhǎng)遞增子序列
  const increasingNewIndexSequence = moved
    ? getSequence(newIndexToOldIndexMap)
    : EMPTY_ARR
  let j = increasingNewIndexSequence.length - 1
  // 倒序遍歷以便我們可以使用最后更新的節(jié)點(diǎn)作為錨點(diǎn)
  for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex]
    // 錨點(diǎn)指向上一個(gè)更新的節(jié)點(diǎn)，如果 nextIndex 超過(guò)新子節(jié)點(diǎn)的長(zhǎng)度，則指向 parentAnchor
    const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
      // 掛載新的子節(jié)點(diǎn)
     patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG)
    }
    else if (moved) {
      // 沒(méi)有最長(zhǎng)遞增子序列（reverse 的場(chǎng)景）或者當(dāng)前的節(jié)點(diǎn)索引不在最長(zhǎng)遞增子序列中，需要移動(dòng)
      if (j < 0 || i !== increasingNewIndexSequence[j]) {
        move(nextChild, container, anchor, 2)
      }
      else {
        // 倒序遞增子序列
        j--
      }
    }
  }
}

我們前面已經(jīng)判斷了是否移動(dòng)，如果 moved 為 true 就通過(guò) getSequence(newIndexToOldIndexMap) 計(jì)算最長(zhǎng)遞增子序列。

接著我們采用倒序的方式遍歷新子序列，因?yàn)榈剐虮闅v可以方便我們使用最后更新的節(jié)點(diǎn)作為錨點(diǎn)。在倒序的過(guò)程中，錨點(diǎn)指向上一個(gè)更新的節(jié)點(diǎn)，然后判斷 newIndexToOldIndexMap[i] 是否為 0，如果是則表示這是新節(jié)點(diǎn)，就需要掛載它；接著判斷是否存在節(jié)點(diǎn)移動(dòng)的情況，如果存在的話則看節(jié)點(diǎn)的索引是不是在最長(zhǎng)遞增子序列中，如果在則倒序最長(zhǎng)遞增子序列，否則把它移動(dòng)到錨點(diǎn)的前面。

為了便于你更直觀地理解，我們用前面的例子展示一下這個(gè)過(guò)程，此時(shí) toBePatched 的值為 4，j 的值為 1，最長(zhǎng)遞增子序列 increasingNewIndexSequence 的值是 [1, 2]。在倒序新子序列的過(guò)程中，首先遇到節(jié)點(diǎn) i，發(fā)現(xiàn)它在 newIndexToOldIndexMap 中的值是 0，則說(shuō)明它是新節(jié)點(diǎn)，我們需要掛載它；然后繼續(xù)遍歷遇到節(jié)點(diǎn) d，因?yàn)?moved 為 true，且 d 的索引存在于最長(zhǎng)遞增子序列中，則執(zhí)行 j-- 倒序最長(zhǎng)遞增子序列，j 此時(shí)為 0；接著繼續(xù)遍歷遇到節(jié)點(diǎn) c，它和 d 一樣，索引也存在于最長(zhǎng)遞增子序列中，則執(zhí)行 j--，j 此時(shí)為 -1；接著繼續(xù)遍歷遇到節(jié)點(diǎn) e，此時(shí) j 是 -1 并且 e 的索引也不在最長(zhǎng)遞增子序列中，所以做一次移動(dòng)操作，把 e 節(jié)點(diǎn)移到上一個(gè)更新的節(jié)點(diǎn)，也就是 c 節(jié)點(diǎn)的前面。

新子序列倒序完成，即完成了新節(jié)點(diǎn)的插入和舊節(jié)點(diǎn)的移動(dòng)操作，也就完成了整個(gè)核心 diff 算法對(duì)節(jié)點(diǎn)的更新。

我們來(lái)看一下示例處理后的結(jié)果，如下圖所示：

可以看到新子序列中的新節(jié)點(diǎn) i 被掛載，舊子序列中的節(jié)點(diǎn) e 移動(dòng)到了 c 節(jié)點(diǎn)前面，至此，我們就在已知舊子節(jié)點(diǎn) DOM 結(jié)構(gòu)和 vnode、新子節(jié)點(diǎn) vnode 的情況下，求解出生成新子節(jié)點(diǎn)的 DOM 的更新、移動(dòng)、刪除、新增等系列操作，并且以一種較小成本的方式完成 DOM 更新。

我們知道了子節(jié)點(diǎn)更新調(diào)用的是 patch 方法， Vue.js 正是通過(guò)這種遞歸的方式完成了整個(gè)組件樹(shù)的更新。

核心 diff 算法中最復(fù)雜就是求解最長(zhǎng)遞增子序列，下面我們?cè)賮?lái)詳細(xì)學(xué)習(xí)一下這個(gè)算法。

最長(zhǎng)遞增子序列

求解最長(zhǎng)遞增子序列是一道經(jīng)典的算法題，多數(shù)解法是使用動(dòng)態(tài)規(guī)劃的思想，算法的時(shí)間復(fù)雜度是 O(n2)，而 Vue.js 內(nèi)部使用的是維基百科提供的一套“貪心 + 二分查找”的算法，貪心算法的時(shí)間復(fù)雜度是 O(n)，二分查找的時(shí)間復(fù)雜度是 O(logn)，所以它的總時(shí)間復(fù)雜度是 O(nlogn)。

單純地看代碼并不好理解，我們用示例來(lái)看一下這個(gè)子序列的求解過(guò)程。

假設(shè)我們有這個(gè)樣一個(gè)數(shù)組 arr：[2, 1, 5, 3, 6, 4, 8, 9, 7]，求解它最長(zhǎng)遞增子序列的步驟如下：

最終求得最長(zhǎng)遞增子序列的值就是 [1, 3, 4, 8, 9]。

通過(guò)演示我們可以得到這個(gè)算法的主要思路：對(duì)數(shù)組遍歷，依次求解長(zhǎng)度為 i 時(shí)的最長(zhǎng)遞增子序列，當(dāng) i 元素大于 i - 1 的元素時(shí)，添加 i 元素并更新最長(zhǎng)子序列；否則往前查找直到找到一個(gè)比 i 小的元素，然后插在該元素后面并更新對(duì)應(yīng)的最長(zhǎng)遞增子序列。

這種做法的主要目的是讓遞增序列的差盡可能的小，從而可以獲得更長(zhǎng)的遞增子序列，這便是一種貪心算法的思想。

了解了算法的大致思想后，接下來(lái)我們看一下源碼實(shí)現(xiàn)：

function getSequence (arr) {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        // 存儲(chǔ)在 result 更新前的最后一個(gè)索引的值
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      // 二分搜索，查找比 arrI 小的節(jié)點(diǎn)，更新 result 的值
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        }
        else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]

  // 回溯數(shù)組 p，找到最終的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

其中 result 存儲(chǔ)的是長(zhǎng)度為 i 的遞增子序列最小末尾值的索引。比如我們上述例子的第九步，在對(duì)數(shù)組 p 回溯之前， result 值就是 [1, 3, 4, 7, 9] ，這不是最長(zhǎng)遞增子序列，它只是存儲(chǔ)的對(duì)應(yīng)長(zhǎng)度遞增子序列的最小末尾。因此在整個(gè)遍歷過(guò)程中會(huì)額外用一個(gè)數(shù)組 p，來(lái)存儲(chǔ)在每次更新 result 前最后一個(gè)索引的值，并且它的 key 是這次要更新的 result 值：

j = result[result.length - 1]
p[i] = j
result.push(i)

從 result 最后一個(gè)元素 9 對(duì)應(yīng)的索引 7 開(kāi)始回溯，可以看到 p[7] = 6，p[6] = 5，p[5] = 3，p[3] = 1，所以通過(guò)對(duì) p 的回溯，得到最終的 result 值是 [1, 3 ,5 ,6 ,7]，也就找到最長(zhǎng)遞增子序列的最終索引了。這里要注意，我們求解的是最長(zhǎng)子序列索引值，它的每個(gè)元素其實(shí)對(duì)應(yīng)的是數(shù)組的下標(biāo)。對(duì)于我們的例子而言，[2, 1, 5, 3, 6, 4, 8, 9, 7] 的最長(zhǎng)子序列是 [1, 3, 4, 8, 9]，而我們求解的 [1, 3 ,5 ,6 ,7] 就是最長(zhǎng)子序列中元素在原數(shù)組中的下標(biāo)所構(gòu)成的新數(shù)組。

總結(jié)

本文分析了組件更新流程中的diff算法，對(duì)于普通元素節(jié)點(diǎn)的更新，主要是更新一些屬性，以及它的子節(jié)點(diǎn)。子節(jié)點(diǎn)的更新又分為多種情況，其中最復(fù)雜的情況為數(shù)組到數(shù)組的更新，內(nèi)部又根據(jù)不同情況分成幾個(gè)流程去 diff，遇到需要移動(dòng)的情況還要去求解子節(jié)點(diǎn)的最長(zhǎng)遞增子序列。

整個(gè)更新過(guò)程還是利用了樹(shù)的深度遍歷，遞歸執(zhí)行 patch 方法，最終完成了整個(gè)組件樹(shù)的更新。

下面，我們通過(guò)一張圖來(lái)更加直觀感受組件的更新流程：