DIff算法看不懂就一起来锤我(带图)

冷不防 2022-09-11 03:25 172阅读 0赞

# 大厂技术 高级前端 Node进阶    #

点击上方 程序员成长指北，关注公众号

回复1，加入高级Node交流群

![b3a92f40f5f653420aa4536509dedf5d.png][]

# 前言 #

面试官:"你了解`虚拟DOM(Virtual DOM)`跟`Diff算法`吗,请描述一下它们";

我:"额,...鹅,那个",完了????,突然智商不在线,没组织好语言没答好或者压根就答不出来;

所以这次我总结一下相关的知识点,让你可以有一个清晰的认知之余也会让你在今后遇到这种情况可以**坦然自若,应付自如,游刃有余**:

--------------------

## 相关知识点: ##

*  虚拟DOM(Virtual DOM):
 *   *  **什么是虚拟dom**
     *  **为什么要使用虚拟dom**
     *  虚拟DOM库
 *  DIFF算法:
 *   *  init函数
     *  h函数
     *  **patch函数**
     *  **patchVnode函数**
     *  **updateChildren函数**
     *  snabbDom源码

--------------------

## 虚拟DOM(Virtual DOM) ##

### 什么是虚拟DOM ###

一句话总结虚拟DOM就是一个用来描述真实DOM的**javaScript对象**,这样说可能不够形象,那我们来举个????:分别用代码来描述`真实DOM`以及`虚拟DOM`

`真实DOM`:

<ul class="list">
        <li>a</li>
        <li>b</li>
        <li>c</li>
    </ul>
    复制代码

`对应的虚拟DOM`:

let vnode = h('ul.list', [
      h('li','a'),
      h('li','b'),
      h('li','c'),
    ])
    
    console.log(vnode)
    复制代码

#### 控制台打印出来的**Vnode**: ####

![7a60bf225f2ad209c391156d51305ffd.png][] image.png

#### h函数生成的虚拟DOM这个JS对象(Vnode)的源码: ####

export interface VNodeData {
        props?: Props
        attrs?: Attrs
        class?: Classes
        style?: VNodeStyle
        dataset?: Dataset
        on?: On
        hero?: Hero
        attachData?: AttachData
        hook?: Hooks
        key?: Key
        ns?: string // for SVGs
        fn?: () => VNode // for thunks
        args?: any[] // for thunks
        [key: string]: any // for any other 3rd party module
    }
    
    export type Key = string | number
    
    const interface VNode = {
        sel: string | undefined, // 选择器
        data: VNodeData | undefined, // VNodeData上面定义的VNodeData
        children: Array<VNode | string> | undefined, //子节点,与text互斥
        text: string | undefined, // 标签中间的文本内容
        elm: Node | undefined, // 转换而成的真实DOM
        key: Key | undefined // 字符串或者数字
    }
    
    复制代码

##### 补充: #####

上面的h函数大家可能有点熟悉的感觉但是一时间也没想起来,没关系我来帮大伙回忆; `开发中常见的现实场景,render函数渲染`:

// 案例1 vue项目中的main.js的创建vue实例
    new Vue({
      router,
      store,
      render: h => h(App)
    }).$mount("#app");
    
    //案例2 列表中使用render渲染
    columns: [
        {
            title: "操作",
            key: "action",
            width: 150,
            render: (h, params) => {
                return h('div', [
                    h('Button', {
                        props: {
                            size: 'small'
                        },
                        style: {
                            marginRight: '5px',
                            marginBottom: '5px',
                        },
                        on: {
                            click: () => {
                                this.toEdit(params.row.uuid);
                            }
                        }
                    }, '编辑')
                ]);
            }
        }
    ]
    复制代码

--------------------

### 为什么要使用虚拟DOM ###

