什么是虚拟DOM

DOM是很慢的，其元素非常庞大，当我们频繁的去做 DOM更新，会产生一定的性能问题，我们可以直观感受一下 div元素包含的海量属性在Javascript对象中，虚拟DOM表现为一个 Object对象（以VNode 节点作为基础的树）。并且最少包含标签名tag、属性attrs和子元素对象children三个属性，不同框架对这三个属性的名命可能会有差别。

  
a
  
b
  
c

真实节点对应的虚拟DOM：

(资料图片仅供参考)

const VDOM = {  tag: "ul",  data: {    style: { color: "#de5e60", border: "1px solid #de5e60" },  },  children: [    {      tag: "li",      key: "a",      data: {},      children: [{ text: "a" }],    },    {      tag: "li",      key: "b",      data: {},      children: [{ text: "b"}],    },    {      tag: "li",      key: "c",      data: {},      children:  [{ text: "c"}],    },  ],}

我们常说虚拟DOM可以提升效率。这句话是不严谨的❌

通过虚拟DOM改变真正的 DOM并不比直接操作 DOM效率更高。恰恰相反，我们仍需要调用DOM API去操作 DOM，并且虚拟DOM还会额外占用内存！but！！！我们可以通过 虚拟DOM+ diff算法，找到需要更新的最小单位，最大限度地减少DOM操作，从而提升性能。

什么是Diff

Dom 是多叉树结构，完整对比两棵树的差异，时间复杂度是O(n³)，这个复杂度会导致比对性能很差！为了优化，Diff 算法约定只做同层级节点比对，而不是跨层级节点比对，即深度优先遍历算法，其复杂度为O(n)

Diff原理

当数据修改后会触发setter劫持操作，我们在setter中执行dep.notity()，通知所有的订阅者watcher重新渲染。订阅者watcher这时会在回调内部，通过vm._render()获取最新的虚拟DOM；然后通过patch方法比对新旧虚拟DOM，给真实元素打补丁，更新视图

createElm

利用vnode创建真实元素，有一个巧妙的地方是，我们把真实元素挂载到了vnode上，便于我们后续通过虚拟节点去操作对应的真实元素

