前端精读《DOM diff 原理详解》：从 O(n³) 全量对比到 Vue / React 的 O(n) 同层 diff

文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载本文以前端精读周刊《DOM diff 原理详解》为核心脉络系统拆解数据驱动时代框架必须接管 DOM diff 的原因、O(n³) 全量对比为何不可行、同层比较如何把复杂度降到 O(n)并逐层还原 Vue 的双指针 Map 最长上升子序列五步算法与 React 的仅右移 lastIndex策略。读完你将理解两大主流框架在节点增删、位移上的核心决策逻辑能看懂面试中的 diff 算法题也能为阅读 Vue / React 源码的 patch 部分打下基础。为什么数据驱动时代DOM diff 必须交给框架DOM diff 是所有现代框架必须做的事其根本原因是前端开发范式从面向操作过程转变为数据驱动视图。理解这个转变才能理解 diff 存在的必要性与代价。jQuery 时代业务手动 diff最高效但心智负担重在 jQuery 时代diff 是由业务代码手动完成的我们调用.append、.move等 DOM 操作函数本质上就是在显式声明如何做 DOM diff。这种方案的执行效率是最高的——因为哪个节点该往哪移动只有业务代码自己最清楚框架不需要任何猜测。但它的代价同样明显心智负担重复杂系统里需要做 DOM diff 的地方太多写起来极其繁琐状态交错易出边界错误当多个状态交错更新时面向过程的手动 diff 容易出现状态遗漏导致难以排查的边界 bug可维护性差即使没有写 bug过程式的手动 DOM 操作代码也难以维护。换句话说jQuery 时代把 diff 的聪明留给了人代价是业务代码的复杂与脆弱。数据驱动框架接管 diff数据驱动范式的思路是我们只关注数据如何映射到 UI。无论业务逻辑多复杂永远只需要解决局部状态到局部 UI的映射这极大降低了复杂系统的维护成本——以前需要老手才能驾驭的 DOM 编排逻辑现在新手也能通过声明式代码完成。但有利必有弊既然业务不再手写 DOM 操作diff 的职责就整体转移给了框架。因此能否高效地做 DOM diff直接决定了数据驱动框架能否应用于生产环境。理想的 DOM diffO(n³) 全量对比为何不可行理想中的 DOM diff应该是滴水不漏地复用所有能复用的节点只有在真正需要新增或删除时才执行插入与删除——这种效果最贴近 jQuery 时代手写 diff 的性能。但程序无法猜到开发者的意图想做到精确复用就必须付出 O(n³) 的时间复杂度这在生产环境完全不可接受因此理想的 diff 算法无法被使用。O(n³) 复杂度的由来原文档给出了清晰的推导左树中任意一个节点都可能出现在右树中所以必须在对左树深度遍历的同时对右树进行深度遍历为每个节点找到对应关系这一层的时间复杂度是 O(n²)找到对应关系后还需要对树各节点执行增、删、移操作这个过程可以理解为又叠加了一层遍历循环两层相乘再乘一层即 O(n²) × n O(n³)。简化的 DOM diff同层比较把复杂度降到 O(n)既然 O(n³) 不可行框架选择了只按层同层比较把时间复杂度直接降为 O(n)。需要特别澄清按层比较并不是广度优先遍历它只判断某个节点自身的子元素间的 diff连跨父节点的兄弟节点都不需要比较。这极大缩小了对比范围。同层 diff 的代价与权衡这样做确实高效但代价是判断得有点傻比如一个跨层移动的操作原文档中以ac为例明明只是位置移动却会被误识别成删除 新增。好在跨 DOM 复用在实际业务场景中很少出现这种笨拙出现的频率实际上非常低。这正是工程思维与学术思维的差异框架是给实际项目用的实际项目中很少出现的场景算法可以不做考虑。同层 diff 的三种结果同层 diff 的对比结果非常简单只有三种情况情况含义处理方式新节点在旧节点中不存在新增插入该节点旧节点在新节点中不存在删除移除该节点节点在两侧都存在但位置不同移动通过位移算法决定移动策略那么同层比较是怎么做到 O(n) 时间复杂度的这就要看具体框架的实现思路了——下文以 Vue 与 React 为例展开。Vue 的 DOM diff双指针 Map 最长上升子序列Vue 的 DOM diff 一共 5 步核心目标是尽量保证不要发生 DOM 位移能跳过就跳过实在要动也要以最少的移动次数完成。第一、二步双指针首尾夹击跳过相同节点第一步从头部开始第二步从尾部开始两头向中间逼近尽可能跳过首尾相同的元素。这种算法一般用双指针实现示意如下基于文章描述整理便于理解调用流程// 示意patchChildren 中处理新旧子节点数组的骨架 function patchChildren(oldChildren, newChildren) { let i 0; // 头指针 let oldEnd oldChildren.length - 1; let newEnd newChildren.length - 1; // 第一步从头部向中间跳过相同的头节点 while (i oldEnd i newEnd oldChildren[i] newChildren[i]) { i; } // 第二步从尾部向中间跳过相同的尾节点 while (i oldEnd i newEnd oldChildren[oldEnd] newChildren[newEnd]) { oldEnd--; newEnd--; } // 第三、四步批量新增 / 批量删除 if (i oldEnd i newEnd) { // 旧树指针已重合、新树还有剩余 剩余全是新增批量插入 } else if (i newEnd i oldEnd) { // 新树指针已重合、旧树还有剩余 剩余在新树中都不存在批量删除 } else { // 第五步两侧都有剩余进入最长上升子序列算法 } }第三、四步批量新增与批量删除如果前两步做完后发现旧树指针重合了、新树还未重合说明新树剩下来的节点全部是新增的批量插入即可反过来如果新树指针重合了、旧树还未重合说明旧树剩下来的节点在新树中都不存在了批量删除即可。这两种情况都非常简单直接。第五步Map 空间换时间如果第 14 步走完之后两侧指针都还有剩余就进入小小算法时间了——需要在 O(n) 时间内把剩余节点处理完。熟悉算法的读者应该能立刻想到要在 O(n) 时间内对一个数组做检测通常要用一个 Map 以空间换时间Vue 正是这么做的。第五步又分为三小步遍历 Old 创建 Map这个 Map 记录了每个旧节点的index下标稍后在 New 中通过它快速查出这个节点原来在哪遍历 New利用 Map 记录下标同时Old 中存在而 New 中不存在的节点说明被删除了直接删除不存在的位置补 0最终拿到e:4 d:3 c:2 h:0这样一个数组——下标 0 表示新增非 0 表示移过来的节点批量转化为插入操作即可。示意如下// 1. 遍历 Old 建立 Map记录每个节点的下标 const oldIndexMap new Map(); oldChildren.forEach((node, index) oldIndexMap.set(node, index)); // 2. 遍历 New查 Map 得到映射数组 const mapped []; newChildren.forEach((node) { const oldIndex oldIndexMap.get(node); if (oldIndex undefined) { remove(node); // Old 中不存在 删除 mapped.push(0); // 3. 不存在的位置补 0代表新增 } else { mapped.push(oldIndex 1); // 记录真实下标代表移过来的节点 } }); // 得到形如 [e:4, d:3, c:2, h:0] 的映射数组 // 下标为 0 的是新增非 0 的是移动最少移动寻找最长上升子序列最后一步的优化非常关键不要看见不同就随便移动为了保证移动次数尽可能少我们要找到那些相对位置有序的元素保持不变只挪动位置明显错误的元素。什么叫相对有序以a b c d e为例a c e这三个字母在 Old 的原始顺序a b c d e中是相对有序的——只要把b d移走a c e的位置自然就正确了。因此问题转化为在 New 数组中找到最长上升子序列。由于已知每个元素的实际下标比如[b:1, d:3, a:0, c:2, e:4]肉眼看去连续自增的子串有b d1, 3和a c e0, 2, 4因为a c e更长所以选择后者保持不动只移动b d。换成程序去做就要采用贪心 二分进行查找即经典的最长递增子序列算法题时间复杂度 O(nlogn)。由于该算法直接得出的结果顺序是乱的Vue 采用提前复制数组的方式辅助找到了正确序列。贪心 二分求 LISO(nlogn)关于最长上升子序列LIS的求解仓库续篇 前沿技术/192.精读《DOM diff 最长上升子序列》.md 有更完整的三种解法推导这里归纳要点暴力解法O(2ⁿ)模拟选或不选每个数字的过程从[0, n]范围内每次都尝试选或不选当前数前提是后选的数字要比前面的大最多生成 2ⁿ 个结果遍历时记录最长的一段。效率太低仅用于建立思维。动态规划O(n²)定义dp(i)为以第 i 个元素结尾的最长上升子序列长度因为子序列不要求连续第 i 项需要和所有j ∈ [0, i-1]逐一对比状态转移方程为dp[i] max(dp[j]) 1 其中 0 j i 且 nums[j] nums[i]总计算次数为1 2 ... n n * (n 1) / 2剔除常数后数量级为 O(n²)。仓库文档 算法/198.精读《算法 - 动态规划》.md 从动态规划视角对这道题有完整推导不连续是它与最大子段和最本质的区别。贪心 二分O(nlogn)方案一句话就能概括——用栈结构如果值比栈内所有值都大则入栈否则替换掉比它大的最小数最后栈的长度就是答案。因为栈内数字始终升序插入位置可以用二分查找单次操作 O(logn)外层循环 n 次整体 O(nlogn)。// 贪心 二分求 LIS 长度基于续篇描述的标准实现 function lengthOfLIS(nums) { const tails []; // tails 始终保持升序 for (const num of nums) { // 二分查找 tails 中第一个 num 的位置 let left 0, right tails.length; while (left right) { const mid (left right) 1; if (tails[mid] num) left mid 1; else right mid; } if (left tails.length) tails.push(num); // 比栈内所有值都大 入栈 else tails[left] num; // 否则替换比它大的最小数 } return tails.length; }为什么替换能同时保证长度正确与未来机会核心在于牺牲栈内容的正确性换取总长度正确同时让每一步都能抓住未来最好的机遇。只要没有替换到最后一个数新插入的值只起占位作用其背后代表的仍是原始队列因此不管怎么换只要没替换完长度就是对的一旦后续遇到潜力更大的序列替换会逐层推进最终得到更长的结果。如果想在得到长度的同时还原出正确序列续篇给出的办法是用二维数组存储被替换的数字保留历史计算完毕后从最后一位向前查找一旦发现某个值不是单调递减就向数组上方继续查找直到首节点。工程代价O(n) 与 O(nlogn) 的取舍Vue 用贪心计算最长上升子序列付出的代价是 O(nlogn) 相对 O(n) 多出的分析时间。但在工程场景中一个父节点的子节点个数不可能太多因此 O(nlogn) 的增长趋势勉强可以接受不会占用太多分析时间换来的是最少的 DOM 移动次数——这是算法与工程结合的比较完美的实践。React 的 DOM diff仅右移策略假设这样一种情况把a移到c后面即旧顺序a b c d e变为新顺序b c a d e。React 从最终状态倒推采用了仅右移策略对元素发生的位置变化只会将其移动到右边——因为右边移完了其他位置自然也就有序了。用右移代替左移React 的做法是遍历 Old 建立 Map这一步与 Vue 一样然后遍历 New 逐项判断。整个过程如下节点旧下标新下标变化React 的决策b10需要左移不左移不动c21需要左移不左移不动a02需要右移执行右移d33不变不动e44不变不动遍历完成后可以看到b和c因为前面的a被抽走了自然发生了左移。这就是用一个右移代替两个左移的高效操作——所有右移做完后左移等于自动做掉了前面的元素右移后自己自然被顶到前面实现了左移的效果。这个例子恰好与之前提到的最佳位移策略吻合。仅右移策略并不是万能的需要清醒认识到这个算法只是歪打误撞碰对了而已。有右移替代左移的算法就有左移替代右移的算法——既然选择了右移替代左移就必然丢失了左移替代右移场景下的效率。什么时候用左移代替右移效率最高把数组最后一位移到第一位的场景。以a b c d e变为e a b c d为例左移显然只要 1 步而右移需要 n-1 4 步。lastIndex右移策略的关键记账右移算法处理这个反例时先找到e它的位置从4变成了0但策略不允许左移所以只能保持不动——悲剧从此开始。不过该做的还是要做这里引出一个此前未提到的概念lastIndex因为e已经在 4 的位置所以再把a从 0 挪到 1 已经不够了此时a应该从 0 挪到 5方法就是记录lastIndex max(oldIndex, newIndex)即lastIndex max(4, 0) 4下一次移动到lastIndex 1也就是 5。处理过程汇总节点旧下标新下标决策e40需左移但禁止不动lastIndex max(4, 0) 4a01oldIndex(0) lastIndex(4)右移到 lastIndex 1 5b12同理右移c23同理右移d34同理右移最终发生了4 次右移e也因此自然左移了 4 次到达首位符合预期。// 示意基于 lastIndex 的仅右移决策逻辑 let lastIndex 0; newChildren.forEach((node) { const oldIndex oldIndexMap.get(node); // 第一步构建的 Map if (oldIndex ! undefined) { if (oldIndex lastIndex) { move(node, lastIndex 1); // 必须右移到 lastIndex 1 } lastIndex Math.max(oldIndex, lastIndex); // 更新 lastIndex } else { insert(node); // 新增节点 } });可以看出这是一个有利有弊的算法它在大部分从左往右移的业务场景中表现较好但在末位移到首位这种场景下会付出 n-1 次移动的代价而新增和删除的处理比较简单与 Vue 差别不大。总结DOM diff 的核心设计考量可以归纳为五点完全对比 O(n³) 无法接受故降级为同层对比的 O(n) 方案降级为何可行跨层级的 DOM 复用很少发生可以忽略同层级也不简单难点在于如何高效位移即用最小步数完成位移Vue 的策略为尽量不移动先左右夹击跳过不变的节点再通过最长上升子序列保持有序部分不动、移动其他元素React 的策略采用仅右移方案在大部分从左往右移的业务场景中得到了较好的性能但存在 lastIndex 带来的额外移动代价。需要说明的是以上是对 Vue 2 / 经典 React diff 实现思路的分析后续框架版本如 Vue 3 基于 key 的快速 diff、React 新架构的 fiber 化更新在实现细节上已有演进但空间换时间、保持有序部分不动、最小化移动等核心思想一脉相承。延伸阅读前沿技术/192.精读《DOM diff 最长上升子序列》.mdLIS 的暴力、动态规划、贪心 二分三种解法推导以及如何找回正确序列的完整方案算法/198.精读《算法 - 动态规划》.md从动态规划视角重解最长递增子序列理解dp[i] max(dp[j]) 1状态转移方程的形成过程readme.md前端精读周刊全部文章索引可继续阅读框架源码、算法等相关系列。赞分享文档技术博客教程【免费下载链接】weekly前端精读周刊。帮你理解最前沿、实用的技术。项目地址https://gitcode.com/GitHub_Trending/we/weekly点击查看免费下载相关推荐React 调和算法diff深度解析reconcileChildren 的比较原理与 O(n) 复用策略React 调和算法diff深度解析reconcileChildren 的比较原理与 O n 复用策略 本文基于 react illustration s教程前端OptiScaler终极指南打破显卡壁垒的免费AI超分辨率解决方案OptiScaler终极指南打破显卡壁垒的免费AI超分辨率解决方案 你是否曾经遇到过这样的困境你的AMD显卡无法使用DLSS或者你的Nvidia老显卡不支图形学游戏开发7个Python算法优化技巧从O(n²)到O(n log n)的性能蜕变7个Python算法优化技巧从O n² 到O n log n 的性能蜕变 在Python编程中算法效率往往决定了程序的性能上限。 GitHub 加速计划 /示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考