Vue的Diff算法原理

Vue中的Diff算法（差异算法）是虚拟DOM的核心优化手段，用于对比新旧虚拟DOM树，找出最小变更，高效更新真实DOM，其设计目标是减少DOM操作次数，提升渲染性能

diff算法：

特点：

• 只比较同层的节点，不跨层级对比（若节点跨层级移动，视为销毁和新建），跨层级对比时间复杂度从O(n^3)降为O(n)，极大提高效率
• 同层比较时，如果类型不同，会把该节点和该节点的所有子节点全部销毁
• 相同类型的节点（标签名和key均相同）会被复用，避免重新创建DOM元素

vue2的diff算法是双端比较，双端比较​​是 Vue 中 Diff 算法用于对比新旧子节点列表的一种核心策略，通过​​头尾交叉对比​​的方式，尽可能复用现有 DOM 节点，减少不必要的移动或重建。其核心思想是​​用四个指针（旧头、旧尾、新头、新尾）同时从新旧子节点列表的两端向中间扫描​​，快速匹配可复用的节点，优化性能。

patch源码

function patch(oldVnode, vnode, hydrating, removeOnly) {// 1. 判断新节点是否为空（卸载旧节点）if (isUndef(vnode)) {if (isDef(oldVnode)) invokeDestroyHook(oldVnode); // 触发旧节点销毁钩子return;}let isInitialPatch = false;const insertedVnodeQueue = []; // 收集待触发插入钩子的节点// 2. 旧节点不存在 → 直接创建新节点（首次渲染）if (isUndef(oldVnode)) {isInitialPatch = true;createElm(vnode, insertedVnodeQueue); // 创建 DOM 元素} // 3. 旧节点存在 → 对比更新else {const isRealElement = isDef(oldVnode.nodeType); // 判断旧节点是否为真实 DOM（SSR 场景）// 4. 新旧节点可复用 → 精细化更新（核心 Diff 逻辑）if (!isRealElement && sameVnode(oldVnode, vnode)) {patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly);} // 5. 节点不可复用 → 替换旧节点else {// 5.1 处理服务端渲染（SSR）激活逻辑if (isRealElement) {if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {oldVnode.removeAttribute(SSR_ATTR); // 移除 SSR 标记属性hydrating = true;}// 5.2 执行客户端激活（hydrate）if (isTrue(hydrating)) {if (hydrate(oldVnode, insertedVnodeQueue)) {invokeInsertHook(vnode, insertedVnodeQueue, true); // 触发插入钩子return;}}}// 5.3 创建新节点并替换旧节点const oldElm = oldVnode.elm; // 旧节点对应的真实 DOMconst parentElm = nodeOps.parentNode(oldElm); // 父元素createElm(vnode, insertedVnodeQueue, parentElm, nodeOps.nextSibling(oldElm)); // 插入新节点// 5.4 销毁旧节点if (isDef(parentElm)) {removeVnodes(parentElm, [oldVnode], 0, 0); // 移除旧 DOM}}}// 6. 触发插入生命周期钩子（如 mounted）invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch);return vnode.elm; // 返回新 DOM 元素
}

 patchVnode函数

执行流程：

1. 如果oldVnode和vnode指向同一个对象，直接return，因为同一地址的内容一定相同
2. oldVnode的DOM属性变成Vnode，关联到真实的DOM，对真实DOM进行update，class，style，props，events均被进行更新
3. oldVnode和Vnode如果都是文本节点，看是否为单一节点，是的话直接更新内容即可，vnode.text
4. oldVnode有子节点，Vnode没有子节点，删除oldVnode
5. oldVnode没有子节点，Vnode有子节点，添加节点，并转换为真实DOM，最后挂载到DOM上
6. oldVnode和Vnode都有子节点，updateChildren

patchVnode核心逻辑：

