이 기사에서는 Vue2의 이중 종료 알고리즘을 이해하고 Vue2가 노드를 업데이트하는 방법에 대해 설명합니다. 모든 사람에게 도움이 되기를 바랍니다.
오늘은 Vue2의 double-ended diff 알고리즘에 대해 이야기하겠습니다. (학습 영상 공유: vue 영상 튜토리얼)
왜 채팅이 필요한가요? 가장 직접적인 이유는 면접관이 키의 역할에 대해 물으면 열에 아홉은 차이점을 언급할 것입니다. 연산.
다른 방법은 없습니다. 면접 때 물어보면 배울 수 있어요. 다행히도 저와 함께 보러 오세요.
공간상의 이유로 이 글에서는 가상 DOM 트리가 생성되는 방법을 소개하지 않습니다. 두 개의 가상 DOM 트리를 비교하고 데이터가 업데이트될 때 실제 DOM을 업데이트하는 방법만 설명합니다. 주로 patchVnode, <code>updateChildren
함수patchVnode
、updateChildren
函数
聊 diff 算法前得认识一下它是干嘛的。
我们知道在网页运行中,我们改变一些数据,它们可能会影响到 DOM 树。如何在页面中展示最新的数据呢,最简单的方式就是整棵树推到重建,当然这样会导致大量的浪费,所以 Vue 使用虚拟 DOM 保存页面中 DOM 树的状态,在数据变化后,构建一棵新的虚拟 DOM 树,找到前后两颗树的不同之处,针对性地更新真实 DOM。
而如何找到两颗树的不同之处,减少 DOM 元素的销毁与重建,就是 diff 算法的作用
虚拟 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 }
当数据更新后,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
두 트리의 차이점을 찾고 DOM 요소의 파괴 및 재구성을 줄이는 방법이 diff 알고리즘의 역할입니다
h
함수에 의해 생성됩니다. 다음 객체는 가상 노드if (isDef(oldCh) && isDef(newCh)) { updateChildren(elm, oldCh, newCh) }
// 三个参数为:父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) } } }
// 比较节点的数据及子节点,并且将旧节点的DOM赋给新节点 patchVnode(newStartVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newStartVnode = newCh[++newStartIdx]
patchVnode(newEndVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newEndVnode = newCh[--newEndIdx]
🎜은 가상 노드의 텍스트와 하위 항목이 동시에 값을 가질 수 없음을 지적합니다. children 속성의 경우 텍스트의 내용은 텍스트 노드로 변환되어 children 배열🎜
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
patchVnode(newEndVnode, oldStartVnode) oldStartVnode = oldCh[++oldStartIdx] newEndVnode = newCh[--newEndIdx]
patchVnode
함수를 실행합니다. 새 가상 노드와 이전 가상 노드를 비교한 다음 상황에 따라 처리합니다🎜parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
patchVnode(newStartVnode, oldEndVnode) oldEndVnode = oldCh[--oldEndIdx] newStartVnode = newCh[++newStartIdx]
// 以下出自 v2 源码 var needsKey = !!el.if …… needsKey ? ',null,false,' + hash(generatedSlots) : ''
updateChildren
을 호출하세요. 이 함수는 다음 장에서 설명하겠습니다🎜rrreee🎜사례 4는 사례 3과 동일한 방식으로 처리할 수 있으며, 이전 노드를 지운 다음 순회하여 새 노드를 생성합니다. DOM. 하지만 DOM 요소를 생성하는 것은 시간이 많이 걸리는 작업이며, 이전 하위 노드와 새 하위 노드가 대부분 동일하다는 점을 알아야 합니다. 재사용할 수 있다면 성능이 크게 최적화될 것입니다. 🎜🎜그렇다면 노드를 재사용할 수 있는지 어떻게 판단할 수 있나요? 🎜🎜이를 위해서는 Vue 사용자의 도움이 필요합니다. 사용자는 어떤 노드를 재사용할 수 있는지 Vue에 알리기 위해 노드의 키 속성을 정의해야 합니다.🎜🎜🎜레이블 유형과 키 값이 동일하다면 현재 요소를 재사용할 수 있다는 뜻입니다🎜 🎜🎜 그런데 저희 프로젝트에서는 일반적으로 v-for에만 키가 설정되어 있고, 다른 노드에는 키가 설정되어 있지 않습니다🎜🎜실제로🎜키가 설정되지 않은 노드는 기본적으로 키 값이 동일합니다🎜🎜🎜이것은 또한 프로젝트의 대부분의 요소는 재사용이 가능합니다. v-for에 의해 생성된 하위 요소만 의존하는 배열에 복잡한 변경 사항이 있을 수 있으므로 Vue 노드 재사용을 돕기 위해 키 값을 명확하게 표시해야 합니다. 가능한 한 많이. 🎜patchVnode 的内容当然不止这些,还有样式、类名、props等数据的对比更换,篇幅原因本文将其省略了。
好了,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 算法就讲完了
学完 diff 算法,再聊聊 key 的作用
上面讲的都是有 key 情况下,diff 算法能够迅速找到新旧序列中的同一节点,以较小的代价完成更新。
而如果在 v-for 中不设置 key 呢?
假设我们在数组头部插入了一个新节点,然后开始循环,每次循环都命中情况 1,尝试“复用”此节点。
但是,在对比新旧节点的内容时,都会发现内容不同,需要用新节点的内容替换旧节点。这只是复用了 DOM 的外壳,节点的内容、数据以及该节点的子节点全都要更改。
相比有 key 时的只添加一个新节点,无 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 发生变化时,会导致 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!