Vue 的 Diff 算法是虛擬 DOM 實現中的核心部分，它在視圖更新時比較新舊虛擬 DOM 樹并高效更新實際 DOM。

一、什么是 Diff 算法？

Diff 算法用于在虛擬 DOM 更新時，通過比較新舊兩棵虛擬 DOM 樹，找出最小差異并將這些變化應用到實際 DOM 上。Vue 采用了一種高效的算法，只對同層級節點進行比較，避免了深度遍歷帶來的性能開銷。

1.1 虛擬 DOM

虛擬 DOM 是對真實 DOM 的抽象表示，它是一個輕量級的 JavaScript 對象。每次數據變化時，Vue 會生成一棵新的虛擬 DOM 樹，并與舊的虛擬 DOM 樹進行對比。

1.2 Diff 算法的作用

Diff 算法的作用就是通過對比新舊虛擬 DOM 樹，計算出需要更新的部分，最終將這些變化應用到真實 DOM 上，從而實現視圖的高效更新。

二、核心原理

Vue 的 Diff 算法基于以下兩個關鍵假設：

1. 同層級比較：只比較同一層級的節點，忽略跨層級的比較。
2. 節點類型相同的情況下才進行深度比較：如果節點類型不同，直接替換；如果類型相同，則進一步比較它們的屬性和子節點。

2.1 簡化的 Diff 流程

1. 先從頭開始，比較新舊節點的頭部。
2. 如果頭部不相同，則從尾部開始，比較新舊節點的尾部。
3. 如果頭尾都不相同，則尋找中間的可復用節點，通過 key 來進行快速定位。
4. 最后處理剩下的節點，添加新節點或移除多余節點。

三、Diff 算法的詳細過程

1. 比較首尾節點：Vue 從新舊虛擬 DOM 樹的頭和尾進行雙端比較：

   • 如果舊節點和新節點的開頭節點相同（可以復用），則移動到下一個節點繼續比較。
   • 如果舊節點和新節點的結尾節點相同（可以復用），則移動到上一個節點繼續比較。

2. 跨節點比較：如果新舊節點的開頭和結尾都不匹配，則檢查中間節點是否有可復用的：

   • 通過遍歷找到新節點中的 key 與舊節點相同的節點，找到后進行復用，并更新位置。

3. 節點的添加與刪除：對于新虛擬 DOM 樹中有而舊樹中沒有的節點，進行插入；舊樹中有而新樹中沒有的節點，進行刪除。

3.1 Key 的作用

在上述步驟中，key 的作用非常重要。key 是唯一標識節點的屬性，用于標記節點的身份。借助 key，Diff 算法可以快速識別出哪些節點是相同的，從而實現節點的復用和高效更新。

3.2 雙端比較策略

雙端比較的策略是 Vue Diff 算法的一個重要優化點。通過從頭和尾同時進行比較，避免了全量比較，提升了性能。

四、優化策略

1. 只進行同層級比較：跨層級的節點直接不進行對比，從而減少不必要的計算。
2. 使用 Key 提升性能：通過為每個節點添加唯一 key，Vue 可以利用對象的映射快速定位可復用節點。
3. 最短路徑匹配：Vue 的 Diff 算法通過最短路徑匹配策略，只對真正變化的部分進行操作。

五、Diff 算法的復雜度

在最理想的情況下（所有節點都可以復用且有序），Vue 的 Diff 算法的時間復雜度是 O(n)；而在最壞的情況下，時間復雜度接近 O(n^2)，但得益于關鍵優化策略，實際應用中很少會出現性能瓶頸。

六、代碼實現簡析

簡化版的 Diff 算法實現如下：

function patch(oldVNode, newVNode) {
  if (oldVNode.tag === newVNode.tag) {
    // 節點類型相同，進行深度比較
    updateAttributes(oldVNode, newVNode);
    updateChildren(oldVNode.children, newVNode.children);
  } else {
    // 節點類型不同，直接替換
    replaceNode(oldVNode, newVNode);
  }
}

function updateChildren(oldChildren, newChildren) {
  let oldStart = 0, newStart = 0;
  let oldEnd = oldChildren.length - 1, newEnd = newChildren.length - 1;

  while (oldStart <= oldEnd && newStart <= newEnd) {
    // 依次進行首尾比較
    if (oldChildren[oldStart].key === newChildren[newStart].key) {
      patch(oldChildren[oldStart], newChildren[newStart]);
      oldStart++;
      newStart++;
    } else if (oldChildren[oldEnd].key === newChildren[newEnd].key) {
      patch(oldChildren[oldEnd], newChildren[newEnd]);
      oldEnd--;
      newEnd--;
    } else {
      // 處理跨節點的情況，利用 key 進行快速匹配
      let oldIndex = findIndexByKey(oldChildren, newChildren[newStart].key);
      if (oldIndex !== -1) {
        patch(oldChildren[oldIndex], newChildren[newStart]);
        moveNode(oldChildren, oldIndex, oldStart);
        oldStart++;
        newStart++;
      } else {
        createNode(newChildren[newStart]);
        newStart++;
      }
    }
  }

  // 處理剩余節點
  if (oldStart <= oldEnd) {
    removeNodes(oldChildren, oldStart, oldEnd);
  }
  if (newStart <= newEnd) {
    addNodes(newChildren, newStart, newEnd);
  }
}

Vue 的 Diff 算法通過同層級比較、雙端比較、Key 復用等策略，極大提升了視圖更新的性能。