*  MVVM框架解决视图和状态同步问题
 *  模板引擎可以简化视图操作,没办法跟踪状态
 *  虚拟DOM跟踪状态变化
 *  参考github上virtual-dom\[1\]的动机描述
 *   *  虚拟DOM可以维护程序的状态,跟踪上一次的状态
     *  通过比较前后两次状态差异更新真实DOM
 *  跨平台使用
 *   *  浏览器平台渲染DOM
     *  服务端渲染SSR(Nuxt.js/Next.js),前端是vue向,后者是react向
     *  原生应用(Weex/React Native)
     *  小程序(mpvue/uni-app)等
 *  真实DOM的属性很多，创建DOM节点开销很大
 *  虚拟DOM只是普通JavaScript对象，描述属性并不需要很多，创建开销很小
 *  **复杂视图情况下提升渲染性能**(操作dom性能消耗大,减少操作dom的范围可以提升性能)

**灵魂发问**:使用了虚拟DOM就一定会比直接渲染真实DOM快吗?答案当然是`否定`的,且听我说:![33f1b2ab26516fc9fdfd60f810c012a6.png][]

**举例**:当一个节点变更时DOMA->DOMB

![a2ec1c9b8ad0a5ce43a49636f5553959.png][]上述情况: `示例1`是创建一个`DOMB`然后替换掉`DOMA`; `示例2`去`创建虚拟DOM+DIFF算法`比对发现`DOMB`跟`DOMA`不是相同的节点,最后还是创建一个`DOMB`然后替换掉`DOMA`; 可以明显看出1是更快的,同样的结果,2还要去创建虚拟DOM+DIFF算啊对比 所以说使用虚拟DOM比直接操作真实DOM就一定要快这个说法是`错误的,不严谨的`

**举例**:当DOM树里面的某个子节点的内容变更时:

![3c47d7c5f15594a607f45693d5b83071.png][]当一些复杂的节点,比如说一个父节点里面有多个子节点,当只是一个子节点的内容发生了改变,那么我们没有必要像`示例1`重新去渲染这个`DOM树`,这个时候`虚拟DOM+DIFF算法`就能够得到很好的体现,我们通过`示例2`使用`虚拟DOM+Diff算法`去找出改变了的子节点更新它的内容就可以了

总结:**复杂视图情况下提升渲染性能**,因为`虚拟DOM+Diff算法`可以精准找到DOM树变更的地方,减少DOM的操作(重排重绘)

--------------------

### 虚拟dom库 ###

*  Snabbdom\[2\]
 *   *  Vue.js2.x内部使用的虚拟DOM就是改造的Snabbdom
     *  大约200SLOC(single line of code)
     *  通过模块可扩展
     *  源码使用TypeScript开发
     *  最快的Virtual DOM之一
 *  virtual-dom\[3\]

--------------------

## Diff算法 ##

在看完上述的文章之后相信大家已经对Diff算法有一个初步的概念,没错,Diff算法其实就是找出两者之间的差异;

> diff 算法首先要明确一个概念就是 Diff 的对象是虚拟DOM（virtual dom），更新真实 DOM 是 Diff 算法的结果。

下面我将会手撕`snabbdom`源码核心部分为大家打开`Diff`的心,给点耐心,别关网页,我知道你们都是这样:

![b27d6eae1cdd42cd0aac68d30e93d1d2.png][] src=http\_\_\_img.wxcha.com\_file\_201905\_17\_f5a4d33d48.jpg&refer=http\_\_\_img.wxcha.jpeg

--------------------

## snabbdom的核心 ##

*  `init()`设置模块.创建`patch()`函数
 *  使用`h()`函数创建JavaScript对象`(Vnode)`描述`真实DOM`
 *  `patch()`比较`新旧两个Vnode`
 *  把变化的内容更新到`真实DOM树`

### init函数 ###

init函数时设置模块,然后创建patch()函数,我们先通过场景案例来有一个直观的体现:

import {init} from 'snabbdom/build/package/init.js'
    import {h} from 'snabbdom/build/package/h.js'
    
    // 1.导入模块
    import {styleModule} from "snabbdom/build/package/modules/style";
    import {eventListenersModule} from "snabbdom/build/package/modules/eventListeners";
    
    // 2.注册模块
    const patch = init([
      styleModule,
      eventListenersModule
    ])
    
    // 3.使用h()函数的第二个参数传入模块中使用的数据(对象)
    let vnode = h('div', [
      h('h1', {style: {backgroundColor: 'red'}}, 'Hello world'),
      h('p', {on: {click: eventHandler}}, 'Hello P')
    ])
    
    function eventHandler() {
      alert('疼,别摸我')
    }
    
    const app = document.querySelector('#app')
    
    patch(app,vnode)
    复制代码

