原生 DOM 更新

Diff 算法更新

什么是 Diff 算法？

Diff 算法（差異算法） 是一種用于比較兩個樹形結構（通常是虛擬 DOM 樹）之間的差異，并計算出最小變更集的高效算法。它是現代前端框架（如 React, Vue, Angular 等）實現高性能渲染的核心機制之一。

核心思想

1. 比較對象：比較的是內存中表示 UI 結構的 JavaScript 對象（虛擬 DOM 樹），而非直接操作瀏覽器中笨重的真實 DOM。
2. 找出差異：精確找出新舊兩棵虛擬 DOM 樹中哪些節點發生了變化（增、刪、改、移）。
3. 最小化操作：只將必要的、最少的變更應用到真實 DOM 上，避免不必要的渲染開銷。

Diff 算法的作用

1. 性能優化（核心作用）:

   • 減少 DOM 操作成本：直接操作真實 DOM（尤其是涉及布局重排和重繪）是瀏覽器中最昂貴的操作之一。Diff 算法確保只更新真正變化的部分。
   • 批量更新：框架可以將 Diff 計算出的多個變更集合并成一次批量的 DOM 操作，進一步提高效率。
   • 避免全量更新：無需在每次狀態變化時都銷毀整個舊 DOM 樹并重建整個新 DOM 樹。

2. 簡化開發邏輯:

   • 聲明式編程：開發者只需關注“目標 UI 狀態應該是什么樣子”（描述新的虛擬 DOM），而無需手動編寫繁瑣的“如何從當前狀態變過去”的命令式代碼（如 document.getElementById(...).appendChild(...)）。Diff 算法和渲染引擎自動處理更新過程。
   • 關注點分離：開發者聚焦于業務邏輯和狀態管理，框架負責高效的 UI 更新。

3. 跨平臺能力的基礎:

   • 虛擬 DOM 和 Diff 算法提供了一層抽象。計算出的最小變更集不僅可以應用于瀏覽器 DOM，也可以應用于 Native 組件（React Native）、Canvas、WebGL，甚至服務端渲染。

為什么需要實現 Diff 算法？

實現 Diff 算法是為了解決直接操作真實 DOM 帶來的嚴重性能瓶頸和開發體驗問題：

1. 直接操作 DOM 的代價高昂：

   • 每次 DOM 操作（尤其是修改布局屬性）都可能觸發瀏覽器的 重排（Reflow） 和 重繪（Repaint） ，這是非常消耗 CPU 和 GPU 資源的操作。
   • 頻繁或低效的 DOM 更新會導致界面卡頓、響應遲緩，用戶體驗變差。

2. 手動更新 DOM 復雜且易錯：

   • 在復雜的 Web 應用中，隨著狀態變化，需要精確計算出哪些 DOM 元素需要添加、刪除、修改屬性或移動位置。
   • 手動編寫這些更新邏輯極其繁瑣、容易出錯，且代碼難以維護。例如，在一個動態列表中插入一項，可能需要精確找到插入點、更新后續元素的索引、處理動畫狀態等。

3. 全量更新不可行：

   • 最簡單粗暴的更新方式是：銷毀整個舊的 DOM 樹，然后用新的狀態重建并插入整個新的 DOM 樹。
   • 這種方法在簡單靜態頁面上也許可行，但對于復雜動態應用：
     • 性能災難：銷毀和重建整個樹的開銷巨大，導致界面嚴重閃爍或卡死。
     • 狀態丟失：輸入框焦點、滾動條位置、組件內部狀態（如視頻播放進度）等都會被重置，破壞用戶體驗。

Diff 算法的優勢解決方案

1. 虛擬 DOM：輕量級的中間層：

   • 在內存中創建真實 DOM 的輕量級 JavaScript 對象表示。創建和操作 JS 對象遠比操作真實 DOM 快得多。
   • 狀態變化時，先創建新的虛擬 DOM 樹。

2. Diff：計算最小變更：

   • 使用優化過的 Diff 算法（通常是 O(n) 復雜度）對比新舊虛擬 DOM 樹。
   • 精準找出節點級別的差異（元素類型變化？屬性變化？子節點順序變化？）。

