详解虚拟DOM并实现DOMDIFF算法

jiezi

5 年前

所谓虚拟 DOM，就是用 JavaScript 对象的方式去描述真实 DOM。由于真实 DOM 的创建、修改、删除会造成页面的重排和重绘，频繁操作真实 DOM 会影响页面的性能 ，页面中会有数据、样式的更新， 操作真实 DOM 是不可避免的 ，而虚拟 DOM 的产生是为了 最大限度的减少对真实 DOM 的操作 ，因为虚拟 DOM 可以 将真实 DOM 操作映射为 JavaScript 对象操作，尽量复用真实的 DOM。

比如以下一段 HTML 代码，我们可以看到这是一个 div 元素节点，这个 div 元素节点上有一个属性 id，值为 container，并且这个 div 元素节点有两个子节点，一个子节点是 span 元素节点，span 元素节点有 style 属性，属性值为 color: red，span 元素节点内也有一个子节点，hello 文本节点；另一个子节点是 world 文本节点

<div id="container">
    hello world
</div>

// 对应的 JavaScript 对象描述为

{
    _type: "VNODE_TYPE",
    tag: "div",
    key: undefined,
    props: {"id": "container"},
    children: [
        {
             _type: "VNODE_TYPE",
             tag: undefined,
             key: undefined,
             props: undefined,
             children: undefined,
             text: "hello world",
             domNode: undefined
        }
    ],
    text: undefined,
    domNode: undefined
}

本项目需要通过 webpack 进行打包、并通过 webpack-dev-server 启动项目，所以需要安装webpack、webpack-cli、webpack-dev-server。

① 新建一个 dom-diff 项目，并执行 npm init --yes 生成项目的 package.json 文件。
② 修改 package.json 文件， 添加 build 和 dev 脚本，build 用于 webpack 打包项目，dev 用于 webpack-dev-server 启动项目，如:

// 修改 package.json 文件的 scripts 部分

{
    "scripts": {
        "build": "webpack --mode=development",
        "dev": "webpack-dev-server --mode=development --contentBase=./dist"
    }
}

③ 在项目 根目录 下新建一个 src 目录，然后在 src 目录下，新建一个 index.js 文件，webpack 默认入口文件为 src 目录下的 index.js，默认输出目录为 项目根目录下的 dist 目录

// index.js 文件初始化内容

console.log("hello virtual dom-diff.");

④ 首先执行 npm run bulid 打包输出，会在项目根目录下生成一个 dist 目录，并在 dist 目录下打包输出一个 main.js，然后在 dist 目录下，新建一个 index.html 文件，其引入打包输出后的 main.js，如:

// dist/index.html 文件内容

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Vue DOM DIFF</title>
    <style>
    </style>
</head>
<body>
    <div id="app"></div>
    <script src="./main.js"></script>
</body>
</html>

⑤ 执行 npm run dev 启动项目 ，然后在浏览器中输入http://localhost:8080，如果控制台中输出了hello virtual dom-diff. 表示项目初始化成功。

由于虚拟 DOM 本质就是一个 JavaScript 对象，所以创建虚拟 DOM 节点就是创建一个 JavaScript 对象，关键在于这个 JavaScript 对象上有哪些属性 。Vue 中创建虚拟 DOM 节点使用的是h() 方法，所以要创建虚拟 DOM，主要就是实现这个 h()方法。我们需要知道 要创建的虚拟 DOM 的标签名 tag、属性名对象 props(有多个属性)、子节点数组 children(有多个子节点)、key(节点的唯一标识)、text(如果是文本节点则有对应的 text)、真实 DOM 节点 domNode、还有一个就是 节点类型_type(是否是虚拟 DOM 节点)，如:

① 在 src 目录下新建一个 vdom 目录，创建一个index.js、vnode.js、h.js。

// src/vdom/index.js 主要是导出 h.js 中暴露的 h()方法

