虚拟DOM与Diff算法

深藏阁楼爱情的钟 2022-12-04 09:10 153阅读 0赞

## 虚拟DOM ##

![fa2492926ca56a5b9b520bc095eef45d.png][]

### 什么是虚拟DOM？ ###

虚拟DOM,也就是我们常说的虚拟节点，是用JS对象来模拟真实DOM中的节点，该对象包含了真实DOM的结构及其属性，用于对比虚拟DOM和真实DOM的差异，从而进行局部渲染来达到优化性能的目的。

真实的元素节点：

<div id="wrap">
        <p class="title">Hello world!</p>
    </div>

VNode：

{
        tag:'div',
        attrs:{
            id:'wrap'
        },
        children:[
            {
                tag:'p',
                text:'Hello world!',
                attrs:{
                    class:'title',
                }
            }
        ]
    }

### 为什么使用虚拟DOM？  ###

起初我们在使用JS/JQuery时，不可避免的会大量操作DOM，而DOM的变化又会引发回流或重绘，从而降低页面渲染性能。那么怎样来减少对DOM的操作呢？此时虚拟DOM应用而生，所以虚拟DOM出现的主要目的就是为了**减少频繁操作DOM而引起回流重绘所引发的性能问题的**！

### 虚拟DOM的作用是什么？ ###

1.  兼容性好。因为Vnode本质是JS对象，所以不管Node还是浏览器环境，都可以操作；
2.  减少了对Dom的操作。页面中的数据和状态变化，都通过Vnode对比，只需要在比对完之后更新DOM，不需要频繁操作，提高了页面性能；

### 虚拟DOM和真实DOM的区别？ ###

说到这里，那么虚拟DOM和真实DOM的区别是什么呢？总结大概如下：

*  虚拟DOM减少了重绘和重排；
 *  真实DOM在频繁操作时引发的重绘和重排导致性能很低；
 *  虚拟DOM频繁修改，然后一次性对比差异并修改真实DOM，最后进行依次重绘和重排，减少了真实DOM中多次重绘和重排引起的性能损耗；
 *  虚拟DOM有效降低大面积的重绘和重排，因为是和真实DOM对比，更新差异部分，所以只渲染局部；

总损耗 = 真实DOM增删改 + (多节点)回流/重绘;    //计算使用真实DOM的损耗
    总损耗 = 虚拟DOM增删改 + (diff对比)真实DOM差异化增删改 + (较少节点)回流/重绘;   //计算使用虚拟DOM的损耗

可以发现，都是围绕频繁操作真实DOM引起重绘和重排，导致页面性能损耗来说的。不过框架也不一定非要使用虚拟DOM，关键在于看是否频繁操作会引起大面积的DOM操作。

那么虚拟DOM究竟通过什么方式来减少了页面中频繁操作DOM呢？这就不得不去了解DOM Diff算法了。

## DIFF算法 ##

### 传统diff ###

![format_png][]

计算两颗树形结构差异并进行转换，传统diff算法是这样做的：循环递归每一个节点

比如左侧树a节点依次进行如下对比，左侧树节点b、c、d、e亦是与右侧树每个节点对比

> a->e、a->d、a->b、a->c、a->a

### 传统diff的时间复杂度 ###

将两颗树中所有的节点一一对比需要**O(n²)**的复杂度，在对比过程中发现旧节点在新的树中未找到，那么就需要把旧节点删除，删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是**O(n³)**

###  vue的diff ###

当数据变化时，vue如何来更新视图的？其实很简单，一开始会根据真实DOM生成虚拟DOM，当虚拟DOM某个节点的数据改变后会生成一个新的Vnode，然后VNode和oldVnode对比，把不同的地方修改在真实DOM上，最后再使得oldVnode的值为Vnode。

> diff过程就是调用patch函数，比较新老节点，一边比较一边给真实DOM打补丁(patch)；

对照vue源码来解析一下，贴出核心代码

### patch ###

那么patch是怎样打补丁的？

//patch函数  oldVnode:老节点   vnode:新节点
    function patch (oldVnode, vnode) {
        ...
        if (sameVnode(oldVnode, vnode)) {
            patchVnode(oldVnode, vnode)    //如果新老节点是同一节点,那么进一步通过patchVnode来比较子节点
        } else {
            /* -----否则新节点直接替换老节点----- */
            const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
            let parentEle = api.parentNode(oEl)  // 父元素
            createEle(vnode)  // 根据Vnode生成新元素
            if (parentEle !== null) {
                api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
                api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
                oldVnode = null
            }
        }
        ...
        return vnode
    }
    
    //判断两节点是否为同一节点
    function sameVnode (a, b) {
        return (
            a.key === b.key &&  // key值
            a.tag === b.tag &&  // 标签名
            a.isComment === b.isComment &&  // 是否为注释节点
            // 是否都定义了data，data包含一些具体信息，例如onclick , style
            isDef(a.data) === isDef(b.data) &&  
            sameInputType(a, b) // 当标签是<input>的时候，type必须相同
        )
    }

从上面可以看出，patch函数是通过判断新老节点是否为同一节点：

