Une analyse approfondie de l'algorithme Diff dans Vue2

L'algorithme diff est un algorithme efficace qui compare les nœuds d'arbre au même niveau, évitant ainsi d'avoir à rechercher et parcourir l'arbre couche par couche. Alors, que savez-vous de l’algorithme diff ? L'article suivant vous donnera une analyse approfondie de l'algorithme diff de vue2. J'espère qu'il vous sera utile !

Parce qu'on m'a souvent posé des questions sur l'algorithme Diff lorsque je regardais des interviews en direct auparavant, et que l'auteur lui-même utilise beaucoup Vue2, j'ai donc l'intention d'étudier l'algorithme Diff de Vue2. En fait, j'ai voulu l'apprendre. Cela fait longtemps, mais peut-être parce que je pense que l'algorithme Diff est relativement ésotérique, j'ai retardé son apprentissage, mais récemment je me préparais pour une interview, et je pensais que je l'apprendrais tôt ou tard. opportunité de comprendre l'algorithme Diff ? L'auteur a passé une journée à l'étudier et n'a peut-être pas complètement compris Diff L'essence de l'algorithme, veuillez me pardonner.

 ? Cela compte en fait comme des notes d'étude de l'auteur, et le niveau de l'auteur est limité. L'article révisé ne représente que l'opinion personnelle de l'auteur, vous pouvez les signaler dans la zone de commentaire et elles le seront en permanence. En même temps, cet article est très long, nous demandons donc aux lecteurs d'être patients. Après l'avoir lu, l'auteur pense que vous aurez une compréhension plus approfondie de l'algorithme Diff. Je pense que cet article est meilleur que la plupart des articles sur Internet expliquant actuellement l'algorithme Diff, car cet article part du problème et apprend à chacun comment penser, plutôt que de partir directement de la réponse, tout comme lire la réponse, ce qui semble Cela n'a aucun sens.Cet article explique étape par étape Guidez tout le monde à ressentir la subtilité de l'algorithme Diff, et enfin faites une petite expérience pour donner à chacun une sensation plus intuitive de l'algorithme Diff.

Pourquoi utiliser l'algorithme Diff

DOM virtuel

Parce que la couche inférieure de Vue2 utilise le DOM virtuel pour représenter la structure de la page. Si vous voulez savoir comment le générer, le DOM virtuel est en fait un objet. Le processus approximatif est le suivant :

• Analysez d'abord la chaîne de modèle, qui est le fichier .vue.vue 文件
• 然后转换成 AST 语法树
• 接着生成 render 函数
• 最后调用 render 函数，就能生成虚拟 DOM  【相关推荐：vuejs视频教程、web前端开发】

最小量更新

其实框架为了性能才使用的虚拟 DOM，因为 js 生成 DOM 然后展示页面是很消耗性能的，如果每一次的更新都把整个页面重新生成一遍那体验肯定不好，所以需要找到两个页面中变化的地方，然后只要把变化的地方用 js 更新 (可能是增加、删除或者更新) 一下就行了，也就是最小量更新。 那么怎么实现最小量更新呢？那么就要用 Diff 算法了，那么 Diff 算法对比的到底是什么呢？可能这是刚学 Diff 算法比较容易误解的地方，其实比对的是新旧虚拟 DOM，所以 Diff 算法就是找不同，找到两次虚拟 DOM 的不同之处，然后将不同反应到页面上，这就实现了最小量更新，如果只更新变化的地方那性能肯定更好。

页面更新流程

其实这个比较难解释，作者也就大致说一下，学了 Vue 的都知道这个框架的特点之一就有数据响应式，什么是响应式，也就是数据更新页面也更新，那么页面是怎么知道自己要更新了呢？其实这就是这个框架比较高明的地方了，大致流程如下：

