Vue2 の両端差分アルゴリズムについて説明し、ノードを更新する方法を見てみましょう。

この記事では、Vue2 の両端差分アルゴリズムを理解し、Vue2 がノードを更新する方法について説明します。

今日は、Vue2 の両端差分アルゴリズムについて説明します。 (学習ビデオ共有: vue ビデオ チュートリアル)

なぜ話したいのですか? 最も単純な理由は面接試験です。面接官がキーの役割について質問したとき、9 10 人中、diff アルゴリズムに引用します。

仕方がありません、面接で聞かれないとわかりませんが、幸いなことに、それほど難しいことではありませんので、フォローして見てください。

スペースの都合上、この記事では仮想 DOM ツリーの生成方法については紹介しません。2 つの仮想 DOM ツリーを比較し、データ更新時に実際の DOM を更新する方法のみを説明します。主に次の実装です。 # Vue2 ソースコード内 ##patchVnode, updateChildren Function

予備知識

#diff アルゴリズム関数

diff アルゴリズムについて話す前に、それが何をするのかを理解する必要があります。

Web ページの実行中に一部のデータが変更され、DOM ツリーに影響を与える可能性があることがわかっています。ページに最新のデータを表示するにはどうすればよいでしょうか? 最も簡単な方法は、ツリー全体をプッシュして再構築することです。もちろん、これには多くの無駄が生じるため、Vue は仮想 DOM を使用してページ内の DOM ツリーの状態を保存します。データが変更されたら、新しい仮想 DOM ツリーを作成し、2 つのツリー間の違いを見つけて、目的の方法で実際の DOM を更新します。

2 つのツリー間の違いを見つけて、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 要素に。そして、後続の差分アルゴリズムでは、キーを使用してノードを一意に識別するため、以下の vnode がそのようなオブジェクトです

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

Vue の仮想ノードにも多くの属性がありますが、差分アルゴリズムとは異なります無関係なのでリストしません

説明するだけですが、仮想ノードのテキストと子は同時に値を持ちません。 Children属性の場合、テキスト内の内容がテキストノードに変換され、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
}

と 3 つのツール関数

// 判断是否未定义
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 要素を新しいノードに割り当て、新旧ノードの子属性を取得します

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

値を割り当てることができますpatchVnode を呼び出す古いノードと新しいノードのタグとキーは同じである必要があるため、ここに直接記述します。これについては以下で説明します

#次に、2 つのノードの内容に基づいて 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

を呼び出して処理します。この関数については次の章で説明します。<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">if (isDef(oldCh) &amp;&amp; isDef(newCh)) { updateChildren(elm, oldCh, newCh) }</pre><div class="contentsignin">ログイン後にコピー</div></div>ケース 4 はケース 3 と同じ方法で処理でき、古いノードをクリアしてから、次のノードに移動します。新しい DOM を生成します。ただし、DOM 要素の作成は非常に時間のかかる作業であり、古い子ノードと新しい子ノードはほとんどの場合同じであることを理解しておく必要があり、再利用できればパフォーマンスが大幅に最適化されます。

それでは、ノードが再利用できるかどうかをどのように判断するのでしょうか?

これには Vue ユーザーの協力が必要です。ユーザーはノードのキー属性を定義し、どのノードが再利用できるかを Vue に指示します。

ラベルのタイプとキーの値が等しい限り、それは意味します。現在の要素が再利用できることを確認します。

ただし、私たちのプロジェクトでは、通常、キーは v-for にのみ設定され、他のノードにはキーが設定されません。

実際には、

キーが設定されていないノード、そのキー値はデフォルトで等しいです

これも当てはまります。プロジェクト内のほとんどの要素は再利用できます。v-for によって生成された子要素のみです配列には複雑な変更が加えられる可能性があるため、Vue がノードをできるだけ再利用できるようにキー値を明確にマークする必要があります。

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

updateChildren

为什么采用双端 diff

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

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

然而这明显有优化的空间，Vue 实现这部分功能时借鉴了 snabbdom 的双端 diff 算法，因为此算法将我们平时操作数组常见的 4 种情况抽离了出来，涵盖了我们业务中的大多数场景，将 O(n²) 的时间复杂度降到了 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，旧前与新前(key)相等

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果把 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），更新子元素又会复现上一节的情况。

然而 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 和以前的教程，加了点自己的风格将 patchVnode 和 updateChildren 实现了一遍。

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

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

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

作者：清隆

【相关视频教程推荐：vuejs入门教程、web前端入门】

以上がVue2 の両端差分アルゴリズムについて説明し、ノードを更新する方法を見てみましょう。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。