Diff 算法是用于比較兩個虛擬 DOM 樹的差異，并以最小的操作代價將舊的 DOM 樹更新為新的 DOM 樹的一種算法。

Diff 算法的高效實現對于提高前端應用的性能和用戶體驗至關重要，尤其是在頻繁更新組件狀態導致 DOM 頻繁更新的情況下。

1. 原理

1.1 樹層級比較

首先，比較新舊兩棵樹的根節點。如果根節點的類型不同，直接替換整個舊根節點及其子樹。

1.2 節點類型相同的比較

比較節點的屬性（如 id、class 等），如果屬性有變化，更新相應的屬性。

1.3 子節點列表比較

對新舊節點的子節點列表進行比較。

常見的策略有雙指針比較、key 值比較等。

雙指針比較：從新舊子節點列表的頭部和尾部同時開始比較。

key 值比較：如果子節點設置了 key 屬性，通過 key 來快速找到對應的節點進行比較和更新。

1.4 處理新增和刪除

如果新節點列表中有新增的節點，將其添加到適當的位置。

如果舊節點列表中有不再存在于新列表中的節點，將其刪除。

1.5 最小化操作

算法的目標是盡量減少 DOM 操作，例如盡量通過修改節點屬性而不是刪除和重新創建節點來更新 DOM。

2. 實現

通過 js 實現一個簡單的 diff 算法

function diff(oldArray, newArray) {let inserts = [];let deletes = [];let oldIndex = 0;let newIndex = 0;while (oldIndex < oldArray.length && newIndex < newArray.length) {if (oldArray[oldIndex] !== newArray[newIndex]) {if (oldArray[oldIndex] === undefined) {inserts.push(newArray[newIndex]);newIndex++;} else {deletes.push(oldArray[oldIndex]);oldIndex++;}} else {oldIndex++;newIndex++;}}while (oldIndex < oldArray.length) {deletes.push(oldArray[oldIndex++]);}while (newIndex < newArray.length) {inserts.push(newArray[newIndex++]);}return { inserts, deletes };}let oldArray = [1, 2, 3, 4, 5];let newArray = [1, 3, 5, 6, 7];console.log(diff(oldArray, newArray));// {// ? deletes: (2)[(2, 4)];// ? inserts: (2)[(6, 7)];// }