简单diff算法

1.Diff算法介绍

在vue中用于比较新旧vnode的子节点都是一组节点时，为了以最小的性能开销完成更新，需要比较两个子节点，用与比较的算法就叫作diff算法。

2.简单diff算法几种不同情况

• 节点顺序、个数相同，节点文本不同，直接更新节点文本
• 节点顺序相同，但个数不同（又分为新节点多或者旧节点多）
• 节点个数相同，但顺序不同（又分为标签类型相同和标签类型不同）

2.1 节点顺序、个数相同，节点文本不同，复用节点更改文本

看一个例子，通过这组虚拟节点进行更新的步骤（节点顺序相同，且个数相同）

const oldVNode = {
    type: 'div',
    children: [
        { type: 'p', children: '1' },
        { type: 'p', children: '2' },
        { type: 'p', children: '3' }
    ]
}
const newVNode = {
    type: 'div',
    children: [
        { type: 'p', children: '4' },
        { type: 'p', children: '5' },
        { type: 'p', children: '6' }
    ]
}

function patchChildren(n1, n2) {
    if (typeof n2.chilren === 'string') {
        // 省略部分代码
    } else if (Array.isArray(n2.children)) {
        // 更新逻辑
        const oldChildren = n1.children
        const newChildren = n2.children
        for (let i = 0; i < newChildren.length; i++) {
            // 更新子节点
            patch(oldChildren[i], newChildren[i])
        }
    } else {
        // 省略部分代码
    }
}

2.2 如果节点的个数对不上怎么解决？（节点顺序相同，但个数不同）

原理：多余的新节点挂载，多余的旧节点卸载，其他的直接复用

步骤：

• 获取新旧节点长度，Math.min()获取相同长度commonLength的节点；
• 直接遍历更新commonLength的相关节点；
• 如果有多余新节点则挂载，如果有多余旧节点则卸载；

 代码实现：

function patchChildren(n1, n2) {
    if (typeof n2.chilren === 'string') {
        // 省略部分代码
    } else if (Array.isArray(n2.children)) {
        // 更新逻辑
        const oldChildren = n1.children
        const newChildren = n2.children
        // 旧节点的长度
        const oldlen = oldChildren.length
        // 新节点的长度
        const newlen = newChildren.length
 
        const commonLength = Math.min(oldlen, newlen)
 
        for (let i = 0; i < commonLength; i++) {
            // 更新节点
            patch(oldChildren[i], newChildren[i])
        }
        // newlen > oldlen, 需要挂载
        if (newlen > oldlen) {
            for (let i = commonLength; i < newlen; i++) {
                patch(null, newChildren[i])
            }
        } else if (oldlen > newlen) {
            // oldlen > newlen, 需要卸载
            for (let i = commonLength; i < oldlen; i++) {
                unmount(null, oldChildren[i])
            }
        }
    } else {
        // 省略部分代码
    }
}

2.3 如果虚拟节点的顺序发生变化怎么解决？（节点个数相同，但顺序不同）

分为两种情况：

1. 新旧虚拟节点标签类型相同；
2. 新旧虚拟节点标签类型不同；

比较方法：通过key值进行比较

// type不同的虚拟节点
// oldVNode
[
    { type: 'p' },
    { type: 'div' },
    { type: 'span' },
]
// newChildren
[
    { type: 'span' },
    { type: 'p' },
    { type: 'div' },
]
// type相同数据不同的虚拟节点
// oldVNode
[
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' }
]
// newChildren
[
    { type: 'p', children: '3' },
    { type: 'p', children: '2' },
    { type: 'p', children: '1' }
]

图示： 

思路分析

第一步：取新的一组子节点中的第一个节点p-3，它的key为3。尝试在旧的一组子节点中找到具有相同key值的可复用节点，如果能找到，记录旧子节点中当前节点的索引为2

第二步：取新的一组子节点中的第二个节点p-1，它的key为1。尝试在旧的一组子节点中找到具有相同key值的可复用节点，如果能找到，记录旧子节点中当前节点的索引为0

此时索引值的递增顺序被打破。节点p-1在旧children中的索引是0，它小于节点p-3在旧children中的索引2。说明p-1在旧children中排在节点p-3前面，但在新的children中，他排在节点p-3后面。 所以，我们得到结论：节点p-1对应的真实DOM需要移动。

第三步：取新的一组子节点中的第二个节点p-2，它的key为2。尝试在旧的一组子节点中找到具有相同key值的可复用节点，如果能找到，记录旧子节点中当前节点的索引为1

同理，节点p-2在旧children中排在节点p-3前面，但在新的children中，它排在节点p-3后面。因此，节点p-2对应的真实DOM也需要移动

