面试进阶核心，10张图，带你吃透 “Diff” 算法核心原理（图文详解）_diff算法原理

虚拟 DOM 与 Diff 算法

什么是虚拟DOM

虚拟DOM是一个对象，一个什么样的对象呢？一个用来表示真实DOM的对象，要记住这句话。我举个例子，请看以下真实DOM：

<ul id="list">
    <li class="item">哈哈</li>
    <li class="item">呵呵</li>
    <li class="item">嘿嘿</li>
</ul>

1
2
3
4
5
6

对应的虚拟DOM为：

let oldVDOM = { // 旧虚拟DOM
        tagName: 'ul', // 标签名
        props: { // 标签属性
            id: 'list'
        },
        children: [ // 标签子节点
            {
                tagName: 'li', props: { class: 'item' }, children: ['哈哈']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['呵呵']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['嘿嘿']
            },
        ]
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这时候，我修改一个li标签的文本：

<ul id="list">
    <li class="item">哈哈</li>
    <li class="item">呵呵</li>
    <li class="item">哈哈哈哈哈</li> // 修改
</ul>

1
2
3
4
5
6

这时候生成的新虚拟DOM为：

let newVDOM = { // 新虚拟DOM
        tagName: 'ul', // 标签名
        props: { // 标签属性
            id: 'list'
        },
        children: [ // 标签子节点
            {
                tagName: 'li', props: { class: 'item' }, children: ['哈哈']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['呵呵']
            },
            {
                tagName: 'li', props: { class: 'item' }, children: ['哈哈哈哈哈']
            },
        ]
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这就是咱们平常说的新旧两个虚拟DOM，这个时候的新虚拟DOM是数据的最新状态，那么我们直接拿新虚拟DOM去渲染成真实DOM的话，效率真的会比直接操作真实DOM高吗？那肯定是不会的，看下图：

可以看到，虚拟DOM渲染成页面还需要经过一层转化虚拟DOM的步骤，那明显消耗要大于直接转化为真实DOM的方式，那么为什么又要需要转化虚拟DOM呢？所以虚拟DOM比真实DOM快这句话其实是错的，或者说是不严谨的。那正确的说法是什么呢？虚拟DOM算法操作真实DOM，性能高于直接操作真实DOM，虚拟DOM和虚拟DOM算法是两种概念。虚拟DOM算法 = 虚拟DOM + Diff算法

什么是Diff算法

Diff算法是一种对比算法。对比两者是旧虚拟DOM和新虚拟DOM，对比出是哪个虚拟节点更改了，找出这个虚拟节点，并只更新这个虚拟节点所对应的真实节点，而不用更新其他数据没发生改变的节点，实现精准地更新真实DOM，进而提高效率。

使用虚拟DOM算法的损耗计算： 总损耗 = 虚拟DOM增删改+（与Diff算法效率有关）真实DOM差异增删改+（较少的节点）排版与重绘

直接操作真实DOM的损耗计算： 总损耗 = 真实DOM完全增删改+（可能较多的节点）排版与重绘

Diff算法的原理

Diff同层对比

新旧虚拟DOM对比的时候，Diff算法比较只会在同层级进行, 不会跨层级比较。 所以Diff算法是:深度优先算法。 时间复杂度:O(n)

Diff对比流程

当数据改变时，会触发setter，并且通过Dep.notify去通知所有订阅者Watcher，订阅者们就会调用patch方法，给真实DOM打补丁，更新相应的视图。

newVnode和oldVnode：同层的新旧虚拟节点

patch方法

这个方法作用就是，对比当前同层节点的虚拟节点是否为同一种类型的标签（同一类型的标准，下面会讲）：

• 是：进行执行 patchVnode方法 进行深层对比
• 否：不进行对比，直接整个节点替换成新虚拟节点

看看 patch 的核心原理代码

function patch(oldVnode, newVnode) {
  // 比较是否为一个类型的节点
  if (sameVnode(oldVnode, newVnode)) {
    // 是：继续进行深层比较
    patchVnode(oldVnode, newVnode)
  } else {
    // 否
    const oldEl = oldVnode.el // 旧虚拟节点的真实DOM节点
    const parentEle = api.parentNode(oldEl) // 获取父节点
    createEle(newVnode) // 创建新虚拟节点对应的真实DOM节点
    if (parentEle !== null) {
      api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
      api.removeChild(parentEle, oldVnode.el)  // 移除以前的旧元素节点
      // 设置null，释放内存
      oldVnode = null
    }
  }

  return newVnode
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

sameVnode方法

patch 关键的一步就是，判断sameVnode方法判断是否为同一类型节点，看看核心代码，如何判断同一类型节点

function sameVnode(oldVnode, newVnode) {
  return (
    oldVnode.key === newVnode.key && // key值是否一样
    oldVnode.tagName === newVnode.tagName && // 标签名是否一样
    oldVnode.isComment === newVnode.isComment && // 是否都为注释节点
    isDef(oldVnode.data) === isDef(newVnode.data) && // 是否都定义了data
    sameInputType(oldVnode, newVnode) // 当标签为input时，type必须是否相同
  )
}
1
2
3
4
5
6
7
8
9

patchVnode方法

当为同一节点时，会调用 patchVnode方法进行逐层的对比

这个函数做了以下事情：

• 找到对应的 oldVnode，真实DOM ，称为 el
• 判断 newVnode 和 oldVnode 是否指向同一个对象，如果时，那么直接返回 return
• 如果他们都有文本节点并且不相等，那么将el的文本节点设置为newVnode的文本节点。
• 如果oldVnode有子节点而newVnode没有，则删除el的子节点
• 如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el
• 如果两者都有子节点，则执行updateChildren函数比较子节点，这一步很重要

function patchVnode(oldVnode, newVnode) {
  const el = newVnode.el = oldVnode.el // 获取真实DOM对象
  // 获取新旧虚拟节点的子节点数组
  const oldCh = oldVnode.children, newCh = newVnode.children
  // 如果新旧虚拟节点是同一个对象，则终止
  if (oldVnode === newVnode) return
  // 如果新旧虚拟节点是文本节点，且文本不一样
  if (oldVnode.text !== null && newVnode.text !== null && oldVnode.text !== newVnode.text) {
    // 则直接将真实DOM中文本更新为新虚拟节点的文本
    api.setTextContent(el, newVnode.text)
  } else {
    // 否则

    if (oldCh && newCh && oldCh !== newCh) {
      // 新旧虚拟节点都有子节点，且子节点不一样

      // 对比子节点，并更新
      updateChildren(el, oldCh, newCh)
    } else if (newCh) {
      // 新虚拟节点有子节点，旧虚拟节点没有

      // 创建新虚拟节点的子节点，并更新到真实DOM上去
      createEle(newVnode)
    } else if (oldCh) {
      // 旧虚拟节点有子节点，新虚拟节点没有

      //直接删除真实DOM里对应的子节点
      api.removeChild(el)
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

其他几个点都很好理解，我们详细来讲一下updateChildren

updateChildren方法

这是 patchVnode里最重要的一个方法，新旧虚拟节点的子节点对比，就是发生在 updateChildren方法 中

是怎么样一个对比方法呢？

就是首尾指针法，新的子节点集合和旧的子节点集合，各有首尾两个指针，举个例子：

<ul>
    <li>a</li>
    <li>b</li>
    <li>c</li>
</ul>

修改数据后

<ul>
    <li>b</li>
    <li>c</li>
    <li>e</li>
    <li>a</li>
</ul>
1
2
3
4
5
6
7
8
9
10
11
12
13
14

那么新旧两个子节点集合以及其首尾指针为：

然后会进行比较，总共有五种比较情况：

• 1、oldS 和 newS使用sameVnode方法进行比较，sameVnode(oldS, newS)

• 2、oldS 和 newE使用sameVnode方法进行比较，sameVnode(oldS, newE)

• 3、oldE 和 newS使用sameVnode方法进行比较，sameVnode(oldE, newS)

• 4、oldE 和 newE使用sameVnode方法进行比较，sameVnode(oldE, newE)

• 5、如果以上逻辑都匹配不到，再把所有旧子节点的 key 做一个映射到旧节点下标的 key -> index 表，然后用新 vnode 的 key 去找出在旧节点中可以复用的位置。

接下来就以上面代码为例，分析一下比较的过程

分析之前，请大家记住一点，最终的渲染结果都要以newVDOM为准，这也解释了为什么之后的节点移动需要移动到newVDOM所对应的位置

• 第一步

oldS = a, oldE = c
newS = b, newE = a
1
2

比较结果：oldS 和 newE 相等，需要把节点a移动到newE所对应的位置，也就是末尾，同时oldS++，newE--

• 第二步

oldS = b, oldE = c
newS = b, newE = e
1
2

比较结果：oldS 和 newS相等，需要把节点b移动到newS所对应的位置，同时oldS++,newS++

• 第三步

oldS = c, oldE = c
newS = c, newE = e
1
2

比较结果：oldS、oldE 和 newS相等，需要把节点c移动到newS所对应的位置，同时oldS++,newS++，oldE--

• 第四步

oldS > oldE，则oldCh先遍历完成了，而newCh还没遍历完，说明newCh比oldCh多，所以需要将多出来的节点，插入到真实DOM上对应的位置上

• 思考题

上面的例子是newCh比oldCh多，假如相反，是oldCh比newCh多的话，那就是newCh先走完循环，然后oldCh会有多出的节点，结果会在真实DOM里进行删除这些旧节点。大家可以自己思考一下，模拟一下这个过程，像我一样，画图模拟，才能巩固上面的知识。

附上updateChildren的核心原理代码

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0, newStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  let oldKeyToIdx
  let idxInOld
  let elmToMove
  let before
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode == null) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newStartVnode == null) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newEndVnode == null) {
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode)
      api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode)
      api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      // 使用key时的比较
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
      }
      idxInOld = oldKeyToIdx[newStartVnode.key]
      if (!idxInOld) {
        api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
        newStartVnode = newCh[++newStartIdx]
      }
      else {
        elmToMove = oldCh[idxInOld]
        if (elmToMove.sel !== newStartVnode.sel) {
          api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
        } else {
          patchVnode(elmToMove, newStartVnode)
          oldCh[idxInOld] = null
          api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
        }
        newStartVnode = newCh[++newStartIdx]
      }
    }
  }
  if (oldStartIdx > oldEndIdx) {
    before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

用index做key

key 的作用：

key 是虚拟 DOM 对象的标识，可提高页面更新渲染的效率。

当状态中的数据发生变化时，Diff 会根据新数据生成新的虚拟 DOM ，接着对新旧虚拟 DOM 进行 Diff 比较，规则如下：

• 旧虚拟 DOM 找到和新虚拟 DOM 相同的 key：
  • 若内容没变，直接复用真实 DOM
  • 若内容改变，则生成新的真实 DOM ，替换页面中之前的真实 DOM
• 旧虚拟 DOM 未找到和新虚拟 DOM 相同的 key：根据数据创建新的真实 DOM ，渲染到页面

平常v-for循环渲染的时候，为什么不建议用index作为循环项的key呢？

使用 index 作为 key 可能引发的问题：

• 若对数据进行逆序添加、逆序删除等破坏顺序的操作，会进行没有必要的真实 DOM 更新。界面效果没问题，但效率低下。
• 如果结构中包含输入类的 DOM（如 input 输入框） ，则会产生错误的 DOM 更新。
• 若不存在对数据逆序添加、逆序删除等破坏顺序的操作，则没有问题。

在进行子节点的 diff算法 过程中，会进行 旧首节点和新首节点的sameNode对比，这一步命中了逻辑，因为现在新旧两次首部节点 的 key 都是 0了，同理，key为1和2的也是命中了逻辑，导致相同key的节点会去进行patchVnode更新文本，而原本就有的c节点，却因为之前没有key为4的节点，而被当做了新节点，所以很搞笑，使用index做key，最后新增的居然是本来就已有的c节点。所以前三个都进行patchVnode更新文本，最后一个进行了新增，那就解释了为什么所有li标签都更新了。

<ul>
   <li v-for="(item, index) in list" :key="index">{{ item.title }}</li>
</ul>
<button @click="add">增加</button>

list: [
        { title: "a", id: "100" },
        { title: "b", id: "101" },
        { title: "c", id: "102" },
      ]
      
add() {
      this.list.unshift({ title: "孙悟空", id: "99" });
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解决办法：

用唯一的ID作为key即可

总结：

Diff算法主要首先通过：

• setter，中捕获数据的更新

• 随后通过Dep.notify，通知对应的订阅者watcher，

• 调用 patch方法 ，给真实DOM打补丁，更新对应的试图

• patch方法会判断同层节点是否为相同类型

• 否就直接返回新节点

• 是就进行 patchVnode方法 进行深层对比

• patchVnode中又会进行五层对比

  • 找到对应的真实DOM，称为el

  • 判断newVnode和oldVnode是否指向同一个对象，如果是，那么直接return

  • 如果他们都有文本节点并且不相等，那么将el的文本节点设置为newVnode的文本节点。

  • 如果oldVnode有子节点而newVnode没有，则删除el的子节点

  • 如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el

  • 如果两者都有子节点，则执行updateChildren函数比较子节点，这一步很重要

• updateChildren方法利用首尾指针进行比较

• 若有key时则使用key进行比较

参考文章