• 之前也说了会运行 render 函数，那么运行 render 函数的时候会被数据劫持，也就是进入 Object.defineProperty 的 get，那么在这里收集依赖，那么是谁收集依赖呢？是每个组件，每个组件就是一个 Watcher，会记录这个组件内的所有变量 (也就是依赖)，当然每个依赖 (Dep) 也会收集自己所在组件的 Watcher；
• 然后当页面中的数据发生变化，那么就会出发 Object.defineProperty 的 set，在这个函数里面数据就会通知每个 Watcher 更新页面，然后每个页面就会调用更新方法，这个方法就是 patch
Puis convertissez-la en un arbre de syntaxe AST
• Ensuite, générez la fonction de rendu
• Enfin, appelez la fonction de rendu pour générer le DOM virtuel [Recommandations associées ：vuejs video tutoriel a>, développement web front-end]

Mise à jour minimale

🎜🎜En fait, le framework n'utilise que du DOM virtuel pour les performances, car js génère du DOM puis affiche la page, ce qui est très gourmand en performances si la page entière est régénérée à chaque fois. est mis à jour, l'expérience ne sera certainement pas bonne, il faut donc trouver deux pages. Ensuite, utilisez simplement js pour mettre à jour les emplacements modifiés (il peut s'agir d'ajout, de suppression ou de mise à jour) en un clic, ce qui est le minimum. quantité de mises à jour. Alors, comment obtenir le minimum de mises à jour ? Ensuite, nous devons utiliser l'algorithme Diff. Alors, que compare exactement l'algorithme Diff ? C'est peut-être là qu'il est facile de mal comprendre l'algorithme Diff lorsque vous l'apprenez pour la première fois 🎜En fait, il compare l'ancien et le nouveau DOM virtuel🎜, donc l'algorithme Diff consiste à trouver la différence, à trouver la différence entre les deux DOM virtuels. , puis reflète la différence sur la page. Cela permet d'obtenir le plus petit nombre de mises à jour. Si seuls les emplacements modifiés sont mis à jour, les performances seront certainement meilleures. 🎜

🎜Processus de mise à jour des pages🎜🎜🎜En fait, c'est difficile à expliquer. L'auteur donnera une brève introduction. Quiconque a appris Vue sait que l'une des caractéristiques de celui-ci. Le framework est la réactivité des données, qu'est-ce que la réactivité, c'est-à-dire que la page est également mise à jour lorsque les données sont mises à jour, alors comment la page sait-elle qu'elle doit être mise à jour ? En fait, c'est la partie intelligente de ce framework. Le processus général est le suivant : 🎜🎜🎜Comme mentionné précédemment, la fonction de rendu sera exécutée, donc lorsque la fonction de rendu est exécutée, les données seront détournées, c'est-à-dire que en entrant le get de Object.defineProperty, alors les dépendances sont collectées ici, alors qui collecte les dépendances ? C'est chaque composant. Chaque composant est un Watcher, qui enregistrera toutes les variables (c'est-à-dire les dépendances) dans ce composant. Bien entendu, chaque dépendance (Dep) le sera également. être collecté Observateur du composant dans lequel vous vous trouvez ; 🎜🎜 Ensuite, lorsque les données de la page changent, alors le set de Object.defineProperty sera déclenché dans cette fonction, les données informeront tout le monde. Un observateur met à jour la page, puis chaque page appellera la méthode de mise à jour. Cette méthode est patch ; alors nous devons utiliser l'algorithme Diff 🎜🎜Après avoir enfin trouvé le montant de la monnaie, vous pouvez mettre à jour la page🎜🎜🎜🎜En fait, elle est mise à jour lors de la recherche Afin de faciliter la compréhension de tous, ces deux parties sont. séparé🎜

Une brève introduction à l'algorithme Diff

Lorsqu'on lui demande lors d'une interview ce qu'est l'algorithme Diff, tout le monde dira certainement quelques mots, tels que tête-à-tête, queue-à-queue, queue -à tête, tête à queue, traversée en profondeur en premier (dfs), Comparaison du même niveau Semblable à ces mots, même si je peux dire une ou deux phrases, ce n'est qu'une égratignure. En fait, l'auteur a lu un article sur l'algorithme Diff publié sur CSDN, qui est un article très lu. L'auteur a le sentiment de ne pas l'avoir bien compris. Peut-être qu'il ne l'a pas compris lui-même, ou qu'il l'a compris mais ne l'a pas expliqué. clairement. Ensuite, l'auteur utilisera le sien. Laissez-moi partager mes idées avec vous. 头头、尾尾、尾头、头尾、深度优先遍历(dfs)、同层比较 类似这些话语，虽然能说一两句其实也是浅尝辄止。 其实作者看了 CSDN 上发的关于 Diff 算法的文章，就是阅读量很高的文章，作者觉得他也没讲明白，可能他自己没明白，或者自己明白了但是没讲清楚，那么作者会用自己的感悟和大家分享一下。

