likes
comments
collection
share

认识一下Diff算法

作者站长头像
站长
· 阅读数 18

Diff算法是什么？

通过比对找出虚拟DOM树发生变更的地方，实现最小量更新

Ps：虚拟DOM是一个用来描述真实DOM的JavaScript对象

为什么会有Diff算法？

在复杂视图情况下可以提升渲染性能

稍具体来说如果直接对DOM节点进行大量增删改会触发样式计算、布局、绘制、栅格化、合成等任务（整个过程为重排），除此之外还会触发重绘或者合成操作，在复杂页面中重排和重绘非常消耗资源和时间，而使用虚拟DOM的话会先将页面改变的内容应用到虚拟DOM，而且不会立马渲染页面，而是调整虚拟DOM的状态，待收集到足够的变化时，再一次性应用到真实DOM，在复杂视图情况下可以提升渲染性能，减少DOM的操作（重绘重排）

Diff算法是如何实现的？

（Snabbdom优化后的Diff算法）

认识一下Diff算法

Diff的对象是虚拟DOM（virtual dom），Diff算法结果为真实DOM

虚拟DOM节点生产厂 —— h( ) 函数

首先需要得到虚拟DOM

通过h()函数可以创建一个JavaScript对象作为虚拟DOM来描述真实DOM树

Ps:h 是hyperscript 的简称——意思是“能生成 HTML (超文本标记语言) 的 JavaScript，可用于创建虚拟节点vnodes

let vnode = h('ul.list', [ 
            h('li','a'),
            h('li','b'), 
            h('li','c'), ]) 
    console.log(vnode)

通过h函数生成的vnodes结构如下图所示：

认识一下Diff算法

虚拟DOM节点(VNode)结构中，sel属性值表示该虚拟节点的标签名，key属性值表示该虚拟节点的唯一键，通过对比两个虚拟节点的key和sel属性是否分别相等来判断是否为同一个虚拟节点,text属性和children属性只有其中一个会存在对应的属性值（意思就是text属性有属性值的时候children属性则为undefined，反之也成立），elm属性则是用来存放该虚拟DOM节点对应的真实DOM节点

虚拟节点加工厂 —— vnode( ) 函数

vnode()函数将得到的虚拟节 点以对象的形式返回

虚拟节点对象鉴定所 —— sameVnode( ) 函数

通过对比两个虚拟节点的key和sel属性是否分别相等来判断是否为同一个虚拟节点对象，返回Boolean值

比较新旧两个虚拟DOM节点对象 —— patch( ) 函数

得到虚拟节点对象后则需要对新旧虚拟节点对象进行比较，判断节点是否有变化 比较流程如下图所示：

认识一下Diff算法

新旧虚拟节点对象精细化比较 —— patchVnode( ) 函数

认识一下Diff算法

新旧虚拟节子节点精细化比较 —— updateChildren( ) 函数⭐

当比较的新旧虚拟节点都存在子节点时，需要判断子节点的差异

子节点之间的比较属于diff算法的精华部分,其中比较过程存在五种情况,执行该过程是一个循环，每次循环里只要执行了五种情况之一，就会结束本次循环

主要需要用到以下变量:

   //旧前虚拟节点指针 (oSI)
    let oldStartIdx = 0;
    //新前虚拟节点指针 (oEI)
    let newStartIdx = 0;
    //旧后虚拟节点指针  (nSI)
    let oldEndIdx = oldCh.length-1;
    //新后虚拟节点指针 (nEI)
    let newEndIdx = newCh.length-1;
    //旧前虚拟节点  
    let oldStartVnode = oldCh[oldStartIdx];
    //旧后虚拟节点 
    let oldEndVnode =oldCh[oldEndIdx];
    //新前虚拟节点
    let newStartVnode = newCh[newStartIdx];
    //新后虚拟节点
    let newEndVnode = newCh[newEndIdx]

  1. oldStartVnode/newStartVnode(旧开始节点/新开始节点)相同

    若符合情况1，从新旧节点的开始节点开始对比，oldCh[oldStartIdx]和newCh[newStartIdx]进行sameVnode判断是否为相同节点(key和sel相同)

    执行patchVnode 函数找出节点之间的差异，更新图，若不存在差异则结束循环，指针后移

  2. oldEndVnode/newEndVnode(旧结束节点/新结束节点)相同

    不符合情况1时会判断情况2，从新旧节点的结束节点开始对比，oldCh[oldEndIdx]和newCh[newEndIdx]进行sameVnode判断是否为相同节点(key和sel相同)

    执行patchVnode 函数找出节点之间的差异，更新图，若不存在差异则结束循环，指针前移

  3. oldStartVnode/newEndVnode(旧开始节点/新结束节点)相同

    情况1，2都不符合时，判断情况3，旧节点的开始节点与新节点的结束节点开始对比，oldCh[oldStratIdx]和startCh[newEndIdx]进行sameVnode 判断是否为相同节点(key和sel相同)

    执行patchVnode 找出节点之间的差异，更新图，若不存在差异则结束本次循环，旧节点的开始节点对应的真实dom（oldCh[oldStartIdx]）位移到结束节点对应的真实dom(oldCh[oldEndIdx])之后

  4. oldEndVnode/newStartVnode(旧结束节点/新开始节点)相同

    当情况1、2、3都不符合时，判断情况4，旧节点的结束节点和新节点的开始节点开始对比，oldCh[oldEndIdx]和startCh[newStartIdx]进行sameVnode 判断是否为相同节点(key和sel相同)

    执行patchVnode 找出节点之间的差异，更新图，若不存在差异则本次结束循环，旧节点的结束节点对应的真实dom（oldCh[oldEndIdx]）位移到开始节点对应的真实dom(oldCh[oldStartIdx])之前

  5. 特殊情况当1,2,3,4的情况都不符合的时候就会执行该情况5

    在oldVnodes里面寻找跟newStartVnode一样的节点然后位移到oldStartVnode 对应节点的真实DOM位移到oldCh[oldStartIdx] 对应的真实dom之前

    若没有找到相同的节点，则创建一个与newCh[newStartIdx] 节点对应的真实DOM插入到oldCh[oldStartIdx]对应的真实DOM前

循环结束收尾工作

直到oldStartIdx>oldEndIdx || newStartIdx>newEndIdx(代表旧节点或者新节点已经遍历完)

当新节点的所有子节点遍历完(newStartIdx > newEndIdx)，循环结束，将旧节点中没有对应相同的子节点删除

当旧节点的所有子节点遍历完(oldStartIdx > oldEndIdx)，循环结束，将新节点中多出来的子节点插入到旧结束节点前

具体判断过程如下图所示:

认识一下Diff算法

总结

视频参考:03-尚硅谷-虚拟DOM和diff算法-虚拟DOM和h函数_哔哩哔哩_bilibili

js代码实现:diff算法 (gitee.com)