专栏首页多云转晴理解DOM Diff算法

理解DOM Diff算法

虚拟 DOM 出现的背景:在 jQuery 时代,可以自行控制 DOM 操作的时机,手动调整,但是当项目很大时,操作 DOM 的复杂度就会上来,DOM 操作会很耗费性能,操作 DOM 就还需要考虑优化 DOM 操作,提升性能。《高性能 JavaScript》这本书中说,把 DOM 和 JavaScript 各自想象成一个岛屿,它们之间用收费桥梁连接。操作 DOM 后需要经过跨流程通信和渲染线程触发的重新渲染(重绘或者重排),在开发中,应尽量减少操作 DOM。而虚拟 DOM 出现后,更新 DOM 交给框架处理。操作虚拟 DOM 可能并没有操作真实 DOM 快,但是它让开发人员不再把很多精力放在操作 DOM 上,而是专注于处理业务数据。本文以 Vue 原码中的 DOM diff 算法为例,介绍一下这个算法的实现原理。

虚拟 DOM 是用 JavaScript 模拟 DOM 结构,通过计算出最小的变更,操作 DOM 结构,更新视图。而 Diff 算法是虚拟 DOM 最核心、最关键的部分,好的 Diff 算法可以正确、快速的更新 DOM。DOM diff 算法时间复杂度为 O(n)。它的大概逻辑如下:

  • 只比较同一层级,不跨级比较;
  • tag 不同(标签类型)则直接删掉重建,不再深度比较;
  • tag 和 key 两者都相同则认为是相同的节点,不再深度比较。

虚拟 DOM 并不一定比真实 DOM 更新视图更快,但是它的出现让开发人员省去了操作 DOM 的时间成本和精力,让开发更专注于业务本身。虚拟 DOM 使用 JavaScript 模拟实现,这也为创建跨平台应用提供了可能,比如 React Native。

JavaScript 可以使用对象描述 DOM 结构,例如:

{
    tag: 'div',
    props: {
        className: 'container',
    },
    children: [{
        tag: 'p',
        children: 'hello!'
    }]
}

上面的对象映射出 DOM 结构就是:

<div class="container">
    <p>hello!</p>
</div>

在 Vue 源码中,有一个 sameVnode 函数,它用来判断新老节点是不是同一个节点,代码大致如下:

function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      )
    )
  )
}

a 是 oldVnode 即老的虚拟 DOM,b 是新的虚拟 DOM,从代码中大致可以了解到,a 和 b 的判断条件有:

  • key 我们添加的 key,它们要相等;
  • tag 标签名要一致;
  • isComment 表示不是不是注释节点;
  • isDef 这个函数用来判断传入的数据是不是有值(即数据不等于 undefined 和 null 时返回 true);
  • sameInputType 如果节点是 input 元素时,判断 type 是否相同;

接下来是 patch 函数,当数据发生变化时,set 方法会调用 dep.notify 通知所有订阅者 Watcher,订阅者就会调用 patch 函数,给真实 DOM 打补丁,更新视图。

大致代码如下:

function patch (oldVnode, vnode, hydrating) {
    if (isUndef(vnode)) {   // 如果新的虚拟节点是 undefined 或 null,并且老虚拟节点有值
        // 说明我们删除了节点,就调用 Destroy 生命周期钩子
        if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
        return;
    }

    let isInitialPatch = false
    const insertedVnodeQueue = []

    if (isUndef(oldVnode)) {    // 如果老节点没有值
        // 这说明是首次调用 path,这是初次渲染
        // 初次渲染就直接把 vnode 挂载到 DOM 元素上
        isInitialPatch = true
        createElm(vnode, insertedVnodeQueue)
    } else {
        // 判断老虚拟节点是不是真实 DOM
        const isRealElement = isDef(oldVnode.nodeType)
        // 如果不是真实 DOM 并且 vnode 相同,就调用 pathVnode 进一步处理
        if (!isRealElement && sameVnode(oldVnode, vnode)) {
            // patch existing root node
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null)
        }else{      // 不相等就直接删掉 oldVnode,重新创建
            const oldElm = oldVnode.elm     // oldVnode 对应的真实元素
            const parentElm = nodeOps.parentNode(oldElm);   // 拿到父元素
            createElm(vnode, insertedVnodeQueue);
            if(parentElm !== null){
                // 将新元素插入到父元素中
                insertBefore(parentElm, vnode.elm, nodeOps.nextSibling(oldElm));
                // 移除老的节点
                removeVnodes(parentElm, [oldVnode], 0, 0);
            }
        }
    }   // 返回新的节点
    return vnode.elem
}

