Virtual Dom 算法实现原理？

编程入门行业动态更新时间:2024-10-28 20:28:34

Virtual Dom <a href=https://www.elefans.com/category/jswz/34/1770096.html style= 算法实现原理？"/>

Virtual Dom 算法实现原理？

Virtual Dom 算法实现

既然我们已经通过 JS 来模拟实现了 DOM，那么接下来的难点就在于如何判断旧的对象和新的对象之间的差异。

DOM 是多叉树的结构，如果需要完整的对比两颗树的差异，那么需要的时间复杂度会是 O(n ^ 3)，这个复杂度肯定是不能接受的。于是 React 团队优化了算法，实现了 O(n) 的复杂度来对比差异。

实现 O(n) 复杂度的关键就是只对比同层的节点，而不是跨层对比，这也是考虑到在实际业务中很少会去跨层的移动 DOM 元素。

所以判断差异的算法就分为了两步

首先从上至下，从左往右遍历对象，也就是树的深度遍历，这一步中会给每个节点添加索引，便于最后渲染差异
一旦节点有子元素，就去判断子元素是否有不同

树的递归

首先我们来实现树的递归算法，在实现该算法前，先来考虑下两个节点对比会有几种情况

新的节点的 tagName 或者 key 和旧的不同，这种情况代表需要替换旧的节点，并且也不再需要遍历新旧节点的子元素了，因为整个旧节点都被删掉了
新的节点的 tagName 和 key（可能都没有）和旧的相同，开始遍历子树
没有新的节点，那么什么都不用做

import { StateEnums, isString, move } from './util'
import Element from './element'export default function diff(oldDomTree, newDomTree) {// 用于记录差异let pathchs = {}// 一开始的索引为 0dfs(oldDomTree, newDomTree, 0, pathchs)return pathchs
}function dfs(oldNode, newNode, index, patches) {// 用于保存子树的更改let curPatches = []// 需要判断三种情况// 1.没有新的节点，那么什么都不用做// 2.新的节点的 tagName 和 `key` 和旧的不同，就替换// 3.新的节点的 tagName 和 key（可能都没有） 和旧的相同，开始遍历子树if (!newNode) {} else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key) {// 判断属性是否变更let props = diffProps(oldNode.props, newNode.props)if (props.length) curPatches.push({ type: StateEnums.ChangeProps, props })// 遍历子树diffChildren(oldNode.children, newNode.children, index, patches)} else {// 节点不同，需要替换curPatches.push({ type: StateEnums.Replace, node: newNode })}if (curPatches.length) {if (patches[index]) {patches[index] = patches[index].concat(curPatches)} else {patches[index] = curPatches}}
}

判断属性的更改

判断属性的更改也分三个步骤

遍历旧的属性列表，查看每个属性是否还存在于新的属性列表中
遍历新的属性列表，判断两个列表中都存在的属性的值是否有变化
在第二步中同时查看是否有属性不存在与旧的属性列列表中

function diffProps(oldProps, newProps) {// 判断 Props 分以下三步骤// 先遍历 oldProps 查看是否存在删除的属性// 然后遍历 newProps 查看是否有属性值被修改// 最后查看是否有属性新增let change = []for (const key in oldProps) {if (oldProps.hasOwnProperty(key) && !newProps[key]) {change.push({prop: key})}}for (const key in newProps) {if (newProps.hasOwnProperty(key)) {const prop = newProps[key]if (oldProps[key] && oldProps[key] !== newProps[key]) {change.push({prop: key,value: newProps[key]})} else if (!oldProps[key]) {change.push({prop: key,value: newProps[key]})}}}return change
}

判断列表差异算法实现

这个算法是整个 Virtual Dom 中最核心的算法，且让我一一为你道来。这里的主要步骤其实和判断属性差异是类似的，也是分为三步

遍历旧的节点列表，查看每个节点是否还存在于新的节点列表中
遍历新的节点列表，判断是否有新的节点
在第二步中同时判断节点是否有移动 PS：该算法只对有 key 的节点做处理

