说说vue中的diff算法
参考答案
前提:diff 发生在更新时
首次渲染是 createElm 全量创建,没有 diff;diff 只在新旧 VNode 都存在时进行,目标是「用最少 DOM 操作把旧的变成新的」。
Vue 2 的 patch 流程
patch(oldVnode, vnode)
├─ 不是 sameVnode → 销毁旧 + 创建新(replace)
└─ sameVnode → patchVnode
├─ 都是静态节点且已渲染 → 跳过
├─ 文本节点 → 更新 textContent
├─ 有 children → updateChildren
└─ 无 children → 更新 props(attrs/class/style/事件/指令)
sameVnode:key 相同 + tag 相同 + 是否注释相同 + isAsyncPlaceholder 一致。
updateChildren(双端对比)
维护 4 个指针:oldStartIdx/oldEndIdx/newStartIdx/newEndIdx,循环比较 4 组:
- oldStart vs newStart → 相同则 patch 并
start++; - oldEnd vs newEnd → 相同则 patch 并
end--; - oldStart vs newEnd → 相同则 patch 并把 oldStart 移到 oldEnd 之后(移动);
- oldEnd vs newStart → 相同则 patch 并把 oldEnd 移到 oldStart 之前(移动);
- 都不匹配 → 用 key 在旧 children 的 map 里查找:
- 找到则 patch 并移动;
- 找不到则新建并插入。
循环结束后:旧集合还有剩余 → 删除;新集合还有剩余 → 新建插入。
优势:把常见的「头尾增删」优化成 O(1) 级操作,比朴素的「按索引逐位比较 + 移动」少很多 DOM 操作。
Vue 3 的改进
- 靶向更新:编译期
patchFlag标记「文本/class/props 等哪部分会变」,patch 时只处理标记部分,跳过整段 props 比较; - Block 树:
dynamicChildren让 patch 直接遍历动态节点,跳过静态子树,diff 复杂度与动态节点数相关(Vue 3.2+); - **
patchKeyedChildren:同样是双端 + 最长递增子序列(LIS)优化——先用「同步头部、同步尾部」快速跳过相同前缀后缀,中间段用 key map + LIS 找出最多不需要移动**的子序列,把移动次数降到最少(比 Vue 2 的双端更优); - **
patchUnkeyedChildren**:无 key 时按索引 patch,多删少补(并提示应加 key); - shapeFlag 位运算快速判断节点类型。
面试可答的要点
- diff 的目的:最小化 DOM 操作;
- 同层比较(不跨层);
- key 的作用:识别节点身份,避免错位复用;
- 双端对比 vs LIS:Vue 2 双端已能处理大多数场景,Vue 3 用 LIS 处理乱序移动;
- 编译优化让 Vue 3 的 diff 从「遍历整棵 vnode 树」变成「只遍历动态节点」。