Diff 算法

前言

第 35 篇讲了虚拟 DOM 与key；本篇进入Diff 算法——比较新旧两棵 VNode 树，算出最小 DOM 变更。面试常问：为何同层比较、Vue 2双端 Diff与 Vue 3快速 Diff有何不同、LIS用来干什么、Fiber算不算 Diff 改进。

口诀：同层比、列表靠 key、双端四指针、快速靠 LIS。

一、Diff 在更新流程中的位置

状态变化 → 生成新 VNode 树 → Diff（本篇）→ patch 真实 DOM

单节点比较（类型 → 属性 → 子节点）与列表比较（key+ 双端/快速 Diff）是两层逻辑：先比当前节点，再比 children 数组。

二、单节点 Diff（基础）

functionpatchElement(oldVNode,newVNode){/* 1. 标签/类型不同 → 整节点替换 */if(oldVNode.type!==newVNode.type){replace(oldVNode,newVNode);return;}/* 2. 文本节点 → 只改 nodeValue */if(typeofnewVNode.children==="string"){if(oldVNode.children!==newVNode.children){oldVNode.el.textContent=newVNode.children;}return;}/* 3. 同类型元素 → 比 props，再比子节点（列表走 key Diff） */patchProps(oldVNode,newVNode);patchChildren(oldVNode.children,newVNode.children,oldVNode.el);}

要点：类型不同不做细比，直接替换；列表子节点才进入下文的双端/快速 Diff。

三、同层比较

3.1 核心思想

只比较同一层级的兄弟节点，不尝试把子树整体挪到另一层（跨层移动视为「删旧 + 建新」）。

旧树 新树 A A / \ / \ B C → B D | E 同层比：A↔A、B↔B、C↔D（替换） 不会：把 C「挪」到 E 那一层

3.2 为什么这样做

React / Vue 都采用同层比较 + key 标识列表节点，这是性能与实现复杂度的平衡，不是数学意义上的最优解。

四、key与列表 Diff

第 35 篇已强调：列表必须有稳定key。Diff 在 children 数组上靠key判断「复用 / 移动 / 新增 / 删除」。

以下双端、快速 Diff 均假设children 带 key。

五、双端 Diff（Vue 2 思路）

5.1 四指针

oldStart、oldEnd、newStart、newEnd从两端向中间收缩，每轮依次尝试：

头头：old [A, B, …] new [A, B, …] → ↑↑ 后移 尾尾：old […, C, D] new […, C, D] → ↓↓ 前移 头尾：old [A, …, D] new […, D, A] → A 移到末尾 尾头：old [A, …, D] new [D, A, …] → D 移到开头

5.2 核心循环（示意）

while(oldStartIdx<=oldEndIdx&&newStartIdx<=newEndIdx){if(oldStart.key===newStart.key){patch(oldStart,newStart);oldStart=oldChildren[++oldStartIdx];newStart=newChildren[++newStartIdx];}elseif(oldEnd.key===newEnd.key){patch(oldEnd,newEnd);oldEnd=oldChildren[--oldEndIdx];newEnd=newChildren[--newEndIdx];}elseif(oldStart.key===newEnd.key){patch(oldStart,newEnd);insert(oldStart.el,container,oldEnd.el?.nextSibling);oldStart=oldChildren[++oldStartIdx];newEnd=newChildren[--newEndIdx];}elseif(oldEnd.key===newStart.key){patch(oldEnd,newStart);insert(oldEnd.el,container,oldStart.el);oldEnd=oldChildren[--oldEndIdx];newStart=newChildren[++newStartIdx];}else{/* 注意：findIndex 找不到返回 -1，不能用 > 0 */constidxInOld=oldChildren.findIndex((n)=>n?.key===newStart.key);if(idxInOld!==-1){constvnodeToMove=oldChildren[idxInOld];patch(vnodeToMove,newStart);insert(vnodeToMove.el,container,oldStart.el);oldChildren[idxInOld]=undefined;}else{patch(null,newStart,container,oldStart.el);}newStart=newChildren[++newStartIdx];}}/* 循环结束后：一侧有剩余 → 批量挂载或卸载 */

易错点：findIndex返回0表示第一个元素，条件必须写!== -1，写成> 0会漏掉下标 0。

六、快速 Diff（Vue 3 思路）

借鉴 Inferno，在双端预处理基础上，对中间乱序段用LIS减少 DOM 移动次数。

6.1 五步流程