此时索引值的递增顺序被打破。节点p-1在旧children中的索引是0，它小于节点p-3在旧children中的索引2。说明p-1在旧children中排在节点p-3前面，但在新的children中，他排在节点p-3后面。 所以，我们得到结论：节点p-1对应的真实DOM需要移动。

关键点：

关键点：找最大的索引值，索引值小于最大的索引值，表示需要移动真实DOM

把新节点一个一个得去旧节点中找

lastIndex：用来存储寻找过程中当前节点在旧的Children中最大的索引值。比如第一次 i 的循环找到的最大索引为2，但是第二轮找到的节点为0，那么0<2就证明是需要移动。（为什么？因为新节点按照 i 的循环，第二次循环的节点是递增的，但是结果0<2说明旧节点的不是递增，证明新节点和旧节点的顺序不一样，就需要更新）

代码——查找虚拟节点不同

function patchChildren(n1, n2) {
    if (typeof n2.chilren === 'string') {
        // 省略部分代码
    } else if (Array.isArray(n2.children)) {
        // 更新逻辑
        const oldChildren = n1.children
        const newChildren = n2.children
        
        // 用来存储寻找过程中当前节点在旧的Children中最大的索引值
        let lastIndex = 0
        for (let i = 0; i < newChildren.length; i++) {
            const newVNode = newChildren[i]
            for (let j = 0; j < oldChildren.length; j++) {
                const oldVNode = oldChildren[i]
                if (newVNode.key === oldVNode.key) {
                    patch(oldVNode, newVNode)
                    if (j < lastIndex) {
                        // 如果当前找到的节点在旧Children中的索引小于lastIndex
                        // 说明我们的当前节点对应的真实dom是需要移动的
                    } else {
                        lastIndex = j
                    }
                }
                break;
            }
        }
    } else {
        // 省略部分代码
    }
}

如何移动元素？

思路分析——移动旧节点对应真实DOM

第一步：首先将旧子节点上的真实dom赋值给对应新节点的dom（可复用的旧节点，为什么要将旧子节点的真实DOM赋值给新节点的DOM？因为最终操作DOM是通过新节点的真实DOM去操作）

第二步：找到需要移动的虚拟节点，将它上一个虚拟节点对应的真实DOM的下一个兄弟节点作为锚点

第三步：将当前虚拟节点对应的真实dom移动到锚点位置

（这里是通过找到需要移动的虚拟节点newVnode的上一个节点的位置，如果上一个节点不存在，表示已经是第一个节点不需要移动，如果存在则将该节点的真实DOM移动到上一个节点的下一个兄弟节点的位置）

vnode里面的el存储的是真实的DOM节点，移动的时候就是将旧的虚拟节点的el属性赋值给新的虚拟节点的el；最终是通过新子节点的虚拟节点的顺序来操作真实DOM。

问题？如何移动真实DOM这里移动的真实DOM指的是旧的虚拟DOM对应真实DOM？然后移动完成以后将旧的真实DOM再赋值给对应新节点的DOM？

回答：diff算法中对比出新旧节点位置不一致后，要么移动新节点的真实DOM，要么移动旧节点的真实DOM去保证新旧节点的DOM的顺序保持一致的，而vue底层是移动旧节点的真实DOM的顺序
真实DOM移动完成后不会将旧节点的真实DOM赋值给新节点。diff算法本身存在就是为了对比新旧节点是否相同，如果节点相同只需要复用节点DOM更改节点里面的内容即可，从而保证效率。

最终代码：

function patchChildren(n1, n2) {
    if (typeof n2.chilren === 'string') {
        // 省略部分代码
    } else if (Array.isArray(n2.children)) {
        // 更新逻辑
        const oldChildren = n1.children
        const newChildren = n2.children
        
        // 用来存储寻找过程中最大的索引值
        let lastIndex = 0
        for (let i = 0; i < newChildren.length; i++) {
            const newVNode = newChildren[i]
            for (let j = 0; j < oldChildren.length; j++) {
                const oldVNode = oldChildren[i]
                if (newVNode.key === oldVNode.key) {
                    patch(oldVNode, newVNode)
                    if (j < lastIndex) {
                        // 如果当前找到的节点在旧Children中的索引小于lastIndex
                        // 说明我们的当前节点对应的真实dom是需要移动的
 
                        // 先获取当前newVNode的上一个节点
                        const prevVNode = newChildren[i - 1]
                        if (prevVNode) {
                            // 如果prevVNode不存在，说明prevVNode就是第一个，不需要移动
                            const anchor = prevVNode.el.nextSibling
                            insert(newVNode.el, anchor) //将DOM插入到锚点位置
//vnode里面的el存储的是真实的DOM节点，移动的时候就是将旧的虚拟节点的el属性赋值给新的虚拟节点的el；最终是通过新子节点的虚拟节点的顺序来操作真实DOM。
                        
    }
                    } else {
                        lastIndex = j
                    }
                }
                break;
            }
        }
    } else {
        // 省略部分代码
    }
}