当init使用了导入的模块就能够在h函数中用这些模块提供的api去创建`虚拟DOM(Vnode)对象`;在上文中就使用了`样式模块`以及`事件模块`让创建的这个虚拟DOM具备样式属性以及事件属性,最终通过`patch函数`对比`两个虚拟dom`(会先把app转换成虚拟dom),更新视图;

![f5ec19ac5f92f25e6a4d0e2714fb0e62.png][] image.png

我们再简单看看init的源码部分:

// src/package/init.ts
    /* 第一参数就是各个模块
       第二参数就是DOMAPI,可以把DOM转换成别的平台的API,
    也就是说支持跨平台使用,当不传的时候默认是htmlDOMApi,见下文
       init是一个高阶函数,一个函数返回另外一个函数,可以缓存modules,与domApi两个参数,
    那么以后直接只传oldValue跟newValue(vnode)就可以了*/
    export function init (modules: Array<Partial<Module>>, domApi?: DOMAPI) {
    
    ...
    
    return function patch (oldVnode: VNode | Element, vnode: VNode): VNode {}
    }
    复制代码

--------------------

### h函数 ###

些地方也会用`createElement`来命名,它们是一样的东西,都是创建`虚拟DOM`的,在上述文章中相信大伙已经对h函数有一个初步的了解并且已经联想了使用场景,就不作场景案例介绍了,直接上源码部分:

// 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 {
      var data: VNodeData = {}
      var children: any
      var text: any
      var i: number
        ...
      return vnode(sel, data, children, text, undefined) //最终返回一个vnode函数
    };
    复制代码

// 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 } //最终生成Vnode对象
    }
    复制代码

**总结**:`h函数`先生成一个`vnode`函数,然后`vnode`函数再生成一个`Vnode`对象(虚拟DOM对象)

#### 补充: ####

在h函数源码部分涉及一个`函数重载`的概念,简单说明一下:

*  参数个数或参数类型不同的函数()
 *  JavaScript中没有重载的概念
 *  TypeScript中有重载,不过重载的实现还是通过代码调整参数

> 重载这个概念个参数相关,和返回值无关

*  实例1(函数重载-参数个数)

function add(a:number,b:number){
    
    console.log(a+b)
    
    }
    
    function add(a:number,b:number,c:number){
    
    console.log(a+b+c)
    
    }
    
    add(1,2)
    
    add(1,2,3)
    
    复制代码

*  实例2(函数重载-参数类型)

function add(a:number,b:number){
    
    console.log(a+b)
    
    }
    
    function add(a:number,b:string){
    
    console.log(a+b)
    
    }
    
    add(1,2)
    
    add(1,'2')
    
    复制代码

--------------------

### patch函数(核心) ###

![2aed0e6f13aae052edf39146dfa8addf.png][] src=http\_\_\_shp.qpic.cn\_qqvideo\_ori\_0\_e3012t7v643\_496\_280\_0&refer=http\_\_\_shp.qpic.jpeg

要是看完前面的铺垫,看到这里你可能走神了,`醒醒啊,这是核心啊,上高地了兄弟`;

*  pactch(oldVnode,newVnode)
 *  把新节点中变化的内容渲染到真实DOM,最后返回新节点作为下一次处理的旧节点(核心)
 *  对比新旧`VNode`是否相同节点(节点的key和sel相同)
 *  如果不是相同节点,删除之前的内容,重新渲染
 *  如果是相同节点,再判断新的`VNode`是否有`text`,如果有并且和`oldVnode`的`text`不同直接更新文本内容`(patchVnode)`
 *  如果新的VNode有children,判断子节点是否有变化`(updateChildren,最麻烦,最难实现)`

源码:

return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {    
        let i: number, elm: Node, parent: Node
        const insertedVnodeQueue: VNodeQueue = []
        // cbs.pre就是所有模块的pre钩子函数集合
        for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()
        // isVnode函数时判断oldVnode是否是一个虚拟DOM对象
        if (!isVnode(oldVnode)) {
            // 若不是即把Element转换成一个虚拟DOM对象
            oldVnode = emptyNodeAt(oldVnode)
        }
        // sameVnode函数用于判断两个虚拟DOM是否是相同的,源码见补充1;
        if (sameVnode(oldVnode, vnode)) {
            // 相同则运行patchVnode对比两个节点,关于patchVnode后面会重点说明(核心)
            patchVnode(oldVnode, vnode, insertedVnodeQueue)
        } else {
            elm = oldVnode.elm! // !是ts的一种写法代码oldVnode.elm肯定有值
            // parentNode就是获取父元素
            parent = api.parentNode(elm) as Node
    
            // createElm是用于创建一个dom元素插入到vnode中(新的虚拟DOM)
            createElm(vnode, insertedVnodeQueue)
    
            if (parent !== null) {
                // 把dom元素插入到父元素中,并且把旧的dom删除
                api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))// 把新创建的元素放在旧的dom后面
                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
    }
    复制代码

#### 补充1: sameVnode函数 ####

function sameVnode(vnode1: VNode, vnode2: VNode): boolean { 通过key和sel选择器判断是否是相同节点
        return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel
    }
    复制代码

--------------------

### patchVnode ###

*  第一阶段触发`prepatch`函数以及`update`函数(都会触发prepatch函数,两者不完全相同才会触发update函数)
 *  第二阶段,真正对比新旧`vnode`差异的地方
 *  第三阶段,触发`postpatch`函数更新节点

源码:

function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
        const hook = vnode.data?.hook
        hook?.prepatch?.(oldVnode, vnode)
        const elm = vnode.elm = oldVnode.elm!
        const oldCh = oldVnode.children as VNode[]
        const ch = vnode.children as VNode[]
        if (oldVnode === vnode) return
        if (vnode.data !== undefined) {
            for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
            vnode.data.hook?.update?.(oldVnode, vnode)
        }
        if (isUndef(vnode.text)) { // 新节点的text属性是undefined
            if (isDef(oldCh) && isDef(ch)) { // 当新旧节点都存在子节点
                if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue) //并且他们的子节点不相同执行updateChildren函数,后续会重点说明(核心)
            } else if (isDef(ch)) { // 只有新节点有子节点
                // 当旧节点有text属性就会把''赋予给真实dom的text属性
                if (isDef(oldVnode.text)) api.setTextContent(elm, '') 
                // 并且把新节点的所有子节点插入到真实dom中
                addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
            } else if (isDef(oldCh)) { // 清除真实dom的所有子节点
                removeVnodes(elm, oldCh, 0, oldCh.length - 1)
            } else if (isDef(oldVnode.text)) { // 把''赋予给真实dom的text属性
                api.setTextContent(elm, '')
            }
        } else if (oldVnode.text !== vnode.text) { //若旧节点的text与新节点的text不相同
            if (isDef(oldCh)) { // 若旧节点有子节点,就把所有的子节点删除
                removeVnodes(elm, oldCh, 0, oldCh.length - 1)
            }
            api.setTextContent(elm, vnode.text!) // 把新节点的text赋予给真实dom
        }
        hook?.postpatch?.(oldVnode, vnode) // 更新视图
    }
    复制代码

看得可能有点蒙蔽,下面再上一副思维导图:

![db19b64c9b583cd85dc7d44b1423ae4d.png][] image.png

--------------------

### 题外话:diff算法简介 ###

**传统diff算法**

*  虚拟DOM中的Diff算法
 *  `传统算法`查找两颗树每一个节点的差异
 *  会运行n1(dom1的节点数)\*n2(dom2的节点数)次方去对比,找到差异的部分再去更新

![8f5be582a8ab580d71c2006ed59fc6b5.png][] image.png

**snabbdom的diff算法优化**

*  Snbbdom根据DOM的特点对传统的diff算法做了`优化`
 *  DOM操作时候很少会跨级别操作节点
 *  只比较`同级别`的节点