3. 高效更新：

   • 將 Diff 計算出的 “補丁”（Patch） 應用到真實 DOM 上。
   • 只更新變化的部分，最大程度減少昂貴的 DOM 操作和重排/重繪。

原生 DOM 操作的"精確更新"假象（作用的補充說明）

在原生 JavaScript 中，開發者確實可以手動精確更新特定節點：

// 原生 DOM 精確更新示例
const priceElement = document.getElementById("product-price");
priceElement.textContent = newPrice;

表面優勢：

• 只更新一個節點
• 沒有額外開銷
• 性能看似高效

實際挑戰：

1. 狀態追蹤復雜度：在大型應用中，需要手動維護數百個元素引用
2. 依賴關系管理：當多個數據影響同一元素時，更新邏輯變得復雜
3. 動態內容處理：列表渲染、條件渲染需要大量手動 DOM 操作
4. 跨組件更新：深層嵌套組件更新需要穿透多層結構

Vue 中的 Diff 算法工作原理

組件級顆粒度

1. 當響應式數據變化時，Vue 會：

   • 標記依賴該數據的組件為"待更新"
   • 觸發這些組件的重新渲染

   // Vue 3 響應式更新偽代碼
   effect(() => {
     if (state.dirty) {
       patchComponent(component); // 更新組件
     }
   });
   

2. 未受影響的組件不會重新渲染，保持高性能

節點級顆粒度（Diff 核心）

在組件內部，Vue 使用優化后的 Diff 算法：

1. 同級比較：只比較相同層級的節點

2. 標簽類型檢查：

   <!-- 標簽不同 ? 銷毀重建 -->
   <div>
     →
     <section>
       <!-- 標簽相同 ? 更新屬性 -->
       <div class="old">
         →
         <div class="new"></div>
       </div>
     </section>
   </div>
   

3. Key 優化策略（列表渲染核心）：

   <!-- 無 key ? 順序比較 -->
   <li v-for="item in items">{{ item }}</li>
   
   <!-- 有 key ? 精確匹配 -->
   <li v-for="item in items" :key="item.id">{{ item.name }}</li>
   

Vue 3 的突破性優化

Vue 3 通過編譯時優化解決顆粒度問題：

1. 靜態提升：將靜態內容移出渲染函數
2. Patch Flags：標記動態節點類型

   // 編譯后的虛擬DOM節點
   {
     type: 'div',
     props: { class: 'active' },
     patchFlag: 1 // 1表示只有class是動態的
   }
   

3. Block Tree：追蹤動態節點樹，跳過靜態子樹比較

Diff 算法的關鍵優化策略

1. 列表渲染與 key 的重要性

顆粒度問題最明顯的場景：

<!-- 問題：列表重新排序 -->
<ul>
  <li v-for="item in items">{{ item.text }}</li>
</ul>

<!-- 解決方案：key 提供節點標識 -->
<ul>
  <li v-for="item in items" :key="item.id">{{ item.text }}</li>
</ul>

• 無 key：默認使用"就地復用"策略，可能導致狀態錯亂
• 有 key：精確匹配節點，保持組件狀態（如輸入框內容）

2. 組件復用策略

Vue 通過組件簽名決定是否復用：

// 決定組件復用的關鍵因素
function canPatch(oldVNode, newVNode) {
  return (
    oldVNode.type === newVNode.type && // 相同組件
    oldVNode.key === newVNode.key // 相同key
  );
}

3. 靜態內容跳過

Vue 3 的突破性改進：

<!-- 靜態內容只生成一次 -->
<div>
  <!-- 靜態提升內容 -->
  <header>Site Title</header>

  <!-- 動態內容 -->
  <main>{{ dynamicContent }}</main>
</div>

• Diff 算法完全跳過靜態節點比較
• 性能接近手動優化的 DOM 操作

為什么 Vue 需要 Diff 算法？

