傳統的樹 Diff 演算法時間複雜度高達 O(n^3)，如果直接套用在 DOM 比較上，效能將會是毀滅性的。React 透過 三大啟發式策略 (Heuristic Strategies)，成功將時間複雜度降至 O(n)！

一、 降低複雜度的三大啟發式策略

React 團隊基於對 Web UI 變更規律的實務觀察，立下了三條假定：

1. 同層比較 (Same-level Reconciliation)：DOM 樹跨層級的移動極少發生。React 只會對同階層（Sibling）的 Fiber 節點進行比較，跨層級移動會直接「銷毀舊樹、建立新樹」。

2. 類型決定生存 (Type Preserving)：兩個不同類型的元素（如<div> 變成 <p>、或 <Header> 變成 <Footer>）會產生不同的 DOM 樹，React 會直接拆除舊 DOM 並重新掛載新 DOM。

3. key 的唯一識別 (Key Stability)：開發者可以透過 key 屬性來提示 React 哪些子節點在不同的渲染中保持穩定，從而實現高效的節點復用。

二、 單節點 Diff (Single-node Diffing)

當新生的 Virtual DOM 節點只是一個單一物件（如 typeof newChild === 'object' 且非陣列）時，會觸發 reconcileSingleElement。

復用步驟：

1. 比較 key：檢查當前層級是否存在 key 相同的舊 Fiber 節點。

   • 若 key 不同 -> 刪除當前舊 Fiber，並繼續比對下一個同層 Sibling。

2. 比較 type：若 key 相同，進一步比對 type（如 div vs span）。

   • 若 type 相同 -> 成功復用舊 Fiber！僅更新 Props 並重置刪除標記。

   • 若 type 不同 -> 認定為完全不同的 UI，標記該 Fiber 及其所有同層 Siblings 為刪除 (Deletions)。

新建 Fiber：若無法復用，則建立新的 Fiber 節點。

三、 多節點 Diff (Multi-node Diffing)

當新節點是一個陣列（如列表渲染 map(...)）時，會呼叫 reconcileChildrenArray。這是 Diff 演算法中最複雜的部分。

當新節點是一個陣列（如列表渲染 map(...)）時，會呼叫 reconcileChildrenArray。這是 Diff 演算法中最複雜的部分。

React 將多節點 Diff 拆解為兩輪遍歷 (Two-pass Algorithm)：

第一輪遍歷：處理「位置未變」的更新 (Same-index matching)

• 同時從新陣列與舊 Fiber 鏈表的開頭（索引 0）開始同步向後遍歷。

• 如果 key 與 type 都可復用，則產生新 Fiber 並繼續比對 index + 1。

• 停止條件：一旦遇到 key 不匹配，第一輪遍歷立刻中斷！

第二輪遍歷：處理「位置移動 / 插入 / 刪除」
若第一輪遍歷中斷後，新舊陣列都還有剩餘元素，React 會進行第二輪處理：

1. 建立 Map 雜湊表：將剩餘的舊 Fiber 建立一個以 key (或 index) 為鍵值的 Map 表（existingChildren）。
2. 走訪新陣列：遍歷剩餘的新 VDOM 節點，直接去 Map 中以 O(1) 時間查找是否有可復用的舊 Fiber：
   • 找到 -> 移出 Map 並復用該 Fiber。
   • 找不到 -> 建立全新的 Fiber。
3. 依序標記刪除：遍歷結束後，Map 中殘留的舊 Fiber 全部打上 Deletion 標記。

四、 節點移動判定：lastPlacedIndex 演算法

在第二輪遍歷中，React 如何判斷一個節點是「原地更新」還是「發生了位移」？

React 在內部維護一個變數 lastPlacedIndex（代表當前已掛載節點在舊陣列中的最大索引值，初始為 0）：

舊列表：A(0), B(1), C(2), D(3)
新列表：D(3), A(0), B(1), C(2)

走訪新列表：
1. 處理 D：舊 index = 3。3 >= lastPlacedIndex(0) -> D 不需移動！
   更新 lastPlacedIndex = 3。
2. 處理 A：舊 index = 0。0 < lastPlacedIndex(3) -> A 向右移動 (Placement)！
3. 處理 B：舊 index = 1。1 < lastPlacedIndex(3) -> B 向右移動 (Placement)！
4. 處理 C：舊 index = 2。2 < lastPlacedIndex(3) -> C 向右移動 (Placement)！