![7d23ee8b2655b54a120e8d484f0e761c.png][] image.png ![f6b9ca88ea6eec6fc206ee194e4f4817.png][] src=http\_\_\_img.wxcha.com\_file\_202004\_03\_1ed2e19e4f.jpg&refer=http\_\_\_img.wxcha.jpeg

下面我们就会介绍`updateChildren`函数怎么去对比子节点的`异同`,也是`Diff算法`里面的一个核心以及难点;

--------------------

### updateChildren(核中核:判断子节点的差异) ###

*  这个函数我分为三个部分,`部分1:声明变量`,`部分2:同级别节点比较`,`部分3:循环结束的收尾工作`(见下图);

![fa2c64bfb153d5cd7b4b1454813ee788.png][] image.png

*  `同级别节点比较`的`五种`情况:

1.  `oldStartVnode/newStartVnode`(旧开始节点/新开始节点)相同
2.  `oldEndVnode/newEndVnode`(旧结束节点/新结束节点)相同
3.  `oldStartVnode/newEndVnode`(旧开始节点/新结束节点)相同
4.  `oldEndVnode/newStartVnode`(旧结束节点/新开始节点)相同
5.  `特殊情况当1,2,3,4的情况都不符合`的时候就会执行,在`oldVnodes`里面寻找跟`newStartVnode`一样的节点然后位移到`oldStartVnode`,若没有找到在就`oldStartVnode`创建一个

