vue2 虚拟DOM 和 真实DOM （概念、作用、Diff 算法）

虚拟 DOM 和 真实DOM（概念、作用、Diff 算法）

1.1 概念
真实 DOM（Document Object Model）：是浏览器中用于表示文档结构的树形结构。

<h2>你好</h2>

虚拟DOM：用 JavaScript 对象来模拟真实 DOM 的结构

{children: undefineddata: {}elm: h1key: undefinedsel: "h1"text: "你好h1"
}

步骤
1.用JS对象表示真实的DOM结构，生成一个虚拟DOM，再用虚拟DOM构建一个真实DOM树，渲染到页面
2.状态改变生成新的虚拟DOM，与旧的虚拟DOM进行比对，比对的过程就是DIFF算法，利用patch记录差异
3.把记录的差异用在第一个虚拟DOM生成的真实DOM上，视图就更新了。

（Vue.js 在早期开发过程中借鉴了 Snabbdom 的设计理念来构建自己的虚拟 DOM 系统）

1.2 作用

性能优化方面

真实DOM

• 当直接操作真实 DOM 时，比如频繁地添加、删除或修改节点，会引起浏览器的重排（reflow）和重绘（repaint）。
• 重排： DOM 结构的改变导致浏览器重新计算元素的几何属性，如位置、大小等；
• 重绘：元素的外观发生改变，如颜色、背景等变化，只是重新绘制外观而不涉及布局调整。

虚拟DOM

• 通过一种高效的 Diff 算法比较新旧虚拟 DOM 树的差异，可以快速地找出需要更新的部分，而不是每次都对整个 DOM 进行重新渲染。
• 虚拟 DOM 的操作在 JavaScript 层面进行，比直接操作真实 DOM 快得多
• 当组件的数据发生变化时，Vue.js 会收集一段时间内的数据变化，然后统一进行虚拟 DOM 的更新和差异比较，并根据差异更新真实 DOM，避免大量的无谓计算。

1.1 Diff 算法（源码地址）

它的主要作用是比较新数据与旧数据虚拟 DOM 树的差异，从而找出需要更新的部分，以便将这些最小化的变更应用到真实 DOM上，减少不必要的 DOM 操作，提高性能。

• 树diff的时间复杂度O（n^3）
  第一，遍历tree1；第二，遍历tree2 第三，排序 1000个节点，要计算1亿次，算法不可用
• 优化时间复杂度到O（n）
  只比较同一层级，不跨级比较
  tag不相同，直接删掉重建，不再深度比较
  tag和key，两者都相同，则认为是相同的节点，不再深度比较

1. 首先sameVNode 比较一下新旧节点是不是同一个节点（同级对比，不跨级）

下图比较第二层级的右侧，左边是P，右边是div， 那么会认为这两个节点完全不同，直接删除旧的p替换新的div。

因为 dom 节点做跨层级移动的情况还是比较少的，一般情况下都是同一层级的 dom 的增删改。
但是 diff 算法除了考虑本身的时间复杂度之外，还要考虑一个因素：dom 操作的次数。
如果是一个list数组，新旧节点只是前后顺序的改变，直接删除新增，dom渲染成本会增加。

2.当节点类型相同的时候，Diff 算法会比较节点的属性是否有变化。如果属性有变化，就更新真实 DOM 节点的属性。

例如input节点，旧虚拟 DOM 中的value属性为abc，新虚拟 DOM 中的value属性为def，Diff 算法会更新真实 DOM 中input节点的value属性。

3.当节点类型，属性都相同，则比较是否存在子节点，

4.如果新节点和老节点都有子节点，需要进一步比较（双端diff核心updateChildren）

• diff 算法我们从一端逐个处理的，叫做简单 diff 算法。简单 diff 算法其实性能不是最好的，比如旧的 vnode 数组是 ABCD，新的 vnode 数组是 DABC，按照简单 diff 算法，A、B、C 都需要移动。

那怎么优化这个算法呢？

• vue使用的是双端 diff 算法：是头尾指针向中间移动，分别判断头尾节点是否可以复用，如果没有找到可复用的节点再去遍历查找对应节点的下标，然后移动。全部处理完之后也要对剩下的节点进行批量的新增和删除。

