Vue2의 double-ended diff 알고리즘에 대해 이야기하고 노드를 업데이트하는 방법을 살펴보겠습니다!
- 青灯夜游앞으로
- 2022-07-18 19:56:551912검색
이 기사에서는 Vue2의 이중 종료 알고리즘을 이해하고 Vue2가 노드를 업데이트하는 방법에 대해 설명합니다. 모든 사람에게 도움이 되기를 바랍니다.
오늘은 Vue2의 double-ended diff 알고리즘에 대해 이야기하겠습니다. (학습 영상 공유: vue 영상 튜토리얼)
왜 채팅이 필요한가요? 가장 직접적인 이유는 면접관이 키의 역할에 대해 물으면 열에 아홉은 차이점을 언급할 것입니다. 연산.
다른 방법은 없습니다. 면접 때 물어보면 배울 수 있어요. 다행히도 저와 함께 보러 오세요.
공간상의 이유로 이 글에서는 가상 DOM 트리가 생성되는 방법을 소개하지 않습니다. 두 개의 가상 DOM 트리를 비교하고 데이터가 업데이트될 때 실제 DOM을 업데이트하는 방법만 설명합니다. 주로 patchVnode, <code>updateChildren 함수patchVnode、updateChildren 函数
预备知识
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 <p>以及三个工具函数</p><pre class="brush:php;toolbar:false">// 判断是否未定义
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 <p>4、新旧节点都有子节点。调用 <code>updateChildren</code></p><h2 data-id="heading-1">사전 지식</h2><p></p><h3 data-id="heading-2"> diff 알고리즘 기능 </h3><p></p>diff 알고리즘에 대해 이야기하기 전에 그것이 무엇을 하는지 이해해야 합니다. <p></p>우리는 웹페이지가 실행될 때 일부 데이터를 변경하여 DOM 트리에 영향을 미칠 수 있다는 것을 알고 있습니다. 페이지에 최신 데이터를 표시하는 방법은 무엇입니까? 가장 간단한 방법은 전체 트리를 푸시하여 다시 빌드하는 것입니다. 물론 이렇게 하면 많은 낭비가 발생하므로 Vue는 가상 DOM을 사용하여 페이지에 DOM 트리의 상태를 저장합니다. 데이터가 변경된 후 새 가상 DOM 트리를 생성하고 두 트리 간의 차이점을 찾아 목표 방식으로 실제 DOM을 업데이트합니다. <p><strong>두 트리의 차이점을 찾고 DOM 요소의 파괴 및 재구성을 줄이는 방법이 diff 알고리즘의 역할입니다</strong></p><h3 data-id="heading-3">Virtual DOM</h3><p></p>Virtual 가상 노드(vnode)라고도 알려진 DOM은 단순히 DOM 요소 정보를 포함하는 객체입니다. 일반적으로 <code>h</code> 함수에 의해 생성됩니다. 다음 객체는 가상 노드<p></p><pre class="brush:php;toolbar:false">if (isDef(oldCh) && isDef(newCh)) {
updateChildren(elm, oldCh, newCh)
}로 간주할 수 있습니다. 이 단락 HTML// 三个参数为：父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)
}
}
}을 vnode로 변환하는 방법은 다음과 같습니다// 比较节点的数据及子节点，并且将旧节点的DOM赋给新节点 patchVnode(newStartVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx]가상 노드를 통해 실제 DOM을 작동해야 하기 때문에 vnode에는 실제 DOM 요소를 가리키는 elm 속성이 있습니다. 그리고 후속 diff 알고리즘에서는 노드를 고유하게 식별하는 데 키가 사용되므로 아래의 vnode는 이러한 객체🎜
patchVnode(newEndVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx]🎜Vue의 가상 노드에도 많은 속성이 있지만 diff 알고리즘과 관련이 없습니다.
🎜은 가상 노드의 텍스트와 하위 항목이 동시에 값을 가질 수 없음을 지적합니다. children 속성의 경우 텍스트의 내용은 텍스트 노드로 변환되어 children 배열🎜
🎜준비 함수🎜
🎜에 배치됩니다. 나중에 코드 구현을 더 쉽게 하기 위해 몇 가지 함수를 준비했습니다. 함수는 어렵지 않으니 코드를 직접 붙여넣으면 됩니다🎜🎜가장 먼저 필요한 것은 가상 노드를 실제 DOM으로 변환하는 함수🎜parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)🎜와 세 가지 도구 기능🎜
patchVnode(newEndVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx]🎜patchVnode🎜🎜데이터가 업데이트되면 Vue는 새 vnode를 생성한 다음
patchVnode 함수를 실행합니다. 새 가상 노드와 이전 가상 노드를 비교한 다음 상황에 따라 처리합니다🎜parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)🎜먼저 이전 가상 노드와 새 가상 노드가 동일한 개체인지 확인합니다. 그렇다면 처리할 필요가 없습니다🎜
patchVnode(newStartVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx]🎜 이전 노드의 DOM 요소를 새 노드에 할당하고 이전 노드와 새 노드의 데이터를 가져옵니다. patchVnode를 호출하는 이전 노드와 새 노드의 태그와 키가 여기에 직접 할당될 수 있습니다. 이는 아래에서 설명하겠습니다🎜🎜 그런 다음 두 노드의 내용을 기반으로 DOM을 업데이트하는 방법을 결정합니다🎜🎜1. 이전 노드와 새 노드 각 노드의 내용은 텍스트입니다. 텍스트를 수정하세요🎜
// 以下出自 v2 源码 var needsKey = !!el.if …… needsKey ? ',null,false,' + hash(generatedSlots) : ''🎜2. 이전 노드에는 하위 노드가 있고 새 노드의 내용은 텍스트입니다. 이전 노드 콘텐츠를 지우고 text🎜rrreee🎜로 변경합니다. 3. 이전 노드 콘텐츠는 텍스트이고 새 노드에는 하위 노드가 있습니다. 이전 노드의 콘텐츠를 지우고 새 노드를 탐색하여 하위 DOM 요소를 생성한 후 노드에 삽입합니다🎜rrreee🎜4. 이전 노드와 새 노드에는 하위 노드가 있습니다. 이를 처리하려면
updateChildren을 호출하세요. 이 함수는 다음 장에서 설명하겠습니다🎜rrreee🎜사례 4는 사례 3과 동일한 방식으로 처리할 수 있으며, 이전 노드를 지운 다음 순회하여 새 노드를 생성합니다. DOM. 하지만 DOM 요소를 생성하는 것은 시간이 많이 걸리는 작업이며, 이전 하위 노드와 새 하위 노드가 대부분 동일하다는 점을 알아야 합니다. 재사용할 수 있다면 성능이 크게 최적화될 것입니다. 🎜🎜그렇다면 노드를 재사용할 수 있는지 어떻게 판단할 수 있나요? 🎜🎜이를 위해서는 Vue 사용자의 도움이 필요합니다. 사용자는 어떤 노드를 재사용할 수 있는지 Vue에 알리기 위해 노드의 키 속성을 정의해야 합니다.🎜🎜🎜레이블 유형과 키 값이 동일하다면 현재 요소를 재사용할 수 있다는 뜻입니다🎜 🎜🎜 그런데 저희 프로젝트에서는 일반적으로 v-for에만 키가 설정되어 있고, 다른 노드에는 키가 설정되어 있지 않습니다🎜🎜실제로🎜키가 설정되지 않은 노드는 기본적으로 키 값이 동일합니다🎜🎜🎜이것은 또한 프로젝트의 대부분의 요소는 재사용이 가능합니다. v-for에 의해 생성된 하위 요소만 의존하는 배열에 복잡한 변경 사항이 있을 수 있으므로 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，旧前与新前(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
作者：清隆
위 내용은 Vue2의 double-ended diff 알고리즘에 대해 이야기하고 노드를 업데이트하는 방법을 살펴보겠습니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!