趁着五一假期之余，笔者想面试一波，趁机跳个槽，没想到被打脸了。终究还是倒在了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上实现更新

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

Diff算法的对比过程

像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.elmif (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 iconst data = vnode.dataif (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {	i(oldVnode, vnode)}const oldCh = oldVnode.childrenconst ch = vnode.childrenif (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里进行删除这些旧节点。可以模拟一下过程，画图模拟，比较清晰。