Virtual DOM 的 Diff 算法演进：从 Vue 的双端比较到 React 的单端链表遍历

各位同学，大家好！今天我们来深入探讨前端框架中一个至关重要的核心技术：虚拟DOM的Diff算法。这个算法的效率高低，直接决定了我们应用渲染性能的上限。我们将沿着历史的脉络，对比分析Vue 2.x时代经典的双端比较算法，以及React Fiber架构下更具现代意义的单端链表遍历策略，看看它们各自的设计哲学、实现细节、优劣势，以及它们如何演进以适应不断变化的前端需求。

一、引言：虚拟DOM与前端性能优化基石

在前端开发中，DOM操作是昂贵且耗时的。每一次直接的DOM操作，例如元素的创建、删除、修改属性或插入文本，都可能触发浏览器的重排（reflow）和重绘（repaint），从而导致页面卡顿，严重影响用户体验。尤其是在数据频繁更新、UI结构复杂的大型应用中，直接操作DOM几乎是不可接受的。

为了解决这一痛点，虚拟DOM（Virtual DOM）应运而生。虚拟DOM本质上是一个轻量级的JavaScript对象，它代表了真实DOM的结构。当我们应用的状态发生变化时，框架不会直接去修改真实DOM，而是先生成一个新的虚拟DOM树。然后，将这个新的虚拟DOM树与旧的虚拟DOM树进行比较，找出两者之间的差异。这个“找出差异”的过程，就是我们今天的主角——Diff算法。

Diff算法的目标是尽可能高效地计算出最小的DOM操作集合，然后将这些操作批量地应用到真实DOM上。这样，就将昂贵的DOM操作最小化，从而显著提升了前端应用的渲染性能。

二、Diff算法的通用原则与核心假设

尽管Vue和React的Diff算法在实现细节上有所不同，但它们都遵循一些基本原则和核心假设，这些假设是算法高效运作的基石：

1. 同层比较原则（Level-by-level Comparison）：Diff算法通常只比较同一层级的节点，而不会跨层级比较。这意味着，如果一个DOM节点在Diff过程中被移动到了不同的层级，Diff算法不会尝试去“移动”这个节点，而是会销毁旧层级的节点，并在新层级重新创建它及其子节点。这是基于Web UI结构通常稳定的经验法则。
2. 组件类型决定子树结构：如果两个VNode的类型不同（例如，一个<div>变成了<span>），那么框架会认为这两个节点及其子树是完全不同的，会直接销毁旧节点及其所有子节点，然后创建新节点及其所有子节点。这样做比尝试去比较和转换不同类型的子树更为高效。
3. Key属性的重要性：在处理列表类节点时，key属性是Diff算法识别节点身份的关键。当列表中的子节点顺序发生变化，或者有新增/删除时，key能够帮助Diff算法准确地识别哪些节点是同一个，从而进行复用或移动，而不是销毁重建。没有key或key不唯一会导致性能下降和潜在的bug。
4. 深度优先遍历（DFS）的基础：Diff算法通常采用深度优先遍历的方式，从根节点开始，逐层向下比较。

理解了这些基本原则，我们就能更好地理解Vue和React各自算法的精妙之处。

三、Vue 2.x 的双端比较算法：精巧的指针艺术

Vue 2.x 的Diff算法以其在处理列表更新时的优雅和高效而闻名，其核心是“双端比较”（Two-Pointers Comparison）策略。这种策略尤其擅长处理列表头部、尾部插入、删除、反转等常见操作。

3.1 背景与动机

在Vue 2.x中，patch函数负责将旧的VNode树更新为新的VNode树。当需要更新一个元素的子节点列表时，updateChildren函数被调用，它就是双端比较算法的所在地。Vue的设计者观察到，在实际应用中，列表的更新往往发生在两端，例如聊天记录的加载、待办事项的增删等。如果能针对这些常见场景进行优化，将大大提升性能。

3.2 核心思想

双端比较算法的核心思想是维护四个指针：

• oldStartIdx：旧子节点列表的起始索引
• oldEndIdx：旧子节点列表的结束索引
• newStartIdx：新子节点列表的起始索引
• newEndIdx：新子节点列表的结束索引