大致流程如下:

patch 函数

当 oldVnode 与 newVnode 相同时,调用 patchVnode 函数。他比较的不是真实节点,而是虚拟节点(JS 对象)。大致代码如下:

function patchVnode (oldVnode, vnode) {
    if (oldVnode === vnode) {
        // 新老节点相同,就直接返回
        return
    }
    // oldVnode 和 vnode 的标签一样,直接把老的虚拟DOM对应的元素赋给新的即可
    const elm = vnode.elm = oldVnode.elm;
    const oldCh = oldVnode.children;    // 获取到老虚拟节点的儿子
    const ch = vnode.children;          // 获取到新虚拟节点的儿子
    // 比较新老虚拟节点的儿子节点
    // 如果 vnode 没有文本
    if (isUndef(vnode.text)) {
        // 如果都有儿子节点
        if (isDef(oldCh) && isDef(ch)) {
            if (oldCh !== ch)   // 而且两个儿子节点不相同,这时就要更新儿子节点
                updateChildren(elm, oldCh, ch, insertedVnodeQueue);
        } else if (isDef(ch)) {
            // oldVnode 有文本,新的没有,删掉老的文本
            if (isDef(oldVnode.text))   nodeOps.setTextContent(elm, '');
            // 如果新的儿子有,老的儿子节点没有
            // 会把新增的子节点插入到老的 DOM 上
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        } else if (isDef(oldCh)) {
            // 如果 oldVnode 有子节点,而 vnode 没有子节点
            // 就直接删掉子节点
            removeVnodes(oldCh, 0, oldCh.length - 1);
        } else if (isDef(oldVnode.text)) {
            // 老的有文本,新的没有文本
            // 就把老的元素文本设置成空
            nodeOps.setTextContent(elm, '');
        }
    } else if (oldVnode.text !== vnode.text) {
        // 都有文本,但不相同,就使用 vnode(新的)的文本
        nodeOps.setTextContent(elm, vnode.text);
    }
}

patchVnode 的函数执行大致如下:

patchVnode 函数

接下来是 diff 算法中最为核心的一个函数:updateChildren。DOM diff 算法有以下几个特点:

  1. 先同级比较,再比较子节点;
  2. 先判断一方有 children,一方没有 children 的情况;
  3. 比较都有 children 的情况;
  4. 递归比较子节点;

