首页 前端知识 diff算法知多少,html实体字符

diff算法知多少,html实体字符

2024-08-30 20:08:03 前端知识 前端哥 90 200 我要收藏

渲染真实DOM会有一定的开销,如果每次修改数据都进行真实DOM渲染,都会引起DOM树的重绘和重排,性能开销很大。那么有没有可能只修改一小部分数据而不渲染整个DOM呢?虚拟DOM和Diff算法可以实现。

怎么实现?

先根据真实DOM生成一颗虚拟DOM树

当某个DOM节点数据发生改变时,生成一个新的Vnode

新的Vnode和旧的oldVnode进行对比

通过patch函数一边比对一边给真实DOM打补丁或者创建Vnode、移除oldVnode等

有什么不一样?

真实DOM操作为一个属性一个属性去修改,开销较大。

虚拟DOM直接修改整个DOM节点再替换真实DOM

还有什么好处?

Vue的虚拟DOM数据更新机制是异步更新队列,并不是数据变更马上更新DOM,而是被推进一个数据更新异步队列统一更新。想要马上拿到DOM更新后DOM信息?有个API叫 Vue.nextTick

二、 Diff算法


传统Diff算法

遍历两棵树中的每一个节点,每两个节点之间都要做一次比较。

比如 a->e 、a->d 、a->b、a->c、a->a

  • 遍历完成的时间复杂度达到了O(n^2)

  • 对比完差异后还要计算最小转换方式,实现后复杂度来到了O(n^3)

在这里插入图片描述

Vue优化的Diff算法

Vue的diff算法只会比较同层级的元素,不进行跨层级比较

在这里插入图片描述

三、 Vue中的Diff算法实现


Vnode分类

EmptyVNode: 没有内容的注释节点

TextVNode: 文本节点

ElementVNode: 普通元素节点

ComponentVNode: 组件节点

CloneVNode: 克隆节点,可以是以上任意类型的节点,唯一的区别在于isCloned属性为true

Patch函数


patch函数接收以下参数:

  1. oldVnode:旧的虚拟节点

  2. Vnode:新的虚拟节点

  3. hydrating:是否要和真实DOM混合

  4. removeOnly:特殊的flag,用于 transition-group

处理流程大致分为以下步骤:

  1. vnode不存在,oldVnode存在时,移除oldVnode

  2. vnode存在,oldVnode不存在时,创建vnode

  3. vnode和oldVnode都存在时

  4. 如果vnode和oldVnode是同一个节点(通过sameVnode函数对比 后续详解),通过patchVnode进行后续比对工作

  5. 如果vnode和oldVnode不是同一个节点,那么根据vnode创建新的元素并挂载至oldVnode父元素下。如果组件根节点被替换,遍历更新父节点element。然后移除旧节点。如果oldVnode是服务端渲染元素节点,需要用hydrate函数将虚拟dom和真是dom进行映射

源码如下,已写好注释便于阅读