/* ① ② 头尾同步（与双端思想一致，先吃掉确定相等的部分） */while(i<=e1&&i<=e2&&c1[i].key===c2[i].key){patch(c1[i],c2[i]);i++;}while(i<=e1&&i<=e2&&c1[e1].key===c2[e2].key){patch(c1[e1],c2[e2]);e1--;e2--;}/* ③ ④ 一侧耗尽 */if(i>e1){/* mount 新节点 */}elseif(i>e2){/* unmount 旧节点 */}/* ⑤ 乱序：Map 匹配 + LIS + 倒序挂载/移动 */else{constkeyToNewIndexMap=newMap(/* c2[s2..e2] 的 key → index */);constnewIndexToOldIndexMap=newArray(toBePatched).fill(0);/* 遍历旧节点填 map：0 表示新列表中新增项 */constincreasingSeq=getSequence(newIndexToOldIndexMap);/* 倒序遍历：不在 LIS 中的才 move */}

与 Vue 2 双端相比：中间段不再四轮比较，改为哈希表 + LIS，移动次数更优。

七、最长递增子序列（LIS）

7.1 是什么

在数组里找最长严格递增的下标序列（不要求连续）。

/* 数值数组示例 */[10,9,2,5,3,7,101,18]/* 其一 LIS：2 → 3 → 7 → 18，长度 4 */

7.2 在 Diff 里干什么

乱序段匹配后，newIndexToOldIndexMap[i]表示：新列表第 i 个位置对应旧列表中的旧下标+1（0 表示新增）。

旧 key 顺序：A B C D E 新 key 顺序：A C E B D newIndexToOldIndexMap ≈ [1, 3, 5, 2, 4] （示意） LIS 下标序列对应「相对顺序已正确」的节点 → 不必 move 其余节点才 insert/move

直觉：LIS 越长，需要移动的 DOM 越少。

7.3getSequence（Vue 3 同款，O(n log n)）

functiongetSequence(arr){constp=arr.slice();constresult=[0];for(leti=0;i<arr.length;i++){constarrI=arr[i];if(arrI===0)continue;/* 0 表示新节点，跳过 */constlast=result[result.length-1];if(arr[last]<arrI){p[i]=last;result.push(i);continue;}/* 二分找第一个 >= arrI 的位置并替换 */letu=0,v=result.length-1;while(u<v){constc=(u+v)>>1;if(arr[result[c]]<arrI)u=c+1;elsev=c;}if(arrI<arr[result[u]]){if(u>0)p[i]=result[u-1];result[u]=i;}}/* 回溯得到真实 LIS 下标 */letu=result.length;letv=result[u-1];while(u-->0){result[u]=v;v=p[v];}returnresult;}

面试能说清用途即可，不必默写全文；知道O(n log n)与「减少 move」就够。

八、Vue 2 / Vue 3 / React 对比（适可而止）

React Fiber：主要改的是调度（可中断、分片、优先级），不是换了一套列表 Diff 公式。Diff 仍是同层 +key；Fiber 让大量 Diff/patch不长时间阻塞主线程。口述时别把「Fiber Diff」和「Vue 快速 Diff」混成同一类算法。

九、易混淆点归纳

1. 同层比较是工程启发式，把每层降到O(n)，不是证明意义上的全局最优。
2. 双端 Diff优化比较轮次；快速 Diff优化乱序段的移动次数（LIS）。
3. LIS 标的是「不用动」，不在序列里的才move。
4. findIndex > 0是错的，应为!== -1。
5. index 当 key在增删排序时会导致错误复用（第 35 篇）。
6. Fiber ≠ 新 Diff 公式，是渲染调度架构。

十、思考与练习

1.为什么采用同层比较？

解析：完整树编辑代价高（可达O(n³)）；UI 里跨层挪动少，同层 + key在工程中足够快且实现清晰。

2.双端 Diff 四种命中方式是什么？

解析：头头、尾尾、头尾、尾头；都不中则key 查找或新建。

3.Vue 3 快速 Diff 比 Vue 2 多做了什么？

解析：头尾同步后，乱序段用key → indexMap+newIndexToOldIndexMap+LIS决定谁需要move。

4.LIS 在 Diff 里的输入输出各是什么？

解析：输入是乱序段的newIndexToOldIndexMap；输出是不必移动的新下标序列；其余倒序move。

5.单节点 Diff 与列表 Diff 先后关系？

解析：先比type（不同则替换），再props，最后children；children 是数组且带 key 时走双端/快速 Diff。

6.Fiber 改进了 Diff 吗？

解析：没有换核心比较策略；改进的是可中断调度，让大更新不长时间卡死主线程。

总结

• 同层比较：每层 O(n)，不跨层挪子树。
• 列表靠 key：稳定标识复用与移动，忌用 index。
• Vue 2 双端：四指针 + 中间 key 查找；注意findIndex !== -1。
• Vue 3 快速：头尾同步 → Map 匹配 →LIS减移动。
• React Fiber：调度层能力，别当成「第三种列表 Diff 公式」背。