Diff 算法的前提

为了让大家能够了解清楚，这里先说明一下函数调用流程：

• patch
• patchVnode
• updateChildren

Diff 算法的 前提 这个是很重要的，可能大家会问什么是前提？不就是之前说的那些比较嘛？说的没错但也不对，因为 Diff 算法到达之前说的 头头、尾尾、尾头、头尾 这一步的前提就是两次对比的节点是 相同的，这里的相同不是大家想的完全相同，只是符合某些条件就是相同了，为了简化说明，文章就只考虑一个标签只包含 key 和 标签名(tag)，那么之前说的相同就是 key 相同以及 tag 相同，为了证明作者的说法是有点正确的，那么这里也贴上源码：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 36行
function sameVnode(a, b) {
  return (
    a.key === b.key &&
    a.asyncFactory === b.asyncFactory &&
    ((a.tag === b.tag &&
      a.isComment === b.isComment &&
      isDef(a.data) === isDef(b.data) &&
      sameInputType(a, b)) ||
      (isTrue(a.isAsyncPlaceholder) && isUndef(b.asyncFactory.error)))
  )
}

如果怕乱了，下面的可以省略不看也没事不影响整体了解，下面只是为了考虑所有情况才加的一个判断： 那么如果两个虚拟 DOM 不相同其实就不用继续比较了，而且如果相同也不用比较了，这里的相同是真的完全相同，也就是两个虚拟 DOM 的地址是一样的，那么也贴上源码：

function patchVnode(......) {
  if (oldVnode === vnode) {
    return
  }
  ......
}

到目前为止大家可能会比较乱，现在总结一下：

• 在 patch 函数里比较的是新老虚拟 DOM 是否是 key 相同以及 tag 相同，如果不相同那么就直接替换，如果相同用 patchVnode

说了这么多，其实作者也就想表达一个观点，就是只有当两次比较的虚拟 DOM 是 相同的 才会考虑 Diff 算法，如果不符合那直接把原来的删除，替换新的 DOM 就行了。

patchVnode 函数

这个函数里的才是真正意义上的 Diff 算法，那么接下来会结合源码向大家介绍一下。

源码中核心代码在 patch.ts 的 638 行至 655 行。

其实，目前介绍 patchVnode 的都是直接对着源码来介绍的，但是大家可能不清楚为啥要这么分类，那么作者在这里就让大家明白为什么这么分类，首先在这里说一个结论：

• 就是 text 属性和 children 属性不可能同时存在，这个需要大家看模板解析源码部分

那么在对比新旧节点的情况下，主要比较的就是是否存在 text 和 children

Les prémisses de l'algorithme Diff

Pour que tout le monde comprenne clairement, voici le processus d'appel de fonction :

• patch
• patchVnode
• updateChildren

if (isUndef(vnode.text)) {
  // 新虚拟 DOM 有子节点
} else if (oldVnode.text !== vnode.text) {
  // 如果新虚拟 DOM 是文本节点，直接用 textContent 替换掉
  nodeOps.setTextContent(elm, vnode.text)
}

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 递归处理，精细比较
      // 对应分类 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 对应分类 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 对应分类 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 对应分类 1️⃣
    nodeOps.setTextContent(elm, '')
  }
}

• Ce qui est comparé dans la fonction patch est si le nouveau et l'ancien DOM virtuel ont la même clé et la même balise, sinon, remplacez-le directement. Si c'est le même, utilisez patchVnode
.

Cette fonction est le véritable algorithme Diff, je vais donc vous le présenter ensuite en fonction du code source.

