关于前端:一文搞定Diff算法

11次阅读

共计 5472 个字符，预计需要花费 14 分钟才能阅读完成。

关注公众号“执鸢者”，回复“材料”获取 500G 材料（各“兵种”均有），还有业余交换群等你一起来洒脱。（哈哈）

不论是 Vue 还是 React，其为了比拟虚构 DOM 节点的变动，实现最小量更新，均利用了 diff 算法，本文就与老铁们一起来看看 diff 算法。

Diff 算法实现的是最小量更新虚构 DOM。这句话尽管简短，然而波及到了两个外围因素：虚构 DOM、最小量更新。

虚构 DOM

虚构 DOM 指的就是将实在的 DOM 树结构为 js 对象的模式，从而解决浏览器操作实在 DOM 的性能问题。

例如：如下 DOM 与虚构 DOM 之间的映射关系

最小量更新

Diff 的用处就是在新老虚构 DOM 之间找到最小更新的局部，从而将该局部对应的 DOM 进行更新。

Diff 算法真的很美，整个流程如下图所示：

一、首先比拟一下新旧节点是不是同一个节点（可通过比拟 sel（选择器）和 key（惟一标识）值是不是雷同），不是同一个节点则进行暴力删除（注：先以旧节点为基准插入新节点，而后再删除旧节点）。

二、若是同一个节点则须要进一步比拟

完全相同，不做解决
新节点内容为文本，间接替换完事
新节点有子节点，这个时候就要认真考虑一下了: 若老节点没有子元素，则间接清空老节点，将新节点的子元素插入即可；若老节点有子元素则就须要依照上述的更新策略老搞定了（记住更新策略，又能够吹好几年了，666666）。

光说不练假把式，上面开搞 diff 算法的核心内容。

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);
    }
}

该函数次要负责精细化比拟，通过依照上述流程图中的逻辑顺次判断属于哪一个分支，从而采取不同的解决逻辑。（思路清晰，算法太牛了）

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);
            }
        }
    }
}

外围函数，次要负责旧虚构节点和新虚构节点均存在子元素的状况，依照比拟策略顺次进行比拟，最终找出子元素中变动的局部，实现最小更新。对于该局部，波及到一些指针，如下所示：

旧前指的就是更新前虚构 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);
            }
        }
    }
}