• 技术文章 >web前端 >Vue.js

    聊聊Vue2中的双端diff算法,看看如何更新节点的!

    青灯夜游青灯夜游2022-07-18 19:56:55转载235
    本篇文章带大家了解一下Vue2中的双端diff算法,并聊聊Vue2 是如何更新节点的,希望对大家有所帮助!

    今天我们来聊聊 Vue2 的双端 diff 算法。(学习视频分享:vue视频教程

    为什么要聊呢,最直白的原因就是面试会考,当面试官问你 key 的作用,十有八九都会引到 diff 算法。

    没办法,面试问咱们就只能学,好在也不怎么难,跟着我一起看看吧。

    篇幅原因,本文并不会介绍虚拟 DOM 树是如何生成的,仅讲解在数据更新时,是如何比较两颗虚拟 DOM 树并更新真实 DOM 的,主要实现 Vue2 源码中的 patchVnodeupdateChildren 函数

    预备知识

    diff 算法作用

    聊 diff 算法前得认识一下它是干嘛的。

    我们知道在网页运行中,我们改变一些数据,它们可能会影响到 DOM 树。如何在页面中展示最新的数据呢,最简单的方式就是整棵树推到重建,当然这样会导致大量的浪费,所以 Vue 使用虚拟 DOM 保存页面中 DOM 树的状态,在数据变化后,构建一棵新的虚拟 DOM 树,找到前后两颗树的不同之处,针对性地更新真实 DOM。

    而如何找到两颗树的不同之处,减少 DOM 元素的销毁与重建,就是 diff 算法的作用

    虚拟 DOM

    虚拟 DOM,又称虚拟节点(vnode),简单来说就是包含 DOM 元素信息的对象,一般由 h 函数创建,下面这个对象就可以看成是一个虚拟节点

    const vnode = {
        tag: 'div', // 标签类型
        text: '', // 文本内容
        children: undefined, // 子节点
    }

    对于这段 HTML

    <div>
        <p>a</p>
        <p>b</p>
        <p>c</p>
    </div>

    转换成 vnode 是这样的

    const vnode = {
        tag: 'div', // 标签类型
        text: undefined, // 文本内容
        children: [ // 子节点
            {
                tag: 'p',
                text: 'a',
                children: undefined,
            },
            {
                tag: 'p',
                text: 'b',
                children: undefined,
            },
            {
                tag: 'p',
                text: 'c',
                children: undefined,
            },
        ],
    }

    因为我们需要通过虚拟节点去操作真实 DOM,所以 vnode 身上有个 elm 属性指向真实的 DOM 元素。而且在之后的 diff 算法中,还会用到一个 key 来对节点进行唯一标识,所以下文中的 vnode 是这样的对象

    const vnode = {
        tag: 'div', // 标签类型
        text: '', // 文本内容
        children: undefined, // 子节点
        elm: undefined, // 对应的真实DOM
        key: '', // 唯一标识
    }

    Vue 的虚拟节点还有很多属性,不过与 diff 算法无关,就不列举了

    说明一点,虚拟节点的 text 和 children 不会同时有值。在有 children 属性的情况下,text 中的内容会转化为一个文本节点置入 children 数组中

    预备函数

    为了使等会的代码实现更简单,我们准备几个函数,功能不难,直接贴代码了

    我们首先需要就是一个将虚拟节点转换为真实 DOM 的函数

    // 根据虚拟节点创建真实节点
    function createElement(vnode) {
        const dom = document.createElement(vnode.tag)
        if (vnode.children) {
            // 包含子节点,递归创建
            for (let i = 0; i < vnode.children.length; i++) {
                const childDom = createElement(vnode.children[i])
                dom.appendChild(childDom)
            }
        } else {
            // 内部是文字
            dom.innerHTML = vnode.text
        }
        // 补充elm属性
        vnode.elm = dom
        return dom
    }

    以及三个工具函数

    // 判断是否未定义
    function isUndef(v) {
        return v === undefined || v === null
    }
    // 判断是否已定义
    function isDef(v) {
        return v !== undefined && v !== null
    }
    // 检查是否可复用
    function checkSameVnode(a, b) {
        return a.tag === b.tag && a.key === b.key
    }

    patchVnode

    当数据更新后,Vue 创建出一棵新 vnode,然后执行 patchVnode 函数比较新老两个虚拟节点的不同之处,然后根据情况进行处理

    function patchVnode(newVnode, oldVnode) {}

    首先判断新旧两个虚拟节点是同一对象,如果是的话就不用处理

    if (oldVnode === newVnode) return

    然后将旧节点的 DOM 元素赋给新节点,并获取新旧节点的 children 属性

    let elm = (newVnode.elm = oldVnode.elm)
    let oldCh = oldVnode.children
    let newCh = newVnode.children

    这里可以直接赋值是因为调用 patchVnode 的新旧节点它们的 tag 与 key 是一定相同的,在下文会有讲解

    然后根据两个节点内容,决定如何更新 DOM

    1、新旧两个节点内容都是文本。修改文本即可

    if (isUndef(oldCh) && isUndef(newCh)) {
        if (newVnode.text !== oldVnode.text) {
            elm.innerText = newVnode.text
        }
    }

    2、旧节点有子节点,新节点内容是文本。清空旧节点内容,改为文本

    if (isDef(oldCh) && isUndef(newCh)) {
        elm.innerHTML = newVnode.text
    }

    3、旧节点内容是文本,新节点有子节点。清空旧节点内容,遍历新节点生成子 DOM 元素插入节点中

    if (isUndef(oldCh) && isDef(newCh)) {
        elm.innerHTML = ''
        for (let i = 0, n = newCh.length; i < n; i++){
            elm.appendChild(createElement(newCh[i]))
        }
    }

    4、新旧节点都有子节点。调用 updateChildren 来处理,该函数在下一章讲解

    if (isDef(oldCh) && isDef(newCh)) {
        updateChildren(elm, oldCh, newCh)
    }

    情况 4 可以与情况 3 的处理一样,清空旧节点,然后遍历生成新 DOM。但是我们要知道,创建 DOM 元素是一件非常耗时的工作,而且新旧子节点在大多时候都是相同的,如果可以复用,将极大优化我们的性能。

    那我们要如何判定一个节点是否可以复用呢?

    这就需要 Vue 的使用者来帮忙了,使用者在节点上定义 key 属性,告诉 Vue 哪些节点可以复用

    只要标签类型与 key 值都相等,就说明当前元素可以被复用

    然而在我们的项目中,一般只有在 v-for 中才设置 key,其他节点都没设置 key

    其实没有设置 key 的节点,它们的 key 值默认相等

    事实也是如此,我们项目中大部分元素都可以复用,只有 v-for 生成的子元素,它依赖的数组可能发生一些较复杂的变化,所以才需要明确标注 key 值,以帮助 Vue 尽可能地复用节点。

    patchVnode 的内容当然不止这些,还有样式、类名、props等数据的对比更换,篇幅原因本文将其省略了。

    updateChildren

    为什么采用双端 diff

    好了,Vue 的使用者为每个节点的设置了 key,我们要如何从老节点中找到 key 相等的节点复用元素呢?

    简单的方式就是穷举遍历,对于每个新节点的 key 遍历所有老节点,找到了就移动到首位,没找到就创建添加。

    然而这明显有优化的空间,Vue 实现这部分功能时借鉴了 snabbdom 的双端 diff 算法,因为此算法将我们平时操作数组常见的 4 种情况抽离了出来,涵盖了我们业务中的大多数场景,将 O(n2) 的时间复杂度降到了 O(n)

    接下来我们来学习这是如何实现的

    函数实现

    函数实现较为复杂,我直接把完整的代码放上来,再带领大家一段段解读

    // 三个参数为:父DOM元素,旧的子节点数组,新的子节点数组
    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 newStartVnode = newCh[0]
        let oldEndVnode = oldCh[oldEndIdx]
        let newEndVnode = newCh[newEndIdx]
    
        let keyMap
    
        // 开始循环
        while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            // 跳过空节点 (和最后一种情况有关)
            if (isUndef(oldStartVnode)) {
                oldStartVnode = oldCh[++oldStartIdx]
            } else if (isUndef(oldEndVnode)) {
                oldEndVnode = oldCh[--oldEndIdx]
            } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
                // 情况1
                // 旧前和新前相等,不需要移动
                patchVnode(newStartVnode, oldStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
                // 情况2
                // 旧后和新后相等,也不需要移动
                patchVnode(newEndVnode, oldEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
                // 情况3
                // 旧前和新后相等
                // 旧序列的第一个节点,变成了新序列的最后一个节点
                // 需要将这个节点移动到旧序列最后一个节点的后面
                // 也就是最后一个节点的下一个节点的前面
                parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
                patchVnode(newEndVnode, oldStartVnode)
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
            } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
                // 情况4
                // 旧后和新前相等
                // 旧序列的最后一个节点,变成了新序列的第一个节点
                // 需要将这个节点移动到旧序列第一个节点的前面
                parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
                patchVnode(newStartVnode, oldEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            } else {
                // 以上四种情况都不符合
                // 制作旧节点key的映射对象
                // 键为 key,值为 索引
                if (!keyMap) {
                    keyMap = {}
                    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                        keyMap[oldCh[i].key] = i
                    }
                }
                // 寻找当前新节点在keyMap中映射的位置序号
                const idxInOld = keyMap[newStartVnode.key]
                if (isUndef(idxInOld)) {
                    // 没有找到,表示他是全新的项
                    // 转化为DOM节点,加入旧序列第一个节点的前面
                    parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
                } else {
                    // 不是全新的项,需要移动
                    const oldVnode = oldCh[idxInOld]
                    // 移动到旧序列第一个节点之前
                    parentElm.insertBefore(oldVnode.elm, oldStartVnode.elm)
                    patchVnode(oldVnode, newStartVnode)
                    // 把这项设置成空,循环时遇到时跳过
                    oldCh[idxInOld] = undefined
                }
                // 当前新节点处理完毕,下一轮循环处理下一个新节点
                newStartVnode = newCh[++newStartIdx]
            }
        }
    
        // 循环结束了,start还是比end小,说明有节点没有处理到
        if (newStartIdx <= newEndIdx) {
            // 新节点没有处理到,则创建按DOM添加到新序列最后一个节点的前面
            for (let i = newStartIdx; i <= newEndIdx; i++) {
                // insertBefore方法传入null则添加到队尾
                const before = newCh[newEndIdx + 1]?.elm || null
                parentElm.insertBefore(createElement(newCh[i]), before)
            }
        } else if (oldStartIdx <= oldEndIdx) {
            // 旧节点没有处理到,删除
            for (let i = oldStartIdx; i <= oldEndIdx; i++) {
                parentElm.removeChild(oldCh[i].elm)
            }
        }
    }

    代码注释中及下文的新/旧序列,仅包含从新/旧开始索引到结束索引间的节点,也就是还未处理的节点序列,而不是整个子节点数组。

    根据例子讲解

    我们以下图的例子,来讲解这个函数的运行流程(方框中的内容为子节点的 key,所有节点标签相同)

    首先定义了 8 个变量,表示新旧序列的开始和结束位置的索引与节点

    1.png

    然后开始循环,初始时节点都不为空

    第一次循环命中情况 1,旧前与新前(key)相等

    这表示旧序列的第一个节点到新序列仍是第一个节点,也就不需要移动,但还需要比较一下节点的内容有没有改变(patchVnode),并且让新旧开始索引都前进一步

    // 比较节点的数据及子节点,并且将旧节点的DOM赋给新节点
    patchVnode(newStartVnode, oldStartVnode)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]

    2.png

    情况 1 是业务中最常见的,表示从前至后两两比较。一般把商品添加到购物车末尾,或是没有设置 key 值的子节点,都是依靠情况 1 把可复用的节点筛选完毕。

    第二次循环命中情况 2,旧后和新后相等

    这表示序列的末尾节点到新序列仍是末尾节点,也不需要移动,然后让新旧结束索引都后退一步

    patchVnode(newEndVnode, oldEndVnode)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]

    3.png

    情况 2 是情况 1 的补充,表示从后向前两两比较。有时会把新发布的评论插到开头,或者从购物车删除了一些商品,这时仅依靠情况 1 就无法迅速的筛选可复用节点,所以需要从后向前比较来配合。

    第三次循环命中情况 3,旧前和新后相等

    这表示旧序列的第一个节点,变成了新序列的最后一个节点。需要将这个节点移动到序列的末尾,也就是旧序列末尾节点的下一个节点(节点 e)的前面

    parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

    4.png

    然后比较新旧节点,修改索引

    patchVnode(newEndVnode, oldStartVnode)
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]

    5.png

    情况 3 主要处理数组反转的情况,比如升序改降序,每个起始节点被移动到了末尾的位置,使用此情况将它们重新排序。

    第四次循环命中情况 4,旧后与新前相等

    这表示旧序列的最后一个节点,变成了新序列的第一个节点。需要将这个节点移动到序列的开头,也就是旧序列开始节点(节点 c)的前面

    parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)

    6.png

    到这里说一下,图上标注的是节点 a 的后面,是因为节点 b 被移动到了末尾

    节点的移动都是根据旧节点来定位的,如果想把一个节点放到序列的开头,就放到旧序列开始节点的前面;如果想把一个节点放到序列的末尾,就要放到旧序列结束节点的下一个节点的前面

    然后也是比较新旧节点,修改索引,之后是下图情况

    patchVnode(newStartVnode, oldEndVnode)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]

    7.png

    情况 4 是情况 3 的补充,避免反转数组后又插入/删除了节点导致情况 3 无法匹配,本例就是这个情况。

    第五次循环,4 种情况均为未命中

    很遗憾,无法迅速锁定节点的位置,只能用传统的方式进行遍历

    我们这里选择了以空间换时间的方式,定义了 keyMap,将旧序列节点的 key 与索引存起来,然后使用新开始节点的 key 去查找。

    如果没找到,说明这是一个新节点,创建节点并放到开头,也就是插入到旧序列开始节点的前面

    但如果找到了,则同样移动节点到序列开头,然后将对应的旧节点索引置空,在以后循环遇到空的旧节点就跳过了

    本例中是未找到的情况,此节点处理完毕,新开始索引加一,超过了新结束索引,不满足循环条件,退出循环

    8.png

    然而,节点 c 并没有被处理,此时的 DOM 序列为:a,d,f,c,b,e

    所以在循环之后,要检测是否有未处理的节点,如果是旧节点未处理,删除即可;

    如果是新节点未处理,则创建新节点插入到旧序列的末尾或者旧序列的开头,二者其实是一个位置

    我们假设旧节点中没有 c,则在第四次循环后就会出现以下情况(第四次循环命中的是情况 1)

    9.png

    如果把 f 放到序列的开头,就是旧开始节点(节点 e)的前面

    而如果把 f 放到序列的末尾,也就是旧结束节点的下一个节点(节点 e)的前面

    此时旧序列就是一个点,不分开头和结尾,只要保证新增节点序列按序添加就好了

    至此,双端 diff 算法就讲完了

    Vue 中的 key

    学完 diff 算法,再聊聊 key 的作用

    v-for 中的 key

    上面讲的都是有 key 情况下,diff 算法能够迅速找到新旧序列中的同一节点,以较小的代价完成更新。

    而如果在 v-for 中不设置 key 呢?

    假设我们在数组头部插入了一个新节点,然后开始循环,每次循环都命中情况 1,尝试“复用”此节点。

    但是,在对比新旧节点的内容时,都会发现内容不同,需要用新节点的内容替换旧节点。这只是复用了 DOM 的外壳,节点的内容、数据以及该节点的子节点全都要更改。

    相比有 key 时的只添加一个新节点,无 key 则将所有节点都修改一遍。

    v-if 自带 key

    v-for 以外的元素我们一般是不设置 key 的,但是如果子元素中有 v-if 的话,就像下面这个场景(abcd是内容,并不是 key),更新子元素又会复现上一节的情况。

    10.png

    然而 Vue 官方也考虑到了这点,会为 v-if 的元素加上利用 hash 函数生成的唯一 key

    // 以下出自 v2 源码
    var needsKey = !!el.if 
    ……
    needsKey ? ',null,false,' + hash(generatedSlots) : ''

    key 的另一个用法

    顺便再提一嘴,key 可以绑到任意元素上,当 key 发生变化时,会导致 DOM 的销毁与重建,一般用来重复触发动画或生命周期钩子。

    详情可看官方链接

    https://cn.vuejs.org/v2/api/#key

    结语

    不记得这是第几次梳理双端 diff 的逻辑了,很早之前就已经拥抱 v3 了,把 v2 的响应式原理和 diff 算法总结一遍也算是给 v2 画上句号了。

    没想到这篇文章写了 4000 多字,为此还特意去翻看了 v2 的源码。本文的代码和 v2 差别还是蛮大的,主要参考的是 snabbdom 和以前的教程,加了点自己的风格将 patchVnodeupdateChildren 实现了一遍。

    接下来就能心无旁骛地看 v3 的源码了……

    整理不易,如果有所帮助的话,希望能点赞关注,鼓励一下作者。

    原文地址:https://juejin.cn/post/7120919895713251335

    作者:清隆

    【相关视频教程推荐:vuejs入门教程web前端入门

    以上就是聊聊Vue2中的双端diff算法,看看如何更新节点的!的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:掘金社区,如有侵犯,请联系admin@php.cn删除
    专题推荐:vue.js Vue
    上一篇:聊聊Vue3中的一个好用的功能:Teleport 下一篇:分享 6 个实用的 Vue 依赖库(值得收藏)
    VIP课程(WEB全栈开发)

    相关文章推荐

    • 【活动】充值PHP中文网VIP即送云服务器• Vue2和Vue3在响应式上有什么区别?简单对比• vue2.0组件之间怎么传值?组件传输方式浅析• 【吐血整理】Vue.js面试题汇总及答案解析(快来收藏)• 2022年 Vue 的发展情况报告【整理分享】• 前端怎么埋点?浅析vue自定义指令进行前端埋点的方法
    1/1

    PHP中文网