Le code principal du code source se trouve dans patch.ts.

• Il est impossible que l'attribut text et l'attribut children existent en même temps. regardez la partie du code source d'analyse du modèle

Situationsanciens nœuds texteanciens nœuds enfantsnouveau nœud textenouveaux nœuds enfants1❎. ❎ ❎❎ 2❎✅❎❎3✅❎❎❎4❎❎❎✅5❎✅❎ ✅6✅❎ ❎✅7❎❎ ✅❎8

Le prérequis de l'algorithme Diff est très important. Vous vous demandez peut-être quelle est la prémisse ? Ne s'agit-il pas simplement des comparaisons mentionnées précédemment ? C'est vrai mais c'est aussi faux, car l'algorithme Diff atteint le tête, queue, queue, tête, queue mentionné précédemment. Le principe de cette étape est que les nœuds comparés deux fois sont identiques<.> code>, la similitude ici n'est pas exactement la même que tout le monde le pense, mais elle est la même si elle remplit certaines conditions. Afin de simplifier l'explication, l'article ne considère qu'une balise qui ne contient que <code>key<.> et <code> nom de la balise (tag ), alors ce que j'ai dit avant, c'est que la clé est la même et la balise est la même Afin de prouver que celle de l'auteur. La déclaration est quelque peu correcte, le code source est également publié ici :	Si vous avez peur de la confusion, ce qui suit peut être omis sans le regarder et cela n'affectera pas la compréhension globale. Ce qui suit n'est qu'un jugement ajouté à considérer. toutes les situations : Donc, si les deux DOM virtuels ne sont pas identiques, il n'est pas nécessaire de continuer à comparer, et s'ils sont identiques, il n'est pas nécessaire de comparer. La similitude ici est vraiment exactement la même, c'est-à-dire les adresses des deux. les DOM virtuels sont les mêmes, alors collez également le code source :	Tout le monde peut être confus jusqu'à présent, résumons-le maintenant :	Cela dit, l'auteur veut en fait exprimer un point de vue, c'est-à-dire que seulement lorsque les deux DOM virtuels comparés sont identiques, l'algorithme Diff sera pris en compte Si. ils ne sont pas cohérents, supprimez simplement celui d'origine et remplacez-le par le nouveau DOM.	Fonction patchVnode
	En fait, l'introduction actuelle de patchVnode est directement introduite dans le code source, mais vous ne savez peut-être pas pourquoi il est classé de cette manière, l'auteur est donc là pour faire comprendre à tout le monde pourquoi il est classé de cette manière. , permettez-moi de conclure :	Donc, dans Lors de la comparaison des anciens et des nouveaux nœuds, la comparaison principale est de savoir s'il y a du text et des enfants . Ensuite, il y aura les neuf situations suivantes

🎜❎🎜🎜✅🎜🎜 ✅🎜🎜❎🎜🎜🎜🎜9🎜🎜✅🎜🎜 ❎🎜🎜✅🎜🎜❎🎜🎜🎜🎜

按照上面的表格，因为如果新节点有文本节点，其实老节点不管是什么都会被替换掉，那么就可以按照 新节点 text 是否存在来分类，其实 Vue 源码也是这么来分类的：

if (isUndef(vnode.text)) {
  // 新虚拟 DOM 有子节点
} else if (oldVnode.text !== vnode.text) {
  // 如果新虚拟 DOM 是文本节点，直接用 textContent 替换掉
  nodeOps.setTextContent(elm, vnode.text)
}

那么如果有子节点的话，那应该怎么分类呢？我们可以按照每种情况需要做什么来进行分类，比如说：

• 第一种情况，我们啥都不用做，因此也可以不用考虑
• 第二种情况，我们应该把原来 DOM 的 textContent 设置为 ''
• 第三种情况，我们也应该把原来 DOM 的 textContent 设置为 ''
• 第四种情况，我们应该加入新的子节点
• 第五种情况，这个情况比较复杂，需要对比新老子节点的不同
• 第六种情况，我们应该把原来的 textContent 设置为 '' 后再加入新的子节点