function patchVnode (oldVnode,         // 旧虚拟节点vnode,            // 新虚拟节点insertedVnodeQueue, // 插入队列（用于触发插入钩子）ownerArray,       // 父级节点数组（用于子节点复用）index,            // 当前节点在父数组中的索引removeOnly        // 特殊模式标记（仅用于 transition-group）
) {// 1. 新旧节点地址相同 → 跳过更新if (oldVnode === vnode) return// 2. 克隆复用节点（维护不可变性）if (isDef(vnode.elm) && isDef(ownerArray)) {vnode = ownerArray[index] = cloneVNode(vnode)}// 3. 复用旧节点的 DOM 元素const elm = vnode.elm = oldVnode.elm// 4. 处理异步占位符（SSR 激活）if (isTrue(oldVnode.isAsyncPlaceholder)) {if (isDef(vnode.asyncFactory.resolved)) {hydrate(oldVnode.elm, vnode, insertedVnodeQueue)} else {vnode.isAsyncPlaceholder = true}return}// 5. 静态节点复用优化（跳过 Diff）if (isTrue(vnode.isStatic) &&isTrue(oldVnode.isStatic) &&vnode.key === oldVnode.key &&(isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {vnode.componentInstance = oldVnode.componentInstancereturn}// 6. 执行 prepatch 钩子（组件级预处理）let iconst data = vnode.dataif (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {i(oldVnode, vnode)}// 7. 获取新旧子节点const oldCh = oldVnode.childrenconst ch = vnode.children// 8. 更新节点属性（核心）if (isDef(data) && isPatchable(vnode)) {// 更新属性（class, style, attrs, domProps, events...）for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)// 调用自定义 update 钩子if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)}// 9. 处理文本节点（优化路径）if (isUndef(vnode.text)) {// 非文本节点 → 处理子节点if (isDef(oldCh) && isDef(ch)) {// 新旧都有子节点 → 双端对比算法if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)} else if (isDef(ch)) {// 仅新节点有子节点 → 批量添加if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)} else if (isDef(oldCh)) {// 仅旧节点有子节点 → 批量移除removeVnodes(elm, oldCh, 0, oldCh.length - 1)} else if (isDef(oldVnode.text)) {// 旧节点是文本 → 清空nodeOps.setTextContent(elm, '')}} else if (oldVnode.text !== vnode.text) {// 文本节点 → 直接更新内容nodeOps.setTextContent(elm, vnode.text)}// 10. 执行 postpatch 钩子（组件级后处理）if (isDef(data) && isDef(i = data.hook) && isDef(i = i.postpatch)) {i(oldVnode, vnode)}
}

双端比较原理（updateChildren函数）

vue2diff