import h from "./h"; // 引入 h 方法
export {h // 对外暴露 h 方法}

// src/vdom/vnode.js 主要就是提供了一个 vnode 方法，用于接收虚拟 DOM 节点的属性并生成对应的虚拟 DOM 节点

const VNODE_TYPE = "VNODE_TYPE"; // 虚拟 DOM 节点
function vnode(tag, key, props, children = [], text, domNode) {
    return {
        _type: VNODE_TYPE, // 表示这是一个虚拟 DOM 节点
        tag, // 对应的标签类型
        key, // DOM 节点的唯一标识
        props, // DOM 节点上对应的属性集
        children, // DOM 节点的子节点
        text, // DOM 节点 (文本节点) 对应的文本内容
        domNode // 创建的真实 DOM 节点
    }
}
export default vnode;

// src/vdom/h.js 主要就是提供了一个 h()方法用于解析传递过来的参数，即从全部属性中分离出 key，然后创建对应的 vnode

import vnode from "./vnode";

const hasOwnProperty = Object.prototype.hasOwnProperty;

function h(tag, attrs, ...children) {const props = {}; // 属性对象，移除 key 后的属性集
    let key; // 从全部属性中分离出 key 值
    if (attrs && attrs.key) {key = attrs.key;}
    // 迭代 attrs 中的每一个属性，生成一个将 key 移除后的属性集对象
    for(let propName in attrs) {if (hasOwnProperty.call(attrs, propName) && propName !== "key") {props[propName] = attrs[propName];
        }
    }
    return vnode(tag, key, props, children.map((child) => {// 如果子节点是一个纯文本节点，那么生成一个文本节点对应的 vnode(其他属性均为 undefined，但是 text 属性为对应文本)
        // 如果已经是虚拟节点了，那么直接返回即可
        return typeof child == "string" || typeof child == "number" ? vnode(undefined, undefined, undefined, undefined, child) : child;
    }));
}
export default h;

② 之后我们就可以 通过 h()方法创建虚拟节点 了，修改项目根目录下的 index.js 并创建对应的虚拟 DOM 节点，如:
// src/index.js

import {h} from "./vdom"; // 引入 h()方法, 用于创建虚拟 DOM
const oldVnode = h("div", {id: "container"}, 
    h("span", {style: {color: "red"}}, "hello"), // 参数中的函数会先执行
    "world"
);
console.log(oldVnode);

要想将虚拟 DOM 节点 mount 出来，那么必须 将虚拟 DOM 节点转换为真实的 DOM 节点 ， 然后将其添加进真实的 DOM 中 。挂载 DOM 节点非常简单，只需要获取到真实的挂载点 DOM 元素，然后通过其 append() 方法即可挂载上去，所以 其关键点就在于将虚拟 DOM 转换为真实的 DOM 节点。

① 在 vdom 目录中 新建一个 mount.js文件，里面对外暴露一个 mount() 方法和 createDOMElementByVnode() 方法，如:

// src/vdom/mount.js

// 传入一个新的虚拟 DOM 节点，和旧的虚拟 DOM 的 props 进行比较并更新
export function updateProperties(newVnode, oldProps = {}) {

}
// 通过虚拟 DOM 节点创建真实的 DOM 节点
export function createDOMElementByVnode(vnode) {

}
// mount 方法用于接收一个虚拟 DOM 节点，和一个真实的父 DOM 节点，即挂载点
// mount 方法内部会首先将这个虚拟 DOM 节点转换为真实的 DOM 节点，然后将其添加到真实的挂载点元素上
function mount(vnode, parentNode) {let newDOMNode = createDOMElementByVnode(vnode); // 将虚拟 DOM 转换为真实的 DOM
    parentNode.append(newDOMNode); // 再将真实的 DOM 挂载到父节点中
}
export default mount;

② 在 src/vdom/index.js 文件中引入 mount.js 中的 mount()方法并对外暴露

// src/vdom/index.js 文件

import h from "./h";
import mount from "./mount";

export {
    h,
    mount
}

③ src/index.js 中引入 mount()方法并传入 虚拟 DOM和 挂载点 对虚拟 DOM 进行挂载

// src/index.js 文件

import {h, mount} from "./vdom"; // 引入 h()方法, 用于创建虚拟 DOM
const oldVnode = h("div", {id: "container"}, 
    h("span", {style: {color: "red"}}, "hello"), // 参数中的函数会先执行
    "world"
);
console.log(oldVnode);
// 挂载虚拟 DOM
const app = document.getElementById("app");
mount(oldVnode, app);

④ 接下来就是要实现 createDOMElementByVnode()方法，将虚拟 DOM 转换为真实的 DOM 节点，就可以将其挂载到 id 为 app 的元素内了。其转换过程主要为:

根据虚拟 DOM 的 tag 类型判断，如果 tag 存在则是元素节点，创建出对应的元素节点；如果 tag 为 undefined 则是文本节点，创建出对应的文本节点；
然后 更新 DOM 节点上的属性，
然后 遍历子节点 ，通过递归调用 createDOMElementByVnode() 方法，创建出子节点对应的真实 DOM 节点并添加到父节点内。

// createDOMElementByVnode()方法实现

export function createDOMElementByVnode(vnode) {
    // 从虚拟 DOM 节点中获取到对应的标签类型及其中的子节点
    const {tag, children} = vnode;
    if (tag) { // 如果虚拟 DOM 上存在 tag，说明是元素节点，需要根据这个 tag 类型创建出对应的 DOM 元素节点
        // 创建真实 DOM 元素并保存到虚拟 DOM 节点上的 domNode 属性上，方便操作 DOM 添加属性
        vnode.domNode= document.createElement(tag); // 根据虚拟 DOM 的 type 创建出对应的 DOM 节点
        // DOM 节点创建出来之后，就需要更新 DOM 节点上的属性了
        updateProperties(vnode); // 更新虚拟 DOM 上的属性，更新节点属性
        // DOM 节点上的属性更新完成后，就需要更新子节点了
        if (Array.isArray(children)) { // 如果有 children 属性，则遍历子节点，将子节点添加进去，即更新子节点
            children.forEach((child) => {const domNode = createDOMElementByVnode(child); // 递归遍历子节点并继续创建子节点对应的真实 DOM 元素
                vnode.domNode.appendChild(domNode);
            });
        } 
    } else { // 如果虚拟 DOM 上不存在 tag，说明是文本节点，直接创建一个文本节点即可
        vnode.domNode = document.createTextNode(vnode.text);
    }
    return vnode.domNode;
}

⑤ 此时已经把真实的 DOM 节点创建出来了，但是 DOM 节点上的属性未更新，所以需要实现 updateProperties()方法，其更新过程为:

更新属性，意味着是在同一个 DOM 节点上进行操作，即比较同一个节点上属性的变化，由于 样式 style 也是一个对象 ，所以首先遍历老的样式， 如果老的样式在新的样式中不存在了 ，那么 需要操作 DOM 移除该样式属性
接着更新非 style 属性，同样如果 老的属性在新的属性中不存在了 ，那么 需要操作 DOM 移除该属性
移除了不存在的样式和属性后，那么接下来就要 更新都存在的样式和属性了(都有该属性，但是值不同)。遍历新属性对象进行一一覆盖旧值即可。

// 传入一个新的虚拟 DOM 节点，和旧的虚拟 DOM 的 props 进行比较并更新
export function updateProperties(newVnode, oldProps = {}) { // 如果未传递旧节点属性，那么将旧节点属性设置空对象
    const newProps = newVnode.props; // 取出新虚拟 DOM 节点上的属性对象
    const domNode = newVnode.domNode; // 取出新虚拟 DOM 上保存的真实 DOM 节点方便属性更新
    // 先处理样式属性, 因为 style 也是一个对象
    const oldStyle = oldProps.style || {};
    const newStyle = newProps.style || {};
    // 遍历节点属性对象中的 style，如果老的样式属性在新的 style 样式对象里面没有，则需要删除，// 即新节点上没有该样式了，那么需要删除该样式
    for (let oldAttrName in oldStyle) {if (!newStyle[oldAttrName]) {domNode.style[oldAttrName] = ""; // 老节点上的样式属性，新节点上已经没有了，则清空真实 DOM 节点上不存在的老样式属性
        }
    }
    // 再处理非 style 属性，把老的属性对象中有，新的属性对象中没有的删除
    // 即新节点上没有该属性了，就需要删除该属性
    for (let oldPropName in oldProps) {if (!newProps[oldPropName]) {domNode.removeAttribute(oldPropName); // 老节点上的属性，新节点上已经没有了，那么删除不存在的属性
        }
    }
    // 移除新节点上不存在的样式和属性后，遍历新节点上的属性，并将其更新到节点上
    for (let newPropName in newProps) {if (newPropName === "style") {
            let styleObject = newProps.style;  // 取出新的样式对象
            for (let newAttrName in styleObject) {domNode.style[newAttrName] = styleObject[newAttrName]; // 更新新老节点上都存在的样式
            }
        } else {domNode[newPropName] = newProps[newPropName]; // 更新新老节点上都存在的属性
        }
    }
}

DOM-DIFF 算法的核心就是 对新旧虚拟 DOM 节点进行比较 ， 根据新旧虚拟 DOM 节点是否发生变化来决定是否复用该 DOM。为了模拟新旧节点变化，首先我们创建一个旧的虚拟 DOM 节点并 mount 出来，然后通过定时器，设置 3 秒后创建一个新的虚拟 DOM 节点并进行比较更新。

① 首先在 src/vdom 目录下新建一个 patch.js，里面对外暴露一个 patch(oldVnode, newVnode)方法，传入新旧节点进行比较更新，patch 方法具体实现后面实现，同样的方式将 patch()方法暴露出去，以便 src/index.js 能够引入这个 patch()方法，这里同上不重复了。

// src/vdom/patch.js

// 用于比较新旧虚拟 DOM 节点并进行相应的更新
function patch(oldVnode, newVnode) { }
export default patch;

// 更新 src/index.js

import {h, mount, patch} from "./vdom"; // 引入 h()方法, 用于创建虚拟 DOM
const oldVnode = h("ul", {id: "container"}, 
    h("li", {style: {background: "red"}, key: "A"}, "A"), // 参数中的函数会先执行
    h("li", {style: {background: "green"}, key: "B"}, "B"),
    h("li", {style: {background: "blue"}, key: "C"}, "C"),
    h("li", {style: {background: "yellow"}, key: "D"}, "D")
);
console.log(oldVnode);
// 挂载虚拟 DOM
const app = document.getElementById("app");
mount(oldVnode, app); // 首先将旧虚拟 DOM 节点 mount 出来

setTimeout(() => {const newVnode = h("div", {id: "container"}, "hello world"); // 3 秒后创建一个新的虚拟 DOM 节点
    patch(oldVnode, newVnode); // 新建虚拟 DOM 进行比较并更新
}, 3000);

② 实现 patch()方法

patch 主要用于比较新旧虚拟 DOM 节点的变化，根据不同的变化决定是否复用真实 DOM，其存在比较多种情况:

新旧虚拟 DOM 节点的 tag 不一样 的情况，由于新旧节点的 tag 不一样，所以这两个 DOM 节点肯定无法复用，必须新创建一个 DOM 节点，替换调用旧的 DOM 节点。比如上面新的虚拟 DOM 节点的 tag 变成了div，而原先是ul。

import {createDOMElementByVnode} from "./mount";
// 用于比较新旧虚拟 DOM 节点并进行相应的更新
function patch(oldVnode, newVnode) {
    // 1. 如果新的虚拟 DOM 节点类型 tag 不一样，必须重建 DOM
    if(oldVnode.tag !== newVnode.tag) {// 通过旧虚拟 DOM 的 domNode 获取到其父节点然后调用 createDOMElementByVnode()方法创建出新虚拟 DOM 节点对应的真实 DOM，并替换掉旧节点
        oldVnode.domNode.parentNode.replaceChild(createDOMElementByVnode(newVnode), oldVnode.domNode);
    }
}
export default patch;

新旧虚拟 DOM 节点的 tag 一样，但是 子节点不一样 ，子节点不一样，还有三种情况: ① 新旧节点都有子节点 ；② 旧节点有子节点，新节点没有子节点 ；③ 旧节点没有子节点，但是新节点有子节点 ，其中②和③比较简单，主要第①种比较复杂，对于②， 直接清空 即可，对于③创建出新的子节点挂载上去 即可。这里先实现②和③的情况

function patch(oldVnode, newVnode) {
    // 1. 如果新的虚拟 DOM 节点类型 tag 不一样，必须重建 DOM
    if(oldVnode.tag !== newVnode.tag) {// 通过旧虚拟 DOM 的 domNode 获取到其父节点然后调用 createDOMElementByVnode()方法创建出新虚拟 DOM 节点对应的真实 DOM，并替换掉旧节点
        oldVnode.domNode.parentNode.replaceChild(createDOMElementByVnode(newVnode), oldVnode.domNode);
    }
    // 如果类型一样，则复用当前父元素 domElement, 要继续往下比较 
    const domNode = newVnode.domNode = oldVnode.domNode; // 获取到新的或老的真实 DOM 节点，因为类型一致，所以新旧节点是一样的可以直接复用
    // 首先判断是元素节点还是文本节点, 比如比较的是两个文本节点，但是值不同，则直接更新文本节点的值即可
    if (typeof newVnode.text !== "undefined") { // 如果新节点是一个文本节点
        return oldVnode.domNode.textContent = newVnode.text;
    }
    // 父节点复用后，传入新的虚拟 DOM 节点和老的属性对象，更新 DOM 节点上的属性
    updateProperties(newVnode, oldVnode.props);
    // 更新子节点
    let oldChildren = oldVnode.children; // 老的虚拟 DOM 节点的子节点数组
    let newChildren = newVnode.children; // 新的虚拟 DOM 节点的子节点数组
    if (oldChildren.length > 0 && newChildren.length > 0) { // 如果两个 li 标签并且都有儿子，那么接着比较两个儿子节点
        // 如果新旧节点都有子节点，那么继续比较儿子节点，并进行相应更新
        updateChildren(domNode, oldChildren, newChildren);
    } else if (oldChildren.length > 0) { // 老节点有子节点，新节点没子节点
        domNode.innerHTML = ""; // 直接清空
    } else if (newChildren.length > 0) { // 老节点没有子节点，新节点有子节点
        for (let i = 0; i < newChildren.length; i++) { // 遍历新节点上的子节点
            domNode.appendChild(createDOMElementByVnode(newChildren[i])); // 创建对应的真实 DOM 并添加进去
        }
    }
}

③ 实现 updateChildren()方法

对于上一步中提到第一种情况，就新旧虚拟 DOM 节点中都有子节点的情况，那么我们需要进一步比较其子节点，看子节点能否复用，子节点的比较又分为五种情况:
这里先定义一下什么的节点才算是相同的节点？即 标签名相同 并且 key 也相同，所以需要在src/vdom/vnode.js 中添加一个 isSameNode()方法，传递新旧虚拟 DOM 节点比较两个节点是否是相同的节点。

// src/vdom/vnode.js 中添加一个 isSameNode 方法并对外暴露

export function isSameNode(oldVnode, newVnode) {
    // 如果两个虚拟 DOM 节点的 key 一样并且 tag 一样，说明是同一种节点，可以进行深度比较
    return oldVnode.key === newVnode.key && oldVnode.tag === newVnode.tag;
}

从新旧节点的头部开始比较，并且头部节点相同，这里以特殊情况为例: 比如 ul 节点中原先是 A 一个节点，后面增加了一个 B 节点变成了 A、B，这样新旧节点头部的 A 是相同节点，可以复用，直接在后面添加一个 B 节点即可，如:

function updateChildren(parentDomNode, oldChildren, newChildren) {
    let oldStartIndex = 0; // 老的虚拟 DOM 节点子节点开始索引
    let oldStartVnode = oldChildren[0]; // 老的虚拟 DOM 节点开始子节点(第一个子节点)
    let oldEndIndex = oldChildren.length - 1; // 老的虚拟 DOM 节点子节点结束索引
    let oldEndVnode = oldChildren[oldEndIndex];// 老的虚拟 DOM 节点结束子节点(最后一个子节点)

    let newStartIndex = 0; // 新的虚拟 DOM 节点子节点开始索引
    let newStartVnode = newChildren[0]; // 新的虚拟 DOM 节点开始子节点(第一个子节点)
    let newEndIndex = newChildren.length - 1; // 新的虚拟 DOM 节点子节点结束索引
    let newEndVnode = newChildren[newEndIndex];// 新的虚拟 DOM 节点结束子节点(最后一个子节点)
    // 每次比较新旧虚拟 DOM 节点的开始索引或者结束索引都会进行向前或向后移动，每比较一次，新旧节点都会少一个，直到有一个队列比较完成才停止比较
    while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {if(isSameNode(oldStartVnode, newStartVnode)) { // 旧节点的第一个子节点和新节点的第一个子节点相同，即头部相同，可以复用
            patch(oldStartVnode, newStartVnode); // 更新可复用的两个队列的头部节点的属性及其子节点
            // 第一次新旧节点头部比较完成后，头部索引需要往后移，更新新旧节点的头部节点位置
            oldStartVnode = oldChildren[++oldStartIndex];
            newStartVnode = newChildren[++newStartIndex];
        }
    }
    // 由于子节点数量不一样，所以循环结束后，可能有一个队列会多出一些还未比较的节点
    // 如果旧节点的子节点比新节点的子节点数量少，那么新节点则会有剩余节点未比较完成
    if (newStartIndex <= newEndIndex) { // 老的队列处理完了，新的队列没有处理完
        for (let i = newStartIndex; i <= newEndIndex; i++) { // 遍历新队列中多出的未比较的节点，这些节点肯定无法复用，必须创建真实的 DOM 并插入到队列后面
            // newEndIndex 是会发生变化移动的，根据此时 newEndIndex 的值，将多出的节点插入到 newEndIndex 的后面或者说是 newEndIndex + 1 的前面
            const beforeDOMNode = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].domNode;
            parentDomNode.insertBefore(createDOMElementByVnode(newChildren[i]), beforeDOMNode);
            // 为了通用可以用 insertBefore 代替 appendChild，insertBefore 第二参数为 null 就是在末尾插入，不为 null 则是在当前元素前插入
            // parentDomNode.appendChild(createDOMElementByVnode(newChildren[i]));
        }
    }
    // 如果旧节点的子节点比新节点的子节点数量多，那么旧节点则会有剩余节点未比较完成
    if (oldStartIndex <= oldEndIndex) { // 新的队列处理完了，旧的队列还没有处理完
        for (let i = oldStartIndex; i <= oldEndIndex; i++) { // 遍历旧队列中多出的未比较的节点，并移除
            parentDomNode.removeChild(oldChildren[i].domNode);
        }
    }
}

const oldVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A")
);
const newVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A1"), // 参数中的函数会先执行
    h("li", {style: {background: "green"}, key: "B"}, "B")
);

其比较过程就是: ① 旧节点与新节点的第一个子节点进行比较，由于 key 都为 A ，所以是相同的节点， 直接调用 patch()方法进行属性更新 ，即将 A 更新为 A1 ② 新旧节点的头部索引都加 1，向后移 ，此时旧节点的所有子节点都比较完成了，所以 退出 while 循环 ③ 但是 新节点中还有一个 B 节点未比较 ，所以遍历多出的未比较的子节点， 转换成真实的 DOM 节点并追加到队列末尾 ，即可完成A 到 A B的更新，此时 A 被复用了。

从新旧节点的尾部开始比较，并且尾部节点相同，这里以特殊情况为例: 比如 ul 节点中原先是 A 一个节点，前面增加了一个 B 节点变成了 B、A，这样新旧节点尾部的 A 是相同节点，可以复用，直接在前面添加一个 B 节点即可，如:

// 更新 while 循环，添加一个 else if 即可

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {if(isSameNode(oldStartVnode, newStartVnode)) { // 旧节点的第一个子节点和新节点的第一个子节点相同，即头部相同，可以复用
            console.log("头部相同");
        } else if (isSameNode(oldEndVnode, newEndVnode)) { // 旧节点的最后一个子节点和新节点的最后一个子节点相同，即尾部相同，可以复用
            patch(oldEndVnode, newEndVnode); // 更新可复用的两个队列的尾部节点的属性及其子节点
            // 第一次新旧节点尾部比较完成后，尾部索引需要往前移，更新新旧节点的尾部节点位置
            oldEndVnode = oldChildren[--oldEndIndex];
            newEndVnode = newChildren[--newEndIndex];
        }
    }

const oldVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A")
);
const newVnode = h("ul", {id: "container"},
        h("li", {style: {background: "green"}, key: "B"}, "B"),
        h("li", {style: {background: "red"}, key: "A"}, "A1"), // 参数中的函数会先执行
    );

其比较过程就是: ① 旧节点与新节点的最后一个子节点进行比较，由于 key 都为 A ，所以是相同的节点， 直接调用 patch()方法进行属性更新 ，即将 A 更新为 A1 ② 新旧节点的尾部索引都减 1，向前移 ，此时旧节点的所有子节点都比较完成了，所以 退出 while 循环 ③ 但是 新节点中还有一个 B 节点未比较 ，所以遍历多出的未比较的子节点， 转换成真实的 DOM 节点并追加到队列末尾 ，即可完成A 到 B A 的更新，此时 A 被复用了。

让旧节点的尾部与新节点的头部进行交叉比较，并且尾头节点相同，这里以特殊情况为例: 比如 ul 节点中原先是 A、B、C 三个节点，新节点变成了 C、A、B，这样旧节点尾部与新节点的头部都是 C，是相同节点，可以复用，如:

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {if(isSameNode(oldStartVnode, newStartVnode)) { // 旧节点的第一个子节点和新节点的第一个子节点相同，即头部相同，可以复用
            console.log("头部相同");
        } else if (isSameNode(oldEndVnode, newEndVnode)) { // 旧节点的最后一个子节点和新节点的最后一个子节点相同，即尾部相同，可以复用
            console.log("尾部相同");
        } else if (isSameNode(oldEndVnode, newStartVnode)) { // 旧节点的最后一个子节点和新节点的第一个子节点相同，即尾头相同，尾部节点可以复用
            console.log("尾头相同");
            patch(oldEndVnode, newStartVnode); // 更新可复用的两个队列的尾头部节点的属性及其子节点
            // 尾部节点可以复用，所以需要将旧节点的尾部移动到头部
            parentDomNode.insertBefore(oldEndVnode.domNode, oldStartVnode.domNode);
            // 旧节点的尾部移动到头部后，相当于旧节点的尾部已经比较过了，旧节点的尾部节点位置需要更新，旧节点的尾部索引向前移
            oldEndVnode = oldChildren[--oldEndIndex];
            // 旧节点的尾部移动到头部后，相当于新节点的头部已经比较过了，新节点的头部节点位置需要更新，下一次比较的是新节点原来头部的下一个位置
            newStartVnode = newChildren[++newStartIndex];
        }
    }

const oldVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A"),
    h("li", {style: {background: "green"}, key: "B"}, "B"),
    h("li", {style: {background: "blue"}, key: "C"}, "C")
);
const newVnode = h("ul", {id: "container"},
    h("li", {style: {background: "blue"}, key: "C"}, "C1"),
    h("li", {style: {background: "red"}, key: "A"}, "A1"), // 参数中的函数会先执行
    h("li", {style: {background: "green"}, key: "B"}, "B1")
);

其比较过程就是: ① 旧节点的最后一个子节点与新节点的第一个子节点进行比较，由于 key 都为 C ，所以是相同的节点， 直接调用 patch()方法进行属性更新 ，即将 C 更新为 C1，并且将 C 移动到头部 ② 旧节点的尾部索引减 1，向前移，新节点的头部索引加 1 往后移 ，继续 while 循环，此时新旧节点都剩下 A、B，又开始检测头部是否相同，头部都为 A，故相同，此时将 A 更新为 A1 ③ 此时新旧节点都剩下 B，又开始检测头部是否相同，头部都为 B，故相同，此时将 B 更新为 B1④此时新旧队列都已经比较完成，退出 while 循环，即可完成A B C 到 C A B 的更新，此时A、B、C 都被复用了。

让旧节点的头部与新节点的尾部进行交叉比较，并且头尾节点相同，这里以特殊情况为例: 比如 ul 节点中原先是 A、B、C 三个节点，新节点变成了 B、C、A，这样旧节点头部与新节点的尾部都是 A，是相同节点，可以复用，如:

while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {if(isSameNode(oldStartVnode, newStartVnode)) { // 旧节点的第一个子节点和新节点的第一个子节点相同，即头部相同，可以复用
            console.log("头部相同");
        } else if (isSameNode(oldEndVnode, newEndVnode)) { // 旧节点的最后一个子节点和新节点的最后一个子节点相同，即尾部相同，可以复用
            console.log("尾部相同");
        } else if (isSameNode(oldEndVnode, newStartVnode)) { // 旧节点的最后一个子节点和新节点的第一个子节点相同，即尾头相同，尾部节点可以复用
            console.log("尾头相同");
        } else if (isSameNode(oldStartVnode, newEndVnode)) { // 旧节点的第一个子节点和新节点的最后一个子节点相同，即头尾相同，头部节点可以复用
            console.log("头尾相同");
            patch(oldStartVnode, newEndVnode); // 更新可复用的两个队列的头尾部节点的属性及其子节点
            // 头部节点可以复用，所以需要将旧节点的头部移动到尾部
            parentDomNode.insertBefore(oldStartVnode.domNode, oldEndVnode.domNode.nextSibling);
            // 旧节点的头部移动到尾部后，相当于旧节点的头部已经比较过了，旧节点的头部节点位置需要更新，旧节点的头部索引向后移
            oldStartVnode = oldChildren[++oldStartIndex];
            // 旧节点的头部移动到尾部后，相当于新节点的尾部已经比较过了，新节点的尾部节点位置需要更新，新节点的尾部索引向前移
            newEndVnode = newChildren[--newEndIndex];
        }
    }

const oldVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A"),
    h("li", {style: {background: "green"}, key: "B"}, "B"),
    h("li", {style: {background: "blue"}, key: "C"}, "C")
);
const newVnode = h("ul", {id: "container"},
        h("li", {style: {background: "green"}, key: "B"}, "B1"),
        h("li", {style: {background: "blue"}, key: "C"}, "C1"),
        h("li", {style: {background: "red"}, key: "A"}, "A1"), // 参数中的函数会先执行
);

其比较过程就是: ① 旧节点的第一个子节点与旧节点的最后一个子节点进行比较，由于 key 都为 A ，所以是相同的节点， 直接调用 patch()方法进行属性更新 ，即将 A 更新为 A1，并且将 A 移动到尾部 ② 旧节点的头部索引加 1，向后移，新节点的尾部索引减 1 往前移 ，继续 while 循环，此时新旧节点都剩下 B、C，又开始检测头部是否相同，头部都为 B，故相同，此时将 B 更新为 B1 ③ 此时新旧节点都剩下 C，又开始检测头部是否相同，头部都为 C，故相同，此时将 C 更新为 C1④此时新旧队列都已经比较完成，退出 while 循环，即可完成A B C 到 B C A 的更新，此时A、B、C 都被复用了。

最后还有一种就是，头头、尾尾、头尾、尾头都无法找到相同的，那么就是 顺序错乱的比较 ，此时需要 先把旧节点中所有 key 和 index 的对应关系生成一个 map 映射关系 ，即 通过 key 可以找到其位置 ， 首先从新节点的第一个子节点开始比较 ，然后根据第一个节点的 key 值从 map 映射中查找对应的索引，如果 找不到对应的索引 ，说明 是新节点 ，无法复用，此时 直接创建 DOM 并插入到头部 即可，如果 找到了对应的索引 ，key 相同 tag 不一定相同，此时再比较一下对应的 tag 是否相同，如果tag 不相同，那么也无法复用，也是 直接创建 DOM 并插入到头部 ，如果tag 相同，那么可以复用，更新这两个节点，同时 将找到的节点清空，然后将找到的节点插入到旧节点中的头部索引节点前面，这里以特殊情况为例: 比如 ul 节点中原先是 A、B、C 三个节点，新节点变成了 D、B、A、C、E，这样以上四种情况都无法匹配，如:

// 添加一个 createKeyToIndexMap 方法

// 生成 key 和 index 索引的对应关系
function createKeyToIndexMap(children) {let map = {};
    for (let i = 0; i< children.length; i++) {let key = children[i].key;
        if (key) {map[key] = i;
        }
    }
    return map;
}

