diff 算法处理新旧节点是同一个节点时
本文讨论的是当新旧节点是同一个节点时，也就是节点的 sel 属性和 key 属性相等时，diff 算法更新节点的策略。
先给出程序流程图
1.新旧节点其中一个节点存在 text 属性
节点的 text 属性中有值也就意味着 children 属性为 undefined，在所有的情况中新旧节点同时存在 children 属性是最复杂的，所以这里先实现其他的情况。
patchVnode.js
该函数的功能是对比新旧节点，更新旧节点。当新旧节点同时存在 children 属性调用 updateChildren 函数实现最小化更新。
import createElement from "./createElement";
import updateChildren from './updateChildren.js';
// 对比同一个虚拟节点
export default function patchVnode(oldVnode, newVnode) {
// 判断新旧vnode是否是同一个对象
if (oldVnode === newVnode) return;
// 判断新vnode有没有text属性
if (newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length == 0)) {
// 新vnode有text属性
console.log('新vnode有text属性');
if (newVnode.text != oldVnode.text) {
// 如果新虚拟节点中的text和老的虚拟节点的text不同，那么直接让新的text写入老的elm中即可。如果老的elm中是children，那么也会立即消失掉。
oldVnode.elm.innerText = newVnode.text;
}
} else {
// 新vnode没有text属性，有children
console.log('新vnode没有text属性');
// 判断老的有没有children
if (oldVnode.children != undefined && oldVnode.children.length > 0) {
// 老的有children，新的也有children，此时就是最复杂的情况。
updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
} else {
// 老的没有children，新的有children
// 清空老的节点的内容
oldVnode.elm.innerHTML = '';
// 遍历新的vnode的子节点，创建DOM，上树
for (let i = 0; i < newVnode.children.length; i++) {
let dom = createElement(newVnode.children[i]);
oldVnode.elm.appendChild(dom);
}
}
}
}
2.新旧节点同时存在 children 属性
diff 算法处理新旧节点同时存在 children 属性时的更新策略是该算法的精华。
diff 算法使用了 4 个指针分别指向新节点的头和尾，旧节点的头和尾。diff 算法给出的对比策略能够在 O(n)的线性时间复杂度内找出新旧节点的差异并实现旧节点的更新。并且在对比结束后可以根据指针得到要新增加或是删除的节点。
它是如何进行对比新旧节点的差异的呢？首先它会查找旧节点中是否存在与新节点相同的节点（也就是 sel 和 key 属性相同），它的查找策略是这样的。
四种命中查找：
- 新前与旧前
- 新后与旧后
- 新后与旧前（此种情况发生了，涉及移动节点，那么新后指向的节点，移动到旧后之后）
- 新前与旧后（此种情况发生了，涉及移动节点，那么新前指向的节点，移动到旧前之前）
如果这 4 种情况都没有命中，则会在哈希表中进行查找，哈希表中存储的是旧节点 key->index(数组下标)的映射。我们知道在哈希表中查找元素的时间复杂度是 O(1)，引入哈希表的目的就在于提高查找效率。如果还是没有找到相同节点，则说明该节点是新增的节点，将该节点插入。
循环语句是while(新前 <= 新后 && 旧前 <= 就后){}，所以当循环结束后要么是新节点先遍历完，旧节点中还有剩余节点未遍历，说明这些节点是要删除的节点。要么是旧节点先遍历完，新节点中还有剩余节点未遍历，说明这些节点是要新增的节点。还有一种情况是都遍历完了，则不用处理。
注意：因为最终的渲染结果都要以 newVDOM 为准，所以移动和插入节点的位置都是根据 newVnode 中节点的位置进行的。移动、插入和删除节点都是对旧的真实 DOM 进行操作的。虚拟 DOM 的 elm 属性是连接虚拟 DOM 和真实 DOM 的桥梁。
下面是 diff 算法的子节点更新策略的函数实现
updateChildren.js
import patchVnode from './patchVnode.js';
import createElement from './createElement.js';
// 判断是否是同一个虚拟节点
function checkSameVnode(a, b) {
return a.sel == b.sel && a.key == b.key;
};
export default function updateChildren(parentElm, oldCh, newCh) {
console.log('我是updateChildren');
console.log(oldCh, newCh);
// 旧前
let oldStartIdx = 0;
// 新前
let newStartIdx = 0;
// 旧后
let oldEndIdx = oldCh.length - 1;
// 新后
let newEndIdx = newCh.length - 1;
// 旧前节点
let oldStartVnode = oldCh[0];
// 旧后节点
let oldEndVnode = oldCh[oldEndIdx];
// 新前节点
let newStartVnode = newCh[0];
// 新后节点
let newEndVnode = newCh[newEndIdx];
let keyMap = null;
// 开始大while了
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
console.log('★');
// 首先不是判断①②③④命中，而是要略过已经加undefined标记的东西
if (oldStartVnode == null || oldCh[oldStartIdx] == undefined) {
oldStartVnode = oldCh[++oldStartIdx];
} else if (oldEndVnode == null || oldCh[oldEndIdx] == undefined) {
oldEndVnode = oldCh[--oldEndIdx];
} else if (newStartVnode == null || newCh[newStartIdx] == undefined) {
newStartVnode = newCh[++newStartIdx];
} else if (newEndVnode == null || newCh[newEndIdx] == undefined) {
newEndVnode = newCh[--newEndIdx];
} else if (checkSameVnode(oldStartVnode, newStartVnode)) {
// 新前和旧前
console.log('①新前和旧前命中');
patchVnode(oldStartVnode, newStartVnode);
oldStartVnode = oldCh[++oldStartIdx];
newStartVnode = newCh[++newStartIdx];
} else if (checkSameVnode(oldEndVnode, newEndVnode)) {
// 新后和旧后
console.log('②新后和旧后命中');
patchVnode(oldEndVnode, newEndVnode);
oldEndVnode = oldCh[--oldEndIdx];
newEndVnode = newCh[--newEndIdx];
} else if (checkSameVnode(oldStartVnode, newEndVnode)) {
// 新后和旧前
console.log('③新后和旧前命中');
patchVnode(oldStartVnode, newEndVnode);
// 当③新后与旧前命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧后的后面
// 如何移动节点？？只要你插入一个已经在DOM树上的节点，它就会被移动
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
} else if (checkSameVnode(oldEndVnode, newStartVnode)) {
// 新前和旧后
console.log('④新前和旧后命中');
patchVnode(oldEndVnode, newStartVnode);
// 当④新前和旧后命中的时候，此时要移动节点。移动新前指向的这个节点到老节点的旧前的前面
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);
// 如何移动节点？？只要你插入一个已经在DOM树上的节点，它就会被移动
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
// 四种命中都没有命中
// 制作keyMap一个映射对象，这样就不用每次都遍历老对象了。
if (!keyMap) {
keyMap = {};
// 从oldStartIdx开始，到oldEndIdx结束，创建keyMap映射对象
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
const key = oldCh[i].key;
if (key != undefined) {
keyMap[key] = i;
}
}
}
console.log(keyMap);
// 寻找当前这项（newStartIdx）这项在keyMap中的映射的位置序号
const idxInOld = keyMap[newStartVnode.key];
console.log(idxInOld);
if (idxInOld == undefined) {
// 判断，如果idxInOld是undefined表示它是全新的项
// 被加入的项（就是newStartVnode这项)现不是真正的DOM节点
parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
} else {
// 如果不是undefined，不是全新的项，而是要移动
const elmToMove = oldCh[idxInOld];
patchVnode(elmToMove, newStartVnode);
// 把这项设置为undefined，表示我已经处理完这项了
oldCh[idxInOld] = undefined;
// 移动，调用insertBefore也可以实现移动。
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
}
// 指针下移，只移动新的头
newStartVnode = newCh[++newStartIdx];
}
}
// 继续看看有没有剩余的。循环结束了start还是比old小
if (newStartIdx <= newEndIdx) {
console.log('new还有剩余节点没有处理，要加项。要把所有剩余的节点，都要插入到oldStartIdx之前');
// 遍历新的newCh，添加到老的没有处理的之前
for (let i = newStartIdx; i <= newEndIdx; i++) {
// insertBefore方法可以自动识别null，如果是null就会自动排到队尾去。和appendChild是一致了。
// newCh[i]现在还没有真正的DOM，所以要调用createElement()函数变为DOM
parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
}
} else if (oldStartIdx <= oldEndIdx) {
console.log('old还有剩余节点没有处理，要删除项');
// 批量删除oldStart和oldEnd指针之间的项
for (let i = oldStartIdx; i <= oldEndIdx; i++) {
if (oldCh[i]) {
parentElm.removeChild(oldCh[i].elm);
}
}
}
};
总结：Diff 算法是一种对比算法。该算法能够在线性的时间复杂度内找出旧虚拟 DOM 和新虚拟 DOM 的差异，对比出是哪个虚拟节点更改了，只更新这个虚拟节点所对应的真实节点，而不影响其他没发生变化的节点，提高 DOM 的复用，实现真实 DOM 的最小量更新，进而提高渲染效率。
本文主要介绍了虚拟 dom 和 diff 算法相关的 patchVnode 函数、updateChildren 函数并进行了简单实现，处理的是新旧节点是同一个节点的情况。函数的实现并非官方源码，只对大体的逻辑流程进行了代码实现，而忽略了很多细节问题，仅可作学习使用。