1. 解決顆粒度鴻溝：彌合細粒度的數據變化與粗粒度的 UI 更新之間的差距
2. 開發體驗優先：讓開發者專注于業務邏輯，無需手動優化 DOM 操作
3. 平臺抽象層：為 SSR、小程序等目標平臺提供統一更新機制
4. 性能與效率平衡：在框架開銷與手動優化成本間取得最佳平衡點

性能對比基準

總結

1. 在內存中（虛擬 DOM）進行高效的差異計算。
2. 找出新舊 UI 表示之間的最小變更集。
3. 只將必要的更新應用到昂貴的真實 DOM 上。

vue2 雙端比較算法（雙指針 diff）簡單示例，主要是處理 v-for 關鍵之一：

function sameVNode(a, b) {
  return a.key === b.key && a.tag === b.tag;
}

function updateChildren(parentEl, oldCh, newCh) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let newEndIdx = newCh.length - 1;

  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];

  // 創建舊節點 key 映射
  const keyMap = {};
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    const key = oldCh[i].key;
    if (key) keyMap[key] = i;
  }

  // 可視化步驟
  const steps = [];

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 1. 頭頭比較
    if (sameVNode(oldStartVnode, newStartVnode)) {
      steps.push(`頭頭比較: ${oldStartVnode.key} 和 ${newStartVnode.key} 匹配`);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 2. 尾尾比較
    else if (sameVNode(oldEndVnode, newEndVnode)) {
      steps.push(`尾尾比較: ${oldEndVnode.key} 和 ${newEndVnode.key} 匹配`);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 3. 頭尾比較
    else if (sameVNode(oldStartVnode, newEndVnode)) {
      steps.push(`頭尾比較: ${oldStartVnode.key} 移動到末尾`);
      parentEl.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    }
    // 4. 尾頭比較
    else if (sameVNode(oldEndVnode, newStartVnode)) {
      steps.push(`尾頭比較: ${oldEndVnode.key} 移動到開頭`);
      parentEl.insertBefore(oldEndVnode.el, oldStartVnode.el);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    }
    // 5. key 匹配
    else {
      const idxInOld = keyMap[newStartVnode.key];

      if (idxInOld !== undefined) {
        const vnodeToMove = oldCh[idxInOld];
        steps.push(
          `Key匹配: 找到 ${newStartVnode.key} 并移動到位置 ${newStartIdx}`
        );
        parentEl.insertBefore(vnodeToMove.el, oldStartVnode.el);
        oldCh[idxInOld] = undefined;
      } else {
        steps.push(`創建節點: ${newStartVnode.key} 是新增節點`);
        parentEl.insertBefore(createElm(newStartVnode), oldStartVnode.el);
      }

      newStartVnode = newCh[++newStartIdx];
    }
  }

  // 添加新節點
  if (oldStartIdx > oldEndIdx) {
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      steps.push(`添加節點: ${newCh[i].key}`);
      parentEl.appendChild(createElm(newCh[i]));
    }
  }
  // 刪除舊節點
  else {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      if (oldCh[i]) {
        steps.push(`刪除節點: ${oldCh[i].key}`);
        parentEl.removeChild(oldCh[i].el);
      }
    }
  }

  return steps;
}

function createElm(vnode) {
  const el = document.createElement("div");
  el.className = "node";
  el.textContent = vnode.key + (vnode.key === "E" ? " (新增節點)" : "");
  el.dataset.key = vnode.key;
  vnode.el = el;
  return el;
}

vue3 的簡化 patchKeyedChildren 示例（偽代碼）:

// --------------- 工具函數 ---------------
function isSameVNode(n1, n2) {
  return n1.key === n2.key && n1.type === n2.type;
}
function createElement(vnode) {
  const el = document.createElement(vnode.type);
  if (typeof vnode.children === "string") el.textContent = vnode.children;
  vnode.el = el;
  return el;
}
function mountElement(vnode, container, anchor = null) {
  const el = createElement(vnode);
  container.insertBefore(el, anchor);
}
function unmount(vnode) {
  vnode.el && vnode.el.parentNode.removeChild(vnode.el);
}

