不管是Vue还是React，其为了比较虚拟DOM节点的变化，实现最小量更新，均利用了diff算法，本文就与老铁们一起来看看diff算法。
一、基础
Diff算法实现的是最小量更新虚拟DOM。这句话虽然简短，但是涉及到了两个核心要素：虚拟DOM、最小量更新。
- 虚拟DOM
虚拟DOM指的就是将真实的DOM树构造为js对象的形式，从而解决浏览器操作真实DOM的性能问题。
例如：如下DOM与虚拟DOM之间的映射关系
- 最小量更新
Diff的用途就是在新老虚拟DOM之间找到最小更新的部分，从而将该部分对应的DOM进行更新。
二、整个流程
Diff算法真的很美，整个流程如下图所示：
一、 首先比较一下新旧节点是不是同一个节点（可通过比较sel（选择器）和key（唯一标识）值是不是相同），不是同一个节点则进行暴力删除（注：先以旧节点为基准插入新节点，然后再删除旧节点）。
二、 若是同一个节点则需要进一步比较
- 完全相同，不做处理
- 新节点内容为文本，直接替换完事
- 新节点有子节点，这个时候就要仔细考虑一下了:若老节点没有子元素，则直接清空老节点，将新节点的子元素插入即可；若老节点有子元素则就需要按照上述的更新策略老搞定了（记住更新策略，又可以吹好几年了，666666）。
三、实战
光说不练假把式，下面直接输出diff算法的核心内容。
3.1 patch函数
Diff算法的入口函数，主要判断新旧节点是不是同一个节点，然后交由不同的逻辑进行处理。
export default function patch(oldVnode, newVnode) { // 判断传入的第一个参数，是DOM节点还是虚拟节点 if (oldVnode.sel === '' || oldVnode.sel === undefined) { // 传入的第一个参数是DOM节点，此时要包装成虚拟节点 oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode); } // 判断oldVnode和newVnode是不是同一个节点 if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) { //是同一个节点，则进行精细化比较 patchVnode(oldVnode, newVnode); } else { // 不是同一个节点，暴力插入新的，删除旧的 let newVnodeElm = createElement(newVnode); // 将新节点插入到老节点之前 if (oldVnode.elm.parentNode && newVnodeElm) { oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm); } // 删除老节点 oldVnode.elm.parentNode.removeChild(oldVnode.elm); } }
3.2 patchVnode函数
该函数主要负责精细化比较，通过按照上述流程图中的逻辑依次判断属于哪一个分支，从而采取不同的处理逻辑。（思路清晰，算法太牛了）
export default function patchVnode(oldVnode, newVnode) { // 判断新旧vnode是否是同一个对象 if (oldVnode === newVnode) { return; } // 判断vnode有没有text属性 if (newVnode.text !== undefined && (newVnode.children === undefined || newVnode.children.length === 0)) { console.log('新vnode有text属性'); if (newVnode.text !== oldVnode.text) { 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); } } } }
3.3 updateChildren函数
核心函数，主要负责旧虚拟节点和新虚拟节点均存在子元素的情况，按照比较策略依次进行比较，最终找出子元素中变化的部分，实现最小更新。对于该部分，涉及到一些指针，如下所示：
- 旧前指的就是更新前虚拟DOM中的头部指针
- 旧后指的就是更新前虚拟DOM中的尾部指针
- 新前指的就是更新后虚拟DOM中的头部指针
- 新后指的就是更新后虚拟DOM中的尾部指针
按照上述的更新策略，上述旧虚拟DOM更新为新虚拟DOM的流程为：
- 命中“新后旧前”策略，然后将信后对应的DOM节点（也就是节点1）移动到旧后节点（节点3）后面，然后旧前节点指针下移，新后节点指针上移。
- 仍然命中“新后旧前”策略，做相同的操作，将节点2移动到旧后节点（节点3）后面，下移旧前节点，上移新后节点。
- 命中“新前旧前”策略，DOM节点不变，旧前和新前节点均下移。
- 跳出循环，移动结束。
export default function updateChildren(parentElm, 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 (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) { // 略过已经加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[--newEndVnode]; } else if (checkSameVnode(oldStartVnode, newEndVnode)) { console.log('新后和旧前命中'); patchVnode(oldStartVnode, newEndVnode); // 当新后与旧前命中的时候，此时要移动节点，移动新后指向的这个节点到老节点旧后的后面 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); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; } else { // 四种都没有命中 // 制作keyMap一个映射对象，这样就不用每次都遍历老对象了 if (!keyMap) { keyMap = {}; for (let i = oldStartIdx; i <= oldEndIdx; i++) { const key = oldCh[i].key; if (key !== undefined) { keyMap[key] = i; } } } // 寻找当前这项（newStartIdx）在keyMap中的映射的位置序号 const idxInOld = keyMap[newStartVnode.key]; if (idxInOld === undefined) { // 如果idxInOld是undefined表示踏实全新的项，此时会将该项创建为DOM节点并插入到旧前之前 parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm); } else { // 如果不是undefined，则不是全新的项，则需要移动 const elmToMove = oldCh[idxInOld]; patchVnode(elmToMove, newStartVnode); // 把这项设置为undefined，表示已经处理完这项了 oldCh[idxInOld] = undefined; // 移动 parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm); } // 指针下移，只移动新的头 newStartVnode = newCh[++newStartIdx]; } } // 循环结束后，处理未处理的项 if (newStartIdx <= newEndIdx) { console.log('new还有剩余节点没有处理，要加项，把所有剩余的节点插入到oldStartIdx之前'); // 遍历新的newCh，添加到老的没有处理的之前 for (let i = newStartIdx; i <= newEndIdx; i++) { // insertBefore方法可以自动识别null，如果是null就会自动排到队尾去 // 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); } } } }