return function patch(oldVnode, vnode, hydrating, removeOnly) {

// 如果vnode不存在,但是oldVnode存在,移除oldVnode

if (isUndef(vnode)) {

if (isDef(oldVnode)) invokeDestroyHook(oldVnode)

return

}

let isInitialPatch = false

const insertedVnodeQueue = []

// 如果oldVnode不存在,但是vnode存在时,创建vnode

if (isUndef(oldVnode)) {

isInitialPatch = true

createElm(vnode, insertedVnodeQueue)

} else {

// 剩余情况为vnode和oldVnode都存在

// 判断是否为真实DOM元素

const isRealElement = isDef(oldVnode.nodeType)

if (!isRealElement && sameVnode(oldVnode, vnode)) {

// 如果vnode和oldVnode是同一个(通过sameVnode函数进行比对 后续详解)

// 受用patchVnode函数进行后续比对工作 (函数后续详解)

patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly)

} else {

// vnode和oldVnode不是同一个的情况

if (isRealElement) {

// 如果存在真实的节点,存在data-server-render属性

if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {

// 当旧的Vnode是服务端渲染元素,hydrating记为true

oldVnode.removeAttribute(SSR_ATTR)

hydrating = true

}

// 需要用hydrate函数将虚拟DOM和真实DOM进行映射

if (isTrue(hydrating)) {

// 需要合并到真实DOM上

if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {

// 调用insert钩子

invokeInsertHook(vnode, insertedVnodeQueue, true)

return oldVnode

} else if (process.env.NODE_ENV !== ‘production’) {

warn(

'The client-side rendered virtual DOM tree is not matching ’ +

'server-rendered content. This is likely caused by incorrect ’ +

'HTML markup, for example nesting block-level elements inside ’ +

'

, or missing . Bailing hydration and performing ’ +

‘full client-side render.’

)

}

}

// 如果不是服务端渲染元素或者合并到真实DOM失败,则创建一个空的Vnode节点去替换它

oldVnode = emptyNodeAt(oldVnode)

}

// 获取oldVnode父节点

const oldElm = oldVnode.elm

const parentElm = nodeOps.parentNode(oldElm)

// 根据vnode创建一个真实DOM节点并挂载至oldVnode的父节点下

createElm(

vnode,

insertedVnodeQueue,

oldElm._leaveCb ? null : parentElm,

nodeOps.nextSibling(oldElm)

)

// 如果组件根节点被替换,遍历更新父节点Element

if (isDef(vnode.parent)) {

let ancestor = vnode.parent

const patchable = isPatchable(vnode)

while (ancestor) {

for (let i = 0; i < cbs.destroy.length; ++i) {

cbs.destroyi

}

ancestor.elm = vnode.elm

if (patchable) {

for (let i = 0; i < cbs.create.length; ++i) {

cbs.create[i](emptyNode, ancestor)

}

// #6513

// invoke insert hooks that may have been merged by create hooks.

// e.g. for directives that uses the “inserted” hook.

const insert = ancestor.data.hook.insert

if (insert.merged) {

// start at index 1 to avoid re-invoking component mounted hook

for (let i = 1; i < insert.fns.length; i++) {

insert.fnsi

}

}

} else {

registerRef(ancestor)

}

ancestor = ancestor.parent

}

}

// 销毁旧节点

if (isDef(parentElm)) {

// 移除老节点

removeVnodes(parentElm, [oldVnode], 0, 0)

} else if (isDef(oldVnode.tag)) {

// 调用destroy钩子

invokeDestroyHook(oldVnode)

}

}

}

// 调用insert钩子并返回节点

invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)

return vnode.elm

}

sameVnode函数

Vue怎么判断是不是同一个节点?流程如下:

  1. 判断Key值是否一样

  2. tag的值是否一样

  3. isComment,这个不用太关注。

  4. 数据一样

  5. sameInputType(),专门对表单输入项进行判断的:input一样但是里面的type不一样算不同的inputType

从这里可以看出key对diff算法的辅助作用,可以快速定位是否为同一个元素,必须保证唯一性。

如果你用的是index作为key,每次打乱顺序key都会改变,导致这种判断失效,降低了Diff的效率。

因此,用好key也是Vue性能优化的一种方式。

  • 源码如下:

function sameVnode(a, b) {

return (

a.key === b.key && (

(

a.tag === b.tag &&

a.isComment === b.isComment &&

isDef(a.data) === isDef(b.data) &&

sameInputType(a, b)

) || (

isTrue(a.isAsyncPlaceholder) &&

a.asyncFactory === b.asyncFactory &&

isUndef(b.asyncFactory.error)

)

)

)

}

patchVnode函数

前置条件vnode和oldVnode是同一个节点

执行流程:

  1. 如果oldVnode和vnode引用一致,可以认为没有变化,return

  2. 如果oldVnode的isAsyncPlaceholder属性为true,跳过检查异步组件,return

  3. 如果oldVnode跟vnode都是静态节点,且具有相同的key,同时vnode是克隆节点或者v-once指令控制的节点时,只需要把oldVnode.elm和oldVnode.child都复制到vnode上,也不用再有其他操作,return

  4. 如果vnode不是文本节或注释节点

  5. 如果vnode和oldVnode都有子节点并且两者子节点不一致时,就调用updateChildren更新子节点

  6. 如果只有vnode有自子节点,则调用addVnodes创建子节点

  7. 如果只有oldVnode有子节点,则调用removeVnodes把这些子节点都删除

  8. 如果vnode文本为undefined,则清空vnode.elm文本

  9. 如果vnode是文本节点但是和oldVnode文本内容不同,只需更新文本。

源代码如下,已写好注释便于阅读

