Diff 算法
大约 17 分钟
Diff 算法
diff 算法是 Vue 渲染器的核心算法，它会在页面或者组件将要更新时，比较新旧两组 vnode（虚拟dom）节点，并以最小的性能开销完成更新操作（能够复用的节点尽量复用，没办法复用的节点再进行 dom 操作）
diff 算法的目标是尽可能的减少 dom 操作从而降低性能开销，它主要通过以下几步实现：
- 找出可以复用的元素（复用 dom 元素，需要使用 vnode 的类型与绑定的 key 来判断元素是否可以复用，此操作不会创建 dom）
- 找出需要移动的元素（更改移动 dom 的位置，此操作不会创建 dom）
- 添加新元素（此操作会创建新的 dom）
- 移除不存在的元素（此操作会删除 dom）
假设现在有一组 vnode 需要更新：
//旧的 vnode
const oldVnode = {
type:'div',
children:[
{ type:'p',children:'1' },
{ type:'p',children:'2' },
{ type:'p',children:'3' },
{ type:'p',children:'4' },
]
}
//新的 vnode
const newVnode = {
type:'div',
children:[
{ type:'p',children:'1' },
{ type:'p',children:'4' },
{ type:'h1',children:'3' },
{ type:'p',children:'2' },
]
}
如果不使用 diff 算法直接对新旧 vnode 进行更新操作，那么就要先卸载旧的 3 个子节点，在挂载新的 3 个子节点，一共要执行 6 次操作，这样移除在创建 dom 元素的操作会造成极大的性能开销。下面将探究使用 diff 算法是如何减小操作 dom 的性能开销的。
ℹ️提示
这里在更新节点时没有提到使用 innerHTML 接口是因为这样做会存在一些问题：
innerHTML会将容器内所有节点全部清空，但容器的内容可能是由许多其他组件渲染的，这样做不能正确的执行这些组件的beforeUnmount、unmounted等生命周期函数。- 容器当中的元素可能存在自定义指令，直接清空就不能触发对应的指令钩子函数。
innerHTML清空元素时不会移除元素上绑定的事件处理函数。
patch 方法
在探究 diff 算法之前，还应当了解 Vue 渲染器中的另一个重要的方法: patch，不同于 diff 算法，patch 方法的作用是将 diff 算法中新旧节点有差异的部分（即需要进行 dom 操作更新的部分）更新到页面上。它的简易版实现如下：
//n1 代表旧的 vnode
//n2 代表新的 vnode
//container 代表容器元素，vnode 的容器
//anchor 代表锚点元素，插入 vnode 时的实用的锚点
function patch(n1, n2, container, anchor){
//如果旧的 vnode 存在并且与新的 vnode 是不同类型
if(n1 && n1.type !== n2.type){
//卸载清空旧的 vnode
unmount(n1)
n1 = null
}
//获取新的 vnode 的类型
const { type } = n2
//如果新的 vnode 的 type 属性类型是字符，表示新的 vnode 是一个 dom 元素
if(typeof type === 'string'){
if(!n1){
//如果不存在旧的 vnode，那么直接挂载新的 vnode
mountElement(n2, container, anchor)
}else{
//否则比较新旧 vnode 的差异在进行更新操作
patchElement(n1, n2)
}
}
//如果新的 vnode 是文本类型
else if(type === Text){
if(!n1){
//如果不存在旧的 vnode，那么直接创建新的文本节点，使新的 vnode 保持对其引用然后插入到页面
const el = n2.el = document.createTextNode(n2.children)
insert(el, container, anchor)
}else{
//如果存在旧的 vnode，那么直接使用新的 vnode 的文本内容更新旧的 vnode 的文本内容
const el = n2.el = n1.el
if(n2.children !== n1.children){
el.nodeValue = n2.children
}
}
}
//....
//省略部分逻辑
}
function mountElement(vnode, container, anchor){
//获取到 vnode 对应的 真实 dom 元素
let el = vnode.el
//....
//省略部分处理逻辑
// 将 dom 元素插入到容器中（透传锚点元素给 insert 函数）
insert(el, container, anchor)
}
function unmount(vnode){
//获取 vnode 对应 dom 元素的父元素
const parent = vnode.el.parent
if(parent){
//从父元素中卸载 vnode 对应的真实 dom 元素
parent.removeChild(vnode.el)
}
}
function patchElement(n1, n2){
//新的 vonde 也保持对真实 dom 的引用
const el = n2.el = n1.el
//....
//其他处理逻辑此处省略
}
function setElementText(el, text){
//将操作 dom 的方法封装可以提供更好的跨平台兼容性
el.nodeValue = text
}
function insert(el, parent, anchor=null){
//利用浏览器提供的 insertBefore 方法移动元素
parent.insertBefore(el, anchor)
}
简单 diff
简单 diff 算法的核心逻辑是：用新的一组子节点中的节点与旧的一组子节点中的节点进行比较，寻找出可以复用的节点，如果找到了，就记录该节点的位置索引 lastIndex（也叫最大索引），然后在后续比较的过程中，如果有节点的索引小于这个最大索引，那么说明节点索引小于最大索引的这个节点对应的真实 dom 需要更新。如果有节点的索引大于最大索引，那么就将最大索引更新为当前节点的索引。
它的简易实现如下：
// diff 算法核心逻辑比较新旧一组 vnode 子节点
function patchChildren(n1, n2, container) {
//如果新的子节点是文本节点
if (typeof n2.children === 'string') {
//如果旧的子节点是一组子节点，那么就将旧的子节点全部卸载
if (Array.isArray(n1.children)) {
n1.children.forEach((c) => unmount(c))
}
//将新的子节点内容更新
setElementText(container, n2.children)
}
//如果新的子节点是一组子节点
else if (Array.isArray(n2.children)) {
//保存新旧子节点
const oldChildren = n1.children
const newChildren = n2.children
//设置最大索引值
const lastIndex = 0
//遍历新的子节点
for (let i = 0; i < newChildren.length; i++) {
//当前每个新子节点
const newVnode = newChildren[i]
let j = 0
//设置 find 标识，表示是否找到了可复用的节点
let find = false
//遍历旧的子节点
for (j; j < oldChildren.length; j++) {
//当前每个新子节点下的每个旧子节点
const oldVnode = oldChildren[j]
//如果新子节点的key与旧子节点的key相同，说明是同一个节点，可以复用
if (newVnode[key] === oldVnode[key]) {
//找到可复用节点后将 find 标识设置为 true
find = true
//使用 patch 方法对新旧节点更新
patch(oldVnode, newVnode, container)
//当旧子节点的索引小于设置的最大索引时，说明新的子节点对应的真实 dom 需要移动
if (j < lastIndex) {
//获取新的子节点的上一个节点
const prevVnode = newChildren[i - 1]
if (prevVnode) {
//将上一个节点作为锚点元素，将新的子节点插入到锚点元素之前
const anchor = prevVnode.el.nextSibling
insert(newVnode.el, container, anchor)
}
} else {
//如果旧子节点的索引大于设置的最大索引时，说明不需要移动新子节点
//对应的真实 dom，那么就更新最大索引
lastIndex = j
}
//找到可复用的节点后结束当前对于旧的子节点的循环
break
}
}
//如果在上一步循环遍历旧的子节点的过程中没有找到可以复用的节点，说明新子节点是新增的节点
if (!find) {
//获取当前新子节点的上一个节点
const prevVnode = newChildren[i - 1]
//设置锚点元素
let anchor = null
if (prevVnode) {
//如果当前新子节点的上一个节点存在，就使用它作为锚点元素
anchor = prevVnode.el.nextSibling
}
else {
//否则说明当前新子节点是容器的第一个子节点，使用容器的 firstChild 作为锚点元素
anchor = container.firstChild
}
//使用 patch 方法挂载更新
patch(null, newVnode, container, anchor)
}
}
//在上面新旧子节点更新操作完成后，遍历旧的子节点，寻找到需要卸载的旧的子节点
for (let i = 0; i < oldChildren.length; i++) {
const oldVnode = oldChildren[i]
//从新子节点中寻找旧的子节点是否还存在
const has = newChildren.find(vnode => vnode.key === oldVnode.key)
//如果不存在旧的子节点，就卸载它
if (!has) {
unmount(oldVnode)
}
}
} else {
//如果上面两个条件都不满足，说明就没有子节点
//设置容器的内容为空
setElementText(container, '')
//更新新旧子节点内容
n2.children.forEach((c) => patch(null, c, container))
}
}
双端 diff
双端 diff 算法的核心逻辑是：在新旧两组子节点的开始与结束位置的四个端点之间分别进行比较，寻找可以复用的节点，并动态的更新四个端点的位置索引，直到新旧两组子节点的开始位置索引小于等于结束位置索引。
它的简易实现如下：
function patchChildren(n1, n2, container){
//如果新的子节点是文本节点
if (typeof n2.children === 'string') {
//.....
//此处逻辑与简单 diff 算法相同，省略
}
else if(Array.isArray(n2.children)){
const oldChildren = n1.children
const newChildren = n2.children
//设置新旧两组子节点开始与结束位置的索引
let oldStartIndex = 0
let oldEndIndex = oldChildren.length - 1
let newStartIndex = 0
let newEndIndex = newChildren.length - 1
//设置新旧两组子节点开始与结束位置的索引对应的 vnode 节点
let oldStartVnode = oldChildren[oldStartIndex]
let oldEndVnode = oldChildren[oldEndIndex]
let newStartVnode = newChildren[newStartIndex]
let newEndVnode = oldChildren[newEndIndex]
//从新旧子节点索引开始的位置循环，直到开始索引小于等于结束索引时结束循环
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
//当旧的开始位置的 vnode 的 key 与 新的开始位置的 vnode 的 key 相同时，
//说明是同一节点，可以复用
if (oldStartVnode.key === newStartVnode.key) {
//使用 patch 方法进行打补丁更新
patch(oldStartVnode, newStartVnode, container)
//旧的开始位置的索引增加 1，新的开始位置的索引也增加 1，
//并且更新新旧开始索引对应的 vnode（继续向后寻找）
oldStartVnode = oldChildren[++oldStartIndex]
newStartVnode = newChildren[++newStartIndex]
}
//当旧的结束位置的 vnode 的 key 与新的结束位置的 vnode 的 key 相同时，
//说明是同一节点，可以复用
else if (oldEndVnode.key === oldEndVnode.key) {
//使用 patch 方法进行打补丁更新
patch(oldEndVnode, newStartVnode, container)
//旧的结束位置的索引减少 1，新的结束位置的索引也减少 1，
//并且更新新旧结束索引对应的 vnode（继续向前寻找）
oldEndVnode = oldChildren[--oldEndIndex]
newEndVnode = newChildren[--newEndIndex]
}
//当旧的开始位置的 vnode 的 key 与新的结束位置的 vnode 的 key 相同时，
//说明是同一节点，但是旧的开始位置的 vnode 需要移动
//以新的结束位置为准，旧的开始位置的 vnode 需要移动到新的结束位置
else if (oldStartVnode.key === newEndVnode.key) {
//使用 patch 方法进行打补丁更新
patch(oldStartVnode, newEndVnode, container)
//使用 insert 方法进行节点移动
insert(oldStartVnode.el, container, oldEndVnode.el.nextSibling)
//旧的结束位置的索引增加 1，新的结束位置的索引减少 1，
//并且更新新旧结束索引对应的 vnode（继续向中间寻找）
oldStartVnode = oldChildren[++oldStartIndex]
newEndVnode = newChildren[--newEndIndex]
}
//当旧的结束位置的 vnode 的 key 与新的开始位置的 vnode 的 key 相同时，
//说明是同一节点，但是旧的结束位置的 vnode 需要移动
//以新的开始位置为准，旧的结束位置的 vnode 需要移动到新的开始位置
else if (oldEndVnode.key === newStartVnode.key) {
//使用 patch 方法进行打补丁更新
patch(oldEndVnode, newStartVnode, container)
//使用 insert 方法进行节点移动
insert(oldEndVnode.el, container, oldStartVnode.el.nextSibling)
//旧的结束位置的索引减少 1，新的结束位置的索引增加 1，
//并且更新新旧结束索引对应的 vnode（继续向中间寻找）
oldEndVnode = oldChildren[--oldEndIndex]
newStartVnode = newChildren[++newStartIndex]
}
//当新旧两组子节点的开始与结束位置都比较过后仍然没有找到可复用的旧的 vnode 时
else {
//使用新的开始位置的 vnode 的 key 直接到旧的一组子节点中进行比较，找出对应的索引
const indexOld = oldChildren.findIndex(node => node.key === newStartVnode.key)
//如果在旧的一组子节点中没有找到了新的开始位置的 vnode 对应的节点时，
//说明旧的 vnode 可以复用
if (indexOld > 0) {
//找到可以复用的旧的 vnode
const vnodeToMove = oldChildren[indexOld]
//使用 patch 方法进行打补丁更新
patch(vnodeToMove, newStartVnode, container)
//使用 insert 方法进行节点移动
insert(vnodeToMove.el, container, oldStartVnode.el.nextSibling)
//将已经复用过的节点销毁
oldChildren[indexOld] = undefined
}
//如果在旧的一组子节点中没有找到新的 vnode 对应的节点时，
//说明新的 vnode 是新增节点
else {
//使用 patch 方法进行挂载
patch(null, newStartVnode, container, oldStartVnode.el)
}
//新的开始位置的索引增加 1，并且更新新的开始索引对应的 vnode（继续向后寻找）
newStartVnode = newChildren[++newStartIndex]
}
}
//在上面的循环更新结束后再检查一遍索引的情况，
//如果旧的结束索引小于旧的开始索引并且新的开始索引小于新的结束索引，
//说明新的一组子节点还有遗漏的情况，这些遗漏的新的一组子节点都是新增节点
if (oldEndIndex < oldStartIndex && newStartIndex < newEndIndex) {
//从新的开始位置到新的结束位置再对新的一组子节点进行遍历
//（在它们之间的节点都是遗漏的新增节点）
for (let i = newStartIndex; i <= newEndIndex; i++) {
//找到新增节点的锚点元素
const anchor = newChildren[newEndIndex + 1] ? newChildren[newEndIndex + 1].el : null
//使用 patch 方法进行挂载
patch(null, newChildren[i], container, anchor)
}
}
//如果新的结束索引小于新的开始索引并且旧的开始索引小于旧的结束索引，
//说明旧的一组子节点还有遗漏的情况，这些遗漏的旧的一组子节点都是已经不存在的节点
else if (newEndIndex < newStartIndex && oldStartIndex < oldEndIndex) {
//从旧的开始位置到旧的结束位置再对旧的一组子节点进行遍历
//（在它们之间的节点都是遗漏的不存在的节点）
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
//使用 unmount 方法移除这些不存在的旧的节点
unmount(oldChildren[i])
}
}
}
else{
//.....
//此处逻辑与简单 diff 算法相同，省略
}
}
快速 diff
快速 diff 算法的核心逻辑是：先对新旧两组子节点中相同的前置位置与相同的后置位置进行处理，当这些相同的前置节点与后置节点都处理完成后，剩下的节点如果不能通过挂载新增节点或者卸载已经不存在的节点进行更新操作时，就需要根据节点的索引关系，构造一个最长递增子序列，最长递增子序列所对应的节点既为不需要移动的节点。
它的简易实现如下：
function patchChildren(n1, n2, container) {
const newChildren = n2.children
const oldChildren = n1.children
//设置新旧两组子节点的开始索引 j
let j = 0
//设置新旧两组开始索引对应的 vnode
let oldVnode = oldChildren[j]
let newVnode = newChildren[j]
//循环向后遍历，直到找到 key 不相同的新旧 vnode 结束循环（相同的前置节点处理）
while (oldVnode.key === newVnode.key) {
//相同可复用的节点使用 patch 方法打补丁更新
patch(oldVnode, newVnode, container)
//新旧两组子节点的开始索引增加 1
j++
//更新新旧两组开始索引对应的 vnode
oldVnode = oldChildren[j]
newVnode = newChildren[j]
}
//设置新旧两组子节点的结束索引
let oldEnd = oldChildren.length - 1
let newEnd = newChildren.length - 1
//设置新旧两组开始索引对应的 vnode
oldVnode = oldChildren[oldEnd]
newVnode = newChildren[newEnd]
//循环向前遍历，直到找到 key 不相同的新旧 vnode 结束循环（相同的后置节点处理）
while (oldVnode.key === newVnode.key) {
//相同可复用的节点使用 patch 方法打补丁更新
patch(oldVnode, newVnode, container)
//新旧两组子节点的结束索引减少 1
oldEnd--
newEnd--
//更新新旧两组结束索引对应的 vnode
oldVnode = oldChildren[oldEnd]
newVnode = newChildren[newEnd]
}
//如果新的一组子节点的开始索引大于旧的一组子节点的结束索引
//并且新的一组子节点的开始索引小于等于新的一组子节点的结束索引
//说明新的一组子节点中有新增节点
if (j > oldEnd && j <= newEnd) {
//找到新增的节点的锚点元素
const anchorIndex = newEnd + 1
const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
//循环遍历新增的节点（从 j 到 newEnd 之间的节点都是新增节点）
while (j <= newEnd) {
//使用 patch 方法进行挂载新增节点
patch(null, newChildren[j++], container, anchor)
}
}
//如果新的一组子节点的开始索引大于新的一组子节点的结束索引
//并且新的一组子节点的开始索引小于等于旧的一组子节点的结束索引
//说明旧的一组子节点中有已经不存在的节点
else if (j > newEnd && j <= oldEnd) {
//循环遍历已经不存在的节点（从 j 到 oldEnd 之间的节点都是不存在的节点）
while (j <= oldEnd) {
//使用 unmount 方法移除已经不存在的节点
unmount(oldChildren[j++])
}
}
//如果还有没有被处理的节点存在
else {
//构造 source 数组，长度为新的一组子节点中没有被处理的节点的数量，数组元素全部填充 -1
//count 表示没有被处理的新的一组子节点的个数
const count = newEnd - j + 1
const source = new Array(count).fill(-1)
//设置 source 数组的开始索引 j
const oldStart = j
const newStart = j
//设置 moved 标识，表示节点是否移动
let moved = false
//设置当前位置变量
let pos = 0
//设置索引对应 vnode节点 key 的位置映射表
const keyIndex = {}
//设置 patched 变量，表示已经更新过的节点数量
let patched = 0
//从新的未被处理的节点开始到结束位置进行遍历，设置索引位置与节点 key 的对应关系
for (let i = newStart; i <= newEnd; i++) {
keyIndex[newChildren[i].key] = i
}
//从旧的未被处理的节点开始到结束位置进行遍历
for (let i = oldStart; i <= oldEnd; i++) {
oldVnode = oldChildren[i]
//如果更新过的节点数量小于未被处理的节点数量，那么继续更新
if (patched <= count) {
//在未被处理的新的一组子节点的索引位置表中找到与旧的子节点有相同 key 的节点的位置
const k = keyIndex[oldVnode.key]
// 如果位置存在
if (typeof k !== 'undefined') {
//找到新的子节点
newVnode = newChildren[k]
//使用 patch 方法进行更新
patch(oldVnode, newVnode, container)
//更新过的节点数量增加 1
patched++
//在 source 数组中找到已经更新的节点位置并填充 source 数组
source[k - newStart] = i
//如果找到的新的子节点的位置小于当前的位置，说明新的子节点需要移动
if (k < pos) {
// moved 标识设置为 true
moved = true
}
//如果找到的新的子节点的位置大于等于当前的位置，说明新的子节点不需要移动
else {
//更新当前位置
pos = k
}
}
//如果位置不存在，说明此处对应的旧的子节点多余
else {
//使用 unmount 方法卸载多余节点
unmount(oldVnode)
}
}
//如果更新过的节点数量大于未被处理的节点数量，说说明有多余节点，卸载多余的节点
else {
//使用 unmount 方法卸载多余节点
unmount(oldVnode)
}
}
//如果 moved 存在，说明有节点需要进行移动
if (moved) {
//计算最长递增子序列
const seq = lis(source)
//设置 s 指向最长递增子序列的最后一个元素
let s = seq.length - 1
//设置 i 指向新的一组子节点的最后一个元素
let i = count - 1
//从新的一组子节点从后向前遍历
for (i; i >= 0; i--) {
//如果在 source（即未被处理的新的一组子节点中） 数组中没有找到对应的元素
if (source[i] === -1) {
//说明该元素是新增元素，找到其锚点元素使用 patch 方法挂载
const pos = i + newStart
const newVnode = newChildren[pos]
const nextPos = pos + 1
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
patch(null, newVnode, container, anchor)
}
//如果节点的索引 i 不等于 seq[s] 的值
else if (i !== seq[s]) {
//说明该节点需要移动，找到其锚点元素使用 insert 方法移动
const pos = i + newStart
const newVnode = newChildren[pos]
const nextPos = pos + 1
const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null
insert(newVnode.el, container, anchor)
}
//如果 i 与 seq[s] 相等
else {
//说明节点不需要移动，让 s 减少 1，指向它前面的位置
s--
}
}
}
}
}
ℹ️提示
最长递增子序列的算法可以参考：最长递增子序列