后来，Vue3 又对 diff 算法进行了一次升级，叫做快速 diff 算法（后续补充）。

双端diff算法updateChildren 逻辑

先贴代码，然后解释代码的含义(部分调用方法代码 放在最后面)

function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {var oldStartIdx = 0; // 旧子节点start下标(游标)var newStartIdx = 0; // 新子节点start下标(游标)var oldEndIdx = oldCh.length - 1; // 旧子节点end下标(游标)var newEndIdx = newCh.length - 1; // 新子节点end下标(游标)var oldStartVnode = oldCh[0]; // 旧start节点(旧头)var newStartVnode = newCh[0]; // 新start节点(新头)var oldEndVnode = oldCh[oldEndIdx]; // 旧end节点(旧尾)var newEndVnode = newCh[newEndIdx]; // 新end节点(新尾)var oldKeyToIdx, idxInOld, vnodeToMove, refElm;var canMove = !removeOnly;checkDuplicateKeys(newCh);// 旧头子节点大于旧尾子节点，或者新头子节点大于新尾子节点时候跳出循环while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {if (isUndef(oldStartVnode)) {// 旧头不存在，oldStartIdx++oldStartVnode = oldCh[++oldStartIdx]; } else if (isUndef(oldEndVnode)) {// 旧尾不存在，oldEndIdx--oldEndVnode = oldCh[--oldEndIdx];// sameVnode key相同，tag相同...都相同} else if (sameVnode(oldStartVnode, newStartVnode)) {// 旧头、新头相同，调用 patchVnode 进行更新节点（如果有子节点，继续调用updateChildren，diff查找子节点新旧dom不同），// 旧头右移一位oldStartVnode++、新头右移一位newStartVnode++patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);oldStartVnode = oldCh[++oldStartIdx];newStartVnode = newCh[++newStartIdx];} else if (sameVnode(oldEndVnode, newEndVnode)) {// 旧尾、新尾相同，patchVnode更新节点，旧尾左移一位oldEndIdx--、新尾左移一位newEndIdx--patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);oldEndVnode = oldCh[--oldEndIdx];newEndVnode = newCh[--newEndIdx];} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right// 旧头、新尾相同，patchVnode更新节点，并且将旧头移到oldCh最后，旧头右移一位 oldStartIdx++、新尾左移一位newEndIdx--patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx);canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm));oldStartVnode = oldCh[++oldStartIdx];newEndVnode = newCh[--newEndIdx];} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left// 旧尾、新头相同，patchVnode更新节点，并且将旧尾移到oldCh最前面，新头右移一位 newStartIdx++、旧尾左移一位oldEndIdx--patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);oldEndVnode = oldCh[--oldEndIdx];newStartVnode = newCh[++newStartIdx];} else {// Undef 判断未定义if (isUndef(oldKeyToIdx)) { oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx); }// isDef 判断新节点是否有key值唯一标示idxInOld = isDef(newStartVnode.key)? oldKeyToIdx[newStartVnode.key] //去旧oldCh 里面找是否有一样的key: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);// 在oldCh列表中查找与newStartVnode匹配的节点索引,如果节点相同，返回索引if (isUndef(idxInOld)) {   // 遍历发现oldCh列表中没有和新节点相同的节点，创建新节点createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);} else { // 遍历发现oldCh列表中有和新节点key相同的节点vnodeToMove = oldCh[idxInOld];//进一步判断是否相等if (sameVnode(vnodeToMove, newStartVnode)) {// 相同，继续往下层判断更新节点patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx);// 被移动的位置 undefined 占位 所以循环开头会增加isUndef 的判断oldCh[idxInOld] = undefined;// 将更改后的节点 移动位置canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm);} else {// 节点不同，新建节点createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx);}}newStartVnode = newCh[++newStartIdx];}}if (oldStartIdx > oldEndIdx) {// 旧子节点先遍历完，新子节点还有剩，调用addVnodes添加节点refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm;addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);} else if (newStartIdx > newEndIdx) {// 新子节点先遍历完，旧子节点还有剩，调用removeVnodes删除节点removeVnodes(oldCh, oldStartIdx, oldEndIdx);}
} 

