本文主要对Virtual DOM（下文中统称为vdom）中的diff算法实现的原理进行讲解，并不会涉及到编码操作。vdom我在之前的文章中已略有提及，你可以点击《基于Vue认识虚拟DOM（Virtual DOM）》进行学习。
vdom是实现vue和React的重要基石，diff算法是vdom中最核心、最关键的部分，vdom是一个热门话题，也是面试中的热门问题。DOM操作非常耗费性能，以前用jQuery，可以自行控制DOM操作的时机，手动调整。Vue和React是数据驱动视图，如何有效控制DOM操作呢？vdom使用方式就是用JS模拟DOM结构，计算出最小的变更，操作DOM。
一、diff算法概述
diff算法即对比，是一个广泛的概念，例如linux diff命令、git diff等。两个js对象也可以做diff，如jiff。两棵树做diff，如这里 vdom diff。
树diff的时间复杂度O(n ^ 3)
第一、遍历tree1；
第二、遍历tree2
第三、排序
第四、1000个节点，要计算1亿次，算法不可用。
优化时间复杂度O(n)
只比较同一层级，不跨级比较。
tag不相同，则直接删除重建，不再深度比较。
tag和key，两者都相同，则认为是相同节点，不再深度比较。
文章已经结束，感谢您的阅读。
下面，我们就通过简单的分析一下snabbdom来看一下整个虚拟DOM的实现过程。
1、h方法生成vnode
var vnode = h('div#container.two.classes', {on: {click: someFn}}, [
h('span', {style: {fontWeight: 'bold'}}, 'This is bold'),
' and this is just normal text',
h('a', {props: {href: '/foo'}}, 'I\'ll take you places!')
]);
源码中h函数的定义
export function h(sel: string): VNode
export function h(sel: string, data: VNodeData | null): VNode
export function h(sel: string, children: VNodeChildren): VNode
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode
export function h (sel: any, b?: any, c?: any): VNode {
....
....
return vnode(sel, data, children, text, undefined)
}
我们可以在源码中看到vnode的数据结构
export function vnode (sel: string | undefined,
data: any | undefined,
children: Array<VNode | string> | undefined,
text: string | undefined,
elm: Element | Text | undefined): VNode {
const key = data === undefined ? undefined : data.key
return { sel, data, children, text, elm, key }
}
2、patch方法
return function patch (oldVnode: VNode | Element, vnode: VNode): VNode {
let i: number, elm: Node, parent: Node
const insertedVnodeQueue: VNodeQueue = []
// 执行pre hook
for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
// 第一个参数不是 vnode，处理这样的情况 patch(container, vnode)
if (!isVnode(oldVnode)) {
//创建一个空的vnode， 关联到着个 DOM 元素
oldVnode = emptyNodeAt(oldVnode)
}
// 相同的 vnode （key 和 $el 都相同）
if (sameVnode(oldVnode, vnode)) {
// 对比vnode
patchVnode(oldVnode, vnode, insertedVnodeQueue)
// 不同的vnode，直接删掉重建
} else {
elm = oldVnode.elm!
parent = api.parentNode(elm) as Node
// 重建
createElm(vnode, insertedVnodeQueue)
if (parent !== null) {
api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
removeVnodes(parent, [oldVnode], 0, 0)
}
}
for (i = 0; i < insertedVnodeQueue.length; ++i) {
insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i])
}
for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
return vnode
}
3、patchVnode对比vnode
function patchVnode (oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
// 执行 prepatch hook
const hook = vnode.data?.hook
hook?.prepatch?.(oldVnode, vnode)
// 设置vnode.elem(保存oldVnode.elm，用于前后vnode进行对比的更新)
const elm = vnode.elm = oldVnode.elm!
// 旧的children
const oldCh = oldVnode.children as VNode[]
// 新的children
const ch = vnode.children as VNode[]
if (oldVnode === vnode) return
// hook相关
if (vnode.data !== undefined) {
for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
vnode.data.hook?.update?.(oldVnode, vnode)
}
// vnode.text === undefined (vnode.children != undefined)
// text 和 children不能共存
if (isUndef(vnode.text)) {
// 新旧都有 children
if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
// 新children有 旧children无（旧的text有）
} else if (isDef(ch)) {
// 清空 text
if (isDef(oldVnode.text)) api.setTextContent(elm, '')
// 添加children
addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
// 旧children有 新children无
} else if (isDef(oldCh)) {
// 移除children
removeVnodes(elm, oldCh, 0, oldCh.length - 1)
// 旧children有
} else if (isDef(oldVnode.text)) {
api.setTextContent(elm, '')
}
// else ：vnode.text !== undefined (vnode.children 无值)
} else if (oldVnode.text !== vnode.text) {
// 移除旧的children
if (isDef(oldCh)) {
removeVnodes(elm, oldCh, 0, oldCh.length - 1)
}
// 设置新的 text
api.setTextContent(elm, vnode.text!)
}
hook?.postpatch?.(oldVnode, vnode)
}
4、updateChildren更新子节点
1、定义了oldStartIdx 、oldEndIdx 、newStartIdx、newEndId新旧vnode开始和结束遍历指针。
let oldStartIdx = 0
let newStartIdx = 0
let oldEndIdx = oldCh.length - 1
let newEndIdx = newCh.length - 1
2、优化处理前后vnode对比方法
// 新开始 && 老开始 对比
else if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
// 新结束 && 老结束 对比
} else if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
// 新结束 && 老开始 对比
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
// 新开始 && 老结束 对比
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
} else {
// 以上四种个都没命中
// 拿新节点 key，能否对应上 oldCh 中某个节点的key
}
首先，先通过交叉比较端点的方式进行vnode的比较，比较成功命中后，相应的指针向后或者向前移动，直至交叉，优化了比较算法。
在上面的几种匹配没有满足的情况下，我们就可以通过比较新旧vnode的key的值来进行比较，这也就是为什么我们要在v-for遍历的时候，一定要传入key,并且不推荐使用index值来充当key值，因为index值会随机改变，导致key不固定，在比较的时候新旧vnode不能很好的匹配。我们也不推荐使用随机数来充当key值。具体你可以参照下图：