*  执行过程是一个循环,在每次循环里,只要执行了上述的情况的五种之一就会结束一次循环
 *  `循环结束的收尾工作`:直到oldStartIdx>oldEndIdx || newStartIdx>newEndIdx(代表旧节点或者新节点已经遍历完)
 *  为了更加直观的了解,我们再来看看`同级别节点比较`的`五种`情况的实现细节:
    
    #### 新开始节点和旧开始节点(情况1) ####
    
    ![d04cdb05d8fcfb0ad88de5d7af030cdf.png][] image.png
    
     *  若`情况1符合:(从新旧节点的开始节点开始对比`,`oldCh[oldStartIdx]和newCh[newStartIdx]`进行`sameVnode(key和sel相同)`判断是否相同节点)
     *  则执行`patchVnode`找出两者之间的差异,更新图;如没有差异则什么都不操作,结束一次循环
     *  `oldStartIdx++/newStartIdx++`
    
    #### 新结束节点和旧结束节点(情况2) ####
    
    ![0770a8ec07824c2ed0c6c7196aae2740.png][] image.png
    
     *  若`情况1不符合`就判断`情况2`,若符合:(从新旧节点的结束节点开始对比,`oldCh[oldEndIdx]和newCh[newEndIdx]`对比,执行`sameVnode(key和sel相同)`判断是否相同节点)
     *  执行`patchVnode`找出两者之间的差异,更新视图,;如没有差异则什么都不操作,结束一次循环
     *  `oldEndIdx--/newEndIdx--`
    
    #### 旧开始节点/新结束节点(情况3) ####
    
    ![7ddcae954c6704b880d231ac590e117c.png][] image.png
    
     *  若`情况1,2`都不符合,就会尝试情况3:(旧节点的开始节点与新节点的结束节点开始对比,`oldCh[oldStartIdx]和newCh[newEndIdx]`对比,执行`sameVnode(key和sel相同)`判断是否相同节点)
     *  执行`patchVnode`找出两者之间的差异,更新视图,如没有差异则什么都不操作,结束一次循环
     *  `oldCh[oldStartIdx]对应的真实dom`位移到`oldCh[oldEndIdx]对应的真实dom`后
     *  `oldStartIdx++/newEndIdx--`;
    
    #### 旧结束节点/新开始节点(情况4) ####
    
    ![95ff951141356298452b52c668c284f9.png][] image.png
    
     *  若`情况1,2,3`都不符合,就会尝试情况4:(旧节点的结束节点与新节点的开始节点开始对比,`oldCh[oldEndIdx]和newCh[newStartIdx]`对比,执行`sameVnode(key和sel相同)`判断是否相同节点)
     *  执行`patchVnode`找出两者之间的差异,更新视图,如没有差异则什么都不操作,结束一次循环
     *  `oldCh[oldEndIdx]对应的真实dom`位移到`oldCh[oldStartIdx]对应的真实dom`前
     *  `oldEndIdx--/newStartIdx++`;
    
    #### 新开始节点/旧节点数组中寻找节点(情况5) ####
    
    ![4b091ca4bde664bd7c2527362687c2a2.png][] image.png
    
     *  从旧节点里面寻找,若寻找到与`newCh[newStartIdx]`相同的节点(且叫`对应节点[1]`),执行`patchVnode`找出两者之间的差异,更新视图,如没有差异则什么都不操作,结束一次循环
     *  `对应节点[1]对应的真实dom`位移到`oldCh[oldStartIdx]对应的真实dom`前
    
    ![b99c23988368f7f1d61006ba50f6b949.png][] image.png
    
     *  `若没有寻找到相同的节点`,则创建一个与`newCh[newStartIdx]`节点对应的`真实dom`插入到`oldCh[oldStartIdx]对应的真实dom`前
     *  `newStartIdx++`
    
    ![17820957839df25cfa664283fc7eafad.png][] 379426071b8130075b11ba142f9468e2.jpeg
    
    --------------------
    
    下面我们再介绍一下`结束循环`的收尾工作`(oldStartIdx>oldEndIdx || newStartIdx>newEndIdx)`:
    
    ![474cc3a6ed0d719d831546508ad6d0ed.png][] image.png
    
     *  `新节点的所有子节点`先遍历完(`newStartIdx>newEndIdx`),循环结束
     *  `新节点的所有子节点`遍历结束就是把没有对应相同节点的`子节点`删除
    
    ![75a0f7e48bbc75f11494af7f77bf6ed8.png][] image.png
    
     *  `旧节点的所有子节点`先遍历完(`oldStartIdx>oldEndIdx`),循环结束
     *  `旧节点的所有子节点`遍历结束就是在多出来的`子节点`插入到`旧节点结束节点`前;(源码:`newCh[newEndIdx + 1].elm)`,就是对应的`旧结束节点的真实dom`,newEndIdx+1是因为在匹配到相同的节点需要-1,所以需要加回来就是结束节点
    
    最后附上源码:
    
        function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
            let oldStartIdx = 0;                // 旧节点开始节点索引
            let 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]; // Vnode might have been moved left
                }
                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)) { // 判断情况1
                    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
                    oldStartVnode = oldCh[++oldStartIdx];
                    newStartVnode = newCh[++newStartIdx];
                }
                else if (sameVnode(oldEndVnode, newEndVnode)) {   // 情况2
                    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
                    oldEndVnode = oldCh[--oldEndIdx];
                    newEndVnode = newCh[--newEndIdx];
                }
                else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right情况3
                    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情况4
                    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
                    api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
                    oldEndVnode = oldCh[--oldEndIdx];
                    newStartVnode = newCh[++newStartIdx];
                }
                else {                                             // 情况5
                    if (oldKeyToIdx === undefined) {
                        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
                    }
                    idxInOld = oldKeyToIdx[newStartVnode.key];
                    if (isUndef(idxInOld)) { // New element        // 创建新的节点在旧节点的新节点前
                        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm);
                    }
                    else {
                        elmToMove = oldCh[idxInOld];
                        if (elmToMove.sel !== newStartVnode.sel) { // 创建新的节点在旧节点的新节点前
                            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm);
                        }
                        else {
                                                                   // 在旧节点数组中找到相同的节点就对比差异更新视图,然后移动位置
                            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
                            oldCh[idxInOld] = undefined;
                            api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm);
                        }
                    }
                    newStartVnode = newCh[++newStartIdx];
                }
            }
            // 循环结束的收尾工作
            if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
                if (oldStartIdx > oldEndIdx) {
                    // newCh[newEndIdx + 1].elm就是旧节点数组中的结束节点对应的dom元素
                    // newEndIdx+1是因为在之前成功匹配了newEndIdx需要-1
                    // newCh[newEndIdx + 1].elm,因为已经匹配过有相同的节点了,它就是等于旧节点数组中的结束节点对应的dom元素(oldCh[oldEndIdx + 1].elm)
                    before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;
                    // 把新节点数组中多出来的节点插入到before前
                    addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
                }
                else {
                    // 这里就是把没有匹配到相同节点的节点删除掉
                    removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
                }
            }
        }
        复制代码
    
    --------------------
    
    #### key的作用 ####
    
     *  Diff操作可以`更加快速`;
     *  Diff操作可以更加准确;`(避免渲染错误)`
     *  `不推荐使用索引`作为key
    
    以下我们看看这些作用的实例:
    
    ##### Diff操作可以更加准确;`(避免渲染错误)`: #####
    
    实例:a,b,c三个dom元素中的b,c间插入一个z元素
    
    没有设置key ![8976c52f7d4054b48d960995408f6266.png][]当设置了key:
    
    ![38d476408c6f678598fd9a9e2edd4433.png][] image.png
    
    ##### Diff操作可以更加准确;`(避免渲染错误)` #####
    
    实例:a,b,c三个dom元素,修改了a元素的某个属性再去在a元素前新增一个z元素
    
    没有设置key:
    
    ![70c10f15a7c0f70d1b8dd098ff8b1159.png][] image.png ![1f946b090ff81b502e923b61cb67a073.png][] image.png
    
    因为没有设置key,默认都是undefined,所以节点都是相同的,更新了text的内容但还是沿用了之前的dom,所以实际上`a->z(a原本打勾的状态保留了,只改变了text),b->a,c->b,d->c`,遍历完毕发现还要增加一个dom,在最后新增一个text为d的dom元素
    
    设置了key:
    
    ![fac71371f51e00f4fbb859a1025a33ee.png][] image.png ![d4a2ad7f389037f9562ab3d4d0cc5a5c.png][] image.png
    
    当设置了key,a,b,c,d都有对应的key,`a->a,b->b,c->c,d->d`,内容相同无需更新,遍历结束,新增一个text为z的dom元素
    
    ##### `不推荐使用索引`作为key: #####
    
    设置索引为key:
    
    ![32e40e703152534db5b770fbfd1dd4ca.png][] image.png
    
    这明显效率不高,我们只希望找出不同的节点更新,而使用索引作为key会增加运算时间,我们可以把key设置为与节点text为一致就可以解决这个问题:
    
    ![81766a51c4438eebb5e0ebf6a9f48e31.png][] image.png
    
    --------------------
    
    ## 最后 ##
    
    如有描述错误或者不明的地方请在下方评论联系我,我会立刻更新,如有收获,请为我点个赞????这是对我的莫大的支持,谢谢各位
    
    关于本文  
    
    
    # 作者：渣渣xiong #
    
    https://juejin.cn/post/7000266544181674014
    
    Node 社群  
    
    
    我组建了一个氛围特别好的 Node.js 社群，里面有很多 Node.js小伙伴，如果你对Node.js学习感兴趣的话（后续有计划也可以），我们可以一起进行Node.js相关的交流、学习、共建。下方加 考拉 好友回复「Node」即可。
    
    ![b8cc23d74429a58c10c94fb80273eb31.png][]
    
     **“分享、点赞、在看” 支持一波** ![fbe69fde2cd73a12049505149e7f313f.png][]