通过这四个指针，算法能够同时从列表的两端向中间推进，尝试在O(1)复杂度内匹配到可以复用的节点。

3.3 算法步骤详解

updateChildren函数在一个while循环中进行，直到oldStartIdx > oldEndIdx或newStartIdx > newEndIdx，表示其中一个列表已经遍历完毕。在每次循环中，它会尝试进行以下四种匹配尝试：

1. 头头比较（oldStartVnodevsnewStartVnode）：
   如果oldStartVnode和newStartVnode是同一个节点（通过sameVnode函数判断，通常是类型相同且key相同），则直接打补丁（patchVnode），然后将oldStartIdx和newStartIdx都向右移动一位。

   // 伪代码 if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; }

   这种场景对应于列表头部未变动或同步更新。

2. 尾尾比较（oldEndVnodevsnewEndVnode）：
   如果oldEndVnode和newEndVnode是同一个节点，则直接打补丁，然后将oldEndIdx和newEndIdx都向左移动一位。

   else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; }

   这种场景对应于列表尾部未变动或同步更新。

3. 头尾比较（oldStartVnodevsnewEndVnode）：
   如果oldStartVnode和newEndVnode是同一个节点，说明oldStartVnode被移动到了新列表的尾部。同样打补丁，然后将oldStartVnode对应的真实DOM移动到oldEndVnode对应的真实DOM后面。oldStartIdx向右移动一位，newEndIdx向左移动一位。

   else if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode(oldStartVnode, newEndVnode); // 移动真实DOM：将oldStartVnode的真实DOM移动到oldEndVnode的真实DOM后面 parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; }

   这个优化对于反转列表等操作非常高效。

