关注公众号“执鸢者”，回复“材料”获取500G材料（各“兵种”均有），还有业余交换群等你一起来洒脱。（哈哈）
不论是Vue还是React，其为了比拟虚构DOM节点的变动，实现最小量更新，均利用了diff算法，本文就与老铁们一起来看看diff算法。
一、根底
Diff算法实现的是最小量更新虚构DOM。这句话尽管简短，然而波及到了两个外围因素：虚构DOM、最小量更新。
- 虚构DOM
虚构DOM指的就是将实在的DOM树结构为js对象的模式，从而解决浏览器操作实在DOM的性能问题。
例如：如下DOM与虚构DOM之间的映射关系
- 最小量更新
Diff的用处就是在新老虚构DOM之间找到最小更新的局部，从而将该局部对应的DOM进行更新。
二、整个流程
Diff算法真的很美，整个流程如下图所示：
一、 首先比拟一下新旧节点是不是同一个节点（可通过比拟sel（选择器）和key（惟一标识）值是不是雷同），不是同一个节点则进行暴力删除（注：先以旧节点为基准插入新节点，而后再删除旧节点）。<br/>
二、 若是同一个节点则须要进一步比拟<br/>
- 完全相同，不做解决<br/>
- 新节点内容为文本，间接替换完事<br/>
- 新节点有子节点，这个时候就要认真考虑一下了:若老节点没有子元素，则间接清空老节点，将新节点的子元素插入即可；若老节点有子元素则就须要依照上述的更新策略老搞定了（记住更新策略，又能够吹好几年了，666666）。<br/>
三、实战
光说不练假把式，上面开搞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);
}
}
}
}参考文献
本文是笔者看了邵山欢老师的视频后做的一次总结，邵老师讲的真心很好，爆赞。
1.如果感觉这篇文章还不错，来个分享、点赞吧，让更多的人也看到
2.关注公众号执鸢者，支付学习材料（前端“多兵种”材料），定期为你推送原创深度好文
发表回复