// --------------- 核心 patch ---------------
function patch(n1, n2, container) {
  if (!n1) {
    // mount
    mountElement(n2, container);
  } else if (!isSameVNode(n1, n2)) {
    // 替換
    unmount(n1);
    mountElement(n2, container);
  } else {
    // 同類型節點 → 復用 el
    const el = (n2.el = n1.el);
    if (typeof n2.children === "string") {
      if (n2.children !== n1.children) el.textContent = n2.children;
    } else {
      patchKeyedChildren(n1.children, n2.children, el);
    }
  }
}

// --------------- Vue3 風格列表 Diff ---------------
function patchKeyedChildren(c1 = [], c2 = [], container) {
  let i = 0;
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;

  // 1?? 從頭同步
  while (i <= e1 && i <= e2 && isSameVNode(c1[i], c2[i])) {
    patch(c1[i], c2[i], container);
    i++;
  }

  // 2?? 從尾同步
  while (i <= e1 && i <= e2 && isSameVNode(c1[e1], c2[e2])) {
    patch(c1[e1], c2[e2], container);
    e1--;
    e2--;
  }

  // 3?? 新列表更長 → 掛載
  if (i > e1) {
    const anchor = c2[e2 + 1]?.el || null;
    while (i <= e2) mountElement(c2[i++], container, anchor);
    return;
  }

  // 4?? 舊列表更長 → 卸載
  if (i > e2) {
    while (i <= e1) unmount(c1[i++]);
    return;
  }

  // 5?? 處理中間亂序區間
  const s1 = i,
    s2 = i;
  const keyToNewIdx = new Map();
  for (let j = s2; j <= e2; j++) keyToNewIdx.set(c2[j].key, j);

  const toBePatched = e2 - s2 + 1;
  const newIdxToOldIdx = new Array(toBePatched).fill(0);

  // 5.1 先遍歷舊節點，找到可復用的并 patch
  for (let j = s1; j <= e1; j++) {
    const oldVNode = c1[j];
    const newIdx = keyToNewIdx.get(oldVNode.key);
    if (newIdx === undefined) {
      unmount(oldVNode); // 不存在 → 刪除
    } else {
      newIdxToOldIdx[newIdx - s2] = j + 1; // 記錄舊索引（+1 防 0）
      patch(oldVNode, c2[newIdx], container); // 復用并遞歸 patch
    }
  }

  // 5.2 計算 LIS，確定哪些節點可以不動
  const increasingSeq = getLIS(newIdxToOldIdx);
  let seqIdx = increasingSeq.length - 1;

  // 5.3 倒序遍歷新列表，邊插入邊移動
  for (let j = toBePatched - 1; j >= 0; j--) {
    const newIdx = j + s2;
    const newVNode = c2[newIdx];
    const anchor = c2[newIdx + 1]?.el || null;

    if (newIdxToOldIdx[j] === 0) {
      // 新節點
      mountElement(newVNode, container, anchor);
    } else if (j !== increasingSeq[seqIdx]) {
      // 需要移動
      container.insertBefore(newVNode.el, anchor);
    } else {
      // 在 LIS 中，保持不動
      seqIdx--;
    }
  }
}

// --------------- 最長遞增子序列 (O(n log n)) ---------------
function getLIS(arr) {
  const p = arr.slice();
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const n = arr[i];
    if (n === 0) continue; // 0 表示新節點，占位
    let last = result[result.length - 1];
    if (last === undefined || n > arr[last]) {
      p[i] = last;
      result.push(i);
      continue;
    }
    // 二分替換
    let l = 0,
      r = result.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (arr[result[mid]] < n) l = mid + 1;
      else r = mid;
    }
    if (n < arr[result[l]]) {
      if (l > 0) p[i] = result[l - 1];
      result[l] = i;
    }
  }
  // 反向回溯出索引序列
  let u = result.length,
    v = result[result.length - 1];
  const lis = Array(u);
  while (u--) {
    lis[u] = v;
    v = p[v];
  }
  return lis;
}

注：以上主要是個人學習使用，各位大佬自行辨別，有錯誤請指正會進行修改更新。