[b3a92f40f5f653420aa4536509dedf5d.png]: /images/20220828/bf246cb532734511869bf1545f07ae16.png
[7a60bf225f2ad209c391156d51305ffd.png]: /images/20220828/4c9ceffcc96843e681f1fb9af7534de6.png
[33f1b2ab26516fc9fdfd60f810c012a6.png]: /images/20220828/8d97bcfdd89e4c3cb1cdde5480ac9770.png
[a2ec1c9b8ad0a5ce43a49636f5553959.png]: /images/20220828/31490cc24a6048b0aaad7f5260cee4c5.png
[3c47d7c5f15594a607f45693d5b83071.png]: /images/20220828/85b779c7a99541138fe211c2e0db703d.png
[b27d6eae1cdd42cd0aac68d30e93d1d2.png]: /images/20220828/e7cbad4c0aaa49468ab8c064baf708d8.png
[f5ec19ac5f92f25e6a4d0e2714fb0e62.png]: /images/20220828/4ba33497fe124b05a8d090a7ae491048.png
[2aed0e6f13aae052edf39146dfa8addf.png]: /images/20220828/dcf787f008ab444aa805c44ec194de6e.png
[db19b64c9b583cd85dc7d44b1423ae4d.png]: /images/20220828/6bcb9d78269e4e7e85276c7454fa6a50.png
[8f5be582a8ab580d71c2006ed59fc6b5.png]: /images/20220828/f023e76eb6174cc684251b243939305e.png
[7d23ee8b2655b54a120e8d484f0e761c.png]: https://img-blog.csdnimg.cn/img_convert/7d23ee8b2655b54a120e8d484f0e761c.png
[f6b9ca88ea6eec6fc206ee194e4f4817.png]: /images/20220828/8952addebcdd449e8790e7a49b47dcb7.png
[fa2c64bfb153d5cd7b4b1454813ee788.png]: /images/20220828/002fe769646747f0a894fe27e72d7be7.png
[d04cdb05d8fcfb0ad88de5d7af030cdf.png]: /images/20220828/db3d466fc1074372bbd9c119605d4eda.png
[0770a8ec07824c2ed0c6c7196aae2740.png]: /images/20220828/eeb1ae3cdcac450c8fd0c4ffeeab4f31.png
[7ddcae954c6704b880d231ac590e117c.png]: /images/20220828/e58817065c7141269d5c5cb35a510957.png
[95ff951141356298452b52c668c284f9.png]: /images/20220828/7971604921764fbbab35689f85c7b7be.png
[4b091ca4bde664bd7c2527362687c2a2.png]: /images/20220828/a9ef981780a145ebb74a91128f38b6db.png
[b99c23988368f7f1d61006ba50f6b949.png]: /images/20220828/e7ffeecec4a74f048d3e195ed254b566.png
[17820957839df25cfa664283fc7eafad.png]: /images/20220828/8e9db6d73d1a4f9285e6a3d0c21412d6.png
[474cc3a6ed0d719d831546508ad6d0ed.png]: /images/20220828/26285e2cc3e94a5baad7027d4de5f38f.png
[75a0f7e48bbc75f11494af7f77bf6ed8.png]: /images/20220828/62b2b0c7461843e3a44e4995d42ac27e.png
[8976c52f7d4054b48d960995408f6266.png]: /images/20220828/cc39ee0efb5b4046b9ca020eedffcb9d.png
[38d476408c6f678598fd9a9e2edd4433.png]: /images/20220828/46bc0e597bbf4a6490d7054b20fe5ca8.png
[70c10f15a7c0f70d1b8dd098ff8b1159.png]: https://img-blog.csdnimg.cn/img_convert/70c10f15a7c0f70d1b8dd098ff8b1159.png
[1f946b090ff81b502e923b61cb67a073.png]: /images/20220828/3483f84e5d16468389fdeb4985370585.png
[fac71371f51e00f4fbb859a1025a33ee.png]: https://img-blog.csdnimg.cn/img_convert/fac71371f51e00f4fbb859a1025a33ee.png
[d4a2ad7f389037f9562ab3d4d0cc5a5c.png]: /images/20220828/f2ce88780f154f38b58342fc1c96c4f7.png
[32e40e703152534db5b770fbfd1dd4ca.png]: /images/20220828/ccfa1b5e92e042ccb678fa3bd877363e.png
[81766a51c4438eebb5e0ebf6a9f48e31.png]: /images/20220828/64ee85ff60d148cea63b35a2b8ec92c4.png
[b8cc23d74429a58c10c94fb80273eb31.png]: /images/20220828/2451d45a2c17430389a9ccb5b71b89ef.png
[fbe69fde2cd73a12049505149e7f313f.png]: /images/20220828/cc4e6fce845444e59b019425a5ee7f6b.png