function listDiff(oldList, newList, index, patches) {// 为了遍历方便，先取出两个 list 的所有 keyslet oldKeys = getKeys(oldList)let newKeys = getKeys(newList)let changes = []// 用于保存变更后的节点数据// 使用该数组保存有以下好处// 1.可以正确获得被删除节点索引// 2.交换节点位置只需要操作一遍 DOM// 3.用于 `diffChildren` 函数中的判断，只需要遍历// 两个树中都存在的节点，而对于新增或者删除的节点来说，完全没必要// 再去判断一遍let list = []oldList &&oldList.forEach(item => {let key = item.keyif (isString(item)) {key = item}// 寻找新的 children 中是否含有当前节点// 没有的话需要删除let index = newKeys.indexOf(key)if (index === -1) {list.push(null)} else list.push(key)})// 遍历变更后的数组let length = list.length// 因为删除数组元素是会更改索引的// 所有从后往前删可以保证索引不变for (let i = length - 1; i >= 0; i--) {// 判断当前元素是否为空，为空表示需要删除if (!list[i]) {list.splice(i, 1)changes.push({type: StateEnums.Remove,index: i})}}// 遍历新的 list，判断是否有节点新增或移动// 同时也对 `list` 做节点新增和移动节点的操作newList &&newList.forEach((item, i) => {let key = item.keyif (isString(item)) {key = item}// 寻找旧的 children 中是否含有当前节点let index = list.indexOf(key)// 没找到代表新节点，需要插入if (index === -1 || key == null) {changes.push({type: StateEnums.Insert,node: item,index: i})list.splice(i, 0, key)} else {// 找到了，需要判断是否需要移动if (index !== i) {changes.push({type: StateEnums.Move,from: index,to: i})move(list, index, i)}}})return { changes, list }
}function getKeys(list) {let keys = []let textlist &&list.forEach(item => {let keyif (isString(item)) {key = [item]} else if (item instanceof Element) {key = item.key}keys.push(key)})return keys
}

遍历子元素打标识

对于这个函数来说，主要功能就两个

判断两个列表差异
给节点打上标记

总体来说，该函数实现的功能很简单

function diffChildren(oldChild, newChild, index, patches) {let { changes, list } = listDiff(oldChild, newChild, index, patches)if (changes.length) {if (patches[index]) {patches[index] = patches[index].concat(changes)} else {patches[index] = changes}}// 记录上一个遍历过的节点let last = nulloldChild &&oldChild.forEach((item, i) => {let child = item && item.childrenif (child) {index =last && last.children ? index + last.children.length + 1 : index + 1let keyIndex = list.indexOf(item.key)let node = newChild[keyIndex]// 只遍历新旧中都存在的节点，其他新增或者删除的没必要遍历if (node) {dfs(item, node, index, patches)}} else index += 1last = item})
}

渲染差异

通过之前的算法，我们已经可以得出两个树的差异了。既然知道了差异，就需要局部去更新 DOM 了，下面就让我们来看看 Virtual Dom 算法的最后一步骤

这个函数主要两个功能

深度遍历树，将需要做变更操作的取出来
局部更新 DOM

整体来说这部分代码还是很好理解的

let index = 0
export default function patch(node, patchs) {let changes = patchs[index]let childNodes = node && node.childNodes// 这里的深度遍历和 diff 中是一样的if (!childNodes) index += 1if (changes && changes.length && patchs[index]) {changeDom(node, changes)}let last = nullif (childNodes && childNodes.length) {childNodes.forEach((item, i) => {index =last && last.children ? index + last.children.length + 1 : index + 1patch(item, patchs)last = item})}
}function changeDom(node, changes, noChild) {changes &&changes.forEach(change => {let { type } = changeswitch (type) {case StateEnums.ChangeProps:let { props } = changeprops.forEach(item => {if (item.value) {node.setAttribute(item.prop, item.value)} else {node.removeAttribute(item.prop)}})breakcase StateEnums.Remove:node.childNodes[change.index].remove()breakcase StateEnums.Insert:let domif (isString(change.node)) {dom = document.createTextNode(change.node)} else if (change.node instanceof Element) {dom = change.node.create()}node.insertBefore(dom, node.childNodes[change.index])breakcase StateEnums.Replace:node.parentNode.replaceChild(change.node.create(), node)breakcase StateEnums.Move:let fromNode = node.childNodes[change.from]let toNode = node.childNodes[change.to]let cloneFromNode = fromNode.cloneNode(true)let cloenToNode = toNode.cloneNode(true)node.replaceChild(cloneFromNode, toNode)node.replaceChild(cloenToNode, fromNode)breakdefault:break}})
}

最后

Virtual Dom 算法的实现也就是以下三步