开启一个循环，循环的条件就是 oldStart 不能大于oldEnd ，newStart不能大于newEnd，以下是循环的重要判断

• 跳过undefined **if (isUndef(oldStartVnode))**

为什么会有undefined，老节点移动过程中，会产生undefined占位，之后的流程图会说明清楚。这里只要记住，如果旧开始节点为undefined，就后移一位；如果旧结束节点为undefined，就前移一位。

• 快捷对比（https://www.jianshu.com/p/b9916979a740）**4个 else if（sameVnode(xxx)）**

1 新开始和旧开始节点比对 如果匹配，表示它们位置都是对的，Dom不用改，就将新、旧节点开始的下标往后移一位即可。

2 旧结束和新结束节点比对 如果匹配，也表示它们位置是对的，Dom不用改，就将新、旧节点结束的下标前移一位即可。

3 旧开始和新结束节点比对 如果匹配，位置不对需要更新Dom视图，将旧开始节点对应的真实Dom插入到最后一位，旧开始节点下标后移一位，新结束节点下标前移一位。

4 旧结束和新开始节点比对 如果匹配，位置不对需要更新Dom视图，将旧结束节点对应的真实Dom插入到旧开始节点对应真实Dom的前面，旧结束节点下标前移一位，新开始节点下标后移一位。

• key值查找（2.快捷对比都不满足的情况下） **}else {**

将旧节点数组剩余的vnode（oldStartIdx到oldEndIdx之间的节点）进行一次遍历，生成由vnode.key作为键，idx索引作为值的对象oldKeyToIdx，然后遍历新节点数组的剩余vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的key在oldKeyToIdx进行查找。

1 找到相同的key

• 如果和已有key值匹配 那就说明是已有的节点，只是位置不对，则将找到的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将旧节点数组中 idxInOld 对应的元素设置为 undefined。
• 如果和已有key值不匹配，那就说明是新的节点，那就创建一个对应的真实Dom节点，插入到旧开始节点对应的真实Dom前面即可

2 没有相同key

• 没有找到对应的索引，则直接createElm创建新的dom节点并将新的vnode插入 oldStartIdx 对应的 vnode 之前。

以上是while内部处理，以下是while外部处理

• 剩余元素处理（不满足循环条件后退出，循环外处理剩余元素）循环外

• 旧节点数组遍历结束、新节点数组仍有剩余，经过两端对比查找都没有查找到，则说明新插入内容是处于 oldstartIdx与 oldEndIdx 之间的，所以可以直接在 newEndIdx 对应的 vnode 之前创建插入新节点即可。
• 新节点数组遍历结束、旧节点数组仍有剩余，则遍历旧节点oldStartIdx 到 oldEndIdx 之间的剩余数据，进行移除
  因为旧节点oldStartIdx之前的数据和 oldEndIdx之后的数据都是对比确认之后的，且数量与新节点数组相同，则中间剩下的都是要删除的节点

以上便是vue2的diff的核心流程了，通过一个例子再来感受一下：

在每个循环单元中，我们执行下面的策略：

• 分支0：旧头遇到空，指针向右移动 / 旧尾不存在，指针向左移动

• 分支1：比较oldStart和newStart是否一致，如果一致，两个指针向右移动即可

• 分支2：比较oldEnd和newEnd是否一致，如果一致，两个指针向左移动即可

• 分支3：比较oldStart和newEnd是否一致，如果一致，就需要移动节点，移动节点都针对old的操作，将旧开始节点对应的真实Dom插入到oldEnd后面，oldStart节点下标后移一位，newEnd节点下标前移一位。

• 分支4：比较newStart和oldEnd是否一致，如果一致，就需要移动节点，将oldEnd移动到oldStart的前一个。

• 分支5：如果以上都没有命中，看看newStart是否在old中存在，如果存在，找到是第几个，假设是在old中的第i个位置，接下来将第i个位置的元素移动到oldStart的前一位，然后将当前第i位置空（所以会存在undef校验）。如果不存在说明创建了一个新的元素，需要执行创建策略。

循环1：
第一步：A不等于B ，未命中分支1
第二步：D不等于C， 未命中分支2
第三步：A不等于C ，未命中分支3
第四步：B不等于D，未命中分支4
第五步：进入分支5，newStart在old中是否存在，执行之前的key值查找：

第一轮循环结束：oldStart指向A，oldEnd指向D，newStart指向A，newEnd指向C

循环2
第一步：判断 A 等于 A，命中分支1，指针都向右移动。

第二轮循环结束：oldStart指向空，oldEnd指向D，newStart指向D，newEnd指向C

循环3： 第一步：oldStart遇到空，命中分支0，指针向右移动，oldStart指向C。

第3轮循环结束 oldStart指向C ，oldEnd指向D，newStart指向D，newEnd指向C

![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/f47f810ae9f644fb85865b48b5813203.png

循环4
第一步：判断 D不等于C，未命中分支1
第二步：判断C不等于D，未命中分支2。
第三步：判断C等于C，命中分支3，将oldStart向oldEnd下一个移动，oldStart++。

第4轮循环结束：oldStart指向D，oldEnd指向D，newStart指向D，newEnd指向C。

循环5 第一步：判断 D等于D ，命中分支1，指针向右移动，oldStart++。

第5轮循环结束：oldStart指向C，oldEnd指向D，newStart指向C，newEnd指向C。

这时候循环已经结束，因为oldStart已经大于oldEnd。

当前的案例已经结束，old已经在相对次序上和new一模一样了，虽然在数据结构上有两个空在那里，而实际上的DOM结构已经移动到了正确的位置上，空对应在DOM上就是什么都没有，所以这个移动是正确的

如果 循环退出后，新节点数组仍有剩余 或者 旧节点数组仍有剩余 两者只有一种情况
接着以上的案例：

• 旧节点数组遍历结束、新节点数组仍有剩余，经过两端对比查找都没有查找到，则说明新插入内容是处于 oldstartIdx与 oldEndIdx 之间的，所以可以直接在 newEndIdx 对应的 vnode 之前创建插入新节点即可。
• 新节点数组遍历结束、旧节点数组仍有剩余，则遍历旧节点oldStartIdx 到 oldEndIdx 之间的剩余数据，进行移除
  因为旧节点oldStartIdx之前的数据和 oldEndIdx之后的数据都是对比确认之后的，且数量与新节点数组相同，则中间剩下的都是要删除的节点

部分调用函数代码简化版
isSameVnode简化版：

// asyncFactory 异步组件  isComment 注释节点
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))))
}