const oldKeyToIndexMap = createKeyToIndexMap(oldChildren); // 生成对应的 key 和 index 映射关系
while(oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // 进行顺序错乱比较后，会清空找到的节点，为不影响前面四种情况比较, 如果节点被清空了，需要进行相应的移动
        if (!oldStartVnode) { // 如果旧的 start 节点被清空了，则旧的头部索引往后移，更新头部节点
            oldStartVnode = oldChildren[++oldStartIndex];
        } else if (!oldEndVnode) { // 如果旧的 End 节点被清空了，则旧的尾部索引往前移，更新尾部节点
            oldEndVnode = oldChildren[--oldEndIndex];
        } else if(isSameNode(oldStartVnode, newStartVnode)) { // 旧节点的第一个子节点和新节点的第一个子节点相同，即头部相同，可以复用
            console.log("头部相同");
        } else if (isSameNode(oldEndVnode, newEndVnode)) { // 旧节点的最后一个子节点和新节点的最后一个子节点相同，即尾部相同，可以复用
            console.log("尾部相同");
        } else if (isSameNode(oldEndVnode, newStartVnode)) { // 旧节点的最后一个子节点和新节点的第一个子节点相同，即尾头相同，尾部节点可以复用
            console.log("尾头相同");
        } else if (isSameNode(oldStartVnode, newEndVnode)) { // 旧节点的第一个子节点和新节点的最后一个子节点相同，即头尾相同，头部节点可以复用
            console.log("头尾相同");
        } else { // 顺序错乱比较
            console.log("顺序错乱");
            let oldIndexByKey = oldKeyToIndexMap[newStartVnode.key]; // 传入新节点的第一个子节点的 key，获取到对应的索引
            if (oldIndexByKey == null) { // 如果索引为 null，那么表示这是一个新的节点，无法复用，直接创建并插入到旧节点中当前头部的前面
                parentDomNode.insertBefore(createDOMElementByVnode(newStartVnode), oldStartVnode.domNode);
            } else { // 如果索引不为 null，则找到了相同 key 的节点
                const oldVnodeToMove = oldChildren[oldIndexByKey]; // 获取到旧节点中具有相同 key 的节点
                if (oldVnodeToMove.tag !== newStartVnode.tag) { // key 相同但是类型不同，也要创建一个新的 DOM，并插入到旧节点中当前头部的前面
                    parentDomNode.insertBefore(createDOMElementByVnode(newStartVnode), oldStartVnode.domNode);
                } else { // 找到了相同 key 和 tag 都相同的元素，则可用复用
                    patch(oldVnodeToMove, newStartVnode); // 更新找到节点
                    oldChildren[oldIndexByKey] = undefined; // 将旧节点中找到的元素设为 undefined，清除找到节点
                    // 将找到的元素插入到 oldStartVnode 前面
                    parentDomNode.insertBefore(oldVnodeToMove.domNode, oldStartVnode.domNode);
                }      
            }
            newStartVnode = newChildren[++newStartIndex]; // 比较新节点中的下一个子节点
        }
    }

const oldVnode = h("ul", {id: "container"},
    h("li", {style: {background: "red"}, key: "A"}, "A"),
    h("li", {style: {background: "green"}, key: "B"}, "B"),
    h("li", {style: {background: "blue"}, key: "C"}, "C")
);
const newVnode = h("ul", {id: "container"},
    h("li", {style: {background: "yellow"}, key: "D"}, "D"), // 参数中的函数会先执行
    h("li", {style: {background: "green"}, key: "B"}, "B1"),  
    h("li", {style: {background: "red"}, key: "A"}, "A1"),
    h("li", {style: {background: "blue"}, key: "C"}, "C1"),
    h("li", {style: {background: "green"}, key: "E"}, "E"),      
);

其比较过程就是: ① 由于以上四种情况都不符合，故进行 顺序错乱 比较，首先调用 createKeyToIndexMap 方法拿到 key 和 index 的对应关系
② 从新节点的第一个子节点开始比较，即 D，此时传入其 key 为 D，到 oldKeyToIndexMap 映射对象中进行查找，肯定找不到，为 null，故 不可复用 ，需要创建一个新节点并插入到头部 ③ 此时旧节点中剩下A、B、C，
新节点中剩下 B、A、C、E，仍然不匹配以上四种情况， 再次进行顺序错乱 比较，比较 B，此时可以在 oldKeyToIndexMap 映射对象中找到对应的索引为 1，然后将 B 更新为 B1，然后清空旧节点中的 B，旧节点当前的头部索引为 0，索引插入到 A 的前面 ④ 此时旧节点中剩下 A undefined C，新节点中剩下A C E，此时符合 头部相同 的情况，直接将 A 更新为 A1，旧节点中头部索引往后移，变为 undefined，新节点头部索引也往后移，变为 C ⑤此时旧节点中剩下 undefined C，新节点中剩下 C E，再次进入 while 循环，由于 旧节点的头部节点变为了 undefined，故 旧节点头部索引往后移动 ， 头部节点变为了 C ⑥此时旧节点中 剩下 C ，新节点中还是 剩下 C E，此时符合 头部相同 ，将 C 更新为 C1 即可 ⑦此时 旧节点已经比较完成 ，新节点中 剩下一个 E ，直接遍历 E 并创建 DOM 插入到末尾即可，此时完成了 A B C 到 D B A C E 的更新。

详解虚拟DOM并实现DOMDIFF算法

一、虚拟 DOM 简介

二、虚拟 DOM 如何描述真实 DOM

三、项目初始化

四、创建虚拟 DOM 节点

五、将虚拟 DOM 节点 mount

六、实现 DOM-DIFF 算法

至此已经完成了 DOM-DIFF 算法。