function vue2Diff(prevChildren, nextChildren, parent) {let oldStartIndex = 0;let oldEndIndex = prevChildren.length - 1;let newStartIndex = 0;let newEndIndex = newChildren.length - 1;let oldStartNode = prevChildren[oldStartIndex];let oldEndNode = prevChildren[oldEndIndex];let newStartNode = nextChildren[newStartIndex];let newEndNode = nextChildren[newEndIndex];while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {// 头头 尾尾 头尾 尾头if (oldStartNode.key == newStartNode.key) {patch(oldStartNode, newStartNode, parent);oldStartIndex++;newStartIndex++;oldStartNode = prevChildren[oldStartIndex];newStartNode = nextChildren[newStartIndex];} else if (oldEndNode.key == newEndNode.key) {patch(oldEndNode, newEndNode, parent);oldEndIndex--;newEndIndex--;oldEndNode = prevChildren[oldEndIndex];newEndNode = nextChildren[newEndIndex];} else if (oldStartNode.key == newEndNode.key) {patch(oldStartNode, newEndNode, parent);parent.insertBefore(oldStartNode.el,oldEndNode.el.nextSibling)oldStartIndex++;newEndIndex--;oldStartNode = prevChildren[oldStartIndex];newEndNode = nextChildren[newEndIndex];} else if (oldEndNode.key == newStartNode.key) {patch(oldEndNode, newStartNode, parent);parent.insertBefore(oldEndNode.el,oldStartNode.el)oldEndIndex--;newStartIndex++;oldEndNode = prevChildren[oldEndIndex];newStartNode = nextChildren[newStartIndex];}else{// 四次比较都没有比较到// 在prevChildren 当前的key，拿着这个key，遍历nextChildren找有没有相同的keylet newKey =newStartNode.key,oldIndex =prevChildren.findIndex(child=>child.key===newKey)if(oldIndex>-1){let oldNode =prevChildren[oldIndex]patch(oldNode,newStartNode,parent)parent.insertBefore(oldNode.el,oldStartNode.el)prevChildren[oldIndex]=undefined}else {mount(newStartNode,parent,oldStartNode.el)// 在旧的开头创建一个新的节点}newStartNode =nextChildren[++newStartIndex]//更新起始节点}}
//   此时新节点还有节点，旧节点已经处理完毕if(oldEndIndex<oldStartIndex){for(let i=newStartIndex;i<=newEndIndex;i++){mount(nextChildren[i])}// 此时新节点已经处理完毕，没有处理的旧节点需要删除}else if(newEndIndex<newStartIndex){parent.removeChild(prevChildren[i])}
}

vue2比较的时候是全量比较，每次比较都要遍历所有旧节点或者新节点，比较消耗内存

vue3diff优化点

1.静态标记+非全量Diff：Vue3在创建虚拟DOM树的时候，会根据DOM中的内容会不会发生变化，添加一个静态标记，之后在与上次虚拟节点进行对比的时候，就只会对比这些带有静态标记的节点。

2. 使用最长递增子序列优化对比流程，可以最大程度的减少DOM的移动，达到最少的DOM操作

实现思路：

vue3的diff算法其中有两个概念，第一个是相同的前置和后置元素的预处理；第二个则是最长递增子序列 

寻找source中最长递增子序列 ，如果有多个最长递增子序列，则第一个最长递增子序列不动，移动其他元素使得在prevChildren中的元素除了前面和后面相同的元素按照source数组的方式进行移动，比如上述中，prevChildren中的b应该放在d后面，即source1在3后面

function vue3Diff(prevChildren, nextChildren, parent) {let j = 0;let prevEnd = prevChildren.length - 1;let nextEnd = nextChildren.length - 1;let prevNode = prevChildren[j];let nextNode = nextChildren[j];// 1. 从前往后同步相同的前缀节点while (prevNode && nextNode && prevNode.key === nextNode.key) {patch(prevNode, nextNode, parent);j++;prevNode = prevChildren[j];nextNode = nextChildren[j];}// 2. 从后往前同步相同的后缀节点prevNode = prevChildren[prevEnd];nextNode = nextChildren[nextEnd];while (prevNode && nextNode && prevNode.key === nextNode.key) {patch(prevNode, nextNode, parent);prevEnd--;nextEnd--;prevNode = prevChildren[prevEnd];nextNode = nextChildren[nextEnd];}// 3. 处理新增节点（旧列表处理完，新列表有剩余）if (j > prevEnd && j <= nextEnd) {const nextPos = nextEnd + 1;const anchor = nextPos < nextChildren.length ? nextChildren[nextPos].el : null;while (j <= nextEnd) {mount(nextChildren[j], parent, anchor);j++;}return;}// 4. 处理删除节点（新列表处理完，旧列表有剩余）if (j > nextEnd) {while (j <= prevEnd) {unmount(prevChildren[j], parent);j++;}return;}// 5. 处理中间乱序序列（核心优化逻辑）const nextStart = j;const prevStart = j;const nextLeft = nextEnd - j + 1;// 5.1 构建 key 到新索引的映射const keyToNewIndexMap = new Map();for (let i = nextStart; i <= nextEnd; i++) {keyToNewIndexMap.set(nextChildren[i].key, i);}// 5.2 遍历旧列表，标记可复用节点const newIndexToOldIndexMap = new Array(nextLeft).fill(-1);let patched = 0;let moved = false;let maxNewIndexSoFar = 0;for (let i = prevStart; i <= prevEnd; i++) {const prevChild = prevChildren[i];if (patched >= nextLeft) {unmount(prevChild, parent);continue;}const newIndex = keyToNewIndexMap.get(prevChild.key);if (newIndex === undefined) {unmount(prevChild, parent);} else {newIndexToOldIndexMap[newIndex - nextStart] = i;if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;} else {moved = true; // 出现逆序需要移动}patch(prevChild, nextChildren[newIndex], parent);patched++;}}// 5.3 计算最长递增子序列（LIS）const increasingSequence = moved ? getSequence(newIndexToOldIndexMap) : [];let seqIndex = increasingSequence.length - 1;// 5.4 从右向左处理移动和新增for (let i = nextLeft - 1; i >= 0; i--) {const nextIndex = nextStart + i;const nextChild = nextChildren[nextIndex];const anchor = nextIndex + 1 < nextChildren.length ? nextChildren[nextIndex + 1].el : null;if (newIndexToOldIndexMap[i] === -1) { // 新增节点mount(nextChild, parent, anchor);} else if (moved) { // 需要移动的节点if (seqIndex < 0 || i !== increasingSequence[seqIndex]) {move(nextChild.el, parent, anchor);} else {seqIndex--;}}}
}// 最长递增子序列算法（O(n log n)）
function getSequence(arr) {const p = arr.slice();const result = [0];let i, j, u, v, c;const len = arr.length;for (i = 0; i < len; i++) {if (arr[i] !== 0) {j = result[result.length - 1];if (arr[j] < arr[i]) {p[i] = j;result.push(i);continue;}u = 0;v = result.length - 1;while (u < v) {c = (u + v) >> 1;if (arr[result[c]] < arr[i]) {u = c + 1;} else {v = c;}}if (arr[i] < arr[result[u]]) {if (u > 0) p[i] = result[u - 1];result[u] = i;}}}u = result.length;v = result[u - 1];while (u-- > 0) {result[u] = v;v = p[v];}return result;
}

一、双端对比，跳过相同前后缀​​

1. ​​同步前缀节点（从左向右）​​

   while (旧头节点.key === 新头节点.key) {执行 patch 更新属性；旧/新头指针后移；
   }

   ​​作用​​：跳过所有相同的前置节点（如列表头部未变的部分）。

2. ​​同步后缀节点（从右向左）​​

   while (旧尾节点.key === 新尾节点.key) {执行 patch 更新属性；旧/新尾指针前移；
   }

   ​​作用​​：跳过所有相同的后置节点（如列表尾部未变的部分）。

​​双端对比后场景示例​​：

旧列表：[A, B, C, D, E]
新列表：[A, D, B, C, F]↑       ↑ ↑同步前缀  同步后缀
处理后的中间待处理旧区间：B, C, D
新列表的中间待新区间：D, B, C, F

---

​​二、处理极端情况（新增/删除）​​

若双端对比后​​旧或新列表已经处理完毕​​：

1. ​​旧列表处理完 → 新增新列表剩余节点​​

   while（新列表还有未处理节点）{创建新节点并插入到尾部；
   }

2. ​​新列表处理完 → 删除旧列表剩余节点​​

   while（旧列表还有未处理节点）{卸载旧节点及其 DOM；
   }

---

​​三、处理中间乱序部分（LIS 优化核心）​​

当双端对比后新旧列表中间存在乱序时，进入最关键的 ​​最长递增子序列优化​​。

​​步骤分解：​​

1. ​​构建 Key 到新索引的映射​​

   const keyToNewIndexMap = new Map();
   // { D → 1, B → 2, C → 3, F → 4 }

   • ​​目的​​：通过 key 快速查找新节点在旧列表中的位置。

2. ​​遍历旧列表，标记可复用的节点位置​​
   生成 newIndexToOldIndexMap 数组：

   // 新索引 → 旧索引（偏移量处理）
   // 示例结果：[2, 0, 1, -1]（-1 表示新列表中新增）

   • ​​意义​​：[新位置0对应旧索引2, 新位置1对应旧索引0...]

3. ​​计算最长递增子序列（LIS）​​
   使用算法（如动态规划 + 二分）找出递增最多的旧索引顺序：

   const increasingSequence = getSequence(newIndexToOldIndexMap);
   // 示例结果：[0, 1] → 对应新位置的索引0和1（即 B 和 C）

   • ​​优化逻辑​​：最长递增序列中的节点顺序未变，无需移动 DOM。

4. ​​反向遍历新列表中间部分，更新或移动节点​​

   从右向左遍历新列表中间：
   if (节点是新增的) {创建新节点；
   } else if (需要移动) {if (当前节点不在 LIS 中) {移动 DOM 到正确位置；}
   }

   • ​​为什么反向遍历？​​
     DOM 插入操作需要锚点（anchor），反向处理确保锚点节点已处于正确位置。

---

​​四、示例图解：具体更新操作​​

以以下新旧列表为例：

旧列表: [A, B, C, D]
新列表: [A, D, B, C, F] // 新增 F，移动 D 到 B 前

1. ​​双端对比后​​：

   • 处理完前后不变的节点（A);
   • 中间待处理旧区间: [B, C, D]
   • 中间待处理新区间: [D, B, C, F]