updateChildren 函数代码大致如下:

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue) {
    // parentElm 是传入的父元素,oldCh 是老的子节点;newCh 是新的子节点
    let oldStartIdx = 0;    // oldVnode 子节点初始索引
    let newStartIdx = 0     // vnode 子节点初始索引
    let oldEndIdx = oldCh.length - 1    // oldVnode 子节点的尾索引
    let oldStartVnode = oldCh[0]        // oldVnode 第一个子节点
    let oldEndVnode = oldCh[oldEndIdx]  // oldVnode 最后一个子节点
    let newEndIdx = newCh.length - 1    // vnode 子节点的尾索引
    let newStartVnode = newCh[0]        // vnode 的第一个子节点
    let newEndVnode = newCh[newEndIdx]  // vnode 的最后一个子节点
    let oldKeyToIdx, idxInOld, vnodeToMove;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (isUndef(oldStartVnode)) {   // 如果 oldVnode 的第一个子节点没有值
            // 指针向右移动
            oldStartVnode = oldCh[++oldStartIdx];
        } else if (isUndef(oldEndVnode)) {  // 如果 oldVnode 的最后一个子节点没有值
            // 指针向左移动
            oldEndVnode = oldCh[--oldEndIdx]
        }

        else if (sameVnode(oldStartVnode, newStartVnode)) {     // 判断开始和开始索引的子节点是否相同
            // 相同就递归(子节点里可能还有子节点,还需要判断)
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);
            // 两个指针同时前进(向右移动)
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
        } else if (sameVnode(oldEndVnode, newEndVnode)) {   // 两个尾部元素是不是相同
            // 相同递归做进一步处理
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 两个指针同时向左移动
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldStartVnode, newEndVnode)) { // 老的开始节点和新的结束节点如果相同
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 把 oldStartVnode 对应的元素(头指针指向的节点)移动到 oldEndVnode 对应的元素(尾指针指向的节点)的前面
            nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
            oldStartVnode = oldCh[++oldStartIdx]    // 老的指针向右移动
            newEndVnode = newCh[--newEndIdx]        // 新的指针向左移动
        } else if (sameVnode(oldEndVnode, newStartVnode)) { // 老的结束节点和新的开始节点如果相同
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 把 oldEndVnode 对应的元素(尾指针指向的节点)移动到 oldStartVnode 对应的元素(头指针指向的节点)的前面
            nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
            oldEndVnode = oldCh[--oldEndIdx]        // 老的指针向左移动
            newStartVnode = newCh[++newStartIdx]    // 新的指针向右移动
        }
        // 上面四个判断是做优化用的几个“特殊情况”,即开始与结束、开始与开始、结束与开始、结束与结束的节点都不相同
        else {
            // 如果 oldKeyToIdx 没有,就遍历老的子节点,生成一个对象,对象的键是元素的 key,值是元素的索引
            if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
            // 新节点的 key,能否对应上 oldCh 中的某个节点的 key
            idxInOld = isDef(newStartVnode.key)     // 新的开始元素有没有 key
            ? oldKeyToIdx[newStartVnode.key]        // 通过 key 可以拿到老的子元素的索引
            // 如果新的开始元素没有 key,就遍历老的子节点,找到对应 key 的索引,没有找到会是 undefined
            : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
            if (isUndef(idxInOld)) { // 如果 idxInOld 是 undefined,说明没有找到对应的 key
                // 新节点的 key 没有找到对应的旧节点,则新节点 key 对应的元素会插入到 oldStartVnode 对应的元素的前面
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)   // 1
            } else {        // 如果找到了对应的 key,通过索引获取到老节点 key 对应的元素
                vnodeToMove = oldCh[idxInOld]   // 引用
                if (sameVnode(vnodeToMove, newStartVnode)) {    // 比较是否相同
                    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                    oldCh[idxInOld] = undefined     // 把对应的元素设置成 undefined
                    // 然后把 vnodeToMove 对应的元素移动到 oldStartVnode 对应的元素前面
                    nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                } else {
                    // 相同的 key,但是不是同一个节点,则新节点 key 对应的元素会插入到 oldStartVnode 对应的元素的前面,与 1 处一样
                    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);
                    // createElm(vnodes[startIdx], insertedVnodeQueue, parentElm, refElm, false, vnodes, startIdx)
                }
            }
            // 操作完之后,将新节点的开始指针向右移动
            newStartVnode = newCh[++newStartIdx]
        }
    }   // 上面判断条件走完之后,需要判断新的开始索引是不是移动到结束索引的右边去了
    if (newStartIdx > newEndIdx) {
        removeVnodes(oldCh, oldStartIdx, oldEndIdx)     // 把旧的开始和结束之间的元素移除
    }
}

下面以一个例子演示一下 diff 的工作流程。

假如 oldVnode 是左边的结构,vnode 是右边的结构。

新旧虚拟DOM树

遍历子节点之后,初始化指针:

初始化指针

然后判断,首先是 oldStart 和 newStart,发现节点相同(假设相同的字母,它们的 key 也相同),两个指针都向右移动。一个指向 C,一个指向 E,发现节点不一样,然后:

  • oldEndIdx 和 newEndIdx 对应的节点比较,不相同(D 和 C 节点);
  • oldStartIdx 和 newEndIdx 对应的节点比较,发现一样(oldStartIdx 已经往右移动了,对应于 C,而 newEndIdx 对应的也是 C),这个时候会遍历 C 中子节点,发现没有子节点,然后将 oldStartIdx 对应的节点 C 插入到 oldEndIdx (D 节点)的后面,然后 oldStartIdx++,newEndIdx--,新旧指针就移动到了如下的位置:

oldStart=newEnd

  • 走完一次 while 循环,接着又开始一轮。oldStartnewStart 都指向 E 节点,两个指针都向右移动(都和 end 指针重合),然后(又一轮循环) oldEndnewEnd 都指向 D 节点,指针都向左移动。接着又一轮循环,结果发现循环条件不能满足,diff 算法结束,DOM 更新完成。

下面是有新增元素的例子:

