Diff 算法 | Notion

## 一、虚拟DOM
- 定义：用JS对象模拟DOM结构（vnode）
  - 核心属性：tag（标签/组件/函数，必选）、props（属性和方法，非必选）、children（内容/子节点，非必选）
- 示例：模板转vnode的结构展示
- 作用：减少真实DOM操作，通过Diff算法计算最小变更，提升性能
- Vue中转换：模板编译过程（详情见另一篇文章）
- 更新机制：异步更新队列（patch负责新老vnode对比）
## 二、Diff算法基础
- 定义：Vue中即patch函数，参考Snabbdom，对比新旧vnode找最小变化并映射为DOM操作
- 演进背景：Vue1无patch，多Watcher性能不足；Vue2改为组件单Watcher，需patch精准定位变化
- 执行时机
  - 首次渲染：创建新vnode，不深度比较
  - 数据变化时：setter→Notify→Watcher→render（新vnode）→patch（对比老vnode）→更新真实DOM
- 核心策略：深度优先、同层比较（优化1000节点10亿次计算的问题）
## 三、Diff算法优化策略
- 1. 同层比较：不跨层级对比，简化次数
- 2. 标签名对比：标签不同直接移除老节点，不深度比较
- 3. key对比：标签相同+key相同视为同一节点，不深度比较
  - key的作用：高效更新vnode，精准匹配节点，避免频繁DOM更新
  - 注意事项：v-for必须写key，避免用数组index作为key（可能导致bug和低效更新）
## 四、Diff算法核心源码解析
- patch函数（src/core/vdom/patch.js -700行）
  - 参数：oldVnode、vnode、hydrating（服务端渲染）、removeOnly（transition-group）
  - 核心流程
    - vnode不存在：卸载oldVnode
    - oldVnode不存在：创建vnode
    - 两者都存在：sameVnode判断→是则patchVnode，否则挂载vnode并删除oldVnode
- sameVnode函数（src/core/vdom/patch.js -35行）：判断是否同一节点（key、标签、注释节点、数据、input类型等）
- patchVnode函数（src/core/vdom/patch.js -501行）：同一节点的文本/子节点对比
  - 流程：引用相同直接返回→静态节点复用→处理钩子→子节点对比（updateChildren/addVnodes/removeVnodes）→文本更新
- updateChildren函数（src/core/vdom/patch.js -404行）：子节点列表对比
  - 初始化指针：oldStartIdx/newStartIdx（开始）、oldEndIdx/newEndIdx（结束）
  - 循环对比（指针不重合时）
    - 四种基础对比：头头/尾尾/头尾/尾头→命中则patchVnode并移动指针
    - 未命中：新节点key找老节点→找到则判断标签，否则创建新节点
  - 循环结束：老列表遍历完则添加新节点，新列表遍历完则删除老节点
## 五、Vue3 Diff算法优化
- 性能提升：update提升1.3~2倍，SSR提升2~3倍
- 核心优化点
  - 事件缓存：事件存入缓存，变为静态（如onClick缓存复用）
  - 静态标记（packages/shared/src/patchFlags.ts）：标记节点类型（动态文本/类/样式等），patch时跳过静态节点
  - 静态提升：静态节点创建后保存，更新时直接复用（避免重复创建）
  - patchKeyedChildren函数：优化子节点对比，基于最长递增子序列减少DOM移动
    - 对比流程：头头比→尾尾比→最长递增子序列优化（移动/添加/删除节点）

因为 Diff 算法，计算的就是虚拟 DOM 的差异，所以先铺垫一点点虚拟 DOM，了解一下其结构，再来一层层揭开 Diff 算法的面纱，深入浅出，助你彻底弄懂 Diff 算法原理

认识虚拟 DOM

虚拟 DOM 简单说就是 用JS对象来模拟 DOM 结构

那它是怎么用 JS 对象模拟 DOM 结构的呢？看个例子

<template>
    <div id="app" class="container">
        <h1>沐华</h1>
    </div>
</template>

上面的模板转在虚拟 DOM 就是下面这样的

{
  'div',
  props:{ id:'app', class:'container' },
  children: [
    { tag: 'h1', children:'沐华' }
  ]
}

这样的 DOM 结构就称之为 虚拟 DOM (Virtual Node)，简称 vnode。

它的表达方式就是把每一个标签都转为一个对象，这个对象可以有三个属性：tag、props、children

tag：必选。就是标签。也可以是组件，或者函数
props：非必选。就是这个标签上的属性和方法
children：非必选。就是这个标签的内容或者子节点，如果是文本节点就是字符串，如果有子节点就是数组。换句话说如果判断 children 是字符串的话，就表示一定是文本节点，这个节点肯定没有子元素

为什么要使用虚拟 DOM 呢？ 看个图

如图可以看出原生 DOM 有非常多的属性和事件，就算是创建一个空div也要付出不小的代价。而使用虚拟 DOM 来提升性能的点在于 DOM 发生变化的时候，通过 diff 算法和数据改变前的 DOM 对比，计算出需要更改的 DOM，然后只对变化的 DOM 进行操作，而不是更新整个视图

在 Vue 中是怎么把 DOM 转成上面这样的虚拟 DOM 的呢，有兴趣的可以关注我另一篇文章详细了解一下 Vue 中的模板编译过程和原理

在 Vue 里虚拟 DOM 的数据更新机制采用的是异步更新队列，就是把变更后的数据变装入一个数据更新的异步队列，就是 patch，用它来做新老 vnode 对比