乐趣区

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

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

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

一、根底

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

  1. 虚构 DOM

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

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

  1. 最小量更新

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

二、整个流程

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

一、首先比拟一下新旧节点是不是同一个节点(可通过比拟 sel(选择器)和 key(惟一标识)值是不是雷同),不是同一个节点则进行暴力删除(注:先以旧节点为基准插入新节点,而后再删除旧节点)。<br/>

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

  1. 完全相同,不做解决 <br/>
  2. 新节点内容为文本,间接替换完事 <br/>
  3. 新节点有子节点,这个时候就要认真考虑一下了: 若老节点没有子元素,则间接清空老节点,将新节点的子元素插入即可;若老节点有子元素则就须要依照上述的更新策略老搞定了(记住更新策略,又能够吹好几年了,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 函数

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

  1. 旧前指的就是更新前虚构 DOM 中的头部指针
  2. 旧后指的就是更新前虚构 DOM 中的尾部指针
  3. 新前指的就是更新后虚构 DOM 中的头部指针
  4. 新后指的就是更新后虚构 DOM 中的尾部指针

依照上述的更新策略,上述旧虚构 DOM 更新为新虚构 DOM 的流程为:

  1. 命中“新后旧前”策略,而后将信后对应的 DOM 节点(也就是节点 1)挪动到旧后节点(节点 3)前面,而后旧前节点指针下移,新后节点指针上移。
  2. 依然命中“新后旧前”策略,做雷同的操作,将节点 2 挪动到旧后节点(节点 3)前面,下移旧前节点,上移新后节点。
  3. 命中“新前旧前”策略,DOM 节点不变,旧前和新前节点均下移。
  4. 跳出循环,挪动完结。
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. 关注公众号执鸢者,支付学习材料(前端“多兵种”材料),定期为你推送原创深度好文

退出移动版