那么通过以上六种情况 (新虚拟 DOM 不含有 text，也就是不是文本节点的情况)，我们可以很容易地进行归类：

• 分类 1️⃣： 第二种情况 和 第三种情况。进行的是操作是：把原来 DOM 的 textContent 设置为 ''
• 分类 2️⃣： 第四种情况 和 第六种情况。进行的是操作是：如果老虚拟 DOM 有 text，就置空，然后加入新的子节点
• 分类 3️⃣：第五种情况。进行的是操作是：需要进行精细比较，即对比新老子节点的不同

其实源码也是这么来进行分类的，而且之前说的 同层比较 也就得出来了，因为每次比较都是比较的同一个父节点每一个子元素 (这里的子元素包括文本节点和子节点) 是否相同，而 深度优先遍历(dfs) 是因为每次比较中，如果该节点有子节点 (这里的子节点指的是有 children 属性，而不包括文本节点) 的话需要进行递归遍历，知道最后到文本节点结束。

⭕️ 这里需要搞清楚子节点和子元素的区别和联系

然后我们来看看源码是怎么写吧，只看新虚拟 DOM 不含有 text，也就是不是文本节点的情况：

if (isUndef(vnode.text)) {
  if (isDef(oldCh) && isDef(ch)) {
    if (oldCh !== ch)
      // 递归处理，精细比较
      // 对应分类 3️⃣
      updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
  } else if (isDef(ch)) {
    if (__DEV__) {
      checkDuplicateKeys(ch) // 可以忽略不看
    }
    // 对应分类 2️⃣
    if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
    addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
  } else if (isDef(oldCh)) {
  	// 对应分类 1️⃣
    removeVnodes(oldCh, 0, oldCh.length - 1)
  } else if (isDef(oldVnode.text)) {
  	// 对应分类 1️⃣
    nodeOps.setTextContent(elm, '')
  }
}

❓我们可以看到源码把分类 1️⃣ 拆开来了，这是因为如果老虚拟 DOM 有子节，那么可能绑定了一些函数，需要进行解绑等一系列操作，作者也没自信看，大致瞄了一眼，但是如果我们要求不高，如果只是想自己手动实现 Diff 算法，那么没有拆开的必要。

作者觉得这么讲可能比网上其他介绍 Diff 算法的要好，其他的可能直接给你说源码是怎么写的，可能没有说明白为啥这么写，但是通过之前这么分析讲解后可能你对为什么这么写会有更深的理解和帮助吧。

updateChildren 函数

同层比较

因为当都含有子节点，即都包含 children 属性后，需要精细比较不同，不能像之前那些情况一样进行简单处理就可以了 那么这个函数中就会介绍大家经常说的 头头、尾尾、尾头、头尾 比较了，其实这不是 Vue 提出来的，是很早就提出来的算法，就一直沿用至今，大家可以参考【snabbdom 库】

? 在这之前我们要定义四个指针 newStartIdx、newEndIdx、oldStartIdx 和 oldEndIdx，分别指向 新头节点、新尾节点、旧头节点 与 旧尾节点

循环条件如下：

while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  ......
}

其实这个比较也就是按人类的习惯来进行比较的，比较顺序如下 ：

• 1️⃣ 新头节点与旧头节点：++newStartIdx 和 ++oldStartIdx
• 2️⃣ 新尾节点与旧尾节点：--newEndIdx 和 --oldEndIdx
• 3️⃣ 新尾节点与旧头节点：需要将 旧头节点 移动到 旧尾节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 --newEndIdx 和 ++oldStartIdx
• 4️⃣ 新头节点与旧尾节点：需要将 旧尾节点 移动到 旧头节点之前，为什么要这么做，讲起来比较复杂，记住就好，然后 ++newStartIdx 和 --oldEndIdx
• 5️⃣ 如果都没有匹配的话，就把 新头节点 在旧节点列表 (也就是 children 属性的值) 中进行查找，查找方式按照如下：
  • 如果有 key 就把 key 在 oldKeyToIdx 进行匹配，oldKeyToIdx 根据旧节点列表中元素的 key 生成对应的下标
  • 如果没有，就按顺序遍历旧节点列表找到该节点所在的下标
  • 如果在旧节点列表是否找到也分为两种情况：
    • 找到了，那么只要将 新头节点 添加到 旧头节点 之前即可
    • 没找到，那么需要创建新的元素然后添加到 旧头节点 之前
    • 然后把这个节点设置为 undefined