4. 尾头比较（oldEndVnodevsnewStartVnode）：
   如果oldEndVnode和newStartVnode是同一个节点，说明oldEndVnode被移动到了新列表的头部。打补丁，然后将oldEndVnode对应的真实DOM移动到oldStartVnode对应的真实DOM前面。oldEndIdx向左移动一位，newStartIdx向右移动一位。

   else if (sameVnode(oldEndVnode, newStartVnode)) { patchVnode(oldEndVnode, newStartVnode); // 移动真实DOM：将oldEndVnode的真实DOM移动到oldStartVnode的真实DOM前面 parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; }

   与头尾比较类似，也是处理节点移动的优化。

5. Key 比较（Fallback）：
   如果以上四种情况都没有匹配成功，说明需要更通用的查找。此时，算法会遍历oldChildren中oldStartIdx到oldEndIdx之间的节点，尝试在新列表中找到一个匹配的key。

   • 为了提高查找效率，Vue通常会创建一个key-to-index的映射表（oldKeyToIdx）来存储旧列表中节点的key及其索引。
   • 如果newStartVnode的key在oldKeyToIdx中找到了匹配，说明该节点存在于旧列表中的某个位置，那么就将对应的旧节点（oldVnodeToMove）取出进行打补丁。然后将oldVnodeToMove对应的真实DOM移动到oldStartVnode对应的真实DOM前面。

   • 如果newStartVnode没有key，或者key在旧列表中找不到匹配，说明这是一个新节点，需要创建并插入新的真实DOM。

     else { // 创建旧VNode的key到索引的映射表（如果不存在） if (!oldKeyToIdx) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); } // 根据newStartVnode的key在旧列表中查找对应的VNode idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx); if (idxInOld) { // 找到了匹配的旧节点 vnodeToMove = oldCh[idxInOld]; if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(vnodeToMove, newStartVnode); oldCh[idxInOld] = undefined; // 标记为已处理 // 移动真实DOM parentElm.insertBefore(vnodeToMove.elm, oldStartVnode.elm); } else { // key相同但类型不同，无法复用，视为新节点 createElm(newStartVnode, parentElm, oldStartVnode.elm); } } else { // 没有找到匹配，是新节点 createElm(newStartVnode, parentElm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; }

6. 剩余节点的处理：
   当循环结束后：

   • 如果oldStartIdx > oldEndIdx，说明旧列表已经遍历完，但新列表中还有剩余节点（newStartIdx <= newEndIdx），这些都是新增的节点，需要创建并插入真实DOM。
   • 如果newStartIdx > newEndIdx，说明新列表已经遍历完，但旧列表中还有剩余节点（oldStartIdx <= oldEndIdx），这些都是需要删除的节点，需要移除对应的真实DOM。

3.4 代码示例 (简化版 Vue 2.xupdateChildren核心逻辑)

为了更好地理解，我们用伪代码来模拟updateChildren的核心逻辑。

// 假设这是VNode结构 class VNode { constructor(tag, key, children, text, elm) { this.tag = tag; this.key = key; this.children = children; this.text = text; this.elm = elm; // 对应的真实DOM元素 } } // 模拟真实DOM操作 const DOM = { createElement(vnode) { const elm = document.createElement(vnode.tag); if (vnode.text) elm.textContent = vnode.text; vnode.elm = elm; return elm; }, insert(parentElm, elm, refElm) { parentElm.insertBefore(elm, refElm); }, remove(parentElm, elm) { parentElm.removeChild(elm); }, patchProps(oldVnode, newVnode) { // 简化：只更新text if (oldVnode.text !== newVnode.text) { oldVnode.elm.textContent = newVnode.text; } } }; // 比较两个VNode是否相同 (key相同且tag相同) function sameVnode(vnode1, vnode2) { return vnode1.key === vnode2.key && vnode1.tag === vnode2.tag; } // 打补丁：更新节点，并递归更新子节点 function patchVnode(oldVnode, newVnode) { if (oldVnode === newVnode) return; // 引用相同，无需更新 if (!newVnode) { // 新节点不存在，删除旧节点 DOM.remove(oldVnode.elm.parentNode, oldVnode.elm); return; } const elm = newVnode.elm = oldVnode.elm; // 复用真实DOM DOM.patchProps(oldVnode, newVnode); // 更新属性 const oldCh = oldVnode.children; const newCh = newVnode.children; if (newCh && oldCh) { // 核心：双端比较更新子节点 updateChildren(elm, oldCh, newCh); } else if (newCh) { // 旧节点没有子节点，新节点有，添加新子节点 addVnodes(elm, null, newCh, 0, newCh.length - 1); } else if (oldCh) { // 旧节点有子节点，新节点没有，移除旧子节点 removeVnodes(elm, oldCh, 0, oldCh.length - 1); } else if (newVnode.text !== undefined && newVnode.text !== oldVnode.text) { // 新节点是文本节点且文本内容不同，更新文本 elm.textContent = newVnode.text; } } // 辅助函数：创建VNode的真实DOM function createElm(vnode, parentElm, refElm) { const elm = DOM.createElement(vnode); if (vnode.children) { for (let i = 0; i < vnode.children.length; i++) { createElm(vnode.children[i], elm); } } DOM.insert(parentElm, elm, refElm); } // 辅助函数：批量添加VNodes function addVnodes(parentElm, refElm, vnodes, startIdx, endIdx) { for (; startIdx <= endIdx; ++startIdx) { createElm(vnodes[startIdx], parentElm, refElm); } } // 辅助函数：批量移除VNodes function removeVnodes(parentElm, vnodes, startIdx, endIdx) { for (; startIdx <= endIdx; ++startIdx) { const vnode = vnodes[startIdx]; if (vnode && vnode.elm) { DOM.remove(parentElm, vnode.elm); } } } // 辅助函数：创建旧VNode的key到索引的映射表 function createKeyToOldIdx(children, beginIdx, endIdx) { let i, key; const map = {}; for (i = beginIdx; i <= endIdx; ++i) { key = children[i].key; if (key !== undefined) map[key] = i; } return map; } // Vue 2.x updateChildren 核心逻辑 function updateChildren(parentElm, oldCh, newCh) { let oldStartIdx = 0; let newStartIdx = 0; let oldEndIdx = oldCh.length - 1; let newEndIdx = newCh.length - 1; let oldStartVnode = oldCh[0]; let newStartVnode = newCh[0]; let oldEndVnode = oldCh[oldEndIdx]; let newEndVnode = newCh[newEndIdx]; let oldKeyToIdx, idxInOld, vnodeToMove; while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { if (!oldStartVnode) { // 已经被处理过的节点，跳过 oldStartVnode = oldCh[++oldStartIdx]; } else if (!oldEndVnode) { // 已经被处理过的节点，跳过 oldEndVnode = oldCh[--oldEndIdx]; } // 1. 头头比较 else if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(oldStartVnode, newStartVnode); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; } // 2. 尾尾比较 else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(oldEndVnode, newEndVnode); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; } // 3. 头尾比较 (oldStartVnode 移动到 oldEndVnode 后面) else if (sameVnode(oldStartVnode, newEndVnode)) { patchVnode(oldStartVnode, newEndVnode); DOM.insert(parentElm, oldStartVnode.elm, oldEndVnode.elm.nextSibling); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; } // 4. 尾头比较 (oldEndVnode 移动到 oldStartVnode 前面) else if (sameVnode(oldEndVnode, newStartVnode)) { patchVnode(oldEndVnode, newStartVnode); DOM.insert(parentElm, oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; } // 5. 以上四种情况都不匹配，使用key进行通用查找 else { if (!oldKeyToIdx) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); } idxInOld = newStartVnode.key ? oldKeyToIdx[newStartVnode.key] : undefined; // 如果没key，则不进行查找优化 if (idxInOld !== undefined) { // 找到了匹配的旧节点 vnodeToMove = oldCh[idxInOld]; if (sameVnode(vnodeToMove, newStartVnode)) { patchVnode(vnodeToMove, newStartVnode); oldCh[idxInOld] = undefined; // 标记为已处理 DOM.insert(parentElm, vnodeToMove.elm, oldStartVnode.elm); } else { // key相同但tag不同，视为新节点 (实际Vue会更严格，这里简化) createElm(newStartVnode, parentElm, oldStartVnode.elm); } } else { // 没有找到匹配，是新节点 createElm(newStartVnode, parentElm, oldStartVnode.elm); } newStartVnode = newCh[++newStartIdx]; } } // 6. 循环结束，处理剩余节点 if (oldStartIdx > oldEndIdx) { // 旧列表处理完，新列表还有，说明是新增节点 // newEndIdx + 1 是插入的参考节点 (null表示插入到最后) const refElm = (newCh[newEndIdx + 1]) ? newCh[newEndIdx + 1].elm : null; addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx); } else if (newStartIdx > newEndIdx) { // 新列表处理完，旧列表还有，说明是删除节点 removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); } }

3.5 适用场景与优势

Vue 2.x的双端比较算法在以下场景表现出色：

• 列表反转：只需两次DOM移动操作（头尾、尾头各一次），而不是重建所有节点。
• 列表头部/尾部增删：O(1)或O(N)（N为移动节点数）的复杂度，非常高效。
• 部分节点移动：在特定情况下，例如将旧列表的第一个节点移动到新列表的倒数第二个节点，也能通过头尾或尾头比较直接命中。

其主要优势在于精细化的局部优化，通过四种快速比较，避免了不必要的循环查找，在许多常见列表操作中能达到很高的效率。

3.6 局限性

尽管双端比较很巧妙，但它也有局限性：

• 当节点在列表中间发生移动，且不满足四种指针的直接匹配条件时，算法会退化到通过key进行遍历查找，此时效率会下降。
• 对于大量无key的节点，或者key不唯一的情况，其性能会受到严重影响，甚至可能导致不正确的DOM更新。

四、React 的单端链表遍历与Fiber架构：面向未来的可中断更新

React的Diff算法，在React 16引入Fiber架构后，发生了根本性的演进。它不再追求在单个函数调用中完成所有Diff工作，而是将其拆分为可中断、可调度的单元。React的Diff过程更准确地说是“Reconciliation”（协调）。

4.1 背景与动机

在React 15及以前，Reconciliation是一个同步的、递归的过程，一旦开始就不能中断，这在大型复杂应用中可能导致长任务，阻塞主线程，造成页面卡顿。React 16引入的Fiber架构，其核心目标是实现可中断的更新和优先级调度。为了实现这一目标，Diff算法也必须从同步递归转变为异步可中断的模式。

4.2 核心思想

React的Reconciliation过程是深度优先遍历，但它将整个工作拆分成了两个主要阶段：

1. Render/Reconciliation阶段（Work Phase）：在这个阶段，React会遍历组件树，执行Diff算法，找出需要更新的节点，并构建一个“副作用列表”（Effect List）。这个阶段是可中断的。它会生成新的Fiber节点，并与旧的Fiber节点进行比较。
2. Commit阶段（Commit Phase）：在这个阶段，React会将Render阶段计算出的所有变更一次性应用到真实DOM上。这个阶段是同步且不可中断的。

在Render阶段进行Diff时，React采用了一种从左到右的单端遍历策略，结合key属性来优化列表的更新。

4.3 Reconciliation 阶段 (Diffing)

React的Diff算法在处理子节点时，会根据子节点的数量采取不同的策略：

1. 单节点子代 (Single Child)：
   如果旧的子节点只有一个，新的子节点也只有一个，那么直接比较这两个节点。

   • 类型不同：直接替换旧节点为新节点（销毁旧子树，创建新子树）。
   • 类型相同：复用旧节点，递归进行属性更新和子节点Diff。
   • Key相同但类型不同：同样视为类型不同，替换。

2. 多节点子代 (Multiple Children – 列表)：
   这是Diff算法最复杂的部分，React采用两轮遍历来处理。

   • 第一轮遍历：尝试按顺序匹配和复用

     • 从左到右遍历新旧子节点列表。
     • 如果oldChild[i]和newChild[i]的key和type都相同，则复用旧节点，打补丁，然后继续下一个。
     • 如果key或type不匹配，或者旧列表已经遍历完，则停止第一轮遍历。
     • 这一轮的目的是处理那些没有移动、仅仅是更新或少量增删的节点。

   • 第二轮遍历：处理剩余节点（移动、删除、新增）

     • 如果旧列表已经遍历完，新列表还有剩余：说明这些剩余的新节点都是新增的，直接创建并插入DOM。
     • 如果新列表已经遍历完，旧列表还有剩余：说明这些剩余的旧节点都是需要删除的，直接移除DOM。
     • 新旧列表都有剩余：这是最复杂的情况，涉及节点的移动。
       • React会为旧列表中剩余的节点创建一个key-to-index的映射表（oldChildrenMap），方便通过key快速查找。
       • 然后继续遍历新列表中剩余的节点：
         • 如果newChild.key在oldChildrenMap中找到了匹配：
           • 获取对应的oldChild。
           • 如果oldChild和newChild的type相同，则复用oldChild，打补丁，并将oldChild在oldChildrenMap中标记为已处理（例如设置为null或undefined）。
           • 如果oldChild和newChild的type不同，则不能复用，创建新节点。
           • 关键的移动判断：React会跟踪一个lastPlacedIndex。如果当前匹配到的oldChild的索引小于lastPlacedIndex，说明这个节点被向前移动了，需要执行DOM移动操作。否则，它要么没有移动，要么向后移动了（不需要显式移动，因为后续节点会插入到它后面）。lastPlacedIndex会更新为当前匹配到的oldChild的索引和lastPlacedIndex中的较大值。
         • 如果newChild.key在oldChildrenMap中没有找到匹配，说明这是一个新节点，需要创建并插入DOM。
       • 最后，遍历oldChildrenMap中所有未被标记为已处理的旧节点，这些是需要删除的节点，执行DOM移除操作。

4.4 Fiber 架构对 Diff 的影响

Fiber架构将Diff过程分解为一系列小的工作单元（Work Unit）。每个Fiber节点代表一个工作单元，包含当前组件的信息、状态以及指向父节点、子节点和兄弟节点的指针，形成一个单向链表。

• beginWork阶段：从父Fiber开始向下遍历，对当前Fiber节点进行Diff操作。如果当前Fiber有子节点，则会创建子Fiber并连接起来。这就是“向下调和”的过程。
• completeWork阶段：当一个Fiber节点的所有子节点都处理完毕后，就会进入completeWork阶段，从子Fiber向上归并。这个阶段会收集当前节点及其子节点的所有副作用（DOM操作，如插入、更新、删除），并添加到父Fiber的effect list中。
• 可中断性：在beginWork阶段，React可以在处理完一个Fiber节点后，检查是否有更高优先级的任务，或者时间切片是否用完。如果需要，它可以暂停当前的Diff工作，稍后再恢复。
• 副作用列表：effect list是一个单向链表，包含了所有需要对真实DOM进行操作的Fiber节点。Commit阶段就是遍历这个effect list，高效地批量执行DOM操作。

4.5 代码示例 (概念性 React Reconciliation 过程)

由于React Fiber的内部实现非常复杂，这里提供一个高度简化的概念性伪代码，以展示其单端遍历和Key匹配的核心逻辑。

// 假设这是Fiber节点结构 class Fiber { constructor(type, key, props, stateNode = null) { this.type = type; // 组件类型或DOM标签 this.key = key; this.props = props; this.stateNode = stateNode; // 对应的真实DOM或组件实例 this.return = null; // 父Fiber this.child = null; // 第一个子Fiber this.sibling = null; // 下一个兄弟Fiber this.pendingProps = props; // 等待处理的props this.memoizedProps = null; // 已处理的props this.updateQueue = null; // 状态更新队列 this.effectTag = null; // 副作用标记 (Placement, Update, Deletion等) this.nextEffect = null; // 指向下一个有副作用的Fiber (用于构建effect list) } } // 辅助函数：创建真实DOM (简化) function createDOMElement(fiber) { if (typeof fiber.type === 'string') { fiber.stateNode = document.createElement(fiber.type); // 简化：只处理文本内容 if (fiber.props.children && typeof fiber.props.children === 'string') { fiber.stateNode.textContent = fiber.props.children; } } // 标记为需要插入 fiber.effectTag = 'Placement'; return fiber.stateNode; } // 辅助函数：更新真实DOM属性 (简化) function updateDOMProperties(oldFiber, newFiber) { // 简化：只更新文本内容 if (oldFiber.props.children !== newFiber.props.children) { oldFiber.stateNode.textContent = newFiber.props.children; newFiber.effectTag = 'Update'; // 标记为需要更新 } } // 比较两个Fiber节点是否可复用 function sameFiber(oldFiber, newFiber) { return oldFiber && newFiber && oldFiber.key === newFiber.key && oldFiber.type === newFiber.type; } // React reconciliation 核心逻辑 (高度简化，只关注子节点调和) function reconcileChildren(returnFiber, currentChildren, newChildren) { let oldFiber = currentChildren ? currentChildren.child : null; // 旧的第一个子Fiber let newIdx = 0; let prevSibling = null; // 用于构建新的兄弟链表 // --- 第一轮遍历：尝试按顺序匹配和复用 --- while (oldFiber && newIdx < newChildren.length) { const newChild = newChildren[newIdx]; if (sameFiber(oldFiber, newChild)) { // 复用旧Fiber，更新props const newFiber = new Fiber(oldFiber.type, oldFiber.key, newChild.props, oldFiber.stateNode); updateDOMProperties(oldFiber, newFiber); // 标记更新副作用 newFiber.return = returnFiber; if (prevSibling) { prevSibling.sibling = newFiber; } else { returnFiber.child = newFiber; } prevSibling = newFiber; oldFiber = oldFiber.sibling; newIdx++; } else { // key或type不匹配，停止第一轮 break; } } // --- 第二轮遍历：处理剩余节点 (移动、删除、新增) --- if (newIdx < newChildren.length) { // 新列表还有剩余节点 (新增或移动) const existingChildren = new Map(); // 用于存储旧节点，通过key查找 // 构建旧列表中剩余节点的key-to-Fiber映射 let currentOldFiber = oldFiber; while (currentOldFiber) { if (currentOldFiber.key !== null) { existingChildren.set(currentOldFiber.key, currentOldFiber); } currentOldFiber = currentOldFiber.sibling; } let lastPlacedIndex = 0; // 记录旧节点在旧列表中的最大索引 for (; newIdx < newChildren.length; newIdx++) { const newChild = newChildren[newIdx]; let newFiber = null; let matchedOldFiber = null; if (newChild.key !== null) { matchedOldFiber = existingChildren.get(newChild.key); } if (matchedOldFiber) { // 找到了匹配的旧节点 if (matchedOldFiber.type === newChild.type) { newFiber = new Fiber(matchedOldFiber.type, matchedOldFiber.key, newChild.props, matchedOldFiber.stateNode); updateDOMProperties(matchedOldFiber, newFiber); // 标记更新副作用 existingChildren.delete(matchedOldFiber.key); // 标记为已处理 // 判断是否需要移动 if (matchedOldFiber.index < lastPlacedIndex) { newFiber.effectTag = 'Placement'; // 标记为移动 } else { lastPlacedIndex = matchedOldFiber.index; // 更新最大索引 } } else { // key相同但type不同，不能复用，创建新节点 newFiber = new Fiber(newChild.type, newChild.key, newChild.props); createDOMElement(newFiber); // 标记插入副作用 } } else { // 没有找到匹配，是新节点 newFiber = new Fiber(newChild.type, newChild.key, newChild.props); createDOMElement(newFiber); // 标记插入副作用 } if (newFiber) { newFiber.return = returnFiber; if (prevSibling) { prevSibling.sibling = newFiber; } else { returnFiber.child = newFiber; } prevSibling = newFiber; } } // 处理剩余的旧节点 (删除) existingChildren.forEach(fiberToDelete => { fiberToDelete.effectTag = 'Deletion'; // 标记删除副作用 // 将删除的fiber添加到父fiber的effect list中 addEffect(returnFiber, fiberToDelete); }); } else if (oldFiber) { // 新列表处理完，旧列表还有剩余 (删除) while (oldFiber) { oldFiber.effectTag = 'Deletion'; // 标记删除副作用 // 将删除的fiber添加到父fiber的effect list中 addEffect(returnFiber, oldFiber); oldFiber = oldFiber.sibling; } } // 返回新的子Fiber链表的头部 return returnFiber.child; } // 模拟addEffect函数，将有副作用的Fiber添加到父Fiber的effect list function addEffect(returnFiber, fiber) { if (returnFiber.firstEffect) { returnFiber.lastEffect.nextEffect = fiber; } else { returnFiber.firstEffect = fiber; } returnFiber.lastEffect = fiber; } // 假设Fiber节点有一个index属性，表示它在兄弟节点中的位置 (用于lastPlacedIndex) // 在实际React中，这个index是在 reconcile 过程中动态计算和使用的 // 这里的伪代码简化了这一点，假设它存在 // oldFiber.index = ...

关键点说明：

• effectTag：每个Fiber节点在Diff过程中会被打上一个标记，表示它需要进行的DOM操作（Placement表示插入/移动，Update表示更新属性，Deletion表示删除）。
• nextEffect：带有effectTag的Fiber节点会被串联成一个单向链表，称为effect list。Commit阶段就是遍历这个链表来执行DOM操作。
• lastPlacedIndex：这是React处理节点移动的关键。它记录了上一个被复用的旧节点在旧列表中的索引。如果当前被复用的旧节点的索引小于lastPlacedIndex，说明它相对于之前的节点是向前移动了，需要进行DOM移动操作。如果大于或等于，则不需要显式移动，因为它会自然地被插入到正确的位置（或者它本身就是后移的）。

4.6 优势

• 与Fiber架构完美结合：支持可中断、优先级调度更新，显著提升大型应用的用户体验，避免了主线程阻塞。
• 灵活性和可扩展性：基于链表结构和effectTag机制，更容易实现并发模式、时间切片等高级特性。
• 大多数UI场景下表现良好：对于常见的组件更新、属性变更、列表少量增删，其效率是足够的。

4.7 局限性

• 特定场景下的DOM操作可能更多：相较于Vue 2.x的双端比较，在极端列表操作（如列表反转，且所有节点都有key）下，React可能需要执行更多的DOM移动操作。例如，如果一个列表被完全反转，Vue可能只需要两次移动，而React可能需要遍历并移动大部分节点。
• 算法本身的复杂性更高：与Fiber架构深度耦合，理解其内部工作原理需要更多背景知识。
• 对key的依赖更强：如果列表中没有key，React的Diff效率会非常低，因为它无法识别节点的身份，只能进行顺序比较，可能导致大量不必要的DOM创建和销毁。

五、Vue 与 React Diff 算法的对比与哲学差异

通过对Vue 2.x双端比较和React单端遍历（结合Fiber）的深入分析，我们可以总结出它们在设计理念和实现上的异同。

性能考量：
单纯从Diff算法的“最小DOM操作”这个角度来看，Vue 2.x的双端比较在某些特定列表操作（如反转）上确实可能比React的单端遍历更“省”DOM操作。然而，这并不是衡量一个框架整体性能的唯一标准。React Fiber架构的引入，将Diff过程与整个应用的调度机制结合起来，实现了可中断更新，这意味着即使Diff计算量稍大，它也可以被分解为小块，分时执行，从而避免阻塞主线程，给用户感觉应用始终是响应的。这在大型、交互复杂的应用中，对用户体验的提升是巨大的。

设计哲学：

• Vue更倾向于“尽可能地优化渲染”，通过精巧的算法在运行时减少DOM操作的绝对数量。Vue 3.x在此基础上，通过编译时优化进一步缩小了Diff的范围。
• React更倾向于“尽可能地优化用户体验和调度”，通过可中断的Diff和优先级调度来确保UI的响应性，即使这意味着在某些边缘情况下可能执行更多的DOM操作。它将Diff视为一个可被调度的任务。

六、Diff 算法的演进与未来趋势

Diff算法作为虚拟DOM的核心，一直在不断演进。

1. Vue 3.x 的编译时优化：
   Vue 3.x在Diff算法层面做了革命性的改进，但并非完全抛弃了双端比较。它引入了PatchFlag和Block Tree的概念。

   • PatchFlag：在编译模板时，Vue编译器会静态分析模板，并为每个VNode打上一个PatchFlag，标记这个VNode将来可能发生变化的类型（例如，只改变文本内容、只改变属性、只改变子节点等）。
   • Block Tree：Vue 3.x将模板中的动态节点（例如v-for、v-if等）以及这些动态节点下的静态节点，组织成一个“块（Block）”。Diff时，Vue可以直接跳过静态节点和静态子树的比较，只比较带有PatchFlag的动态节点，甚至只比较一个Block内的变化。
   • 结果：Vue 3.x的Diff算法结合了编译时优化，使得运行时Diff的范围大大缩小，效率更高，即使对于那些双端比较不擅长的场景，也能通过跳过无关比较来提升性能。

2. React 的并发模式与时间切片：
   React的Fiber架构是为并发模式（Concurrent Mode）和时间切片（Time Slicing）打下基础。Diff算法作为Render阶段的一部分，是可中断的。这意味着React可以根据任务的优先级和浏览器空闲时间来调度Diff工作。高优先级的更新（如用户输入）可以中断低优先级的更新（如数据加载），从而保证应用的响应性。

3. 框架对Diff算法的透明化：
   无论是Vue还是React，它们都在努力让Diff算法对开发者来说是透明的。开发者无需关心内部细节，只需要遵循框架的最佳实践（如使用key），就能获得良好的性能。然而，理解Diff算法的原理，对于开发者在遇到性能瓶颈时进行优化、写出更高效的代码是至关重要的。

4. WebAssembly/Rust等技术对前端渲染的潜在影响：
   随着WebAssembly等技术的成熟，未来前端渲染的性能瓶颈可能会进一步被突破。一些框架（如Svelte、Solid.js）已经尝试通过编译时生成更优化的原生DOM操作代码，绕过虚拟DOM的运行时Diff开销。但对于复杂、动态变化的UI，虚拟DOM和其Diff算法在开发效率、维护性和通用性方面仍有不可替代的优势。

七、深入理解Diff算法，是提升前端应用性能和用户体验的关键。

Diff算法是现代前端框架的灵魂之一。通过对比Vue 2.x的双端比较和React Fiber架构下的单端链表遍历，我们看到了两种不同的设计哲学：Vue倾向于在算法层面进行精细的局部优化，而React则将Diff融入更宏大的可调度、可中断的更新体系，以优化整体用户体验。两者都在不断演进，通过编译时优化、并发模式等手段，持续提升前端应用的性能和响应性。作为开发者，深入理解这些核心原理，不仅能帮助我们更好地使用框架，更能为我们未来面对复杂场景的性能优化提供坚实的理论基础。