*  如果是同一节点，执行patchVnode进行子节点比较；
 *  如果不是同一节点，新节点直接替换老节点；

那如果不是同一节点，但是它们子节点一样怎么办嘞？OMG，要牢记：**diff是同层比较，不存在跨级比较的**！简单提一嘴，React中也是如此，它们只是针对同一层的节点进行比较。

### patchVnode ###

既然到了patchVnode方法，说明新老节点为同一节点，那么这个方法做了什么处理？

function patchVnode (oldVnode, vnode) {
        const el = vnode.el = oldVnode.el           //找到对应的真实DOM
        let i, oldCh = oldVnode.children, ch = vnode.children     
        if (oldVnode === vnode) return         //如果新老节点相同,直接返回
        if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
            //如果新老节点都有文本节点且不相等,那么新节点的文本节点替换老节点的文本节点
            api.setTextContent(el, vnode.text)  
        }else {
            updateEle(el, vnode, oldVnode)
            if (oldCh && ch && oldCh !== ch) {
                //如果新老节点都有子节点,执行updateChildren比较子节点[很重要也很复杂,下面展开介绍]
                updateChildren(el, oldCh, ch)
            }else if (ch){
                //如果新节点有子节点而老节点没有子节点,那么将新节点的子节点添加到老节点上
                createEle(vnode)
            }else if (oldCh){
                //如果新节点没有子节点而老节点有子节点，那么删除老节点的子节点
                api.removeChildren(el)
            }
        }
    }

如果两个节点不一样，直接用新节点替换老节点；

如果两个节点一样，

*   新老节点一样，直接返回；
 *   老节点有子节点，新节点没有：删除老节点的子节点；
 *   老节点没有子节点，新节点有子节点：新节点的子节点直接append到老节点；
 *   都只有文本节点：直接用新节点的文本节点替换老的文本节点；
 *   都有子节点：updateChildren

最复杂的情况也就是新老节点都有子节点，那么updateChildren是如何来处理这一问题的，该方法也是diff算法的核心，下面我们来了解一下！

### updateChildren ###

由于代码太多了，这里先做个概述。updateChildren方法的核心：

1.  提取出新老节点的子节点：新节点子节点ch和老节点子节点oldCh；
2.  ch和oldCh分别设置StartIdx（指向头）和EndIdx（指向尾）变量，它们两两比较（按照sameNode方法），有四种方式来比较。如果4种方式都没有匹配成功，如果设置了key就通过key进行比较，在比较过程中startIdx++，endIdx--，一旦StartIdx > EndIdx表明ch或者oldCh至少有一个已经遍历完成，此时就会结束比较。**当其中两个能匹配上那么真实dom中的相应节点会移到Vnode相应的位置。**

下面结合图来理解：

![format_png 1][]

第一步：

oldStartIdx = A , oldEndIdx = C;
    newStartIdx = A , newEndIdx = D;
    复制代码

此时oldStartIdx和newStarIdx匹配，所以将dom中的A节点放到第一个位置，此时A已经在第一个位置，所以不做处理，此时真实DOM顺序：A B C；

第二步：

oldStartIdx = B , oldEndIdx = C;
    newStartIdx = C , oldEndIdx = D;
    复制代码

![format_png 2][]

此时oldEndIdx和newStartIdx匹配，将原本的C节点移动到A后面，此时真实DOM顺序：A C B；

第三步：

oldStartIdx = C , oldEndIdx = C;
    newStartIdx = B , newEndIdx = D;
    oldStartIdx++,oldEndIdx--;
    oldStartIdx > oldEndIdx
    复制代码

此时遍历结束，oldCh已经遍历完，那么将剩余的ch节点根据自己的index插入到真实DOM中即可，此时真实DOM顺序：A C B D；

所以匹配过程中判断结束有两个条件：

*  oldStartIdx > oldEndIdx表示oldCh先遍历完成，如果ch有剩余节点就根据对应index添加到真实DOM中；
 *  newStartIdx > newEndIdx表示ch先遍历完成，那么就要在真实DOM中将多余节点删除掉；

看下图这个实例，就是新节点先遍历完成删除多余节点：

![format_png 3][]

最后，在这些子节点sameVnode后如果满足条件继续执行patchVnode，层层递归，直到oldVnode和Vnode中所有子节点都比对完成，也就把所有的补丁都打好了，此时更新到视图。

## 总结 ##

最后，用一张图来记忆整个Diff过程，希望你能有所收获！

![format_png 4][]

# #

[fa2492926ca56a5b9b520bc095eef45d.png]: /images/20221123/dfcef01d719d442187435e1aecadd228.png
[format_png]: /images/20221123/5f20d454659a4064a9cdfb19464af909.png
[format_png 1]: /images/20221123/2046e0b0cda54a2282ccb6606ed88440.png
[format_png 2]: /images/20221123/cb84ba21989d4fb883ed78290901267f.png
[format_png 3]: /images/20221123/3e7653452ff7489aa29c4f0fc1185e61.png
[format_png 4]: /images/20221123/d66cd4c3d15f4aee8afbbe68257f6ee9.png