新旧节点如下(第一行是旧节点):

A B C D

C D M E

调用 updateChildren 时会发现开始与开始、结束与结束、开始与结束、结束与开始对应的节点都不一样。这时候就要遍历旧节点,找到与 newStartIdx 对应元素的 key 一样的节点。在旧节点中可以找到 C,它的索引值是 2。把 oldChildren[2](C 节点所在位置)设置成 undefined,然后把 oldVnode 中的 C 移到 oldStartVnode 的前面(A 节点)。

C A B undefined D

  C D M E

然后 newStartIdx 向右移动,条件判断,发现 oldEndVnode 也是 D 节点,会把 D 节点移动到 oldStartVnode (A 节点)前面,变成:

C D A B undefined undefined

    C D M E

newStartIdx 继续向右移动,发现新的节点 M(key 没有在 oldChildren 中找到),把 M 放到 oldStartVnode(A 节点)前面,变成:

C D M A B undefined undefined

      C D M E

newStartIdx 继续向右移动,新节点 E 与 M 一样,变成:

C D M E A B

        C D M E

移动之后,newStartIdx ++,此时的 newStartIdx (为 4)会比 newEndIdx (为 3 指向 E 点)大,就会把 oldStartIdxoldEndIdx 之间的节点删掉,即删掉 A 与 最右边的 undefined 之间的节点(包括自身)。变成:

C D M E

C D M E

到此,diff 完毕。

通过代码我们能发现,Vue 会通过判断 key 的方式来判断是不是同一个节点。如果使用数组的索引作为 key,当对数组排序然后重新渲染时,节点的索引值很可能会发生改变,索引值发生改变导致 key 也会发生改变,节点还是原来的节点,但是它的 key 却发生了变化,这会导致 Vue 重新创建节点,而不是移动节点。因此不推荐使用索引作为 key。更不推荐使用随机数(比如 Math.random)作为 key,当组件更新时,随机数会跟着变化,导致 key 每次都不一样。

本文分享自微信公众号 - Neptune丶(Neptune_mh_0110),作者:多云转晴丶

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Virtual Dom和Diff算法

    这是一篇很长的文章!!!坚持看到最后有彩蛋哦!!! 文章开篇,我们先思考一个问题,大家都说 virtual dom 这,virtual dom 那的,那么 vi...

    前端迷
  • Vue3 DOM Diff 核心算法解析

    想要搞明白 Vue3 的 DOM Diff 核心算法,我们要从一道 LeetCode 真题说起。

    前端劝退师
  • 了解虚拟DOM和diff算法

    今天分享一下虚拟DOM和diff算法,当然,只是非常简单的了解一下,知道这两个东西的概念。

    wade
  • Vue3 DOM Diff 核心算法解析

    本文已收录在前端食堂同名仓库Github github.com/Geekhyt[1],欢迎光临食堂,如果觉得酒菜还算可口,赏个 Star 对食堂老板来说是莫大的...

    童欧巴
  • virtual DOM和diff算法(一)

    哈喽,大家好,今天是周一。周末回老家了,每次回老家后的第一个工作日都感觉很陌生,各位宝宝(づ。◕‿‿◕。)づ,有多久没回老家了?不管在哪里,记得好好照顾自己,好...

    用户3258338
  • virtual DOM和diff算法(二)

    根据昨天的学习,我们知道运用了virtual DOM和diff算法,可以提高程序性能,那么我们今天开始就要看看到底是怎么提高性能的。

    用户3258338
  • Vue中diff算法的理解

    diff算法用来计算出Virtual DOM中改变的部分,然后针对该部分进行DOM操作,而不用重新渲染整个页面,渲染整个DOM结构的过程中开销是很大的,需要浏览...

    WindrunnerMax
  • React中diff算法的理解

    diff算法用来计算出Virtual DOM中改变的部分,然后针对该部分进行DOM操作,而不用重新渲染整个页面,渲染整个DOM结构的过程中开销是很大的,需要浏览...

    WindrunnerMax
  • 【Vuejs】571- Vue 虚拟DOM和Diff算法源码解析

    所谓的Virtual dom,也就是我们常说的虚拟节点,它是通过JS的Object对象模拟DOM中的节点,然后再通过特定的render方法将其渲染成真实的DOM...

    pingan8787

扫码关注云+社区

领取腾讯云代金券