2. ​​LIS 优化流程​​：

   • ​​Key-To-Index 映射​​: { D:0, B:1, C:2, F:3 }
   • ​​newIndexToOldIndexMap​​: [2 (D旧索引), 0 (B旧索引), 1 (C旧索引), -1 (F新增)]
   • ​​最长递增子序列​​: [0,1]（对应 B 和 C）
   • ​​操作步骤​​：
     • ​​遍历新列表从右至左（F → C → B → D）​​
     • ​​处理 F​​：newIndexToOldIndexMap[3] = -1 → 新增节点，追加到尾部。
     • ​​处理 C​​：在 LIS 中 → 无需移动。
     • ​​处理 B​​：在 LIS 中 → 无需移动。
     • ​​处理 D​​：不在 LIS → 将旧 D 对应 DOM 移动到 B 之前。

---

​​五、性能优化点​​

策略	效果
​​双端对比快速跳过多余节点​​	避免不必要的遍历，快速缩小处理范围
​​Key 映射快速查找节点​​	直接定位可复用节点，无需遍历旧列表
​​LIS 减少移动次数​​	仅移动非递增序列中的节点，将 DOM 操作次数降到最低（根据数据集降幅可达50%↑）
​​批量 DOM 操作​​	通过反向遍历统一位置计算，减少 DOM 重排次数

---

​​总结​​

Vue3 的 Diff 算法通过 ​​双端对比快速锁定差异范围 + 最长递增子序列最小化移动次数​​，在大部分实际场景中，DOM 操作量与 Vue2 相比大幅减少。尤其是对顺序调整较多的列表（如拖拽排序），性能优势更为显著。