一、对虚拟DOM的理解

虚拟DOM是对DOM的抽象，这个对象是更加轻量级的对DOM的描述。

它有六个属性：sel表示当前节点标签名，data是节点的属性，children表示当前节点的其他子标签节点，elm表示当前虚拟节点对应的真实节点，key即为当前节点的key，text表示当前节点下的文本。

要知道渲染真实DOM的开销是很大的，比如有时候我们修改了某个数据，如果直接渲染到真实dom上会引起整个dom树的重绘和重排，有没有可能我们只更新我们修改的那一小块dom而不要更新整个dom呢？diff算法能够帮助我们。

我们先根据真实DOM生成一颗 virtual DOM ，当 virtual DOM 某个节点的数据改变后会生成一个新的 Vnode ，然后 Vnode 和 oldVnode 作对比，发现有不一样的地方就直接修改在真实的DOM上，然后使 oldVnode 的值为 Vnode 。

diff的核心就是调用名为path的函数，比较新旧节点，一边比较一边给真实的DOM打补丁

二、virtual DOM 和 真实DOM的区别

virtual DOM是将真实的DOM的数据抽取出来，以对象的形式模拟树形结构。比如dom是这样的：

 
123

1
2
3

对应的virtual DOM（伪代码）：

var Vnode = {
	tag:'div',
	children:[
		{tag:'p',text:'123'}
	]
};
1
2
3
4
5
6

注意：vNode和oldVNode都是对象

三、diff的比较方式

最初，diff的时间复杂度为O(n^3)

1、首先遍历oldVNode；

2、其次遍历vNode

3、最后排序

之后，优化时间复杂度到O(n)

1、只会比较同一层，不跨级比较；

2、tag不相同，直接删除，不再深度比较；

3、tag和key，两则都相同，则认为是相同节点，不再深度比较

diff流程

1、使用h()方法返回一个对象，vNode接收，此时这个vNode代表的就是一个虚拟对象

2、具体分析patch是怎么打补丁（代码只保留核心部分）：

function patch (oldVnode, vnode) {
 // 相同的vnode（key和sel都相等）
 if (sameVnode(oldVnode, vnode)) {
  patchVnode(oldVnode, vnode)
 } else { // 不相同的vnode
  const oEl = oldVnode.el // 当前oldVnode对应的真实元素节点
  let parentEle = api.parentNode(oEl) // 父元素
  createEle(vnode) // 根据Vnode生成新元素
  if (parentEle !== null) {
   api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 将新元素添加进父元素
   api.removeChild(parentEle, oldVnode.el) // 移除以前的旧元素节点
   oldVnode = null
  }
 }
 // some code 
 return vnode
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

patch函数接收两个参数oldVnode和vnode分别代表新的节点和之前的旧节点。判断两个节点是否相等，如果相等，则执行patchvnode，否则就是删除重建。

patchVnode

当我们确定两个节点相等后，我们回对两个节点指定patchVnode方法。那么这个方法做了什么呢？

patchVnode (oldVnode, vnode) {
 const el = vnode.el = oldVnode.el
 let i, oldCh = oldVnode.children, ch = vnode.children
 if (oldVnode === vnode) return
 if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
  api.setTextContent(el, vnode.text)
 }else {
  updateEle(el, vnode, oldVnode)
  if (oldCh && ch && oldCh !== ch) {
   updateChildren(el, oldCh, ch)
  }else if (ch){
   createEle(vnode) //create el's children dom
  }else if (oldCh){
   api.removeChildren(el)
  }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个函数做了以下事情：

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

• 判断Vnode和oldVnode是否指向同一个对象；

• 如果不是，那么直接return；如果是，且他们都有文本但不相同，那么将el的文本节点设置为Vnode的文本节点；

• 如果oldVnode有子节点，而Vnode没有，则使用删除el的子节点；

• 如果olVnode没有子节点，而Vnode有，则将Vnode的子节点实例化之后添加到el；

• 如果两者都有子节点，则执行updateChildren函数比较子节点，关键

  • updateChildren这个函数做了什么呢？

    • 将Vnode的子节点vCh和oldVnode的子节点`oldCh提取出来

    • oldCh 和 vCh 各有两个头尾的变量 StartIdx 和 EndIdx ，它们的2个变量相互比较，一共有4种比较方式，分别是oldCh的StartIdx与vCh的StartIdx比较，oldCh的EndIdx与vCh的EndIdx比较，oldCh的StartIdx与vCh的EndIdx比较，oldCh的EndIdx与vCh的StartIdx比较。

    • 如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx 表明 oldCh 和 vCh 至少有一个已经遍历完了，就会结束比较。

      图解updateChildren：

      粉红色的部分为oldCh和vCh
      

      我们将它们取出并分别用s、e、oldS、oldE指针指向它们的头Child和尾child
      
      现在分别对oldS、oldE、S、E两两做sameVndoe比较，有四种比较方式，当其中两个能匹配上，那么真实的dom中的相应节点就会移到Vnode相应的位置。比如：

    1. 如果是oldS和E匹配上了，那么真实dom中的第一个节点会移到最后
    2. 如果是oldE和S匹配上了，那么真实dom中的最后一个节点会移到最前，匹配上的两个指针向中间移动
    3. 如果四种匹配没有一对是成功的，那么遍历 oldChild ， S 挨个和他们匹配，匹配成功就在真实dom中将成功的节点移到最前面，如果依旧没有成功的，那么将 S对应的节点 插入到dom中对应的 oldS 位置， oldS 和 S 指针向中间移动。

    图解：
    

总结：

由于diff算法对比的是虚拟Dom，而虚拟Dom是呈树状的，所以我们可以发现，diff算法中充满了递归。总结起来，其实diff算法就是一个 patch —> patchVnode —> updateChildren —> patchVnode —> updateChildren —> patchVnode这样的一个循环递归的过程。

相关资料：
https://www.jb51.net/article/140471.htm
https://blog.csdn.net/m0_64023259/article/details/125476986
1
2
3