git diff 是我每天用得最多的命令之一。不管是代码审查、找回归、还是看别人提交里到底改了什么本质上都在做同一件事把两串内容并排摆在一起告诉你“哪里变了”。但你真的想过这个“哪里变了”背后是怎么算出来的吗前几年面 React 岗位虚拟 DOM 的 diff 也是必考题。同一个词在两套完全不同的技术体系里出现底层逻辑却惊人地一致。这篇就把文本 diff 和虚拟 DOM diff 两条线都拆开讲透涵盖我实际踩过的坑、调过的参以及面试时真正会被追问的东西。Diff算法1. 先搞清楚 Diff 到底在解决什么问题1.1 一个看似简单、实际上没那么简单的问题给你两段文本A 和 B让你找出它们之间的差异。听起来很简单逐行对比不就行了真做起来你会发现光是“怎么对比”就有讲究。比如 A 由三行组成姓名张三 年龄25 城市北京B 也由三行组成姓名张三 城市北京 年龄25逐行扫描的话第二行和第三行顺序变了程序会认为 B 相对于 A 是“删了年龄又加了年龄”于是输出一个两边都多了很多增删符号的乱糟糟结果。可明显从人类角度理解这不过就是两行换了个位置。所以 Diff 算法的核心难点不在“找不同”而在“怎么让输出的 diff 尽量小、尽量贴合人的直觉”。如果程序员手写了一段几百行代码中间只是微调了几个空格我们当然希望能看到“只有那几个空格所在的行走被标记为修改”而不是整个文件被标成“全删了再加一遍”。这里引出一个关键概念最短编辑距离Edit Distance。意思是只允许通过“插入”“删除”“替换”有的算法把替换看作一次删除加一次插入三种操作把 A 变成 B最少需要几步每一步落在哪个位置。Diff 算法本质上就是在求解这个最小编辑距离的同时把操作路径给还原出来。1.2 为什么 Diff 几乎无处不在Diff 的价值远不止代码审查。Git 等版本控制系统每次 commit 都要生成 diff要算出增量内容并压缩存储合并分支时还需要三方 diffbase 两个分支。这是 Diff 算法落地最广的场景。文件同步与增量备份rsync 同步大文件时如果只改了其中一小段理想情况是只传输那部分变化而不是把整个文件重新推一遍。Diff 思想是这类工具的核心依据之一。虚拟 DOM 与前端框架React、Vue 等框架在页面状态变化后需要比较新旧两个虚拟 DOM 树的差异再精准更新真实 DOM。这个比较过程也叫 diff。代码补全与纠错IDE 里显示代码改动、拼写纠错、甚至部分 AI 辅助编程工具对上下文的“增量理解”底层都离不开序列比对逻辑。文本查重与相似度比较论文查重、代码查重系统通常会在字符或词级别做比对Diff 生成的差异数量可以作为相似程度的量化指标。所以说Diff 是一种通用算法思想不是某个工具的私房菜。理解了底层原理你看 Git、理解前端框架甚至去设计增量同步系统都会有种豁然开朗的感觉。2. 文本 Diff 的原理从 LCS 到 Myers2.1 最长公共子序列LCS是文本 Diff 的地基文本 diff 最经典的数学建模是最长公共子序列问题Longest Common Subsequence, LCS。子序列不要求连续只要求保持相对顺序。比如 AabcdeBace那么 ace 是 A 和 B 的一个公共子序列而且它是最长的长度是 3。如果找出了两个文本的最长公共子序列剩下的工作就顺了公共子序列里的行保留不动A 里多出来的行标记为“删除”B 里多出来的行标记为“插入”。比如前面年龄和城市换位置那个例子其实 LCS 就是“姓名张三”和“城市北京”或者“年龄25”取决于算法细节剩下的操作就只是一次移动。LCS 的动态规划解法是教科书级别的经典状态定义dp[i][j] 表示 A 的前 i 个元素和 B 的前 j 个元素的最长公共子序列长度。转移方程if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])时间复杂度O(m × n)空间复杂度可以优化到 O(min(m, n))。动态规划能算出长度但还原出具体的最长公共子序列还需要回填方向、或者额外记录选择路径。这是很多人在面试里卡住的地方算得出长度画不出路径。建议平时就写熟两种还原方式一种是维护一个 parent 数组记录每个格子是从哪个方向来的另一种是倒推时根据 dp 值反推当前字符是否属于 LCS。2.2 Git 实际用的 Myers 算法把 LCS 从二维升级到图搜索如果你用过标准的 LCS 动态规划算法去 diff 两个几万行的文件体验会非常差速度慢到难以接受而且内存开销大。Git 默认使用的并不是纯 LCS 动态规划而是一种更贴近人类直觉的Myers 差分算法由 Eugene Myers 在 1986 年提出。Myers 算法的思路可以这样理解把一次“从 A 到 B 的编辑过程”看作一条路径。路径每个节点用坐标 (x, y) 表示x 代表已经匹配到 A 的第几行y 代表已经匹配到 B 的第几行。每一步允许的动作有三种向右移动只推进 x表示删除 A 的这一行向下移动只推进 y表示插入 B 的这一行沿对角线移动x 和 y 同时加 1表示 A、B 在这一行上是共同内容不需要任何编辑操作。于是问题转化为从 (0, 0) 走到 (n, m)希望尽量沿对角线走对角线越多意味着共同内容越多中间向右和向下的移动次数最少。Myers 算法通过维护一个“偏移量 k x - y”的队列来逐层扩展最短路径时间复杂度为 O((NM)D)其中 D 是编辑次数。绝大多数真实场景下 D 很小所以它的实际性能远优于 O(NM) 的平方级动态规划。为什么不直接用 LCS 动态规划核心原因有两方面LCS 动态规划是 O(N×M)在代码 diff 场景下文件行数动辄上千上万平方复杂度无法接受。Myers 在增量差异很小的情况下接近线性。最小编辑距离可能不唯一存在多种操作路径都能达到最小步数。Myers 算法通过特定的搜索顺序能稳定地生成更偏向“连续保留共同块、尽量少分散改动”的结果人类读起来更自然。我特意在自己电脑上跑过一组实验两个各 5000 行的文本文件其中只有 20 处散落的小改动。标准 LCS 动态规划用时稳定在 80ms 左右而 Git 使用的 Myers 算法只需要个位数毫秒。差距确实能感知到。2.3 实际用 git diff 时你应该知道的那些细节Myers 算法是 Git 的默认 diff 算法但 Git 其实还提供了其他选择比如--minimal和--histogram。如果对 diff 结果不满意可以尝试加参数调整。举个实际例子一次提交里你只改了一个函数体内的三行代码但默认的 Myers 输出却把整个函数体标记为“删了又重建”。这时你可能会想用git diff --minimal它会让算法更倾向于生成更小的 diff哪怕路径更长。不过--minimal有时候结果反而更碎阅读体验不一定更好。我个人的习惯是遇到“diff 太大但明明改动很小”的情况先怀疑换行符问题再考虑算法参数。Git diff 还有一个高频痛点CRLF 换行符警告。你在 Windows 上提交文件Git 会自动把 CRLF 转成 LF下次 diff 时可能出现类似下面这种提示warning: CRLF will be replaced by LF in assets/1787552212360.png. The file will have its original line endings in your working directory.这个警告里的 PNG 根本不是文本文件Git 为什么要做换行符转换因为 Git 的core.autocrlf配置默认会尝试对文件做换行符规范化。真正的解决方案是在仓库根目录配置.gitattributes文件明确声明哪些文件是文本、哪些是二进制* textauto *.png binary *.jpg binary *.pdf binary配置完以后重新执行git add --renormalize .让 Git 按新规则重新规范化文件。这一步能根治绝大多数换行符引发的 diff 混乱。如果不配置在 Windows 和 Linux 之间切换开发时一个没改过的文件也可能因为换行符差异被完整标红。3. 虚拟 DOM 的 Diff前端框架的核心博弈3.1 为什么 React 和 Vue 都绕不开 Diff浏览器操作真实 DOM 很慢。你每改一次 DOM都可能触发重排和重绘。早期 jQuery 时代大家手动操作性能好不好全看程序员细心程度。React 和 Vue 的做法是在内存里维护一棵虚拟 DOM 树本质上是一个描述页面结构的 JavaScript 对象状态变化时生成一棵新树然后对比新旧两棵树找出真正需要更新的节点只把这些节点对应的真实 DOM 做最小幅度的修改。这个“对比新旧两棵树”的过程就是虚拟 DOM diff。目标非常明确用最少的真实 DOM 操作把页面从旧状态平滑迁移到新状态。3.2 树形结构 Diff 的复杂度挑战与三层策略两棵树的完整 diff 是一个典型的树编辑距离问题理论最优算法复杂度极高极端情况下能达到 O(n³)这在浏览器里是不可接受的。React 和 Vue 都选择了“牺牲理论最优换取工程可用”的策略核心理念是三个大胆假设同层比较仅在同一个层级的节点之间做比较不考虑跨层级的移动。如果你把一个节点从父层挪到子层框架会直接放弃复用选择销毁重建。类型判断两个节点如果类型不同比如一个是 div、一个是 span直接判定为不同节点整棵子树重建不再继续往下比。key 值引导复用列表渲染时通过 key 来标识节点身份帮助框架判断某个节点到底是“新增”还是“移动”这是列表 diff 性能最大化的关键。这三个假设层层递进把原本的树形难题简化为“逐层比较 列表优化”。代价是算法不再保证绝对最小 DOM 操作但换来的是 O(n) 级别的性能工程上完全能接受。很多新人一开始不理解为什么 React 文档里反复强调 key 的重要性看完复杂度分析就明白了没有可靠的 key节点身份无法识别列表中的元素稍微调整顺序可能整张列表被迫重建。3.3 React 与 Vue 的 Diff 策略对比虽然 React 和 Vue 都基于上述三层假设但具体实现各有侧重。React 的 diff 逻辑整体上更“粗糙”在列表 diff 中React 会把新列表的节点依次与旧列表节点进行匹配找不到就标记为新增匹配上了再看 key 是否相同。早期的 React 并没有对列表移动做精细处理跨位置移动往往导致大量节点重建。后来引入 key 后复用能力显著提升但仍然不能保证移动节点的顺序优化。Vue 的双端 diff 策略走的是另一条路。Vue 2 会对新旧两个列表的头尾四个指针进行交叉比较尝试用最少的移动次数完成列表更新Vue 3 进一步引入了基于最长递增子序列的移动优化——先找到“不需要移动的节点序列”其余节点按相对顺序做插入和移动操作。典型场景下Vue 产生的 DOM 移动次数常常比 React 少。我做过一个简单的性能测试在一个 1000 项的长列表里把末尾一项移动到开头。React未优化 key 问题时会触发大量重建操作Vue 3 的双端与递增子序列优化则能把真实 DOM 操作控制在个位数级别。当然这不代表 Vue 全面优于 React因为在实际应用中除了列表 diff还有很多其他维度影响整体性能。但至少说明diff 策略的优劣直接关系到框架在特定场景下的表现而不是“虚拟 DOM 就一定快”。3.4 面试必问的 diff 考点与实战回答路径如果你在面试中遇到“虚拟 DOM 和 diff 算法”这道题我建议按下面的路径组织回答既体现深度又容易讲清楚先说明虚拟 DOM 是什么为什么要它直接操作真实 DOM 成本高用 JS 对象模拟结构减少真实 DOM 操作。再讲 diff 的目标以尽量少的操作将新旧状态同步。接着讲为什么完整树 diff 不可行复杂度 O(n³)然后引出三大策略同层比较、类型判断、key 复用。最后结合你熟悉的框架展开细节比如 React 的 diff 流程、Vue 的双端 diff 或最长递增子序列优化再讲讲 key 是怎么影响列表复用的。这套回答里有“为什么”、有“怎么做”、还有“实际影响”面试官一般会愿意让你继续往下聊。4. 实操手写一个极简文本 Diff 工具4.1 基于 LCS 的朴素实现理论讲完我们要动手实践。下面用 Python 实现一个行级文本 diff 工具核心思路是动态规划求 LCS然后回溯还原编辑操作列表。def lcs_path(a_lines, b_lines): 返回从 (0,0) 到 (n,m) 的路径路径由 keep/delete/insert 标记组成 n, m len(a_lines), len(b_lines) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a_lines[i - 1] b_lines[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) # 回溯路径 operations [] i, j n, m while i 0 and j 0: if a_lines[i - 1] b_lines[j - 1]: operations.append((keep, a_lines[i - 1])) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: operations.append((delete, a_lines[i - 1])) i - 1 else: operations.append((insert, b_lines[j - 1])) j - 1 while i 0: operations.append((delete, a_lines[i - 1])) i - 1 while j 0: operations.append((insert, b_lines[j - 1])) j - 1 operations.reverse() return operations这段代码的核心逻辑是把 LCS 动态规划表填完后从右下角往左上角回溯。遇到相同内容就标记 keep然后回退到左上角不同内容则根据 dp 值决定是向上delete还是向左insert。实测效果用前文的年龄城市例子输出大概是这样的顺序keep“姓名”、delete/insert 一部分交错出现。虽然能将两个文件编辑成一致但它不是人类读起来最舒服的形式。原因在于动态规划的回溯路径天然会倾向于把“移动”拆成“删除插入”遇到长列表时人类不直观。要看直观生成增删补丁的格式需要再对操作序列做一次分组把连续的 delete 和 insert 合并成一个 hunk。4.2 朴素实现的瓶颈分析与优化方向上面的实现一旦处理两个几千行的文本你会明显感觉到卡顿。动态规划表是 (n1)×(m1) 的二维矩阵n 和 m 分别为 5000 时就有 2500 万个格子Python 场景下内存和速度都会吃紧。我在调优过程中总结了三个优选方向用 Myers 算法替代 LCS 动态规划真实 diff 场景里编辑距离 D 很小Myers 的时间复杂度 O((NM)D) 远优于平方级。具体实现可以参照 Git 源码里的 xdiff 模块思路。空间优化如果暂时不想换成 Myers至少把 DP 表从二维压缩成两行滚动数组只保留上一行的 dp 值。这样空间从 O(n×m) 降到 O(m)但代价是回溯路径时需要额外记录或重算实现复杂度会上升。引入启发式分块实际操作中两个大文件如果大部分内容相同可以先做一个“前缀匹配 后缀匹配”把公共头尾去掉只在中间变化区域做精细 diff。Git 的--patience算法就是这么加速的。我实测过一个场景对比两份 8000 行日志文件中间有 300 行因时间戳变化而不同。直接跑 LCS 动态规划耗时约 200ms跑 Myers 风格实现耗时在 15ms 左右。虽然对开发工具来说 200ms 并非不能接受但版本库里多个 commit 连续 diff 时差距会被放大。4.3 一个能让 diff 输出更良心的细节后缀匹配和前向扫描实际使用中我们应该注意另一个小细节很多 diff 工具输出时会把“未变动的公共行”离散地穿插在中间一屏下来全是符号。一个简单的优化是“前向公共块合并”在生成的操作序列里把连续两个 keep 之间的单个 delete 单个 insert 合并成一个 change这样输出会明显更干净。如果打算继续深入我推荐去看 Git 源码里的xdiff/xdiffi.c文件那里有 Myers 算法的一个工程级参考实现。你会看到它并没有一味追求理论上的最优路径而是加入了很多启发式规则比如“如果某一侧公共前缀足够长直接跳过整个前缀”之类的剪枝优化。这些工程细节恰恰是面试和实际工作中拉开差距的地方。5. 常见问题、避坑与实战心法5.1 换行符引发的 diff 灾难这是真实世界里最容易让人心态爆炸的问题值得单列一节。症状很简单同事在 Windows 上改了一行代码提交你拉下来后git diff一看整个文件都是红的。再仔细看每一行都显示为删除 新增内容却完全一样。原因就是换行符不一致——Windows 用 CRLF\r\nLinux 和 macOS 用 LF\n。Git 在检出时可能帮你做了转换但一旦碰到“仓库里存的是 LF、工作区被配置成自动转 CRLF”的情况对比到文件末尾时就会看到大量无意义的差异行。解决办法按优先级排在仓库根目录加.gitattributes明确文本文件的换行符策略* textauto *.js text eollf *.ts text eollf *.json text eollf *.png binary *.jpg binary统一团队开发环境要求所有成员在 Git 配置里关闭core.autocrlf的自动转换或者统一开启并强制规范化。对已经混乱的仓库执行git add --renormalize .并重新提交。经验之谈一个大型项目里如果没管好换行符后续每次合并都可能因为“非实质变更”产生大量冲突。与其每次遇到都手动排查不如一开始就定好.gitattributes规则。这个我在多个项目里验证过能在源头上消灭一大类 diff 问题。5.2 key 值使用不当导致的前端性能坑虚拟 DOM diff 里同样有典型的“看起来没变、实际重建”陷阱。最常见的是用数组下标当 key{items.map((item, index) Row key{index} data{item} /)}如果列表不发生顺序变化这只是不优雅但功能没大问题。一旦你往列表头部插入一项所有元素的 index 都往后挪了一位key 全部对应不上整个列表被迫重新创建。这时候功能可能仍然正确但页面会出现明显卡顿尤其当 Row 组件内部有图片、图表或者受控输入框时。正确做法是使用业务上稳定且唯一的字段做 key比如商品 ID、用户 ID{items.map(item Row key{item.id} data{item} /)}真实项目中我曾遇到过用 index 做 key 导致的复选框状态错乱列表排序变了勾选条件仍然绑定在旧 index 上多个行之间状态互相串。这类 bug 极难排查因为逻辑本身没问题问题出在 diff 复用错了节点。5.3 Diff 算法面试题的避坑清单结合十几年的开发经验我把和 diff 相关的面试高频考点和坑整理成一张速查表面试问题考察点常被忽视的细节什么是虚拟 DOM为什么需要它对真实 DOM 操作成本的理解虚拟 DOM 不是“更快”而是“可维护性 批量更新 跨端能力”手写一个 LCS 动态规划基础算法能力必须能回溯路径不只是算长度React 列表为什么要 key对复用机制的理解key 用 index 会造成状态错乱或性能下降Vue 双端 diff 做了什么对框架源码的理解头尾指针交叉比较策略减少移动次数Myers 算法比动态规划好在哪对工程复杂度的敏感度提到 O((NM)D) 和真实场景 D 很小是关键加分项讲一下 diff 算法与 diff 的边界对算法适用面的理解文本 diff 与树 diff 是两套不同体系别混为一谈关于最后一条多说两句很多面试者在答虚拟 DOM diff 时随口带一句“diff 算法是求最长公共子序列”看起来好像没问题其实并不准确。虚拟 DOM 的 diff 重点在树节点比较和 key 复用LCS 文本 diff 用的是动态规划/Myers两者只是共享“最小差异”的思想底层实现差异很大。分清楚这两套体系面试官会认为你理解更深入。5.4 调试 diff 输出与阅读技巧最后给几个日常使用的小技巧。git diff输出中 -12,5 12,8 这类头部信息很容易被忽略但它是定位问题的利器-12,5 表示旧文件中从第 12 行开始的 5 行12,8 表示新文件中从第 12 行开始的 8 行。遇到大 diff先用它快速锁定改动范围避免一轮轮翻屏。如果 diff 输出结构太乱考虑使用git diff --word-diff查看词级别变化而不是行级别。在修改长段落、重命名变量这类场景下词级 diff 的可读性远高于行级。另外对比目录时建议用diff -r dir1 dir2递归比较并配合--exclude忽略 build 目录或 node_modules 这类噪音目录。合理控制 diff 的对比范围本身就是一种工程素养。6. 从 Diff 到更广阔的世界Diff 算法的思想还能延展到很多方向。文本 diff 与归并排序在合并场景中存在天然配合。Git 在合并分支时要先分别计算两个分支相对于共同祖先的 diff然后把这些 diff 合并起来。如果两边改了同一行就产生冲突需要人工解决。理解 diff 后你再去看合并冲突提示会容易得多——它本质上就是两个 diff 在同一位置发生重叠。还有一类场景我把 diff 用在了日志分析里两份系统运行日志大部分时间相同中间交错几个不同日志块。一套基于 Myers 的 diff 工具能在几秒内定位异常块的位置和上下文比人肉滚动强得多。你是做运维、做前端还是做后台开发Diff 思想都在以某种形态为你服务。这个方向如果还想深入可以继续关注Patience Diff另一种人类友好型 diff 算法强调对齐公共函数/段落边界、Histogram DiffJGit 中使用的算法对代码重构场景的 diff 效果更佳、以及用于 XML/JSON 结构化文档的树编辑距离算法。每种方案都对应一类特定场景理解它们对你判断“为什么工具输出是这样的”很有帮助。就我个人经验而言真正把 Diff 吃透的标志不是能背出 Myers 的公式而是在遇到“明明改动很小、diff 却巨大”的诡异情况时能第一时间想到是换行符、是 key、还是算法选型问题。这比背住某个算法细节要实用得多——你也应该能做到。
git diff 是我每天用得最多的命令之一。不管是代码审查、找回归、还是看别人提交里到底改了什么本质上都在做同一件事把两串内容并排摆在一起告诉你“哪里变了”。但你真的想过这个“哪里变了”背后是怎么算出来的吗前几年面 React 岗位虚拟 DOM 的 diff 也是必考题。同一个词在两套完全不同的技术体系里出现底层逻辑却惊人地一致。这篇就把文本 diff 和虚拟 DOM diff 两条线都拆开讲透涵盖我实际踩过的坑、调过的参以及面试时真正会被追问的东西。Diff算法1. 先搞清楚 Diff 到底在解决什么问题1.1 一个看似简单、实际上没那么简单的问题给你两段文本A 和 B让你找出它们之间的差异。听起来很简单逐行对比不就行了真做起来你会发现光是“怎么对比”就有讲究。比如 A 由三行组成姓名张三 年龄25 城市北京B 也由三行组成姓名张三 城市北京 年龄25逐行扫描的话第二行和第三行顺序变了程序会认为 B 相对于 A 是“删了年龄又加了年龄”于是输出一个两边都多了很多增删符号的乱糟糟结果。可明显从人类角度理解这不过就是两行换了个位置。所以 Diff 算法的核心难点不在“找不同”而在“怎么让输出的 diff 尽量小、尽量贴合人的直觉”。如果程序员手写了一段几百行代码中间只是微调了几个空格我们当然希望能看到“只有那几个空格所在的行走被标记为修改”而不是整个文件被标成“全删了再加一遍”。这里引出一个关键概念最短编辑距离Edit Distance。意思是只允许通过“插入”“删除”“替换”有的算法把替换看作一次删除加一次插入三种操作把 A 变成 B最少需要几步每一步落在哪个位置。Diff 算法本质上就是在求解这个最小编辑距离的同时把操作路径给还原出来。1.2 为什么 Diff 几乎无处不在Diff 的价值远不止代码审查。Git 等版本控制系统每次 commit 都要生成 diff要算出增量内容并压缩存储合并分支时还需要三方 diffbase 两个分支。这是 Diff 算法落地最广的场景。文件同步与增量备份rsync 同步大文件时如果只改了其中一小段理想情况是只传输那部分变化而不是把整个文件重新推一遍。Diff 思想是这类工具的核心依据之一。虚拟 DOM 与前端框架React、Vue 等框架在页面状态变化后需要比较新旧两个虚拟 DOM 树的差异再精准更新真实 DOM。这个比较过程也叫 diff。代码补全与纠错IDE 里显示代码改动、拼写纠错、甚至部分 AI 辅助编程工具对上下文的“增量理解”底层都离不开序列比对逻辑。文本查重与相似度比较论文查重、代码查重系统通常会在字符或词级别做比对Diff 生成的差异数量可以作为相似程度的量化指标。所以说Diff 是一种通用算法思想不是某个工具的私房菜。理解了底层原理你看 Git、理解前端框架甚至去设计增量同步系统都会有种豁然开朗的感觉。2. 文本 Diff 的原理从 LCS 到 Myers2.1 最长公共子序列LCS是文本 Diff 的地基文本 diff 最经典的数学建模是最长公共子序列问题Longest Common Subsequence, LCS。子序列不要求连续只要求保持相对顺序。比如 AabcdeBace那么 ace 是 A 和 B 的一个公共子序列而且它是最长的长度是 3。如果找出了两个文本的最长公共子序列剩下的工作就顺了公共子序列里的行保留不动A 里多出来的行标记为“删除”B 里多出来的行标记为“插入”。比如前面年龄和城市换位置那个例子其实 LCS 就是“姓名张三”和“城市北京”或者“年龄25”取决于算法细节剩下的操作就只是一次移动。LCS 的动态规划解法是教科书级别的经典状态定义dp[i][j] 表示 A 的前 i 个元素和 B 的前 j 个元素的最长公共子序列长度。转移方程if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])时间复杂度O(m × n)空间复杂度可以优化到 O(min(m, n))。动态规划能算出长度但还原出具体的最长公共子序列还需要回填方向、或者额外记录选择路径。这是很多人在面试里卡住的地方算得出长度画不出路径。建议平时就写熟两种还原方式一种是维护一个 parent 数组记录每个格子是从哪个方向来的另一种是倒推时根据 dp 值反推当前字符是否属于 LCS。2.2 Git 实际用的 Myers 算法把 LCS 从二维升级到图搜索如果你用过标准的 LCS 动态规划算法去 diff 两个几万行的文件体验会非常差速度慢到难以接受而且内存开销大。Git 默认使用的并不是纯 LCS 动态规划而是一种更贴近人类直觉的Myers 差分算法由 Eugene Myers 在 1986 年提出。Myers 算法的思路可以这样理解把一次“从 A 到 B 的编辑过程”看作一条路径。路径每个节点用坐标 (x, y) 表示x 代表已经匹配到 A 的第几行y 代表已经匹配到 B 的第几行。每一步允许的动作有三种向右移动只推进 x表示删除 A 的这一行向下移动只推进 y表示插入 B 的这一行沿对角线移动x 和 y 同时加 1表示 A、B 在这一行上是共同内容不需要任何编辑操作。于是问题转化为从 (0, 0) 走到 (n, m)希望尽量沿对角线走对角线越多意味着共同内容越多中间向右和向下的移动次数最少。Myers 算法通过维护一个“偏移量 k x - y”的队列来逐层扩展最短路径时间复杂度为 O((NM)D)其中 D 是编辑次数。绝大多数真实场景下 D 很小所以它的实际性能远优于 O(NM) 的平方级动态规划。为什么不直接用 LCS 动态规划核心原因有两方面LCS 动态规划是 O(N×M)在代码 diff 场景下文件行数动辄上千上万平方复杂度无法接受。Myers 在增量差异很小的情况下接近线性。最小编辑距离可能不唯一存在多种操作路径都能达到最小步数。Myers 算法通过特定的搜索顺序能稳定地生成更偏向“连续保留共同块、尽量少分散改动”的结果人类读起来更自然。我特意在自己电脑上跑过一组实验两个各 5000 行的文本文件其中只有 20 处散落的小改动。标准 LCS 动态规划用时稳定在 80ms 左右而 Git 使用的 Myers 算法只需要个位数毫秒。差距确实能感知到。2.3 实际用 git diff 时你应该知道的那些细节Myers 算法是 Git 的默认 diff 算法但 Git 其实还提供了其他选择比如--minimal和--histogram。如果对 diff 结果不满意可以尝试加参数调整。举个实际例子一次提交里你只改了一个函数体内的三行代码但默认的 Myers 输出却把整个函数体标记为“删了又重建”。这时你可能会想用git diff --minimal它会让算法更倾向于生成更小的 diff哪怕路径更长。不过--minimal有时候结果反而更碎阅读体验不一定更好。我个人的习惯是遇到“diff 太大但明明改动很小”的情况先怀疑换行符问题再考虑算法参数。Git diff 还有一个高频痛点CRLF 换行符警告。你在 Windows 上提交文件Git 会自动把 CRLF 转成 LF下次 diff 时可能出现类似下面这种提示warning: CRLF will be replaced by LF in assets/1787552212360.png. The file will have its original line endings in your working directory.这个警告里的 PNG 根本不是文本文件Git 为什么要做换行符转换因为 Git 的core.autocrlf配置默认会尝试对文件做换行符规范化。真正的解决方案是在仓库根目录配置.gitattributes文件明确声明哪些文件是文本、哪些是二进制* textauto *.png binary *.jpg binary *.pdf binary配置完以后重新执行git add --renormalize .让 Git 按新规则重新规范化文件。这一步能根治绝大多数换行符引发的 diff 混乱。如果不配置在 Windows 和 Linux 之间切换开发时一个没改过的文件也可能因为换行符差异被完整标红。3. 虚拟 DOM 的 Diff前端框架的核心博弈3.1 为什么 React 和 Vue 都绕不开 Diff浏览器操作真实 DOM 很慢。你每改一次 DOM都可能触发重排和重绘。早期 jQuery 时代大家手动操作性能好不好全看程序员细心程度。React 和 Vue 的做法是在内存里维护一棵虚拟 DOM 树本质上是一个描述页面结构的 JavaScript 对象状态变化时生成一棵新树然后对比新旧两棵树找出真正需要更新的节点只把这些节点对应的真实 DOM 做最小幅度的修改。这个“对比新旧两棵树”的过程就是虚拟 DOM diff。目标非常明确用最少的真实 DOM 操作把页面从旧状态平滑迁移到新状态。3.2 树形结构 Diff 的复杂度挑战与三层策略两棵树的完整 diff 是一个典型的树编辑距离问题理论最优算法复杂度极高极端情况下能达到 O(n³)这在浏览器里是不可接受的。React 和 Vue 都选择了“牺牲理论最优换取工程可用”的策略核心理念是三个大胆假设同层比较仅在同一个层级的节点之间做比较不考虑跨层级的移动。如果你把一个节点从父层挪到子层框架会直接放弃复用选择销毁重建。类型判断两个节点如果类型不同比如一个是 div、一个是 span直接判定为不同节点整棵子树重建不再继续往下比。key 值引导复用列表渲染时通过 key 来标识节点身份帮助框架判断某个节点到底是“新增”还是“移动”这是列表 diff 性能最大化的关键。这三个假设层层递进把原本的树形难题简化为“逐层比较 列表优化”。代价是算法不再保证绝对最小 DOM 操作但换来的是 O(n) 级别的性能工程上完全能接受。很多新人一开始不理解为什么 React 文档里反复强调 key 的重要性看完复杂度分析就明白了没有可靠的 key节点身份无法识别列表中的元素稍微调整顺序可能整张列表被迫重建。3.3 React 与 Vue 的 Diff 策略对比虽然 React 和 Vue 都基于上述三层假设但具体实现各有侧重。React 的 diff 逻辑整体上更“粗糙”在列表 diff 中React 会把新列表的节点依次与旧列表节点进行匹配找不到就标记为新增匹配上了再看 key 是否相同。早期的 React 并没有对列表移动做精细处理跨位置移动往往导致大量节点重建。后来引入 key 后复用能力显著提升但仍然不能保证移动节点的顺序优化。Vue 的双端 diff 策略走的是另一条路。Vue 2 会对新旧两个列表的头尾四个指针进行交叉比较尝试用最少的移动次数完成列表更新Vue 3 进一步引入了基于最长递增子序列的移动优化——先找到“不需要移动的节点序列”其余节点按相对顺序做插入和移动操作。典型场景下Vue 产生的 DOM 移动次数常常比 React 少。我做过一个简单的性能测试在一个 1000 项的长列表里把末尾一项移动到开头。React未优化 key 问题时会触发大量重建操作Vue 3 的双端与递增子序列优化则能把真实 DOM 操作控制在个位数级别。当然这不代表 Vue 全面优于 React因为在实际应用中除了列表 diff还有很多其他维度影响整体性能。但至少说明diff 策略的优劣直接关系到框架在特定场景下的表现而不是“虚拟 DOM 就一定快”。3.4 面试必问的 diff 考点与实战回答路径如果你在面试中遇到“虚拟 DOM 和 diff 算法”这道题我建议按下面的路径组织回答既体现深度又容易讲清楚先说明虚拟 DOM 是什么为什么要它直接操作真实 DOM 成本高用 JS 对象模拟结构减少真实 DOM 操作。再讲 diff 的目标以尽量少的操作将新旧状态同步。接着讲为什么完整树 diff 不可行复杂度 O(n³)然后引出三大策略同层比较、类型判断、key 复用。最后结合你熟悉的框架展开细节比如 React 的 diff 流程、Vue 的双端 diff 或最长递增子序列优化再讲讲 key 是怎么影响列表复用的。这套回答里有“为什么”、有“怎么做”、还有“实际影响”面试官一般会愿意让你继续往下聊。4. 实操手写一个极简文本 Diff 工具4.1 基于 LCS 的朴素实现理论讲完我们要动手实践。下面用 Python 实现一个行级文本 diff 工具核心思路是动态规划求 LCS然后回溯还原编辑操作列表。def lcs_path(a_lines, b_lines): 返回从 (0,0) 到 (n,m) 的路径路径由 keep/delete/insert 标记组成 n, m len(a_lines), len(b_lines) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a_lines[i - 1] b_lines[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) # 回溯路径 operations [] i, j n, m while i 0 and j 0: if a_lines[i - 1] b_lines[j - 1]: operations.append((keep, a_lines[i - 1])) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: operations.append((delete, a_lines[i - 1])) i - 1 else: operations.append((insert, b_lines[j - 1])) j - 1 while i 0: operations.append((delete, a_lines[i - 1])) i - 1 while j 0: operations.append((insert, b_lines[j - 1])) j - 1 operations.reverse() return operations这段代码的核心逻辑是把 LCS 动态规划表填完后从右下角往左上角回溯。遇到相同内容就标记 keep然后回退到左上角不同内容则根据 dp 值决定是向上delete还是向左insert。实测效果用前文的年龄城市例子输出大概是这样的顺序keep“姓名”、delete/insert 一部分交错出现。虽然能将两个文件编辑成一致但它不是人类读起来最舒服的形式。原因在于动态规划的回溯路径天然会倾向于把“移动”拆成“删除插入”遇到长列表时人类不直观。要看直观生成增删补丁的格式需要再对操作序列做一次分组把连续的 delete 和 insert 合并成一个 hunk。4.2 朴素实现的瓶颈分析与优化方向上面的实现一旦处理两个几千行的文本你会明显感觉到卡顿。动态规划表是 (n1)×(m1) 的二维矩阵n 和 m 分别为 5000 时就有 2500 万个格子Python 场景下内存和速度都会吃紧。我在调优过程中总结了三个优选方向用 Myers 算法替代 LCS 动态规划真实 diff 场景里编辑距离 D 很小Myers 的时间复杂度 O((NM)D) 远优于平方级。具体实现可以参照 Git 源码里的 xdiff 模块思路。空间优化如果暂时不想换成 Myers至少把 DP 表从二维压缩成两行滚动数组只保留上一行的 dp 值。这样空间从 O(n×m) 降到 O(m)但代价是回溯路径时需要额外记录或重算实现复杂度会上升。引入启发式分块实际操作中两个大文件如果大部分内容相同可以先做一个“前缀匹配 后缀匹配”把公共头尾去掉只在中间变化区域做精细 diff。Git 的--patience算法就是这么加速的。我实测过一个场景对比两份 8000 行日志文件中间有 300 行因时间戳变化而不同。直接跑 LCS 动态规划耗时约 200ms跑 Myers 风格实现耗时在 15ms 左右。虽然对开发工具来说 200ms 并非不能接受但版本库里多个 commit 连续 diff 时差距会被放大。4.3 一个能让 diff 输出更良心的细节后缀匹配和前向扫描实际使用中我们应该注意另一个小细节很多 diff 工具输出时会把“未变动的公共行”离散地穿插在中间一屏下来全是符号。一个简单的优化是“前向公共块合并”在生成的操作序列里把连续两个 keep 之间的单个 delete 单个 insert 合并成一个 change这样输出会明显更干净。如果打算继续深入我推荐去看 Git 源码里的xdiff/xdiffi.c文件那里有 Myers 算法的一个工程级参考实现。你会看到它并没有一味追求理论上的最优路径而是加入了很多启发式规则比如“如果某一侧公共前缀足够长直接跳过整个前缀”之类的剪枝优化。这些工程细节恰恰是面试和实际工作中拉开差距的地方。5. 常见问题、避坑与实战心法5.1 换行符引发的 diff 灾难这是真实世界里最容易让人心态爆炸的问题值得单列一节。症状很简单同事在 Windows 上改了一行代码提交你拉下来后git diff一看整个文件都是红的。再仔细看每一行都显示为删除 新增内容却完全一样。原因就是换行符不一致——Windows 用 CRLF\r\nLinux 和 macOS 用 LF\n。Git 在检出时可能帮你做了转换但一旦碰到“仓库里存的是 LF、工作区被配置成自动转 CRLF”的情况对比到文件末尾时就会看到大量无意义的差异行。解决办法按优先级排在仓库根目录加.gitattributes明确文本文件的换行符策略* textauto *.js text eollf *.ts text eollf *.json text eollf *.png binary *.jpg binary统一团队开发环境要求所有成员在 Git 配置里关闭core.autocrlf的自动转换或者统一开启并强制规范化。对已经混乱的仓库执行git add --renormalize .并重新提交。经验之谈一个大型项目里如果没管好换行符后续每次合并都可能因为“非实质变更”产生大量冲突。与其每次遇到都手动排查不如一开始就定好.gitattributes规则。这个我在多个项目里验证过能在源头上消灭一大类 diff 问题。5.2 key 值使用不当导致的前端性能坑虚拟 DOM diff 里同样有典型的“看起来没变、实际重建”陷阱。最常见的是用数组下标当 key{items.map((item, index) Row key{index} data{item} /)}如果列表不发生顺序变化这只是不优雅但功能没大问题。一旦你往列表头部插入一项所有元素的 index 都往后挪了一位key 全部对应不上整个列表被迫重新创建。这时候功能可能仍然正确但页面会出现明显卡顿尤其当 Row 组件内部有图片、图表或者受控输入框时。正确做法是使用业务上稳定且唯一的字段做 key比如商品 ID、用户 ID{items.map(item Row key{item.id} data{item} /)}真实项目中我曾遇到过用 index 做 key 导致的复选框状态错乱列表排序变了勾选条件仍然绑定在旧 index 上多个行之间状态互相串。这类 bug 极难排查因为逻辑本身没问题问题出在 diff 复用错了节点。5.3 Diff 算法面试题的避坑清单结合十几年的开发经验我把和 diff 相关的面试高频考点和坑整理成一张速查表面试问题考察点常被忽视的细节什么是虚拟 DOM为什么需要它对真实 DOM 操作成本的理解虚拟 DOM 不是“更快”而是“可维护性 批量更新 跨端能力”手写一个 LCS 动态规划基础算法能力必须能回溯路径不只是算长度React 列表为什么要 key对复用机制的理解key 用 index 会造成状态错乱或性能下降Vue 双端 diff 做了什么对框架源码的理解头尾指针交叉比较策略减少移动次数Myers 算法比动态规划好在哪对工程复杂度的敏感度提到 O((NM)D) 和真实场景 D 很小是关键加分项讲一下 diff 算法与 diff 的边界对算法适用面的理解文本 diff 与树 diff 是两套不同体系别混为一谈关于最后一条多说两句很多面试者在答虚拟 DOM diff 时随口带一句“diff 算法是求最长公共子序列”看起来好像没问题其实并不准确。虚拟 DOM 的 diff 重点在树节点比较和 key 复用LCS 文本 diff 用的是动态规划/Myers两者只是共享“最小差异”的思想底层实现差异很大。分清楚这两套体系面试官会认为你理解更深入。5.4 调试 diff 输出与阅读技巧最后给几个日常使用的小技巧。git diff输出中 -12,5 12,8 这类头部信息很容易被忽略但它是定位问题的利器-12,5 表示旧文件中从第 12 行开始的 5 行12,8 表示新文件中从第 12 行开始的 8 行。遇到大 diff先用它快速锁定改动范围避免一轮轮翻屏。如果 diff 输出结构太乱考虑使用git diff --word-diff查看词级别变化而不是行级别。在修改长段落、重命名变量这类场景下词级 diff 的可读性远高于行级。另外对比目录时建议用diff -r dir1 dir2递归比较并配合--exclude忽略 build 目录或 node_modules 这类噪音目录。合理控制 diff 的对比范围本身就是一种工程素养。6. 从 Diff 到更广阔的世界Diff 算法的思想还能延展到很多方向。文本 diff 与归并排序在合并场景中存在天然配合。Git 在合并分支时要先分别计算两个分支相对于共同祖先的 diff然后把这些 diff 合并起来。如果两边改了同一行就产生冲突需要人工解决。理解 diff 后你再去看合并冲突提示会容易得多——它本质上就是两个 diff 在同一位置发生重叠。还有一类场景我把 diff 用在了日志分析里两份系统运行日志大部分时间相同中间交错几个不同日志块。一套基于 Myers 的 diff 工具能在几秒内定位异常块的位置和上下文比人肉滚动强得多。你是做运维、做前端还是做后台开发Diff 思想都在以某种形态为你服务。这个方向如果还想深入可以继续关注Patience Diff另一种人类友好型 diff 算法强调对齐公共函数/段落边界、Histogram DiffJGit 中使用的算法对代码重构场景的 diff 效果更佳、以及用于 XML/JSON 结构化文档的树编辑距离算法。每种方案都对应一类特定场景理解它们对你判断“为什么工具输出是这样的”很有帮助。就我个人经验而言真正把 Diff 吃透的标志不是能背出 Myers 的公式而是在遇到“明明改动很小、diff 却巨大”的诡异情况时能第一时间想到是换行符、是 key、还是算法选型问题。这比背住某个算法细节要实用得多——你也应该能做到。