function patchVnode(oldVnode, vnode, insertedVnodeQueue, removeOnly) {

// 如果新老节点引用一致,直接返回。

if (oldVnode === vnode) {

return

}

const elm = vnode.elm = oldVnode.elm

// 如果oldVnode的isAsyncPlaceholder属性为true,跳过检查异步组件

if (isTrue(oldVnode.isAsyncPlaceholder)) {

if (isDef(vnode.asyncFactory.resolved)) {

hydrate(oldVnode.elm, vnode, insertedVnodeQueue)

} else {

vnode.isAsyncPlaceholder = true

}

return

}

// 如果新旧都是静态节点,vnode的key也相同

// 新vnode是克隆所得或新vnode有 v-once属性

// 则进行赋值,然后返回。vnode的componentInstance 保持不变

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

// 执行data.hook.prepatch 钩子

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

// 遍历调用 cbs.update 钩子函数,更新oldVnode所有属性

// 包括attrs、class、domProps、events、style、ref、directives

for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)

// 执行data.hook.update 钩子

if (isDef(i = data.hook) && isDef(i = i.update)) i(oldVnode, vnode)

}

// Vnode 的 text选项为undefined

if (isUndef(vnode.text)) {

if (isDef(oldCh) && isDef(ch)) {

//新老节点的children不同,执行updateChildren方法

if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)

} else if (isDef(ch)) {

// oldVnode children不存在 执行 addVnodes方法

if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, ‘’)

addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)

} else if (isDef(oldCh)) {

// vnode不存在执行removeVnodes方法

removeVnodes(elm, oldCh, 0, oldCh.length - 1)

} else if (isDef(oldVnode.text)) {

// 新旧节点都是undefined,且老节点存在text,清空文本。

nodeOps.setTextContent(elm, ‘’)

}

} else if (oldVnode.text !== vnode.text) {

// 新老节点文本内容不同,更新文本

nodeOps.setTextContent(elm, vnode.text)

}

if (isDef(data)) {

// 执行data.hook.postpatch钩子,至此 patch完成

if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)

}

}

updateChildren函数

重点!!!

前置条件:vnode和oldVnode的children不相等

整体的执行思路如下:

  1. vnode头对比oldVnode头

  2. vnode尾对比oldVnode尾

  3. vnode头对比oldVnode尾

  4. vnode尾对比oldVnode头

  5. 只要符合一种情况就进行patch,移动节点,移动下标等操作

  6. 都不对再在oldChild中找一个key和newStart相同的节点

  7. 找不到,新建一个。

  8. 找到,获取这个节点,判断它和newStartVnode是不是同一个节点

  • 如果是相同节点,进行patch 然后将这个节点插入到oldStart之前,newStart下标继续移动

  • 如果不是相同节点,需要执行createElm创建新元素

为什么会有头对尾、尾对头的操作?

  • 可以快速检测出reverse操作,加快diff效率。

源码如下 已写好注释便于阅读:

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {

// 定义变量

let oldStartIdx = 0 // 老节点Child头下标

let newStartIdx = 0 // 新节点Child头下标

let oldEndIdx = oldCh.length - 1 // 老节点Child尾下标

let oldStartVnode = oldCh[0] // 老节点Child头结点

let oldEndVnode = oldCh[oldEndIdx] // 老节点Child尾结点

let newEndIdx = newCh.length - 1 // 新节点Child尾下标
自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。

深知大多数前端工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!

因此收集整理了一份《2024年Web前端开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。

img

既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上前端开发知识点,真正体系化!

由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新!

如果你觉得这些内容对你有帮助,可以扫码获取!!(备注:前端)

最后

正值金三银四招聘旺季,很多小伙伴都询问我有没有前端方面的面试题,特地整理出来赠送给大家!

资料领取方式:点击这里前往免费获取

为、OPPO等大厂,18年进入阿里一直到现在。**

深知大多数前端工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!

因此收集整理了一份《2024年Web前端开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。

[外链图片转存中…(img-D39iQLPY-1712095022660)]

[外链图片转存中…(img-LQsjWGwB-1712095022660)]

既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上前端开发知识点,真正体系化!

[外链图片转存中…(img-SfTTroSq-1712095022661)]

由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新!

如果你觉得这些内容对你有帮助,可以扫码获取!!(备注:前端)

最后

正值金三银四招聘旺季,很多小伙伴都询问我有没有前端方面的面试题,特地整理出来赠送给大家!

资料领取方式:点击这里前往免费获取

前端资料图.PNG

转载请注明出处或者链接地址:https://www.qianduange.cn//article/17296.html
标签
评论
发布的文章

JWT(JSON WEB TOKEN)详解

2024-09-10 23:09:36

NPM 常用命令(十二)

2024-09-10 23:09:24

大家推荐的文章
会员中心 联系我 留言建议 回顶部
复制成功!