3.我的简单示例

html>
<html lang="en">
 
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Documenttitle>
head>
 
<body>
    <script>
        // 1.节点类型和顺序相同，只是文本内容不同，可以复用节点直接更新文本即可
        /*
        const oldVNode = {
            type: 'div',
            children: [
                { type: 'p', children: '1' },
                { type: 'p', children: '2' },
                { type: 'p', children: '3' }
            ]
        }
        const newVNode = {
            type: 'div',
            children: [
                { type: 'p', children: '4' },
                { type: 'p', children: '5' },
                { type: 'p', children: '6' }
            ]
        }
        */
        function patchChildren1(n1, n2) {
            if (typeof n1.children === "string") {
                //省略部分代码
            } else if (Array.isArray(n1.children)) {
                let newChildren = n1.children;
                let oldChildren = n2.children;
                for (let i = 0; i < newChildren.length; i++) {
                    patch(newChildren[i], oldChildren[i]);
                }
            } else {
                //省略部分代码
            }
        }
 
        // 2.如果节点的个数对不上怎么解决？（节点顺序相同，但个数不同）
        /*
        步骤：
            获取新旧节点长度，Math.min()获取相同长度commonLength的节点；
            直接遍历更新commonLength的相关节点；
            如果有多余新节点则挂载，如果有多余旧节点则卸载；
        */
        function patchChildren2(n1, n2) {
            if (typeof n1.children === "string") {
                //省略部分代码
            } else if (Array.isArray(n1.children)) {
                let newLen = n1.children.length;
                let oldLen = n2.children.length;
                let commonLen = Math.min(newLen, oldLen);
 
                for (let i = 0; i < commonLen.length; i++) {
                    patch(newChildren[i], oldChildren[i]);
                }
 
                // 如果有多余新节点进行挂载(注意挂载的节点是用新旧节点做对比，并以commonLen为基准)
                if (newLen > oldLen) {
                    for (let i = commonLen; i < newLen; i++) {
                        insert(null, newChildren[i]);
                    }
                }
 
                // 如果有多余旧节点，进行卸载
                if (oldLen > newLen) {
                    for (let i = commonLen; i < oldLen; i++) {
                        unmount(null, oldChildren[i])
                    }
                }
            } else {
                //省略部分代码
            }
        }
 
 
        // 3.如果虚拟节点的顺序发生变化怎么解决？（节点个数相同，但顺序不同）
        /*
        有两种情况：新旧虚拟节点标签类型相同；新旧虚拟节点标签类型不同；
        原理：循环套用，然后根据上一次查询的节点所在位置的索引，如果本次找到的节点索引位置小于上一次的，说明顺序不对需要移动DOM节点
            // type不同的虚拟节点
            // oldVNode
            [
                { type: 'p' },
                { type: 'div' },
                { type: 'span' },
            ]
            // newChildren
            [
                { type: 'span' },
                { type: 'p' },
                { type: 'div' },
            ]
            // type相同数据不同的虚拟节点
            // oldVNode
            [
                { type: 'p', children: '1' },
                { type: 'p', children: '2' },
                { type: 'p', children: '3' }
            ]
            // newChildren
            [
                { type: 'p', children: '3' },
                { type: 'p', children: '2' },
                { type: 'p', children: '1' }
            ]
        */
        function patchChildren3(n1, n2) {
            let newChildrenNode = n1.children;
            let oldChildrenNode = n2.children;
            // 用于记录索引位置
            let indexId = 0;
 
            for(let i=0; ilength;i++){
                // 当前新节点(记录节点用于后面移动)
                let newVnode = newChildrenNode[i];
 
                for(let j=0;jlength;j++){
                    // 当前旧节点
                    let oldVnode = oldChildrenNode[i];
                    // 当前索引为j，如果当前索引小于上一次记录的indexId则表示DOM顺序有问题
                    if(j
                        // 如何移动？将当前找到的旧节点移动到当前新节点的上一个兄弟节点的位置
                        // 找到当前新节点的上一个兄弟节点
                        let preVnode = newChildren[i-1].el.nextSibling();
                        if (preVnode) { //如果prevVnode不存在说明上一个兄弟节点不存在，即已经在最上面位置
                            // 然后将当前旧节点移动到新节点的上一个兄弟节点
                            insert(newVnode.el, preVnode); //将当前虚拟节点对应的真实dom移动到锚点位置
                        }
                    }else{
                        indexId = j;
                    }
                }
            }
        }
    script>
body>
 
html>