一文搞定Diff算法

2021年3月21日 13点热度 0条评论 来源: 执鸢者520

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

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

一、基础

Diff算法实现的是最小量更新虚拟DOM。这句话虽然简短,但是涉及到了两个核心要素:虚拟DOM、最小量更新。

  1. 虚拟DOM

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

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

  1. 最小量更新

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

二、整个流程

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

一、 首先比较一下新旧节点是不是同一个节点(可通过比较sel(选择器)和key(唯一标识)值是不是相同),不是同一个节点则进行暴力删除(注:先以旧节点为基准插入新节点,然后再删除旧节点)。

二、 若是同一个节点则需要进一步比较

  1. 完全相同,不做处理

  2. 新节点内容为文本,直接替换完事

  3. 新节点有子节点,这个时候就要仔细考虑一下了:若老节点没有子元素,则直接清空老节点,将新节点的子元素插入即可;若老节点有子元素则就需要按照上述的更新策略老搞定了(记住更新策略,又可以吹好几年了,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函数

核心函数,主要负责旧虚拟节点和新虚拟节点均存在子元素的情况,按照比较策略依次进行比较,最终找出子元素中变化的部分,实现最小更新。对于该部分,涉及到一些指针,如下所示:

  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.关注公众号执鸢者,领取学习资料,定期为你推送原创深度好文

3.扫描下方添加进群,里面大佬多多,一起向他们学习

1. 图解JavaScript——代码实现(Object.create()、flat()等十四种代码原理实现不香吗?)

2. 图解JavaScript——代码实现【2】(重点是Promise、Async、发布/订阅原理实现)

3. 图解javascript——基础篇

4. 图解JavaScript——进阶篇

5. 十五张图带你彻底搞懂从URL到页面展示发生的故事

6. 图解浏览器安全(同源策略、XSS、CSRF、跨域、HTTPS、安全沙箱等串成糖葫芦)

7. 六张图带你从HTTP/0.9进化到HTTP3.0

8. (2.6w字)网络知识点灵魂拷问(上)——前端面试必问

9. (2.6w字)网络知识点灵魂拷问(下)——前端面试必问

10. 理论与API相结合理解Node中的网络通信

11. 硬核知识点——浏览器中的三类五种请求

12. 理论与实践相结合彻底理解CORS

13. 三步法解析Express源码

14. 一篇搞定前端高频手撕算法题(36道)

15. 十七张图玩转Node进程——榨干它

16. 理论与API相结合理解Node中的网络通信

17. 一文彻底搞懂前端监控

18. 前端的葵花宝典——架构

19. canvas从入门到猪头

20. 前端工程师的一大神器——puppeteer

21. 2021 年前端宝典【超三百篇】

22. 前端也要懂机器学习(上)

23. 前端也要懂机器学习(下)

24. 学架构助力前端起飞

    原文作者:执鸢者520
    原文地址: https://blog.csdn.net/wang_yu_shun/article/details/115059857
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。