patchVnode简化版：将新节点的状态更新到旧节点对应的真实 DOM 节点上

function patchVnode(oldVnode, newVnode) {// 如果新旧节点是同一个对象，直接返回，无需更新if (oldVnode === newVnode) {return;}// 获取新旧节点对应的真实DOM元素const elm = oldVnode.elm;// 1. 更新属性部分const oldProps = oldVnode.data && oldVnode.data.attrs;const newProps = newVnode.data && newVnode.data.attrs;// 遍历新节点属性来更新或添加属性到真实DOM元素上for (let key in newProps) {//...}// 移除旧节点有但新节点没有的属性for (let key in oldProps) {//...}// 2. 更新子节点部分const oldChildren = oldVnode.children;const newChildren = newVnode.children;// 新旧子节点都是文本节点的情况，直接更新文本内容if (typeof oldChildren ==='string' && typeof newChildren ==='string') {if (oldChildren!== newChildren) {elm.textContent = newChildren;}} else if (Array.isArray(oldChildren) && Array.isArray(newChildren)) {// 继续updateChildren 处理ChildrenupdateChildren(elm, oldChildren, newChildren); }
}

findIdxInOld简化版:新节点在旧节点列表中查找是否有相同的

function findIdxInOld(newVnode, oldCh, start, end) {for (let i = start; i <= end; i++) {let oldVnode = oldCh[i];if (sameVnode(newVnode, oldVnode)) {// 如果节点相同（通过key和标签...判断），返回索引return i;}}return -1;
}

双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作，新旧数组均只需要进行一次遍历即可将所有节点进行对比。

Snabbdom 待完善

本文参考文章
https://www.jb51.net/javascript/2968153yn.htm
https://www.zzsucai.com/biancheng/24014.html
https://news.sohu.com/a/564921201_121124376