根据循环条件我们可以得到两种剩余情况，如下：

• 6️⃣ 如果 oldStartIdx > oldEndIdx 说明老节点先遍历完成，那么新节点比老节点多，就要把 newStartIdx 与 newEndIdx 之间的元素添加
• 7️⃣ 如果 newStartIdx > newEndIdx 说明新节点先遍历完成，那么老节点比新节点多，就要把 oldStartIdx 与 oldEndIdx 之间的元素删除

其实我们上面还没有考虑如果节点为 undefined 的情况，因为在上面也提到过，如果四种都不匹配后会将该节点置为 undefined，也只有旧节点列表中才有，因此要在开头考虑这两种情况：

• 8️⃣ 当 oldStartVnode 为 undefined：++oldStartIdx
• 9️⃣ 当 oldEndVnode 为 undefined：--oldEndIdx

那么我们来看源码怎么写的吧，其中用到的函数可以查看源码附录：

// https://github.com/vuejs/vue/blob/main/src/core/vdom/patch.ts
// 439 行至 556 行
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  if (isUndef(oldStartVnode)) {
  	// 情况 8️⃣
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
  } else if (isUndef(oldEndVnode)) {
  	// 情况 9️⃣
    oldEndVnode = oldCh[--oldEndIdx]
  } else if (sameVnode(oldStartVnode, newStartVnode)) {
  	// 情况 1️⃣
    patchVnode(...)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
  } else if (sameVnode(oldEndVnode, newEndVnode)) {
  	// 情况 2️⃣
    patchVnode(...)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldStartVnode, newEndVnode)) {
    // Vnode moved right
    // 情况 3️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      )
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
  } else if (sameVnode(oldEndVnode, newStartVnode)) {
    // Vnode moved left
    // 情况 4️⃣
    patchVnode(...)
    canMove &&
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
  } else {
  	// 情况 5️⃣
    if (isUndef(oldKeyToIdx)) // 创建 key -> index 的 Map
      oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) 
    // 找到 新头节点 的下标
    idxInOld = isDef(newStartVnode.key)
      ? oldKeyToIdx[newStartVnode.key]
      : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) {
      // New element
      // 如果没找到
      createElm(...)
    } else {
      // 如果找到了
      vnodeToMove = oldCh[idxInOld]
      if (sameVnode(vnodeToMove, newStartVnode)) {
        patchVnode(...)
        oldCh[idxInOld] = undefined
        canMove &&
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          )
      } else {
        // same key but different element. treat as new element
        createElm(...)
      }
    }
    newStartVnode = newCh[++newStartIdx]
  }
}
if (oldStartIdx > oldEndIdx) {
  // 情况 6️⃣
  refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
  addVnodes(...)
} else if (newStartIdx > newEndIdx) {
  // 情况 7️⃣
  removeVnodes(...)
}

如果问为什么这么比较，回答就是经过很多人很多年的讨论得出的，其实只要记住过程就行了，如果想要更深了解 Diff 算法，可以去 B 站看【尚硅谷】Vue源码解析之虚拟DOM和diff算法

v-for 中为什么要加 key

这个问题面试很常见，但是可能大部分人也就只会背八股，没有完全理解，那么经过以上的介绍，我们可以得到自己的理解：

• 首先，如果不加 key 的话，那么就不会去 Map 里匹配 (O(1))，而是循环遍历整个列表 (O(n))，肯定加 key 要快一点，性能更高
• 其次，如果不加 key 那么在插入或删除的时候就会出现，原本不是同一个节点的元素被认为是相同节点，上面也有说过是 sameVnode 函数判断的，因此可能会有额外 DOM 操作