export function createElm(vnode) {  let { tag, data, children, text } = vnode  // 标签  if (typeof tag === "string") {    // 将真实节点挂载到虚拟节点上    vnode.el = document.createElement(tag)     patchProps(vnode.el, {}, data)    children.forEach(child => {      vnode.el.appendChild(createElm(child))    })  } else {    // 文本    vnode.el = document.createTextNode(text)  }  return vnode.el}

sameVnode

判断是否是相同节点，节点的tag和节点的key都相同

export function isSameVnode(vnode1, vnode2) {  return vnode1.tag === vnode2.tag && vnode1.key === vnode2.key}

patch

patch方法有两大作用，一个是初始化元素 ，另一个是更新元素

export function patch(oldVNode, vnode) {  const isRealElement = oldVNode.nodeType  // 初渲染元素  if (isRealElement) {    const elm = oldVNode // 获取真实元素    const parentElm = elm.parentNode // 拿到父元素    let newElm = createElm(vnode) // 根据vnode创建元素    parentElm.insertBefore(newElm, elm.nextSibling) // 插入刚刚创建的元素    parentElm.removeChild(elm) // 删除旧节点    return newElm  } else {    // 更新元素    return patchVnode(oldVNode, vnode)  }}

patchVnode

比对新旧虚拟节点打补丁，diff比对规则如下：

新旧节点不相同（判断节点的tag和节点的key），直接用新节点替换旧节点，无需比对新旧节点相同，且都是文本节点，更新文本内容即可新旧节点是同一个节点，比较两个节点的属性是否有差异，复用旧的节点，将差异的属性更新节点比较完毕后，需要比较两个节点的儿子新旧节点都有儿子，调用updateChildren()，这里是diff算法核心逻辑！后面会详细讲解新节点有儿子，旧节点没有儿子，将新的子节点挂载到oldVNode.el上旧节点有儿子，新节点没有儿子，删除oldVNode.el的所有子节点

function patchVnode(oldVNode, vnode) {  // 1. 新旧节点不相同（判断节点的tag和节点的key），直接用新节点替换旧节点，无需比对  if (!isSameVnode(oldVNode, vnode)) {    let el = createElm(vnode)    oldVNode.el.parentNode.replaceChild(el, oldVNode.el)    return el  }  let el = (vnode.el = oldVNode.el)  // 2. 新旧节点相同，且是文本 (判断节点的tag和节点的key)，比较文本内容  if (!oldVNode.tag) {    if (oldVNode.text !== vnode.text) {      el.textContent = vnode.text // 用新的文本覆盖掉旧的    }  }  // 3. 新旧节点相同，且是标签 (判断节点的tag和节点的key)  // 3.1 比较标签属性  patchProps(el, oldVNode.data, vnode.data)  let oldChildren = oldVNode.children || []  let newChildren = vnode.children || []  // 4 比较两个节点的儿子  // 4.1 新旧节点都有儿子  if (oldChildren.length > 0 && newChildren.length > 0) {    // diff算法核心！！！    updateChildren(el, oldChildren, newChildren)  }  // 4.2 新节点有儿子，旧节点没有儿子，挂载  else if (newChildren.length > 0) {    mountChildren(el, newChildren)  }  // 4.3 旧节点有儿子，新节点没有儿子，删除  else if (oldChildren.length > 0) {    el.innerHTML = ""  }}

updateChildren（Diff核心算法）

这个方法是diff比对的核心！vue2中采用了头尾双指针的方式，通过头头、尾尾、头尾、尾头、乱序五种比对方式，进行新旧虚拟节点的依次比对

在比对过程中，我们需要四个指针，分别指向新旧列表的头部和尾部。为了方便我们理解，我使用了不同颜色和方向的箭头加以区分，图例如下：

双端比对头头比对

旧孩子的头 比对 新孩子的头如果是相同节点，则调用patchVnode打补丁并递归比较子节点；然后将 新旧列表的头指针都向后移动

终止条件：双方有一方头指针大于尾指针，则停止循环

if (isSameVnode(oldStartVnode, newStartVnode)) {  patchVnode(oldStartVnode, newStartVnode)   oldStartVnode = oldChildren[++oldStartIndex]  newStartVnode = newChildren[++newStartIndex]}

尾尾比对

旧孩子的尾 和 新孩子的尾比较如果是相同节点，则调用patchVnode打补丁并递归比较子节点；然后将 新旧列表的尾指针都向前移动

终止条件：双方有一方头指针大于尾指针，则停止循环

else if (isSameVnode(oldEndVnode, newEndVnode)) {  patchVnode(oldEndVnode, newEndVnode)   oldEndVnode = oldChildren[--oldEndIndex]  newEndVnode = newChildren[--newEndIndex]}

头尾比对

旧孩子的头 和 新孩子的尾比较如果是相同节点，则调用patchVnode打补丁并递归比较子节点；然后将 oldStartVnode移动到 oldEndVnode的后面（把 旧列表头指针指向的节点移动到 旧列表尾指针指向的节点后面）最后把 旧列表头指针向后移动，新列表尾指针向前移动

终止条件：双方有一方头指针大于尾指针，则停止循环

else if (isSameVnode(oldStartVnode, newEndVnode)) {  patchVnode(oldStartVnode, newEndVnode)  el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling)  oldStartVnode = oldChildren[++oldStartIndex]  newEndVnode = newChildren[--newEndIndex]}

尾头比对

旧孩子的尾 和 新孩子的头比较如果是相同节点，则调用patchVnode打补丁并递归比较子节点；然后将 oldEndVnode移动到 oldStartVnode的前面（把 旧列表尾指针指向的节点移动到 旧列表头指针指向的节点前面）最后把 旧列表尾指针向前移动，新列表头指针向后移动

终止条件：双方有一方头指针大于尾指针，则停止循环

else if (isSameVnode(oldEndVnode, newStartVnode)) {  patchVnode(oldEndVnode, newStartVnode)  el.insertBefore(oldEndVnode.el, oldStartVnode.el)  oldEndVnode = oldChildren[--oldEndIndex]  newStartVnode = newChildren[++newStartIndex]}

乱序比对

每次比对时，优先进行头头、尾尾、头尾、尾头的比对尝试，如果都没有命中才会进行乱序比较

我们根据旧的列表创建一个 key -> index的映射表，拿新的儿子去映射关系里查找。注意：查找时只能找得到key相同的老节点，并没判断tag若找的到相同key的老节点并且是相同节点，则复用节点移动到 oldStartVnode（旧列表头指针指向的节点）的前面，然后调用 patchVnode打补丁递归比较子节点（移动走的老位置要做空标记，表示这个旧节点已经被移动过了，后续比对时可直接跳过此节点）否则，创建节点并移动到 oldStartVnode（旧列表头指针指向的节点）的前面只需将新列表头指针向后移动即可最后删除老列表中多余的节点，此过程在下一章挂载卸载阶段删除掉

终止条件：双方有一方头指针大于尾指针，则停止循环

----------------- 创建映射关系 -----------------------function makeIndexByKey(children) {  let map = {}  children.forEach((child, index) => {    map[child.key] = index  })  return map}// 旧孩子映射表(key-index)，用于乱序比对let map = makeIndexByKey(oldChildren)-------------------- 乱序比对 -------------------------if (!oldStartVnode) {  oldStartVnode = oldChildren[++oldStartIndex]  continue}if (!oldEndVnode) {  oldEndVnode = oldChildren[--oldEndIndex]  continue}let moveIndex = map[newStartVnode.key]// 找的到相同key的老节点，并且是相同节点if (moveIndex !== undefined && isSameVnode(oldChildren[moveIndex], newStartVnode)) {  let moveVnode = oldChildren[moveIndex] // 复用旧的节点  el.insertBefore(moveVnode.el, oldStartVnode.el) // 将 moveVnode 移动到 oldStartVnode的前面（把复用节点 移动到 旧列表头指针指向的节点 前面）  oldChildren[moveIndex] = undefined // 表示这个旧节点已经被移动过了  patchVnode(moveVnode, newStartVnode) // 递归比较子节点} // 找不到相同key的老节点 or 找的到相同key的老节点但tag不相同else {  el.insertBefore(createElm(newStartVnode), oldStartVnode.el) // 将 创建的节点 移动到 oldStartVnode的前面（把创建的节点 移动到 旧列表头指针指向的节点 前面）}newStartVnode = newChildren[++newStartIndex]

挂载卸载

终止条件：双方有一方头指针大于尾指针，则停止循环。当循环比对结束后，我们需要将新列表中多余的节点插入到oldVNode.el中，并将老列表中多余的节点删除掉。我们将其划分为4种场景，可参考头头比对、尾尾比对章节的图辅助理解

同序列尾部挂载：新列表头指针到 新列表尾指针的节点需要挂载新增，向后追加同序列头部挂载：新列表头指针到 新列表尾指针的节点需要挂载新增，向前追加同序列尾部卸载：旧列表头指针到 旧列表尾指针的节点需要卸载删除同序列头部卸载： 和 同序列尾部卸载 逻辑一致

tip：何时向后追加，何时向前追加，我们根据什么去判断的呢？若 新列表尾指针指向的节点的下一个节点存在，则向前追加，插入到newChildren[newEndIndex + 1].el的前面；若不存在，则向后追加，插入到oldVNode.el子节点列表的末尾处

// 同序列尾部挂载，向后追加// a b c d// a b c d e f// 同序列头部挂载，向前追加//     a b c d// e f a b c dif (newStartIndex <= newEndIndex) {  for (let i = newStartIndex; i <= newEndIndex; i++) {    let childEl = createElm(newChildren[i])    // 这里可能是向后追加 ，也可能是向前追加    let anchor = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].el : null     el.insertBefore(childEl, anchor) // anchor为null的时候等同于 appendChild  }}// 同序列尾部卸载，删除尾部多余的旧孩子// a b c d e f// a b c d// 同序列头部卸载，删除头部多余的旧孩子// e f a b c d//     a b c dif (oldStartIndex <= oldEndIndex) {  for (let i = oldStartIndex; i <= oldEndIndex; i++) {    if (oldChildren[i]) {      let childEl = oldChildren[i].el      el.removeChild(childEl)    }  }}

总结

vue2采用了头尾双指针的方法，每次比对时，优先进行头头、尾尾、头尾、尾头的比对尝试，如果都没有命中才会进行乱序比对

当比对命中时（新旧节点是相同的），则调用patchVnode打补丁并递归比较子节点；打完补丁后呢，如果该节点是头指针指向的节点就向后移动指针，是尾指针指向的节点则向前移动指针终止条件：双方有一方头指针大于尾指针，则停止循环

如果双端比对中的头尾、尾头命中了节点，也需要进行节点移动操作，为什么不直接用乱序比对呢，没理解其优势在哪？但是双端diff相比于简单diff性能肯定会更好一些，例如：从 ABCD到 DABC。简单diff需要移动 ABC 三个节点，但是双端diff只需要移动 D 一个节点

关于简单diff的介绍可移步此文章 - 聊聊 Vue 的双端 diff 算法

tip：vue3中并没有头尾、尾头比对的概念；新增了最长递增子序列算法去优化乱序比对，减少了乱序比对中节点的移动次数

updateChildren 核心代码如下:

function updateChildren(el, oldChildren, newChildren) {  let oldStartIndex = 0  let newStartIndex = 0  let oldEndIndex = oldChildren.length - 1  let newEndIndex = newChildren.length - 1  let oldStartVnode = oldChildren[0]  let newStartVnode = newChildren[0]  let oldEndVnode = oldChildren[oldEndIndex]  let newEndVnode = newChildren[newEndIndex]  function makeIndexByKey(children) {    let map = {}    children.forEach((child, index) => {      map[child.key] = index    })    return map  }  // 旧孩子映射表(key-index)，用于乱序比对  let map = makeIndexByKey(oldChildren)  // 双方有一方头指针大于尾部指针，则停止循环  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {    if (!oldStartVnode) {      oldStartVnode = oldChildren[++oldStartIndex]      continue    }    if (!oldEndVnode) {      oldEndVnode = oldChildren[--oldEndIndex]      continue    }    // 双端比较_1 - 旧孩子的头 比对 新孩子的头；    // 都从头部开始比对（对应场景：同序列尾部挂载-push、同序列尾部卸载-pop）    if (isSameVnode(oldStartVnode, newStartVnode)) {      patchVnode(oldStartVnode, newStartVnode) // 如果是相同节点，则打补丁，并递归比较子节点      oldStartVnode = oldChildren[++oldStartIndex]      newStartVnode = newChildren[++newStartIndex]    }    // 双端比较_2 - 旧孩子的尾 比对 新孩子的尾；    // 都从尾部开始比对（对应场景：同序列头部挂载-unshift、同序列头部卸载-shift）    else if (isSameVnode(oldEndVnode, newEndVnode)) {      patchVnode(oldEndVnode, newEndVnode) // 如果是相同节点，则打补丁，并递归比较子节点      oldEndVnode = oldChildren[--oldEndIndex]      newEndVnode = newChildren[--newEndIndex]    }    // 双端比较_3 - 旧孩子的头 比对 新孩子的尾；    // 旧孩子从头部开始，新孩子从尾部开始（对应场景：指针尽可能向内靠拢；极端场景-reverse）    else if (isSameVnode(oldStartVnode, newEndVnode)) {      patchVnode(oldStartVnode, newEndVnode)      el.insertBefore(oldStartVnode.el, oldEndVnode.el.nextSibling) // 将 oldStartVnode 移动到 oldEndVnode的后面（把当前节点 移动到 旧列表尾指针指向的节点 后面）      oldStartVnode = oldChildren[++oldStartIndex]      newEndVnode = newChildren[--newEndIndex]    }    // 双端比较_4 - 旧孩子的尾 比对 新孩子的头；    // 旧孩子从尾部开始，新孩子从头部开始（对应场景：指针尽可能向内靠拢；极端场景-reverse）    else if (isSameVnode(oldEndVnode, newStartVnode)) {      patchVnode(oldEndVnode, newStartVnode)      el.insertBefore(oldEndVnode.el, oldStartVnode.el) // 将 oldEndVnode 移动到 oldStartVnode的前面（把当前节点 移动到 旧列表头指针指向的节点 前面）      oldEndVnode = oldChildren[--oldEndIndex]      newStartVnode = newChildren[++newStartIndex]    }    // 乱序比对    // 根据旧的列表做一个映射关系，拿新的节点去找，找到则移动；找不到则添加；最后删除多余的旧节点    else {      let moveIndex = map[newStartVnode.key]      // 找的到相同key的老节点，并且是相同节点      if (moveIndex !== undefined && isSameVnode(oldChildren[moveIndex], newStartVnode)) {        let moveVnode = oldChildren[moveIndex] // 复用旧的节点        el.insertBefore(moveVnode.el, oldStartVnode.el) // 将 moveVnode 移动到 oldStartVnode的前面（把复用节点 移动到 旧列表头指针指向的节点 前面）        oldChildren[moveIndex] = undefined // 表示这个旧节点已经被移动过了        patchVnode(moveVnode, newStartVnode) // 比对属性和子节点      }       // 找不到相同key的老节点 or 找的到相同key的老节点但tag不相同      else {        el.insertBefore(createElm(newStartVnode), oldStartVnode.el) // 将 创建的节点 移动到 oldStartVnode的前面（把创建的节点 移动到 旧列表头指针指向的节点 前面）      }      newStartVnode = newChildren[++newStartIndex]    }  }  // 同序列尾部挂载，向后追加  // a b c d  // a b c d e f  // 同序列头部挂载，向前追加  //     a b c d  // e f a b c d  if (newStartIndex <= newEndIndex) {    for (let i = newStartIndex; i <= newEndIndex; i++) {      let childEl = createElm(newChildren[i])      // 这里可能是向后追加 ，也可能是向前追加      let anchor = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].el : null // 获取下一个元素      // el.appendChild(childEl);      el.insertBefore(childEl, anchor) // anchor为null的时候等同于 appendChild    }  }  // 同序列尾部卸载，删除尾部多余的旧孩子  // a b c d e f  // a b c d  // 同序列头部卸载，删除头部多余的旧孩子  // e f a b c d  //     a b c d  if (oldStartIndex <= oldEndIndex) {    for (let i = oldStartIndex; i <= oldEndIndex; i++) {      if (oldChildren[i]) {        let childEl = oldChildren[i].el        el.removeChild(childEl)      }    }  }}

常见问题为什么不建议key用索引

我们先看一段代码。其效果是：当点击按钮后，会在数组前面追加一项数据

/** template代码 */
    
       
        {{item.name}}        
    
    追加
/** js代码 */let vm = new Vue({  el: "#app",  data() {    return {      arr: [{ id: 0, name: "柏成0号" },             { id: 1, name: "柏成1号" },             { id: 2, name: "柏成2号" }]    }  },  methods: {    append() {      this.arr.unshift({        id: 7,        name: "柏成7号"      });    }  }})

index作为key

使用index作为key时，运行结果如下：我们会发现一个神奇的现象，虽然只unshift了一条数据，但是所有的li标签都更新了。并且新增的柏成7号节点还复用了柏成0号节点的checkbox多选框！！！

其原理就是，我们在进行头头比对时，前三项虽然可以匹配到相同节点（标签名和key都相同），但其内容并非一致，所以进行了打补丁更新操作。然后我们又创建一个key为3的柏成2号节点插入到列表尾部

id作为key

使用id作为key时，运行结果如下：这次的diff更新就符合了我们的预期效果，它找到需要更新的最小单位，即只会新增key为3的柏成7号节点，最大限度地减少DOM操作

此时我们在进行尾尾比对时，后三项都可以匹配到相同节点（标签名和key都相同），而且会发现无需更新任何内容。然后去创建一个key为7的柏成7号节点插入列表头部，严格来说是插入新列表头指针下一个虚拟节点对应的真实元素newChildren[newEndIndex + 1].el前面

参考文章

diff 算法深入一下？聊聊 Vue 的双端 diff 算法15张图，20分钟吃透Diff算法核心原理，我说的！！！第三十篇 - diff 算法

标签：