趁着五一假期之余，笔者想面试一波，趁机跳个槽，没想到被打脸了。终究还是倒在了Diff算法的大山面前。为了下次不被问倒，肝了一晚上的源码，希望能帮到即将去"装B"的小伙伴。

什么是虚拟DOM

在讲虚拟DOM前，首页要搞明白真实DOM是如何渲染的，为什么要虚拟DOM,一个网页运行到浏览器是怎么一个渲染过程?

直接上图、有图有真相。

构建DOM树。通过HTML parser解析处理HTML标记，将它们构建为DOM树(DOM tree)，当解析器遇到非阻塞资源(图片，css),会继续解析，但是如果遇到script标签(特别是没有async 和 defer属性)，会阻塞渲染并停止html的解析，这就是为啥最好把script标签放在body下面的原因。
构建CSSOM树。与构建DOM类似,浏览器也会将样式规则，构建成CSSOM。浏览器会遍历CSS中的规则集，根据css选择器创建具有父子，兄弟等关系的节点树。
构建Render树。这一步将DOM和CSSOM关联，确定每个 DOM 元素应该应用什么 CSS 规则。将所有相关样式匹配到DOM树中的每个可见节点，并根据CSS级联确定每个节点的计算样式，不可见节点(head,属性包括 display:none的节点)不会生成到Render树中。
布局/回流(Layout/Reflow)。浏览器第一次确定节点的位置以及大小叫布局，如果后续节点位置以及大小发生变化，这一步触发布局调整，也就是回流。
绘制/重绘(Paint/Repaint)。将元素的每个可视部分绘制到屏幕上，包括文本、颜色、边框、阴影和替换的元素（如按钮和图像）。如果文本、颜色、边框、阴影等这些元素发生变化时，会触发重绘(Repaint)。为了确保重绘的速度比初始绘制的速度更快，屏幕上的绘图通常被分解成数层。将内容提升到GPU层(可以通过tranform,filter,will-change,opacity触发)可以提高绘制以及重绘的性能。
合成(Compositing)。这一步将绘制过程中的分层合并，确保它们以正确的顺序绘制到屏幕上显示正确的内容。

为什么需要虚拟DOM？

从上图我们可以清楚的了解一个真实DOM的渲染过程是怎么样的。很明显如果是DOM节点更新，那么整个DOM将重新渲染，然而DOM节点渲染是非常消耗性能的一件事。那有什么办法让需要更新的节点更新，而不是整个DOM树更新呢？这个时候虚拟DOM就孕育而生。

虚拟DOM本质上是一个js对象，通过对象来表示真实的DOM结构。tag用来描述标签，props用来描述属性，children用来表示嵌套的层级关系。

虚拟DOM的优点：

小修改无需频繁更新DOM，框架的diff算法会自动比较，分析出需要更新的节点，按需更新
更新数据不会造成频繁的回流与重绘
表达力更强，数据更新更加方便
保存的是js对象，具备跨平台能力

缺点：

虚拟DOM同样也有缺点，首次渲染大量DOM时，由于多了一层虚拟DOM的计算，会比innerHTML插入慢。

虚拟DOM实现原理

既然明白了为什么需要虚拟DOM以及虚拟DOM的优点，那我们现在直接进入正题。什么是Diff算法，其实讲的简单点，Diff算法就是实现虚拟DOM的一个核心原理。

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

Diff算法主要的三个流程：

通过js建立节点描述对象
diff算法比较分析新旧两个虚拟DOM差异
将差异patch到真实dom上实现更新

还是老规矩，直接上图，浅显易懂。

像React、vue2.X、vue3.X中都用到了Diff算法。vue2.X用到的Diff算法采用的是深度优先，同层比较的策略。

核心代码patch.js

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
}

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必须是否相同
  )
}

patchNode做了以下几件事：

创建新节点
删除废节点
更新已有节点

找到对应的真实DOM，称为el判断newVnode和oldVnode是否指向同一个对象，如果是，那么直接return

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

如果oldVnode有子节点而newVnode没有，则删除el的子节点如果oldVnode没有子节点而newVnode有，则将newVnode的子节点真实化之后添加到el如果两者都有子节点，则执行updateChildren函数比较子节点，这一步很重要

function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index,
	removeOnly
) { // 判断vnode与oldVnode是否完全一样   
  if (oldVnode === vnode) {   
	return
}
if (isDef(vnode.elm) && isDef(ownerArray)) {
	// 克隆重用节点    
  vnode = ownerArray[index] = cloneVNode(vnode)  
}
const elm = vnode.elm = oldVnode.elm
if (isTrue(oldVnode.isAsyncPlaceholder)) {
	if (isDef(vnode.asyncFactory.resolved)) {
		hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
	} else {
		vnode.isAsyncPlaceholder = true
	}
	return
}
// 是否是静态节点，key是否一样，是否是克隆节点或者是否设置了once属性  
if (isTrue(vnode.isStatic) && isTrue(oldVnode.isStatic) && vnode.key === oldVnode.key && (isTrue(vnode.isCloned) ||
		isTrue(vnode.isOnce))) {
	vnode.componentInstance = oldVnode.componentInstance
	return
}
let i
const data = vnode.data
if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
	i(oldVnode, vnode)
}
const oldCh = oldVnode.children
const ch = vnode.children
if (isDef(data) && isPatchable(vnode)) {
	//调用update回调以及update钩子      
	for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
	if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)
} //判断新节点是否有文本    if (isUndef(vnode.text)) {    
//新旧节点都有子节点情况下，如果新旧子节点不相同，那么进行子节点的比较，就是updateChildren方法  
if (isDef(oldCh) && isDef(ch)) {
	if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
} else if (isDef(ch)) { //只有新节点有子节点           
	if (process.env.NODE_ENV !== 'production') { //重复Key检测               
		checkDuplicateKeys(ch)
	} //清除旧节点文本          
	if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') //添加新节点       
	addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
} else if (isDef(oldCh)) { //只有旧节点有子节点，删除旧节点        
	removeVnodes(oldCh, 0, oldCh.length - 1)
} else if (isDef(oldVnode.text)) { //新旧节点都无子节点            
	nodeOps.setTextContent(elm, '')
}
} else if (oldVnode.text !== vnode.text) { //新节点文本替换旧节点文本       
	nodeOps.setTextContent(elm, vnode.text)
}
if (isDef(data)) {
	if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
}

patchNode里最重要的一个方法就是更新子节点。子节点更新采用的是双端比较的策略，什么是双端比较呢，就是新旧节点比较是通过互相比较首尾元素(存在4种比较)，然后向中间靠拢比较(newStartIdx,与oldStartIdx递增,newEndIdx与oldEndIdx递减)的策略。

直接上源码

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)
  }
}

总结

熬不住了，肝不动了，updateChildren方法的分析就留给各位评论区的大神了。这里给各位留个思考题，上面的例子是newCh比oldCh多，假如相反，是oldCh比newCh多的话，那就是newCh先走完循环，然后oldCh会有多出的节点，结果会在真实DOM里进行删除这些旧节点。可以模拟一下过程，画图模拟，比较清晰。

前军教程网

中小站长与DIV+CSS网页布局开发技术人员的首选CSS学习平台

深入浅出虚拟DOM、Diff算法核心原理(源码解析)

什么是虚拟DOM

虚拟DOM实现原理

总结

前军教程网

中小站长与DIV+CSS网页布局开发技术人员的首选CSS学习平台

深入浅出 虚拟DOM、Diff算法核心原理(源码解析)

什么是虚拟DOM

虚拟DOM实现原理

总结

深入浅出虚拟DOM、Diff算法核心原理(源码解析)