# 👉 diff 算法
Vue2 diff 算法是通过同层之间的树节点进行比较，时间复杂度只有 O(n), 算是一个较高效的算法。 本文章主要针对 Vue2 diff 算法展开，最后再简单提及一下与 Vue3 和 React diff 的区别。
# why diff
数据变化，vue 如何更新节点 会先根据真实的 DOM 节点结构生成 virtual DOM，当 virtual DOM 某个节点的数据改变后，会生成一个新虚拟节点 vnode。 触发 set 方法后，消息发布器 Dep 调用 Dep.notify 通知所有订阅者 watcher，订阅者的回调函数
vm.update(vm.render())，vm.render()就是生成的新 vnode，vm.update(）就会带着新 vnode，和旧虚拟节点 oldVNode 作对比，给真实的 DOM 打补丁，最后更新相应的视图。virtual DOM 和真实 DOM 区别
使用 document.CreateElement 和 document.CreateTextNode 创建的就是真实节点。
virtual DOM 是将真实的 DOM 的数据抽取出来，以对象的形式模拟树形结构：
<div id="test" class="div1"> <p class="p1"></p> <p class="p2"></p> </div>对应以下虚拟 DOM 对象
const vnode = { el: div, //对真实的节点的引用，本例中对应document.querySelector('#test.div1') tag: "div", //节点的标签 sel: "div#test.div1", //节点的选择器 data: null, // 一个存储节点属性的对象，对应节点的el[prop]属性，例如onclick , style text: null, //如果是文本节点，对应文本节点的textContent，否则为null children: [ { el: p, tag: "p", sel: "p.p1", data: null, text: null, children: [], }, { el: p, tag: "p", sel: "p.p2", data: null, text: null, children: [], }, ], //存储子节点的数组，每个子节点也是 vnode 结构 };virtual DOM 本质是在 JS 操控 DOM 的过程中进行一个缓存。使用真实 DOM 对更新的数据重绘整个视图层是相当消耗性能，通过虚拟 DOM 和 diff 算法得出一些需要修改的最小单位，并对小单位的位图作出对应的更新，这样子可以减少不必要的 DOM 操作，以此来提高性能。
diff 比较方式 Vue2 的 diff 通过 patch 函数像打补丁一样修改真实 DOM，比较只会在同层级进行, 不会跨层级比较。（算法核心是同级比较和双端对比）
比较时，在同级比较中，它会同时从新旧子节点数组的头和尾开始，进行四轮快速比对。如果这四轮都没匹配上，就会利用我们在 v-for 中定义的 key 值去旧节点里查找可复用的节点。
# how diff
1） 通过patch对同级进行比较，然后再往下比较子节点；
首先会通过sameNode判断两个节点的 key、tag、isComment、data 同时定义或不定义以及当标签类型为 input 的时候的 type 相不相同来确定两个节点是不是相同的节点：
如果不是的话就将新节点替换旧节点；
如果是相同节点的话才会进入到 patchVNode 阶段。
2）patchVNode 阶段中，会有几种情况的判断：
a. 判断节点引用是否完全一致，是则直接 return；
b. 然后会对文本节点进行判断，如果是文本节点并且不相等，那么将真实 DOM 对应的文本节点设置为 VNode 的文本节点；
c. 然后再判断一方有子节点和一方没有子节点的情况：
如果旧的一方没有而新一方有子节点，则添加创建并添加新的子节点；
如果旧的一方有而新一方没有子节点，则把旧子节点删除；
d. 最后是判断双方都存在子节点的情况，是则执行 updateChildren 操作。
3）通过 updateChildren 来更新子节点：
在这个阶段核心是采用双端比较的算法，同时从新旧节点的两端进行比较。
在这个过程中，会用到模版编译时的静态标记配合 key 来跳过对比静态节点（没有涉及 data 数据{{}}）。
- 核心策略
- 同层限制：只比较同一层级的 VNode，不同层级直接销毁重建。
- 双指针遍历，向中间收缩：对新旧 VNode 列表分别设置oldStartIdx（旧头）、oldEndIdx（旧尾）、newStartIdx（新头）、newEndIdx（新尾）四个指针，优先比较首尾节点以快速复用。
- key 的作用：当首尾无法匹配时，通过key建立旧节点的索引映射，快速查找可复用节点。
# patch
diff 的过程就是调用 patch 函数，就像打补丁一样修改真实 dom。
patch 函数有两个参数，vnode 和 oldVNode，也就是新旧两个虚拟节点。
function patch(oldVNode, vnode) {
if (sameVNode(oldVNode, vnode)) {
patchVNode(oldVNode, vnode);
} else {
// 当前oldVNode对应的真实元素节点
const oEl = oldVNode.el;
// 父元素
let parentEle = api.parentNode(oEl);
// 根据VNode生成新元素
createEle(vnode);
if (parentEle !== null) {
// 将新元素添加进父元素
api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl));
// 移除以前的旧元素节点
api.removeChild(parentEle, oldVNode.el);
oldVNode = null;
}
}
// patch最后会返回vnode，vnode和进入patch之前的不同在哪
return vnode;
}
# sameNode
/*
判断两个VNode节点是否是同一个节点，需要满足以下条件：
key相同
tag相同（当前节点的标签名）
isComment相同（是否为注释节点）
是否data都有定义（当前节点对应的对象，包含了具体的一些数据信息，是一个VNodeData类型，可以参考VNodeData类型中的数据信息）
当标签是<input>时，type是否相同
*/
function sameVNode(a, b) {
return (
a.key === b.key &&
a.tag === b.tag &&
a.isComment == b.isComment &&
isDef(a.data) == isDef(b.data) &&
sameInputType(a, b)
);
}
/*
判断当标签是<input>的时候，type是否相同
某些浏览器不支持动态修改<input>类型，所以他们被视为不同类型
*/
function sameInputType(a, b) {
if (a.tag !== "input") return true;
let i;
const typeA = isDef((i = a.data)) && isDef((i = i.attrs)) && i.type;
const typeB = isDef((i = b.data)) && isDef((i = i.attrs)) && i.type;
return typeA === typeB;
}
# patchNode
当 oldVNode 和 VNode 值得比较后，会对两个节点执行 patchNode：
function patchVNode(oldVNode, vnode) {
// 引用一致则直接返回
if (oldVNode === vNode) return;
// 指向对应的真实DOM
// vnode表示新节点，此时是没有elm属性的。而在经过createElm方法后，vnode.children中的子节点都有了elm属性，此时只有vnode没有elm属性，而能进到 patchVNode 方法来的新旧节点，一定经过了sameVNode方法的判断，说明他们节点本身几乎一样，所以新节点可以用旧节点的elm
const el = (vnode.el = oldVNode.el);
let i;
let oldCh = oldVNode.children;
let ch = vnode.children;
// 如果他们都有文本节点并且不相等，那么将el的文本节点设置为vnode的文本节点
if (
oldVNode.text !== null &&
vnode.text !== null &&
oldVNode.text !== vnode.text
) {
// node.textContent = vnode.text
api.setTextContent(el, vnode.text);
} else {
updateEle(el, vnode, oldVNode);
// 如果oldVNode和vnode都有子节点，则执行updateChildren，对子节点进行比较（diff核心）
if (oldCh && ch && oldCh !== ch) {
updateChildren(el, oldCh, ch);
}
// 如果oldVNode没有子节点，而vnode有，则将vode的子节点真实化并新增至el
else if (ch) {
createEle(vnode);
}
// 如果oldVNode有子节点，而vnode没有，则删除el的子节点
else if (oldCh) {
api.removeChildren(el);
}
}
}
# updateChildren
function updateChildren(parentElm, oldCh, newCh) {
// 提取 oldVNode 子节点的头尾Idx以及节点内容，作为移动指针
let oldStartIdx = 0, oldEndIdx = oldCh.length - 1;
let oldStartVNode = oldCh[0], oldEndVNode = oldCh[oldEndIdx];
// 提取 newVNode 子节点的头尾Idx以及节点内容，作为移动指针
let newStartIdx = 0, newEndIdx = newCh.length - 1;
let newStartVNode = newCh[0], newEndVNode = newCh[newEndIdx];
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 边界情况处理
if (oldStartVNode == null) {
oldStartVNode = oldCh[++oldStartIdx];
} else if (oldEndVNode == null) {
oldEndVNode = oldCh[--oldEnIdx];
} else if (newStartVNode == null) {
newStartVNode = newCh[++newStartVNode];
} else if (newEndVNode == null) {
newEndVNode = newCh[--newEndIdx];
}
// 前四种情况是在有指定key的时候，分别比较oldCh以及newCh的两头节点 2*2=4 种情况。若判定为同一个VNode则直接patchVNode。
// 对于 sameVNode(oldStartVNode, newStartVNode) 和 sameVNode(oldEndVNode,newEndVNode) 为 true 的情况，不需要对DOM进行移动
else if (sameVNode(oldStartVNode, newStartVNode)) {
// 1. 新旧头匹配：直接复用，指针后移
patchVNode(oldStartVNode, newStartVNode);
// 匹配上的两个指针向中间移动
oldStartVNode = oldCh[++oldStartIdx];
newStartVNode = newCh[++newStartIdx];
} else if (sameVNode(oldEndVNode, newEndVNode)) {
// 2. 新旧尾匹配：直接复用，指针前移
patchVNode(oldEndVNode, newEndVNode);
oldEndVNode = oldCh[--oldEndIdx];
newEndVNode = newCh[--newEndIdx];
} else if (sameVNode(oldStartVNode, newEndVNode)) {
// 3. 旧头新尾匹配：复用并移动到尾部
patchVNode(oldStartVNode, newEndVNode);
//若oldStartVNode和newEndVNode匹配上了，说明真实DOM的第一个子节点会被移动最后
api.insertBefore(
parentElm,
oldStartVNode.el,
api.nextSibling(oldEndVNode.el)
);
oldStartVNode = oldCh[++oldStartIdx];
newEndVNode = newCh[--newEndIdx];
} else if (sameVNode(oldEndVNode, newStartVNode)) {
// 4. 旧尾新头匹配：复用并移动到头部
patchVNode(oldEndVNode, newStartVNode);
// 若oldEndVNode和newStartVNode匹配上了，说明真实DOM的最后子节点会被移动最前
api.insertBefore(parentElm, oldEndVNode.el, oldStartVNode.el);
oldEndVNode = oldCh[--oldEndIdx];
newStartVNode = newCh[++newStartIdx];
}
// 5. 首尾均不匹配：通过key映射查找可复用节点
// 根据所有旧子节点的key生成哈希表，key为oldVNode的key，value为对应index序列的哈希表（所有旧子节点的 key 映射到旧节点下标）。
else {
// 所有旧子节点的 key 映射到旧节点下标，然后用新vnode的key去找出在旧节点中可以复用的位置。
// 比如oldCh是这样的 [{xx: xx, key: 'key0'}, {xx: xx, key: 'key1'}, {xx: xx, key: 'key2'}]，oldStartIdx = 0，oldEndIdx = 2
// 存储所有旧子节点的Key -> index的哈希表，生成 {key0: 0, key1: 1, key2: 2}
const oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
// 新节点匹配旧子节点中的index，即在旧节点中匹配可复用的位置
const idxInOld = oldKeyToIdx[newStartVNode.key];
// 无匹配节点则创建新节点，newStartVNode没有key 或 该key没有在老节点中匹配上，则创建一个新的节点插入至oldStartVNode对应位置
if (!idxInOld) {
createElm(newStartVNode, parentElm, oldStartVNode.elm);
} else {
// 匹配上了，则获取同key的旧子节点,移动到当前位置
const vnodeToMove = oldCh[idxInOld];
// 相同key，还要判断和匹配节点是否为sameVNode
if (vnodeToMove.sel !== newStartVNode.sel) {
// 相同key但不是sameVNode的时候，创建新节点并插入至oldStartVNode.el的前边。
api.insertBefore(parentElm,createEle(newStartVNode).el,oldStartVNode.el);
} else {
// 相同key且是sameVNode的时候，则将新节点插入，同时往下patchVNode，并把匹配上的旧子节点设置为null
pathVNode(vnodeToMove, newStartVNode);
oldCh[idxInOld] = null;
api.insertBefore(parentElm, vnodeToMove.el, oldStartVNode.el);
}
}
newStartVNode = newCh[++newStartIdx];
}
}
// 处理剩余节点（新增或删除）
// 在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较。
if (oldStartIdx > oldEndIdx) {
// oldCh先遍历完，则证明剩下的newCh节点是新增的（newStartIdx和newEndIdx之间的vnode），调用addVNodes将其拆入至before后面
const before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el;
addVNodes(parentElm, before, newCh, newStartIdx, newEndIdx);
} else if (newStartIdx > newEndIdx) {
// newCh先遍历完，则在真实DOM中将[oldStartIdx, oldEndIdx]的多余节点删除
removeVNodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
# Vue3 diff 算法
在 Vue2 中，diff 算法是基于同层比较和双端对比进行的。
在 Vue3 中，diff 算法则是双端对比，前缀 + 后缀 + LIS 优化。
- 在 key 映射匹配步骤中，引入了**最长递增子序列（LIS）**算法来进一步减少节点移动次数，这个子序列代表的节点是相对位置没有变化的，只需要移动不在这个子序列中的节点即可。
- 同时也增加了编译时优化：
- 静态提升：在编译阶段将静态节点提升到 render 外，减少运行时对比开销
- Patch Flags：标记动态节点，比如绑定了数据节点或者属性，精准对比标记过的节点
vue3 diff 的核心策略：
- 分阶段处理：双端对比：
- 先匹配前缀相同节点（直接复用，指针后移）。
- 再匹配后缀相同节点（直接复用，指针前移）。
- 中间乱序处理：
- 对剩余节点，用key建立新节点到索引的映射。
- 生成 “新节点在旧列表中的索引” 数组，计算其 LIS（找出无需移动节点序列，其他节点才移动）。
- 遍历旧数组，根据 LIS 结果判断是否需要移动节点，不在 LIS 中的节点需要移动到正确位置。（剩余节点根据 LIS 位置移动，减少操作次数。）
// packages/runtime-core/src/renderer.ts
function patchKeyedChildren(c1, c2, container, ...) {
let i = 0;
let e1 = c1.length - 1, e2 = c2.length - 1;
// 1. 处理前缀相同节点
while (i <= e1 && i <= e2 && isSameVNodeType(c1[i], c2[i])) {
patch(c1[i], c2[i], container);
i++;
}
// 2. 处理后缀相同节点
while (i <= e1 && i <= e2 && isSameVNodeType(c1[e1], c2[e2])) {
patch(c1[e1], c2[e2], container);
e1--;
e2--;
}
// 3. 旧节点处理完，新增剩余新节点
if (i > e1) { /* 新增逻辑 */ }
// 4. 新节点处理完，删除剩余旧节点
else if (i > e2) { /* 删除逻辑 */ }
// 5. 处理中间乱序节点
else {
const s1 = i, s2 = i;
// 建立新节点key到索引的映射
const keyToNewIndexMap = new Map();
for (i = s2; i <= e2; i++) keyToNewIndexMap.set(c2[i].key, i);
// 遍历旧列表，记录新节点在旧列表中的索引（0表示新增）
const newIndexToOldIndexMap = new Array(e2 - s2 + 1).fill(0);
let moved = false, maxNewIndexSoFar = 0;
for (i = s1; i <= e1; i++) {
const oldKey = c1[i].key;
const newIndex = keyToNewIndexMap.get(oldKey);
if (newIndex !== undefined) {
newIndexToOldIndexMap[newIndex - s2] = i + 1; // +1避免0
if (newIndex > maxNewIndexSoFar) maxNewIndexSoFar = newIndex;
else moved = true; // 存在需要移动的节点
} else {
/* 删除无匹配的旧节点 */
}
}
// 计算LIS（无需移动的节点）
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : [];
let lastIndex = increasingNewIndexSequence.length - 1;
// 从后往前处理新节点，移动或新增
for (i = e2; i >= s2; i--) {
const newNode = c2[i];
const newIndex = i - s2;
if (newIndexToOldIndexMap[newIndex] === 0) {
/* 新增节点 */
} else {
if (moved && (lastIndex < 0 || newIndex !== increasingNewIndexSequence[lastIndex])) {
/* 移动节点到正确位置 */
} else {
lastIndex--; // LIS节点无需移动
}
}
}
}
}
# React diff 算法
React 的 diff 基于 Fiber 架构，核心目标是可中断性（时间分片），算法设计更简单，优先保证 UI 响应速度。
因为 Fiber 树是单链表结构，没有子节点数组数据结构，也没有反向指针，也就没有可以供两端同时比较的尾部游标。所以React的这个算法是一个简化的两端比较法，只从头部开始比较。
React diff 采用单向递归比较，它默认从左到右遍历新列表，依靠 key 和节点类型来识别可复用的节点。其算法实现相对简单，可预测性强。
其设计思路：
- 分层，同层比较：将 DOM 树分为多个层级，然后逐层比较，只比较同一层级的节点，从而减少比较的复杂度。同级比较时按照从左到右的顺序进行比较。
- 节点类型优先：两个不同类型的元素会生成不同的树，如果元素类型发生了变化，React 会销毁旧树并创建新树；相同类型复用节点，比较属性，然后递归比较子节点；
- 依赖 Key 属性进行比较：
- 依赖 key 识别可复用节点（无 key 时按索引比较，可能导致状态错乱）。
- 从左到右遍历新列表，用 lastPlacedIndex 标记已处理节点的最大旧索引：
- 若新节点的旧索引 ≤ lastPlacedIndex，则需要移动；否则更新 lastPlacedIndex。
React 的 diff 算法简述：
第一轮遍历 newChildren：处理可复用的节点
- 从头开始遍历 newChildren ，逐个与 oldFiber 链中的节点进行比较，判断 DOM 节点是否可复用。
- 如果节点的 key 不同，则不可复用，直接跳出循环，第一轮遍历结束。
- 如果 key 相同，但是 type 不同，则会重新闯进新 fiber，将 oldFiber 标记为 Deletion 后续删除，并继续遍历。
- 然后比较 oldFiber.Index 是否小于 lastPlacedIndex 如果是，说明这个节点在新集合中需要向右移动，标记为 Placement ，并更新 lastPlacedIndex；否则则不用移动。
第一轮 newChildren 遍历已完成，新节点已经遍历完成，如果还剩老节点，则将剩下老节点直接删除。
如果老节点没有了，新节点还有 或者 初次渲染，就直接插入。
如果新旧节点都还有，就进行第二次遍历：
- 把 oldFiber 按照 key 或者 index 放到Map 里，然后遍历新的 Fiber，进行匹配复用。
- 然后比较 oldFiber.Index 是否小于 lastPlacedIndex 如果是，说明这个节点在新集合中需要向右移动，标记为 Placement ，并更新 lastPlacedIndex；否则则不用移动。
// react-reconciler/src/ReactChildFiber.new.js 简化的核心逻辑
function reconcileChildrenArray(
returnFiber: Fiber, // currentFirstChild 的父级 fiber 节点
currentFirstChild: Fiber | null, // 当前执行更新任务的 fiber 节点
newChildren: Array<*>, // 组件的 render 方法渲染出的新的 ReactElement 节点
lanes: Lanes,
) {
let resultingFirstChild: Fiber | null = null;
let previousNewFiber: Fiber | null = null;
let oldFiber = currentFirstChild;
let newIdx = 0;
let nextOldFiber = null;
let lastPlacedIndex = 0; // 已处理节点的最大旧索引
// 初次渲染（false）还是更新（true）
let shouldTrackSideEffects = !!returnFiber.alternate
// 1.从头开始遍历 newChildren ，逐个与 oldFiber 链中的节点进行比较，判断 DOM 节点是否可复用
// 第一轮遍历完毕后，会有以下几种情况：
// 1.1 newChildren 与 oldFiber 同时遍历完👇
for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
if (oldFiber.index > newIdx) {
nextOldFiber = oldFiber;
oldFiber = null;
} else {
// 获取下一个旧节点
nextOldFiber = oldFiber.sibling;
}
// 生成新的节点，判断 key 与 type 是否相同就在 updateSlot 中
// 只有 key 和 type 都相同才会复用 oldFiber 节点
const newFiber = updateSlot(
returnFiber,
oldFiber,
newChildren[newIdx],
lanes,
);
// 1.1.1 key 不同，newFiber 会为 null ，直接跳出循环，第一轮遍历结束
if (newFiber === null) {
if (oldFiber === null) { oldFiber = nextOldFiber; }
break;
}
// 1.1.2 key 相同，但是 type 不同的情况，将 oldFiber 打上 Deletion 的标记，循环继续
if (shouldTrackSideEffects) {
if (oldFiber && newFiber.alternate === null) {
deleteChild(returnFiber, oldFiber);
}
}
// 1.1.3 记录最后一个可复用的节点在 oldFiber 中的位置索引
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 调整指针
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
oldFiber = nextOldFiber;
}
// 1.2 newChildren 遍历完，oldFiber 没遍历完，遍历剩下的 oldFiber 并标记为 Deletion
if (newIdx === newChildren.length) {
deleteRemainingChildren(returnFiber, oldFiber);
return resultingFirstChild;
}
// 1.3 newChildren 没遍历完，oldFiber 遍历完
// 这说明 newChildren 中剩下的节点都是新插入的节点，只需遍历剩下的 newChildren 创建新的 Fiber 节点并以此标记为 Placement
if (oldFiber === null) {
// 遍历剩余的 newChildren
for (; newIdx < newChildren.length; newIdx++) {
// 创建新的 Fiber 节点
const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
if (newFiber === null) { continue;}
// 将新的 Fiber 节点标记为 Placement
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 将新的 Fiber 节点用 sibling 指针连接成链表
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
// 返回新的 Fiber 节点组成的链表的头部节点
return resultingFirstChild;
}
// 1.4 newChildren 与 oldFiber 都没遍历完，这是 Diff 算法最难的部分。
// 有可能存在移动了位置的节点，所以为了快速地找到 oldFiber 中可以复用的节点，则创建一个以 oldFiber 的 key 为 key ，oldFiber 为 value 的 Map 数据结构。
const existingChildren = mapRemainingChildren(returnFiber, oldFiber);
// 遍历剩余的 newChildren ，逐个在 map 中寻找 oldFiber 中可复用的节点。
// 如果找到可复用的节点，则将 oldIndex 与 lastPlacedIndex 比较。
// 如果 oldIndex 与 lastPlacedIndex 小，则该节点需要右移，将新的 Fiber 节点标记为 Placement 。否则，将 lastPlacedIndex 更新为 oldIndex 。
// 遍历 newChildren，在 map 中查找在 oldFiber 中可复用的节点
for (; newIdx < newChildren.length; newIdx++) {
const newFiber = updateFromMap(
existingChildren,
returnFiber,
newIdx,
newChildren[newIdx],
lanes,
);
// 找到了可复用的 Fiber 节点，将其从 map 中删除，因为该节点已经被复用了
if (newFiber !== null) {
if (shouldTrackSideEffects) {
if (newFiber.alternate !== null) {
existingChildren.delete(newFiber.key === null ? newIdx : newFiber.key,);
}
}
// 更新最后一个可复用节点节点的位置索引
lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
// 将 newFiber 用 sibling 连接成单链表
if (previousNewFiber === null) {
resultingFirstChild = newFiber;
} else {
previousNewFiber.sibling = newFiber;
}
previousNewFiber = newFiber;
}
}
// 遍历完 newChildren 后，还存在 map 在的节点就是剩余的节点，需要标记为删除（Deletion）
if (shouldTrackSideEffects) {
existingChildren.forEach(child => deleteChild(returnFiber, child));
}
// 返回新的 fiber 链表
return resultingFirstChild;
}
https://juejin.cn/post/7131741751152214030
https://juejin.cn/post/7318446267033452570
Fiber 结构：
function FiberNode(
tag: WorkTag,
pendingProps: mixed,
key: null | string,
mode: TypeOfMode,
) {
// Instance
this.tag = tag; // 表示节点类型的标记，例如 FunctionComponent 、ClassComponent 等。
this.key = key;
this.elementType = null;
this.type = null;
this.stateNode = null;
// Fiber
this.return = null; // 指向该 FiberNode 的父节点
this.child = null; // 指向该 FiberNode 的第一个子节点
this.sibling = null; // 指向右边第一个兄弟 Fiber 节点
this.index = 0; // 当前节点在父节点的子节点列表中的索引
this.ref = null; //存储 FiberNode 的引用信息，与 React 的 Ref 有关
this.pendingProps = pendingProps;
this.memoizedProps = null;
this.updateQueue = null;
this.memoizedState = null;
this.dependencies = null;
this.mode = mode;
// Effects
this.flags = NoFlags;
this.nextEffect = null;
this.firstEffect = null;
this.lastEffect = null;
this.lanes = NoLanes;
this.childLanes = NoLanes;
this.alternate = null;
// 省略一些无关的属性...
}
# 一个例子
旧列表: [A, B, C, D] → 新列表 [A, C, B, E]
- Vue2 的处理过程
双端指针与四种配对，尝试头头、尾尾、旧头新尾、旧尾新头四种快速命中，最后利用旧节点映射序列进行映射查找，匹配到的旧节点（即可被复用节点）移到OldStart指针前。
步骤1: 使用双端比较，头头比较
A === A ✓ 匹配，两个指针都后移
剩余 [B, C, D] vs [C, B, E]
步骤2: 四种配对都不命中，走映射查找，用新节点去匹配旧节点map，匹配到的旧节点移到OldStart指针前
指 针：oldStart = B (1), newStart = C (1)
比较四项：B≠C, D≠E, B≠E, D≠C
映 射：newStart(C) -> 匹配上了 旧映射 Index 2，
移动这个旧节点 C 到 oldStart(B) 前面，insertBefore(parent, C.el, B.el)
处理标记：旧数组位置 2 置为占位（如 undefined），newStartIdx++
DOM 变为 [A, C, B, D]
步骤3：头头再次匹配
指 针： oldStart = B (1), newStart = B (2)
比较四项： B=B
动 作：复用/patch B，指针前移
步骤4：四种配对仍不命中，查映射未找到
指 针：指针推进会跳过旧数组中的占位项（idx=2 处是已移动的 C），oldStart = D (3), newStart = E (3)
比较四项：D≠E、D≠E（尾尾）等
映 射：旧列表中没有 E
动 作：创建新节点 E 并插入到未处理窗口的最前方（以 oldStart(D) 为锚），insertBefore(parent, E.el, D.el)
DOM 暂时变为 [A, C, B, E, D] 。
步骤5：清理剩余旧节点
指 针：newStartIdx++ 越界结束主循环（newStartIdx=4 > newEndIdx=3）
新列表已处理完，旧列表还有 D 未被复用
动作：移除旧节点 D
DOM 最终变为 [A, C, B, E] （与新列表一致）
总结：只需要移动D，其他节点都不动
- Vue3 的处理过程 先利用双端比较对齐公共前后缀，然后对未知区间构建 key→index 映射，填充 newIndexToOldIndexMap，计算 LIS，最后从右往左遍历新序列执行插入和移动。
步骤1：同步头部公共前缀
- 相同前缀，无相同后缀，中间乱序：[B,C,D] -> [C, B, E]，此时i=1
步骤2：用新未知区间构建映射，然后扫遍历旧列表，记录新节点在旧列表中的索引（0表示新增）
- 新未知区间 key→index： { C:1, B:2, E:3 }
- 扫描旧：
- C 命中新索引 1 ，记录并 patch(C)，记录至newIndexToOldIndexMap
- B 命中新索引 2 ，记录并 patch(B)，记录至newIndexToOldIndexMap
- D 未命中，执行卸载（ remove(D) ）
- 按 新未知区间顺序 得到旧索引序列，newIndexToOldIndexMap 类似 [oldIndex(C)+1, oldIndex(B)+1, E->0] = [3, 2, 0]
步骤3：计算 LIS
- 新节点 key 映射newIndexToOldIndexMap，即按新未知区间顺序得到旧索引序列（0 基）： [C→2, B→1, E→未命中(0)]
- newIndexToOldIndexMap 类似 [oldIndex(C)+1, oldIndex(B)+1, E->0] = [3, 2, 0]
- 非零部分 [3, 2] 的 LIS 长度为 1,保留其中一个（常见是保留 B ），意味着 C 需要移动。
步骤4：从右向左按新序执行插入/移动
- j=2，新节点 E 未命中（值为 0），需要创建
- 锚点 anchor = new[j+1]?.el 不存在，等价于创建追加到末尾
- insertBefore(parent, E.el, null) → DOM： [A, B, C, E]
- j=1，新节点 B 在 LIS，跳过，不移动
- j=0，新节点 C 不在 LIS，需要移动到锚点 B 之前
- 锚点 anchor = B.el
- insertBefore(parent, C.el, B.el) → DOM： [A, C, B, E]
- React 的处理过程 同层比较，key + type 相同则复用；数组新 children 走 O(n) 扫描，不计算 LIS，用 lastPlacedIndex 判定是否移动，小于lastPlacedIndex 则移动。
步骤1：线性遍历新节点列表，逐个与 oldFiber 链中的节点对比
- 复用/patch A ； lastPlacedIndex = oldIndex(A)=0 。
- 未知区间：旧 [B, C, D] ，新 [C, B, E] 。
步骤2: 构建旧节点 key→fiber 映射，遍历新未知区间，通过key筛选可复用节点
- 旧未知区间 key→fiber：{ B:fiber(B), C:fiber(C), D:fiber(D)}
- 遍历新未知区间 [C, B, E]，检查在旧节点map中是否存在同key节点可以匹配复用
- C 命中旧节点 C， 旧索引 2 ≥ lastPlacedIndex(0) → 不移动，更新 lastPlacedIndex=2 。
- B 命中旧节点 B， 旧索引 1 < lastPlacedIndex(2) → 向右移动，更新 lastPlacedIndex=2 。
- E 未命中，创建并标记 Placement。
- 新未知区间遍历完，删除旧未知区间中未命中节点 D
步骤3: 提交阶段放置
- 根据标记执行插入/移动。
- B 因为需要移动，插入到正确锚点之前（锚点由 getHostSibling 计算，确保最终顺序与新序
- E 作为新建通常追加到末尾。