Diff算法的简单介绍
<h4 id="原生-dom-更新">原生 DOM 更新</h4><div class="mermaid">graph LR
A[数据变化] --> B[手动查找DOM节点]
B --> C[直接修改节点属性]
C --> D[处理相关依赖节点]
</div><h4 id="diff-算法更新">Diff 算法更新</h4>
<div class="mermaid">graph LR
A[应用状态变更] --> B[生成新的虚拟 DOM 树]
B --> C
C --> D[计算最小变更集]
D --> E[批量更新真实 DOM]
</div><h2 id="什么是-diff-算法">什么是 Diff 算法？</h2>
<p><strong>Diff 算法（差异算法）</strong> 是一种用于<strong>比较两个树形结构（通常是虚拟 DOM 树）之间的差异</strong>，并计算出<strong>最小变更集</strong>的高效算法。它是现代前端框架（如 React, Vue, Angular 等）实现高性能渲染的核心机制之一。</p>
<h3 id="核心思想">核心思想</h3>
<ol>
<li><strong>比较对象</strong>：比较的是<strong>内存中</strong>表示 UI 结构的 JavaScript 对象（虚拟 DOM 树），而非直接操作浏览器中笨重的真实 DOM。</li>
<li><strong>找出差异</strong>：精确找出新旧两棵虚拟 DOM 树中哪些节点发生了变化（增、删、改、移）。</li>
<li><strong>最小化操作</strong>：只将<strong>必要的、最少的变更</strong>应用到真实 DOM 上，避免不必要的渲染开销。</li>
</ol>
<h2 id="diff-算法的作用">Diff 算法的作用</h2>
<ol>
<li>
<p><strong>性能优化（核心作用）</strong>:</p>
<ul>
<li><strong>减少 DOM 操作成本</strong>：直接操作真实 DOM（尤其是涉及布局重排和重绘）是浏览器中最昂贵的操作之一。Diff 算法确保只更新真正变化的部分。</li>
<li><strong>批量更新</strong>：框架可以将 Diff 计算出的多个变更集合并成一次批量的 DOM 操作，进一步提高效率。</li>
<li><strong>避免全量更新</strong>：无需在每次状态变化时都销毁整个旧 DOM 树并重建整个新 DOM 树。</li>
</ul>
</li>
<li>
<p><strong>简化开发逻辑</strong>:</p>
<ul>
<li><strong>声明式编程</strong>：开发者只需关注“目标 UI 状态应该是什么样子”（描述新的虚拟 DOM），而无需手动编写繁琐的“如何从当前状态变过去”的命令式代码（如 <code>document.getElementById(...).appendChild(...)</code>）。Diff 算法和渲染引擎自动处理更新过程。</li>
<li><strong>关注点分离</strong>：开发者聚焦于业务逻辑和状态管理，框架负责高效的 UI 更新。</li>
</ul>
</li>
<li>
<p><strong>跨平台能力的基础</strong>:</p>
<ul>
<li>虚拟 DOM 和 Diff 算法提供了一层抽象。计算出的最小变更集不仅可以应用于浏览器 DOM，也可以应用于 Native 组件（React Native）、Canvas、WebGL，甚至服务端渲染。</li>
</ul>
</li>
</ol>
<h2 id="为什么需要实现-diff-算法">为什么需要实现 Diff 算法？</h2>
<p>实现 Diff 算法是为了<strong>解决直接操作真实 DOM 带来的严重性能瓶颈和开发体验问题</strong>：</p>
<ol>
<li>
<p><strong>直接操作 DOM 的代价高昂</strong>：</p>
<ul>
<li>每次 DOM 操作（尤其是修改布局属性）都可能触发浏览器的 <strong>重排（Reflow）</strong> 和 <strong>重绘（Repaint）</strong> ，这是非常消耗 CPU 和 GPU 资源的操作。</li>
<li>频繁或低效的 DOM 更新会导致界面卡顿、响应迟缓，用户体验变差。</li>
</ul>
</li>
<li>
<p><strong>手动更新 DOM 复杂且易错</strong>：</p>
<ul>
<li>在复杂的 Web 应用中，随着状态变化，需要精确计算出哪些 DOM 元素需要添加、删除、修改属性或移动位置。</li>
<li>手动编写这些更新逻辑极其繁琐、容易出错，且代码难以维护。例如，在一个动态列表中插入一项，可能需要精确找到插入点、更新后续元素的索引、处理动画状态等。</li>
</ul>
</li>
<li>
<p><strong>全量更新不可行</strong>：</p>
<ul>
<li>最简单粗暴的更新方式是：销毁整个旧的 DOM 树，然后用新的状态重建并插入整个新的 DOM 树。</li>
<li>这种方法在简单静态页面上也许可行，但对于复杂动态应用：
<ul>
<li><strong>性能灾难</strong>：销毁和重建整个树的开销巨大，导致界面严重闪烁或卡死。</li>
<li><strong>状态丢失</strong>：输入框焦点、滚动条位置、组件内部状态（如视频播放进度）等都会被重置，破坏用户体验。</li>
</ul>
</li>
</ul>
</li>
</ol>
<h3 id="diff-算法的优势解决方案">Diff 算法的优势解决方案</h3>
<ol>
<li>
<p><strong>虚拟 DOM：轻量级的中间层</strong>：</p>
<ul>
<li>在内存中创建真实 DOM 的轻量级 JavaScript 对象表示。创建和操作 JS 对象远比操作真实 DOM 快得多。</li>
<li>状态变化时，先创建新的虚拟 DOM 树。</li>
</ul>
</li>
<li>
<p><strong>Diff：计算最小变更</strong>：</p>
<ul>
<li>使用优化过的 Diff 算法（通常是 O(n) 复杂度）对比新旧虚拟 DOM 树。</li>
<li>精准找出节点级别的差异（元素类型变化？属性变化？子节点顺序变化？）。</li>
</ul>
</li>
<li>
<p><strong>高效更新</strong>：</p>
<ul>
<li>将 Diff 计算出的 <strong>“补丁”（Patch）</strong> 应用到真实 DOM 上。</li>
<li><strong>只更新变化的部分</strong>，最大程度减少昂贵的 DOM 操作和重排/重绘。</li>
</ul>
</li>
</ol>
<h2 id="原生-dom-操作的精确更新假象作用的补充说明">原生 DOM 操作的"精确更新"假象（作用的补充说明）</h2>
<p>在原生 JavaScript 中，开发者确实可以<strong>手动精确更新特定节点</strong>：</p>
<pre><code class="language-javascript">// 原生 DOM 精确更新示例
const priceElement = document.getElementById("product-price");
priceElement.textContent = newPrice;
</code></pre>
<p><strong>表面优势</strong>：</p>
<ul>
<li>只更新一个节点</li>
<li>没有额外开销</li>
<li>性能看似高效</li>
</ul>
<p><strong>实际挑战</strong>：</p>
<ol>
<li><strong>状态追踪复杂度</strong>：在大型应用中，需要手动维护数百个元素引用</li>
<li><strong>依赖关系管理</strong>：当多个数据影响同一元素时，更新逻辑变得复杂</li>
<li><strong>动态内容处理</strong>：列表渲染、条件渲染需要大量手动 DOM 操作</li>
<li><strong>跨组件更新</strong>：深层嵌套组件更新需要穿透多层结构</li>
</ol>
<table>
<thead>
<tr>
<th>特性</th>
<th>原生 DOM 操作</th>
<th>Vue 更新机制</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>更新范围</strong></td>
<td>开发者手动控制</td>
<td>组件级渲染 + Diff 优化</td>
</tr>
<tr>
<td><strong>状态管理</strong></td>
<td>手动维护引用</td>
<td>响应式系统自动追踪</td>
</tr>
<tr>
<td><strong>列表更新</strong></td>
<td>手动操作每个元素</td>
<td>Key 优化 + 最小变更</td>
</tr>
<tr>
<td><strong>条件渲染</strong></td>
<td>手动添加/移除节点</td>
<td>自动 DOM 操作</td>
</tr>
<tr>
<td><strong>性能开销</strong></td>
<td>无框架开销</td>
<td>虚拟 DOM 比较开销</td>
</tr>
<tr>
<td><strong>开发效率</strong></td>
<td>低（代码量大）</td>
<td>高（声明式编程）</td>
</tr>
<tr>
<td><strong>可维护性</strong></td>
<td>随复杂度下降</td>
<td>始终保持良好</td>
</tr>
<tr>
<td><strong>跨平台</strong></td>
<td>需重写逻辑</td>
<td>同一套代码</td>
</tr>
</tbody>
</table>
<h2 id="vue-中的-diff-算法工作原理">Vue 中的 Diff 算法工作原理</h2>
<h3 id="组件级颗粒度">组件级颗粒度</h3>
<ol>
<li>
<p>当响应式数据变化时，Vue 会：</p>
<ul>
<li>标记依赖该数据的<strong>组件为"待更新"</strong></li>
<li>触发这些组件的重新渲染</li>
</ul>
<pre><code class="language-javascript">// Vue 3 响应式更新伪代码
effect(() => {
if (state.dirty) {
patchComponent(component); // 更新组件
}
});
</code></pre>
</li>
<li>
<p>未受影响的组件<strong>不会重新渲染</strong>，保持高性能</p>
</li>
</ol>
<h3 id="节点级颗粒度diff-核心">节点级颗粒度（Diff 核心）</h3>
<p>在组件内部，Vue 使用优化后的 Diff 算法：</p>
<ol>
<li>
<p><strong>同级比较</strong>：只比较相同层级的节点</p>
</li>
<li>
<p><strong>标签类型检查</strong>：</p>
<pre><code class="language-html"><!-- 标签不同 ⇒ 销毁重建 -->
<div>
→
<section>
<!-- 标签相同 ⇒ 更新属性 -->
<div class="old">
→
<div class="new"></div>
</div>
</section>
</div>
</code></pre>
</li>
<li>
<p><strong>Key 优化策略</strong>（列表渲染核心）：</p>
<pre><code class="language-html"><!-- 无 key ⇒ 顺序比较 -->
<li v-for="item in items">{{ item }}</li>
<!-- 有 key ⇒ 精确匹配 -->
<li v-for="item in items" :key="item.id">{{ item.name }}</li>
</code></pre>
</li>
</ol>
<h3 id="vue-3-的突破性优化">Vue 3 的突破性优化</h3>
<p>Vue 3 通过编译时优化解决颗粒度问题：</p>
<div class="mermaid">flowchart LR
A[模板] --> B[编译优化]
B --> C[静态提升]
B --> D
B --> E
</div><ol>
<li><strong>静态提升</strong>：将静态内容移出渲染函数</li>
<li><strong>Patch Flags</strong>：标记动态节点类型<pre><code class="language-javascript">// 编译后的虚拟DOM节点
{
type: 'div',
props: { class: 'active' },
patchFlag: 1 // 1表示只有class是动态的
}
</code></pre>
</li>
<li><strong>Block Tree</strong>：追踪动态节点树，跳过静态子树比较</li>
</ol>
<h2 id="diff-算法的关键优化策略">Diff 算法的关键优化策略</h2>
<h3 id="1-列表渲染与-key-的重要性">1. 列表渲染与 key 的重要性</h3>
<p><strong>颗粒度问题最明显的场景</strong>：</p>
<pre><code class="language-html"><!-- 问题：列表重新排序 -->
<ul>
<li v-for="item in items">{{ item.text }}</li>
</ul>
<!-- 解决方案：key 提供节点标识 -->
<ul>
<li v-for="item in items" :key="item.id">{{ item.text }}</li>
</ul>
</code></pre>
<ul>
<li><strong>无 key</strong>：默认使用"就地复用"策略，可能导致状态错乱</li>
<li><strong>有 key</strong>：精确匹配节点，保持组件状态（如输入框内容）</li>
</ul>
<h3 id="2-组件复用策略">2. 组件复用策略</h3>
<p>Vue 通过组件签名决定是否复用：</p>
<pre><code class="language-javascript">// 决定组件复用的关键因素
function canPatch(oldVNode, newVNode) {
return (
oldVNode.type === newVNode.type && // 相同组件
oldVNode.key === newVNode.key // 相同key
);
}
</code></pre>
<h3 id="3-静态内容跳过">3. 静态内容跳过</h3>
<p>Vue 3 的突破性改进：</p>
<pre><code class="language-html"><!-- 静态内容只生成一次 -->
<div>
<!-- 静态提升内容 -->
<header>Site Title</header>
<!-- 动态内容 -->
<main>{{ dynamicContent }}</main>
</div>
</code></pre>
<ul>
<li>Diff 算法完全跳过静态节点比较</li>
<li>性能接近手动优化的 DOM 操作</li>
</ul>
<h2 id="为什么-vue-需要-diff-算法">为什么 Vue 需要 Diff 算法？</h2>
<ol>
<li><strong>解决颗粒度鸿沟</strong>：弥合细粒度的数据变化与粗粒度的 UI 更新之间的差距</li>
<li><strong>开发体验优先</strong>：让开发者专注于业务逻辑，无需手动优化 DOM 操作</li>
<li><strong>平台抽象层</strong>：为 SSR、小程序等目标平台提供统一更新机制</li>
<li><strong>性能与效率平衡</strong>：在框架开销与手动优化成本间取得最佳平衡点</li>
</ol>
<h3 id="性能对比基准">性能对比基准</h3>
<table>
<thead>
<tr>
<th>更新方式</th>
<th>1000 节点更新时间</th>
<th>内存开销</th>
<th>开发成本</th>
</tr>
</thead>
<tbody>
<tr>
<td>直接 DOM 操作</td>
<td>10ms</td>
<td>低</td>
<td>极高</td>
</tr>
<tr>
<td>全量虚拟 DOM</td>
<td>50ms</td>
<td>高</td>
<td>低</td>
</tr>
<tr>
<td>Vue 3 优化 Diff</td>
<td>15ms</td>
<td>中</td>
<td>低</td>
</tr>
</tbody>
</table>
<h2 id="总结">总结</h2>
<ol>
<li><strong>在内存中（虚拟 DOM）进行高效的差异计算</strong>。</li>
<li><strong>找出新旧 UI 表示之间的最小变更集</strong>。</li>
<li><strong>只将必要的更新应用到昂贵的真实 DOM 上</strong>。</li>
</ol>
<blockquote>
<p>vue2 双端比较算法（双指针 diff）简单示例，主要是处理 v-for 关键之一：</p>
</blockquote>
<pre><code class="language-js">function sameVNode(a, b) {
return a.key === b.key && a.tag === b.tag;
}
function updateChildren(parentEl, oldCh, newCh) {
let oldStartIdx = 0;
let newStartIdx = 0;
let oldEndIdx = oldCh.length - 1;
let newEndIdx = newCh.length - 1;
let oldStartVnode = oldCh;
let oldEndVnode = oldCh;
let newStartVnode = newCh;
let newEndVnode = newCh;
// 创建旧节点 key 映射
const keyMap = {};
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
const key = oldCh.key;
if (key) keyMap = i;
}
// 可视化步骤
const steps = [];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 1. 头头比较
if (sameVNode(oldStartVnode, newStartVnode)) {
steps.push(`头头比较: ${oldStartVnode.key} 和 ${newStartVnode.key} 匹配`);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
}
// 2. 尾尾比较
else if (sameVNode(oldEndVnode, newEndVnode)) {
steps.push(`尾尾比较: ${oldEndVnode.key} 和 ${newEndVnode.key} 匹配`);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
}
// 3. 头尾比较
else if (sameVNode(oldStartVnode, newEndVnode)) {
steps.push(`头尾比较: ${oldStartVnode.key} 移动到末尾`);
parentEl.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling);
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
}
// 4. 尾头比较
else if (sameVNode(oldEndVnode, newStartVnode)) {
steps.push(`尾头比较: ${oldEndVnode.key} 移动到开头`);
parentEl.insertBefore(oldEndVnode.el, oldStartVnode.el);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
}
// 5. key 匹配
else {
const idxInOld = keyMap;
if (idxInOld !== undefined) {
const vnodeToMove = oldCh;
steps.push(
`Key匹配: 找到 ${newStartVnode.key} 并移动到位置 ${newStartIdx}`
);
parentEl.insertBefore(vnodeToMove.el, oldStartVnode.el);
oldCh = undefined;
} else {
steps.push(`创建节点: ${newStartVnode.key} 是新增节点`);
parentEl.insertBefore(createElm(newStartVnode), oldStartVnode.el);
}
newStartVnode = newCh[++newStartIdx];
}
}
// 添加新节点
if (oldStartIdx > oldEndIdx) {
for (let i = newStartIdx; i <= newEndIdx; i++) {
steps.push(`添加节点: ${newCh.key}`);
parentEl.appendChild(createElm(newCh));
}
}
// 删除旧节点
else {
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
if (oldCh) {
steps.push(`删除节点: ${oldCh.key}`);
parentEl.removeChild(oldCh.el);
}
}
}
return steps;
}
function createElm(vnode) {
const el = document.createElement("div");
el.className = "node";
el.textContent = vnode.key + (vnode.key === "E" ? " (新增节点)" : "");
el.dataset.key = vnode.key;
vnode.el = el;
return el;
}
</code></pre>
<blockquote>
<p>vue3 的简化 patchKeyedChildren 示例（伪代码）:</p>
</blockquote>
<pre><code class="language-js">// --------------- 工具函数 ---------------
function isSameVNode(n1, n2) {
return n1.key === n2.key && n1.type === n2.type;
}
function createElement(vnode) {
const el = document.createElement(vnode.type);
if (typeof vnode.children === "string") el.textContent = vnode.children;
vnode.el = el;
return el;
}
function mountElement(vnode, container, anchor = null) {
const el = createElement(vnode);
container.insertBefore(el, anchor);
}
function unmount(vnode) {
vnode.el && vnode.el.parentNode.removeChild(vnode.el);
}
// --------------- 核心 patch ---------------
function patch(n1, n2, container) {
if (!n1) {
// mount
mountElement(n2, container);
} else if (!isSameVNode(n1, n2)) {
// 替换
unmount(n1);
mountElement(n2, container);
} else {
// 同类型节点 → 复用 el
const el = (n2.el = n1.el);
if (typeof n2.children === "string") {
if (n2.children !== n1.children) el.textContent = n2.children;
} else {
patchKeyedChildren(n1.children, n2.children, el);
}
}
}
// --------------- Vue3 风格列表 Diff ---------------
function patchKeyedChildren(c1 = [], c2 = [], container) {
let i = 0;
let e1 = c1.length - 1;
let e2 = c2.length - 1;
// 1️⃣ 从头同步
while (i <= e1 && i <= e2 && isSameVNode(c1, c2)) {
patch(c1, c2, container);
i++;
}
// 2️⃣ 从尾同步
while (i <= e1 && i <= e2 && isSameVNode(c1, c2)) {
patch(c1, c2, container);
e1--;
e2--;
}
// 3️⃣ 新列表更长 → 挂载
if (i > e1) {
const anchor = c2?.el || null;
while (i <= e2) mountElement(c2, container, anchor);
return;
}
// 4️⃣ 旧列表更长 → 卸载
if (i > e2) {
while (i <= e1) unmount(c1);
return;
}
// 5️⃣ 处理中间乱序区间
const s1 = i,
s2 = i;
const keyToNewIdx = new Map();
for (let j = s2; j <= e2; j++) keyToNewIdx.set(c2.key, j);
const toBePatched = e2 - s2 + 1;
const newIdxToOldIdx = new Array(toBePatched).fill(0);
// 5.1 先遍历旧节点，找到可复用的并 patch
for (let j = s1; j <= e1; j++) {
const oldVNode = c1;
const newIdx = keyToNewIdx.get(oldVNode.key);
if (newIdx === undefined) {
unmount(oldVNode); // 不存在 → 删除
} else {
newIdxToOldIdx = j + 1; // 记录旧索引（+1 防 0）
patch(oldVNode, c2, container); // 复用并递归 patch
}
}
// 5.2 计算 LIS，确定哪些节点可以不动
const increasingSeq = getLIS(newIdxToOldIdx);
let seqIdx = increasingSeq.length - 1;
// 5.3 倒序遍历新列表，边插入边移动
for (let j = toBePatched - 1; j >= 0; j--) {
const newIdx = j + s2;
const newVNode = c2;
const anchor = c2?.el || null;
if (newIdxToOldIdx === 0) {
// 新节点
mountElement(newVNode, container, anchor);
} else if (j !== increasingSeq) {
// 需要移动
container.insertBefore(newVNode.el, anchor);
} else {
// 在 LIS 中，保持不动
seqIdx--;
}
}
}
// --------------- 最长递增子序列 (O(n log n)) ---------------
function getLIS(arr) {
const p = arr.slice();
const result = [];
for (let i = 0; i < arr.length; i++) {
const n = arr;
if (n === 0) continue; // 0 表示新节点，占位
let last = result;
if (last === undefined || n > arr) {
p = last;
result.push(i);
continue;
}
// 二分替换
let l = 0,
r = result.length - 1;
while (l < r) {
const mid = (l + r) >> 1;
if (arr] < n) l = mid + 1;
else r = mid;
}
if (n < arr]) {
if (l > 0) p = result;
result = i;
}
}
// 反向回溯出索引序列
let u = result.length,
v = result;
const lis = Array(u);
while (u--) {
lis = v;
v = p;
}
return lis;
}
</code></pre>
<table>
<thead>
<tr>
<th>逻辑点</th>
<th>Vue 2</th>
<th>Vue 3</th>
</tr>
</thead>
<tbody>
<tr>
<td>Patch 函数名</td>
<td><code>updateChildren</code></td>
<td><code>patchKeyedChildren</code></td>
</tr>
<tr>
<td>Diff 方法</td>
<td>双端比较 + keyMap</td>
<td>双端比较 + keyMap + LIS（更优）</td>
</tr>
<tr>
<td>是否支持 Fragment</td>
<td>❌（需要虚拟根）</td>
<td>✅ 支持</td>
</tr>
<tr>
<td>DOM 操作</td>
<td>insertBefore, removeChild 等</td>
<td>同上</td>
</tr>
</tbody>
</table>
<blockquote>
<p>注：以上主要是个人学习使用，各位大佬自行辨别，有错误请指正会进行修改更新。</p>
</blockquote><br><br>
来源：https://www.cnblogs.com/zxlh1529/p/19021119
頁:
[1]