Vue通过渲染器把虚拟DOM渲染成真实DOM。首次调用渲染器的渲染函数时，只需要创建新的DOM元素即可，这个过程只涉及到挂载。而后续再次调用渲染器的渲染函数时，这时候就需要进行新旧虚拟dom的对比，并试图找到更新变更点，这个过程被称为“打补丁”（或更新），英文通常用patch表达。其实首次渲染的挂载也可以看作特殊的patch，只是旧的虚拟dom不存在的patch。
patch函数在比对新旧两个节点时，当新旧两个节点的子节点都是一组子节点时，如果用最简单粗暴的方式卸载全部旧子节点，再挂载全部新子节点，会产生极大的性能开销。所以需要对新旧两组子节点进行比对，以最小的性能开销完成更新操作。这个比对的算法就是vue的diff算法。由此也可以看出，diff算法只会在同层级进行比较, 不会跨层级比较。
假如有以下两个vnode
const oldVnode = {
type: "div",
children: [
{ type: "p", children: "A" },
{ type: "p", children: "B" },
{ type: "p", children: "C" },
],
};
const newVnode = {
type: "div",
children: [
{ type: "p", children: "D" },
{ type: "p", children: "E" },
{ type: "p", children: "F" },
],
};
最简单粗暴的方式，是将旧vnode的三个子节点全部删除，再挂载三个新的子节点，所以一共要6次DOM操作。
而我们可以发现新旧vnode的三个子节点标签按照顺序比较都是一样的，即都是div标签，只是该标签文本节点的内容改变了，所以其实只需要依次更新三个字节点的内容即可，也就是说只需要操作三次DOM。
function diff(oldVnode, newVnode) {
const oldVnodeChildren = oldVnode.children
const newVnodeChildren = newVnode.children
for (let i = 0; i < oldVnodeChildren.length; i++) {
// 省略代码，这里执行oldVnodeChildren[i]和newVnodeChildren[i]的更新操作
}
}
如果新旧vnode的字节点数量不一样时，如果旧的vnode的子节点数量比较多，则需要将多余的旧子节点卸载；反之，如果新的vnode的子节点数量比较多，则需要挂载多出的新的子节点。于是扩展一下上面的函数
function diff(oldVnode, newVnode) {
const oldVnodeChildren = oldVnode.children
const newVnodeChildren = newVnode.children
const oldLength = oldVnodeChildren.length
const newLength = newVnodeChildren.length
const minLength = Math.min(oldLength, newLength)
for (let i = 0; i < minLength; i++) {
// 省略代码，这里执行oldVnodeChildren[i]和newVnodeChildren[i]的更新操作
}
if(newLength > oldLength) {
for (let i = minLength; i < newLength; i++){
// 省略代码，这里执行newVnodeChildren[i]的挂载操作
}
}else if(newLength < oldLength){
for (let i = minLength; i < oldLength; i++){
// 省略代码，这里执行oldVnodeChildren[i]的卸载操作
}
}
}
当然上面的对比方式还有很大的优化空间。例如下面两组新旧vnode，如果按照上面的方式一个一个比对更新，要更新三次。但我们可以发现其实新旧vnode的子节点是一样的，只是顺序变了而已。如果是通过dom移动操作的话，则不需要操作这么多次。
const oldVnode = {
type: "div",
children: [
{ type: "p", children: "A" },
{ type: "p", children: "B" },
{ type: "p", children: "C" },
],
};
const newVnode = {
type: "div",
children: [
{ type: "p", children: "C" },
{ type: "p", children: "A" },
{ type: "p", children: "B" },
],
};
那么代码怎么知道新旧两组子节点中节点的对应关系呢。于是vue中就引入了key作为vnode的标识。有了key值的标识，我们就可以知道新旧节点的映射关系，也就可以知道新子节点在旧子节点的中的位置，就可以进行相应的DOM移动操作了。而且，有了key值，就可以对相同key值的子节点进行比对更新。
上面例子添加对应的key值如下
const oldVnode = {
type: "div",
children: [
{ type: "p", children: "A", key: "1" },
{ type: "p", children: "B", key: "2" },
{ type: "p", children: "C", key: "3" },
],
};
const newVnode = {
type: "div",
children: [
{ type: "p", children: "C", key: "3" },
{ type: "p", children: "A", key: "1" },
{ type: "p", children: "B", key: "2" },
],
};
那么，如何找到需要移动的元素并移动它呢。
我们的目的是要将旧的节点组的顺序调整为新的节点组的顺序。我们可以遍历新的节点组，新的节点组按照索引从小到大顺序执行，每次执行都去查找相同key值节点在旧的节点组的索引。在查找的过程中，存储最大的索引值。后续查找时，遇到索引值比当前存储的最大索引值小时，则需要移动该节点。
function diff(oldVnode, newVnode) {
const oldVnodeChildren = oldVnode.children;
const newVnodeChildren = newVnode.children;
let lastIndex = 0 // 存储索引值
for(let i = 0; i < newVnodeChildren.length; i++){
let newVnode = newVnodeChildren[i];
for(let j = 0; j < oldVnodeChildren.length; j++){
let oldVnode = oldVnodeChildren[j]
if(newVnode.key === oldVnode.key){
// 省略代码，这里执行oldVnode, newVnode的更新操作
if(j<lastIndex){ // 这里说明真实dom需要进行移动操作
const prevVnode = newVnodeChildren[i-1] // 获取新的虚拟vnode的上一个节点
if(prevVnode){
// 省略代码，这里执行DOM移动操作（insertBefore）将newVnode对应的真实dom移动到prevVnode对应的真实DOM后面
}
}else{
lastIndex = j
}
break; // 找到相同的key了就没必要再往下找了
}
}
}
}
在找查找相同key的时候，如果新子节点没有在旧子节点组中找到对应的key值，则说明该节点是新增的节点。如果在旧子节点组中有新子节点组没有的节点，说明该节点已被删除。所以扩展上面的代码为
function diff(oldVnode, newVnode) {
const oldVnodeChildren = oldVnode.children;
const newVnodeChildren = newVnode.children;
let lastIndex = 0 // 存储索引值
for(let i = 0; i < newVnodeChildren.length; i++){
let newVnode = newVnodeChildren[i];
let isFind = false;
for(let j = 0; j < oldVnodeChildren.length; j++){
let oldVnode = oldVnodeChildren[j]
if(newVnode.key === oldVnode.key){
isFind = true
// 省略代码，这里执行oldVnode, newVnode的更新操作
if(j<lastIndex){ // 这里说明真实dom需要进行移动操作
const prevVnode = newVnodeChildren[i-1] // 获取新虚拟vnode的上一个节点
if(prevVnode){
// 省略代码，这里执行DOM移动操作（insertBefore）将newVnode对应的真实dom移动到prevVnode对应的真实DOM后面
}
}else{
lastIndex = j
}
break; // 找到相同的key了就没必要再往下找了
}
}
// 如果没找到
if(!isFind){
const prevVnode = newVnodeChildren[i-1] // 获取新虚拟vnode的上一个节点
if(prevVnode){
// 省略代码，这里执行DOM移动操作（insertBefore）将newVnode对应的真实dom移动到prevVnode对应的真实DOM后面
}else{
// 这里说明没有前一个vnode节点
// 省略代码，将newVnode对应的真实dom挂载为第一个子节点
}
}
}
// 上面更新，新增完了之后，遍历旧的子节点组，卸载需要删除的节点
for(let i = 0; i < oldVnodeChildren.length; i++){
const oldVnode = oldVnodeChildren[i]
const has = newVnodeChildren.find(e=>e.key === oldVnode.key)
if(!has){
// 省略代码，执行oldVnode的卸载操作
}
}
}
vue2的双端Diff算法
const oldVnode = {
type: "div",
children: [
{ type: "p", children: "A", key: "1" },
{ type: "p", children: "B", key: "2" },
{ type: "p", children: "C", key: "3" },
],
};
const newVnode = {
type: "div",
children: [
{ type: "p", children: "C", key: "3" },
{ type: "p", children: "A", key: "1" },
{ type: "p", children: "B", key: "2" },
],
};
按照上面的方法来更新上面的两个vnode的子节点组，需要先将key为1的节点移到key为3的节点下面，接着再将key为2的节点移到key为1的节点下面，一共是两次DOM移动操作。
而其实可以直接将key为3的节点直接移到key为1的节点前面，只需一步就可以。
所以为了优化操作，就需要用到双端diff算法。
双端diff算法，顾名思义就是要对比新旧两组子节点的两个端点。所以需要四个索引值。
function diff(oldVnode, newVnode){
const oldVnodeChildren = oldVnode.children;
const newVnodeChildren = newVnode.children;
// 四个索引值
let oldStartIndex = 0
let oldEndIndex = oldVnodeChildren.length - 1
let newStartIndex = 0
let newEndIndex = newVnodeChildren.length - 1
}
接着这个算法的比较顺序是
1、第一步：oldStartIndex 指向的节点和 newStartIndex 指向的节点进行比较。
2、第二步：oldEndIndex 指向的节点和 newEndIndex 指向的节点进行比较。
3、第三步：oldStartIndex 指向的节点和 newEndIndex 指向的节点进行比较。
4、第四步：oldEndIndex 指向的节点和 newStartIndex 指向的节点进行比较。
具体如下图
上图可以发现第一步比对、第二步比对、第三步比对，比对双方的key值不一致，所以这三步什么也不做，到第四步时，二者的key是一致的，这时候就需要在新旧两个节点之间打补丁更新，然后进行dom移动操作。由于oldEndIndex对应的节点是最后一个子节点，而新的顺序中，它变成了第一个子节点，所以就需要将oldEndIndex指向的虚拟节点对应的真实dom移动到索引oldStartIndex指向的虚拟节点所对应的真实DOM前面。
至此，第一轮对比就结束了，但这时候dom元素还没对比完，所以需要更新索引值继续对比，由于前面第四步相关的两个索引值是oldEndIndex和newStartIndex，所以需要更新这两个值。将oldEndIndex减一，将newStartIndex加一。结果如下图
同理，继续比对，第一步比对key值不同，所以什么都不做，第二步比对发现oldEndIndex指向的节点和newEndIndex指向的节点key值相同，所以在新旧两个节点之间打补丁更新，这时由于两个节点都处于尾部，所以不需要进行dom移动操作。
然后继续更新索引值，将索引oldEndIndex减一和newEndIndex减一。结果如下图
继续比对，第一步和第二步比对key值不同，所以什么都不做，第三步比对发现oldStartIndex指向的节点和newEndIndex指向的节点key值相同，所以在新旧两个节点之间打补丁更新，这时oldStartIndex指向的节点是头部的节点，而newEndIndex指向的节点在尾部，所以需要进行DOM的移动操作，将oldStartIndex指向的虚拟节点对应的真实dom移动到索引oldEndIndex指向的虚拟节点所对应的真实DOM后面。
然后继续更新索引值，将索引oldStartIndex加一和newEndIndex减一。结果如下图
这是新旧两组节点的头部和尾部节点重合，这时继续比对，第一步比对时二者key值相同，所以在新旧两个节点之间打补丁更新，由于他们都是头部节点，所以无需进行dom移动操作。
然后继续更新索引值，将索引oldStartIndex加一和newStartIndex加一。这时oldStartIndex和newStartIndex的值已经分别大于oldEndIndex、newEndIndex的值，就无需继续下一步比对了。
代码如下
function diff(oldVnode, newVnode){
const oldVnodeChildren = oldVnode.children;
const newVnodeChildren = newVnode.children;
// 四个索引值
let oldStartIndex = 0
let oldEndIndex = oldVnodeChildren.length - 1
let newStartIndex = 0
let newEndIndex = newVnodeChildren.length - 1
// 四个索引值指向的vnode节点
let oldStartVnode = oldVnodeChildren[oldStartIndex]
let oldEndVnode = oldVnodeChildren[oldEndIndex]
let newStartVnode = newVnodeChildren[newStartIndex]
let newEndVnode = newVnodeChildren[newEndIndex]
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartVnode.key === newStartVnode.key){
// 省略代码，这里执行oldStartVnode, newStartVnode的更新操作
// 更新索引和索引指向的节点
oldStartVnode = oldVnodeChildren[++oldStartIndex]
newStartVnode = newVnodeChildren[++newStartIndex]
}else if(oldEndVnode.key === newEndVnode.key){
// 省略代码，这里执行oldEndVnode, newEndVnode的更新操作
// 更新索引和索引指向的节点
oldEndVnode = oldVnodeChildren[--oldEndIndex]
newEndVnode = newVnodeChildren[--newEndIndex]
}else if(oldStartVnode.key === newEndVnode.key){
// 省略代码，这里执行oldStartVnode, newEndVnode的更新操作
// 省略代码，这里执行DOM移动操作，将oldStartVnode对应的真实DOM节点移动到oldEndVnode对应的真实DOM节点的后面
// 可以通过 insertBefore 方法将oldStartVnode对应的真实DOM节点移动到oldEndVnode对应的真实DOM节点的nextSibling前面
// 更新索引和索引指向的节点
oldStartVnode = oldVnodeChildren[++oldStartIndex]
newEndVnode = newVnodeChildren[--newEndIndex]
}else if(oldEndVnode.key === newStartVnode.key){
// 省略代码，这里执行oldEndVnode, newStartVnode的更新操作
// 省略代码，这里执行DOM移动操作，将oldEndVnode对应的真实DOM节点移动到newStartVnode对应的真实DOM节点的前面
// 更新索引和索引指向的节点
oldEndVnode = oldVnodeChildren[--oldEndIndex]
newStartVnode = newVnodeChildren[++newStartIndex]
}
}
}
但是，还有一个问题，就是，如果一开始的四步比对都无法命中的情况应该怎么办。
这时候，就需要遍历oldVnodeChildren，找到和newStartVnode相同key值的节点。如果找到了，那可以对两个节点进行打补丁更新，然后由于newStartVnode是新节点组的第一个节点，所以我们需要将找到的相同key值的旧节点移动到旧节点组的最前面。然后将其设置为undefined，最后更新索引值，将索引newStartVnode加一，更新newStartVnode。
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if(oldStartVnode.key === newStartVnode.key){
// 省略代码
}else if(oldEndVnode.key === newEndVnode.key){
// 省略代码
}else if(oldStartVnode.key === newEndVnode.key){
// 省略代码
}else if(oldEndVnode.key === newStartVnode.key){
// 省略代码
}else{
const indexInOld = oldVnodeChildren.findIndex(node => node.key === newStartVnode.key)
if(indexInOld >0 ){
const oldVnodeToMove = oldVnodeChildren[indexInOld]
// 省略代码，这里执行oldVnodeToMove, newStartVnode的更新操作
// 省略代码，这里执行DOM移动操作，将oldVnodeToMove对应的真实DOM节点移动到oldStartVnode对应的真实DOM节点的前面
oldVnodeChildren[indexInOld] = undefined
newStartVnode = newVnodeChildren[++newStartIndex]
}
}
}
后面继续按照顺序比对和更新，如果遇到undefined的节点，就可以更新对应的索引值然后跳过，不用做其他处理，因为该节点已经被处理了。
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
if (!oldStartVnode) { // 增加oldStartVnode为undefined的判断
oldStartVnode = oldVnodeChildren[++oldStartIndex];
}else if (!oldEndVnode) { // 增加oldEndVnode为undefined的判断
oldEndVnode = oldVnodeChildren[--oldEndIndex];
}else if(oldStartVnode.key === newStartVnode.key){
// 省略代码
}else if(oldEndVnode.key === newEndVnode.key){
// 省略代码
}else if(oldStartVnode.key === newEndVnode.key){
// 省略代码
}else if(oldEndVnode.key === newStartVnode.key){
// 省略代码
}else{
const indexInOld = oldVnodeChildren.findIndex(node => node.key === newStartVnode.key)
if(indexInOld >0 ){
const oldVnodeToMove = oldVnodeChildren[indexInOld]
// 省略代码，这里执行oldVnodeToMove, newStartVnode的更新操作
// 省略代码，这里执行DOM移动操作，将oldVnodeToMove对应的真实DOM节点移动到oldStartVnode对应的真实DOM节点的前面
oldVnodeChildren[indexInOld] = undefined
newStartVnode = newVnodeChildren[++newStartIndex]
}
}
}
上文说的遍历oldVnodeChildren，找到和newStartVnode相同key值的节点，如果没找到的情况呢。如下图
如果没找到，说明该节点是一个新增节点。因为该节点是新的节点组的第一个节点，所以只需要挂载该节点到oldStartVnode对应的真实DOM节点的前面。
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
if (!oldStartVnode) {
oldStartVnode = oldVnodeChildren[++oldStartIndex];
} else if (!oldEndVnode) {
oldEndVnode = oldVnodeChildren[--oldEndIndex];
} else if (oldStartVnode.key === newStartVnode.key) {
// 省略代码
} else if (oldEndVnode.key === newEndVnode.key) {
// 省略代码
} else if (oldStartVnode.key === newEndVnode.key) {
// 省略代码
} else if (oldEndVnode.key === newStartVnode.key) {
// 省略代码
} else {
const indexInOld = oldVnodeChildren.findIndex(
(node) => node.key === newStartVnode.key
);
if (indexInOld > 0) {
const oldVnodeToMove = oldVnodeChildren[indexInOld];
// 省略代码，这里执行oldVnodeToMove, newStartVnode的更新操作
// 省略代码，这里执行DOM移动操作，将oldVnodeToMove对应的真实DOM节点移动到oldStartVnode对应的真实DOM节点的前面
oldVnodeChildren[indexInOld] = undefined;
} else {
// 省略代码，这里执行DOM新增挂载操作，将newStartVnode对应的真实DOM节点挂载到oldStartVnode对应的真实DOM节点的前面
}
newStartVnode = newVnodeChildren[++newStartIndex];
}
}
挂载完成后，更新索引，继续后面的比对。直到结束循环。
这时候又有另外的问题，例如就上面的例子，如果新的节点组还有一个新的节点，如下图
按照之前的逻辑走，循环到最后，会变成
这时候oldStartIndex已经大于oldEndIndex了，while循环已经结束，但是新节点组中的key值为5的节点还未处理，可以看出该节点是一个新增节点，需要挂载操作。
需要挂载的节点是newStartIndex和newEndIndex这个区间内的所有节点，那么是挂载到哪里呢，是以newEndIndex+1索引的节点对应的真实dom为锚点，依次通过insertBefore挂载到该锚点的前面，如果newEndIndex+1索引的节点不存在，则传null，insertBefore的第二个参数如果为null，则元素会被插入到末尾。
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
// 省略代码
}
if(oldStartIndex > oldEndIndex && newStartIndex <= newEndIndex){
for(let i = newStartIndex; i <= newEndIndex; i++){
// 省略代码，这里执行DOM新增挂载操作，创建newVnodeChildren[i] 对应的DOM节点，并挂载到newVnodeChildren[newEndIndex+1]对应的真实DOM节点的前面
}
}
另一种情况，如下图
上面的情况循环到最后，会变成
这时候newStartIndex已经大于newEndIndex了，while循环已经结束，但是旧节点组中的key值为2的节点还未处理，可以看出该节点需要卸载。
需要卸载的节点是oldStartIndex和oldEndIndex这个区间内的所有节点。
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex){
// 省略代码
}
if(oldStartIndex > oldEndIndex && newStartIndex <= newEndIndex){
// 省略代码
}else if(newStartIndex > newEndIndex && oldStartIndex <= oldEndIndex){
for(let i = oldStartIndex; i <= oldEndIndex; i++){
// 省略代码，这里执行卸载 oldVnodeChildren[i] 对应的真实DOM
}
}
至此，vue2的双端Diff算法大致就是这样，这里再贴一下vue2关于这块的源码。
function updateChildren(
parentElm,
oldCh,
newCh,
insertedVnodeQueue,
removeOnly
) {
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]
let oldKeyToIdx, idxInOld, vnodeToMove, refElm
// removeOnly is a special flag used only by <transition-group>
// to ensure removed elements stay in correct relative positions
// during leaving transitions
const canMove = !removeOnly
if (__DEV__) {
checkDuplicateKeys(newCh)
}
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
} else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldStartVnode, newEndVnode)) {
// Vnode moved right
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
canMove &&
nodeOps.insertBefore(
parentElm,
oldStartVnode.elm,
nodeOps.nextSibling(oldEndVnode.elm)
)
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
} else if (sameVnode(oldEndVnode, newStartVnode)) {
// Vnode moved left
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
canMove &&
nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
if (isUndef(oldKeyToIdx))
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// New element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldCh[idxInOld] = undefined
canMove &&
nodeOps.insertBefore(
parentElm,
vnodeToMove.elm,
oldStartVnode.elm
)
} else {
// same key but different element. treat as new element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
if (oldStartIdx > oldEndIdx) {
refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
addVnodes(
parentElm,
refElm,
newCh,
newStartIdx,
newEndIdx,
insertedVnodeQueue
)
} else if (newStartIdx > newEndIdx) {
removeVnodes(oldCh, oldStartIdx, oldEndIdx)
}
}
vue3的快速Diff算法
假设有新旧两组vnode如下
快速 diff 算法有个预处理的步骤，会将前面和后面相同部分先计算出来。
例如上面的例子
可以发现旧节点组前面的节点是key为1的p元素，新节点组前面的节点也是key为1的p元素，新旧节点组前面的节点是一样，旧节点组后面的节点是key为2和可以key为3的p元素，新节点组也是一样，由于他们在新旧两组节点中的相对位置不变，所以无需移动他们，但是仍然要进行打补丁更新。
那么，怎么通过代码把前后相同的节点找出来呢，我们可以定义一个索引 j，初始值为0，是起始节点的索引，指向新旧两组节点的头部，再定义另外两个索引oldEnd 和 newEnd 指向新旧两组节点的尾部。开启while循环，遍历比对节点key值。
function diff(oldV, newV){
const oldVnodeChildren = oldV.children;
const newVnodeChildren = newV.children;
let j = 0;
let oldVnode = oldVnodeChildren[j]
let newVnode = newVnodeChildren[j]
while(oldVnode.key === newVnode.key){
// 省略代码，这里执行 oldVnode 和 newVnode 的打补丁更新操作
j++
oldVnode = oldVnodeChildren[j]
newVnode = newVnodeChildren[j]
}
let oldEnd = oldVnodeChildren.length - 1
let newEnd = newVnodeChildren.length - 1
oldVnode = oldVnodeChildren[oldEnd]
newVnode = newVnodeChildren[newEnd]
while(oldVnode.key === newVnode.key){
// 省略代码，这里执行 oldVnode 和 newVnode 的打补丁更新操作
oldEnd--
newEnd--
oldVnode = oldVnodeChildren[oldEnd]
newVnode = newVnodeChildren[newEnd]
}
}
执行后，结果如下
可以发现，这时候j>oldEnd，所以旧的子节点已经处理完毕了，而新的子节点中，key为4的p元素还没处理，很明显它是一个新增节点，可以发现， 在旧的子节点已经全部处理完毕的前提下，这时候 newEnd >= j 的话，j 到 newEnd 的节点都是新增节点。都需要依次挂载，以newEnd+1索引的节点对应的真实dom为锚点，依次通过insertBefore挂载到该锚点的前面。
function diff(oldV, newV){
const oldVnodeChildren = oldV.children;
const newVnodeChildren = newV.children;
// 省略部分代码
if(j>oldEnd && j<=newEnd){
const anchorIndex = newEnd + 1
const anchor = anchorIndex < newVnodeChildren.length ? newVnodeChildren[anchorIndex].el : null
while(j<=newEnd){
// 省略代码, 这里执行元素创建挂载操作，将 newVnodeChildren[j] 对应的dom挂载到 newVnodeChildren[anchorIndex] 对应的dom前面
j++
}
}
}
另一种情况，如果是下图的情况
执行前后循环比对后如下
可以发现，这时候j>newEnd，所以新的子节点已经处理完毕了，而旧的子节点中，key为2的p元素还没处理，很明显它需要卸载，可以发现， 在新的子节点已经全部处理完毕的前提下，这时候 oldEnd >= j 的话，j 到 oldEnd 的节点都需要卸载。
function diff(oldV, newV){
const oldVnodeChildren = oldV.children;
const newVnodeChildren = newV.children;
// 省略代码
if(j>oldEnd && j<=newEnd){
// 省略代码
}else if(j > newEnd && j <= oldEnd){
while(j <= oldEnd){
// 省略代码，这里执行 oldVnodeChildren[j] 的卸载操作
j++
}
}
}
上面两种情况都是在前后节点处理完后，新旧两组节点中总有一组子节点全部被处理完毕。但更多的情况，是前后节点处理完毕后，新旧两组节点都没有全部处理完毕。
例如上面这种情况，前后节点处理完之后如下
可见，在前后节点处理完之后，即不满足j>oldEnd && j<=newEnd也不满足j > newEnd && j <= oldEnd
我们可以构造一个数组，该数组的长度等于新子节点组经过预处理后剩余未处理节点的数量，可以给该数组每个元素的初始值设为-1，其实这个数组的每一项是用来存储新子节点组中的节点在旧子节点中的索引。
function diff(oldV, newV) {
const oldVnodeChildren = oldV.children;
const newVnodeChildren = newV.children;
let oldVnode = oldVnodeChildren[j];
let newVnode = newVnodeChildren[j];
// 省略代码, 前置处理
if (j > oldEnd && j <= newEnd) {
// 省略代码
} else if (j > newEnd && j <= oldEnd) {
// 省略代码
} else {
const count = newEnd - j + 1;
const source = new Array(count);
source.fill(-1);
const oldStart = j;
const newStart = j;
const keyIndex = {};
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newVnodeChildren[i].key] = i
}
let patched = 0;
for (let i = oldStart; i <= oldEnd; i++) {
oldVnode = oldVnodeChildren[i];
// 已经更新过的节点数量应该小于新子节点组中需要更新的节点数量
if (patched <= count) {
const k = keyIndex[oldVnodeChildren[i].key];
if (typeof k !== "undefined") {
newVnode = newVnodeChildren[k];
// 由于找到了相同key值的两个节点，所以这里执行两个节点的更新操作
// 省略代码，这里执行oldVnode和newVnode的更新打补丁操作
patched++
// 因为source的长度小于或等于newVnodeChildren的长度，所以这里需要k - newStart
source[k - newStart] = i;
} else {
// 如果没找到，说明该就就节点需要卸载
// 省略代码，这里执行oldVnode卸载操作
}
} else {
// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
// 省略代码，这里执行oldVnode卸载操作
}
}
}
}
执行之后，source为[2,3,1,-1]
如何判断节点需要移动呢，和前面的类似，在遍历旧的子节点组时，如果该旧子节点对应的新子节点的索引是逐步递增的，则不需要移动，反之，则需要移动。所以可以新建一个变量，存储在遍历旧的子节点组时，遇到的对应的新子节点的最大索引值。
function diff(oldV, newV) {
const oldVnodeChildren = oldV.children;
const newVnodeChildren = newV.children;
let oldVnode = oldVnodeChildren[j];
let newVnode = newVnodeChildren[j];
// 省略代码, 前置处理
if (j > oldEnd && j <= newEnd) {
// 省略代码
} else if (j > newEnd && j <= oldEnd) {
// 省略代码
} else {
const count = newEnd - j + 1;
const source = new Array(count);
source.fill(-1);
const oldStart = j;
const newStart = j;
let moved = false; // 标记是否有需要移动的节点
let pos = 0; // 存储遍历旧的子节点时遇到的对应key值相同的新子节点的索引值的最大值
const keyIndex = {};
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newVnodeChildren[i].key] = i
}
let patched = 0;
for (let i = oldStart; i <= oldEnd; i++) {
oldVnode = oldVnodeChildren[i];
// 已经更新过的节点数量应该小于新子节点组中需要更新的节点数量
if (patched <= count) {
const k = keyIndex[oldVnodeChildren[i].key];
if (typeof k !== "undefined") {
newVnode = newVnodeChildren[k];
// 由于找到了相同key值的两个节点，所以这里执行两个节点的更新操作
// 省略代码，这里执行oldVnode和newVnode的更新打补丁操作
patched++
// 因为source的长度小于或等于newVnodeChildren的长度，所以这里需要k - newStart
source[k - newStart] = i;
// 判断节点是否需要移动
if (k < pos) {
moved = true;
} else {
pos = k;
}
} else {
// 如果没找到，说明该就就节点需要卸载
// 省略代码，这里执行oldVnode卸载操作
}
} else {
// 如果更新过的节点数量大于需要更新的节点数量，则卸载多余的节点
// 省略代码，这里执行oldVnode卸载操作
}
}
}
}
那么，如何移动呢，如何找出最优的移动方案呢
我们需要根据前面计算出的source数组计算出它的最大递增子序列，前面source为[2,3,1,-1]，其最大递增子序列为[2,3]，[2,3]对应的新子节点组的索引为[0,1]，代表新子节点组中索引为0和索引为1的节点不需要移动。
关于如何计算最大递增子序列，本文篇幅有限，暂不做讨论，可查阅相关算法
再需要创建两个索引值i和s，i指向新的子节点组的最后一个节点，s指向最长递增子序列的最后一个元素
if (j > oldEnd && j <= newEnd) {
// 省略代码
} else if (j > newEnd && j <= oldEnd) {
// 省略代码
} else {
// 省略代码
for (let i = oldStart; i <= oldEnd; i++) {
// 省略代码
}
if (moved) {
const seq = lis(source); // lis函数得出source的最大递增子序列所对应的索引数组
let s = seq.length - 1;
let i = count - 1;
for (i; i >= 0; i--) {
if (source[i] === -1) {
// source[i] === -1 代表该节点是新增节点，需要将其挂载
const pos = i + newStart;
const newVNode = newVnodeChildren[pos];
const nextPos = pos + 1;
const anchor =
nextPos < newVnodeChildren.length
? newVnodeChildren[nextPos].el
: null;
// 省略代码，这里执行newVNode的挂载操作，创建其元素并将其挂载到anchor前面
} else if (i !== seq[s]) {
// i !== seq[s]时，说明该节点需要移动
const pos = i + newStart;
const newVNode = newVnodeChildren[pos];
const nextPos = pos + 1;
const anchor =
nextPos < newVnodeChildren.length
? newVnodeChildren[nextPos].el
: null;
// 省略代码，这里DOM移动操作，通过（insertBefore）将newVNode的真实dom移动到anchor对应的真实dom前面
} else {
// i === seq[s]时，说明该节点不需要移动
s--; // s指向下一个位置
}
}
}
}
至此，vue3的快速Diff算法大致就是这样，这里再贴一下vue3关于这块的源码。
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
namespace: ElementNamespace,
slotScopeIds: string[] | null,
optimized: boolean,
) => {
let i = 0
const l2 = c2.length
let e1 = c1.length - 1 // prev ending index
let e2 = l2 - 1 // next ending index
// 1. sync from start
// (a b) c
// (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
namespace,
slotScopeIds,
optimized,
)
} else {
break
}
i++
}
// 2. sync from end
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
namespace,
slotScopeIds,
optimized,
)
} else {
break
}
e1--
e2--
}
// 3. common sequence + mount
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
namespace,
slotScopeIds,
optimized,
)
i++
}
}
}
// 4. common sequence + unmount
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [e d c h] f g
// i = 2, e1 = 4, e2 = 5
else {
const s1 = i // prev starting index
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map()
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if (nextChild.key != null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`,
JSON.stringify(nextChild.key),
`Make sure keys are unique.`,
)
}
keyToNewIndexMap.set(nextChild.key, i)
}
}
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
// used to track whether any node has moved
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if (prevChild.key != null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break
}
}
}
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
namespace,
slotScopeIds,
optimized,
)
patched++
}
}
// 5.3 move and mount
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
namespace,
slotScopeIds,
optimized,
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
}
}
原文链接：https://juejin.cn/post/7352322041850462234 作者：kaaaaaaai