为什么说可能有额外 DOM 操作呢？这个和插入的地方有关，之后会讨论，同理删除也一样

证明 key 的性能

我们分为三个实验：没有 key、key 为 index、key 唯一，仅证明加了 key 可以进行最小化更新操作。

实验代码

有小伙伴评论说可以把代码贴上这样更好，那么作者就把代码附上 ?：

<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <script src="https://cdn.jsdelivr.net/npm/vue@2/dist/vue.js"></script>
  <style>
    .box {
      display: flex;
      flex-direction: row;
    }
    .item {
      flex: 1;
    }
  </style>
</head>

<body>
  <div id="app">
    <div>
      <div>
        <h3>没有 key</h3>
        <p v-for="(item, index) in list">{{ item }}</p>
      </div>
      <div>
        <h3>key 为 index</h3>
        <p v-for="(item, index) in list" :key="index">{{ item }}</p>
      </div>
      <div>
        <h3>key 唯一</h3>
        <p v-for="(item, index) in list" :key="item">{{ item }}</p>
      </div>
    </div>
    <button @click="click1">push(4)</button>
    <button @click="click2">splice(1, 0, 666)</button>
    <button @click="click3">unshift(999)</button>
    <br /><br />
    <button @click="click4">pop()</button>
    <button @click="click5">splice(1, 1)</button>
    <button @click="click6">shift()</button>
  </div>
  <script>
    var app = new Vue({
      el: &#39;#app&#39;,
      data: {
        show: false,
        list: [1, 2, 3],
      },
      methods: {
        click1() {
          this.list.push(4);
        },
        click2() {
          this.list.splice(1, 0, 666);
        },
        click3() {
          this.list.unshift(999);
        },
        click4() {
          this.list.pop();
        },
        click5() {
          this.list.splice(1, 1);
        },
        click6() {
          this.list.shift();
        }
      },
    })
  </script>
</body>

</html>

增加实验

实验如下所示，我们首先更改原文字，然后点击按钮**「观察节点发生变化的个数」**：

在队尾增加

在队内增加

在队首增加

删除实验

在队尾删除

在队内删除

在队首删除

实验结论

增加实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾增加	1	1	1
在队中增加	n - i + 1	n - i + 1	1
在队首增加	n + 1	n + 1	1

删除实验

表格为每次实验中，每种情况的最小更新量，假设列表原来的长度为 n

实验	没有 key	key 为 index	key 唯一
在队尾删除	1	1	1
在队中删除	n - i	n - i	1
在队首删除	n	n	1

通过以上实验和表格可以得到加上 key 的性能和最小量更新的个数是最小的，虽然在 在队尾增加 和 在队尾删除 的最小更新量相同，但是之前也说了，如果没有 key 是要循环整个列表查找的，时间复杂度是 O(n)，而加了 key 的查找时间复杂度为 O(1)，因此总体来说加了 key 的性能要更好。

写在最后

本文从源码和实验的角度介绍了 Diff 算法，相信大家对 Diff 算法有了更深的了解了，如果有问题可私信交流或者评论区交流，如果大家喜欢的话可以点赞 ➕ 收藏 ?

源码函数附录

列举一些源码中出现的简单函数

setTextContent

function setTextContent(node: Node, text: string) {
  node.textContent = text
}

isUndef

function isUndef(v: any): v is undefined | null {
  return v === undefined || v === null
}

isDef

function isDef<T>(v: T): v is NonNullable<T> {
  return v !== undefined && v !== null
}

insertBefore

function insertBefore(
  parentNode: Node,
  newNode: Node,
  referenceNode: Node
) {
  parentNode.insertBefore(newNode, referenceNode)
}

nextSibling

function nextSibling(node: Node) {
  return node.nextSibling
}

createKeyToOldIdx

function createKeyToOldIdx(children, beginIdx, endIdx) {
  let i, key
  const map = {}
  for (i = beginIdx; i <= endIdx; ++i) {
    key = children[i].key
    if (isDef(key)) map[key] = i
  }
  return map
}

（学习视频分享：vuejs入门教程、编程基础视频）

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!