实现一个简单的DOM diff算法

浅浅的花香味﹌ 2022-05-01 13:26 255阅读 0赞

上一篇文章，我说到了如何[实现一个简单的虚拟DOM][DOM]，这一篇文章是接着上一篇文章的知识点的。

**我们都知道虚拟DOM其实就是JS对象，我们用JS来操作对象比操作DOM性能要好得多**。

### 我们为什么还需要diff算法？ ###

*  因为如果我们有一个很庞大的DOM Tree，我们要对它进行更新操作，如果我们只是更新了它很小的一部分，我们就需要更新整个DOM Tree。这也是很浪费性能和资源的。因为有好多无用的更新。所以**我们才需要diff算法来剔除掉无用的更新**。

#### 我先来简单的概括一下diff算法。 ####

1.  它遵循**先序深度优先遍历**的规则。
2.  同级比较。
3.  diff只是找到差异，找到了差异我们还有修补差异，就是打补丁（patch）。
4.  我们diff的过程其实就是对比两个虚拟DOM的过程。通过对比找到patch（差异）。
5.  然后再把patch打到真实的DOM上（打补丁）。

*  我们先来说一下**先序深度优先遍历**，我觉得学过数据结构的人对它都不是很陌生，这是一种对树的遍历方法。（先序、中序、后序，广度优先、深度优先）。 **先序遍历就是先遍历根节点在遍历左边的孩子节点然后是右边的孩子节点（根→左→右）。**

## diff的实现过程 ##

*  首先准备好我们需要的变量： 我们需要一个补丁对象和一个全局的位置索引（遍历的顺序）

let patches = {};
    let index = 0;
    复制代码

*  两个虚拟DOM的不同主要有
    
     *  文本的不同（"a" → "bb"）
     *  属性的不同（class: .a → .b）
     *  删除
     *  替换

所以我们需要建立四个标识符。

const ATTR = 0; // 属性
    const TEXT = 1; // 文本
    const REMOVE = 2; // 删除
    const REPLACE = 3; // 替换
    复制代码

1.  先创建两个不同的虚拟DOM。

let vDom1 = createElement("div", {class: "div"}, [
                	createElement("div", {class: "div"}, ["a"])
                ]);
    let vDom2 = createElement("div", {class: "div1"}, [
                    createElement("div", {class: "div2"}, ["b"])
                ]);
    
    复制代码

2. 然后比较两个虚拟DOM的差异（diff过程） `diff(vDom1, vDom2)`

function diff(oldTree, newTree){
        walk(oldTree, newTree, index); // 遍历两个虚拟DOM树
    }
    复制代码

1.  遍历的过程

*  文本的不同

// 我这里使用了不是很准确的比较（可以使用toString.call）
    // 如果都是文本
    // patch是补丁对象
    // 数据描述： {
        type: 不同的类型，不同的地方}
    if((typeof oldNode === "string") && (typeof newNode === "string")){
    	// 如果文本内容不一样
    	if(newNode !== oldNode){
    		patch.push({
        type: TEXT, text: newNode});
    	}
    }
    复制代码

*  属性的不同

// 如果类型相同就比较属性， 类型不相同默认换掉了整个元素
    if(oldNode.type === newNode.type){
        // 遍历新老节点属性的不同
        let attr = diffAttr(oldNode.props, newNode.props);
        // 如果有不同， 就加入patch中
        if (Object.keys(attr).length > 0) {
            patch.push({ type: ATTR, attr });
        }
        // 遍历子节点
        diffChildren(oldNode.children, newNode.children);
    }
    复制代码

遍历属性

遍历子节点的属性

function diffChildren(oldChildren, newChildren){
        oldChildren.forEach(function(child, i){
            // 子节点递归遍历属性
        	walk(child, newChildren[i], ++ index);
        });
    }
    复制代码

*  删除

// 如果没有新节点，说明删除了，标记处删除的索引
    if(!newNode){
        patch.push({
        type: REMOVE, index});
    }
    复制代码

*  替换

// 其余情况为替换
    patch.push({
        type: REPLACE, newNode});
    复制代码

*  整体代码

我们查看一下补丁对象

## 打补丁（patch） ##

首先建立一个索引对象`let patchIndex = 0;`

1.  将补丁对象和真实的DOM作比较`patch(dom, patches)`

function patch(dom, patches){
        walkPatch(dom);
    }
    复制代码

遍历补丁的实现

function walkPatch(dom){
        // 获取当前节点的补丁
        let patch = patches[patchIndex ++];
        // 获取子节点
        let children = dom.childNodes;
        // 遍历子节点
        // 遍历到最后一个元素，从后往前打补丁
        children.forEach((child)=>walkPatch(child));
        // 如果有补丁，就打补丁
        if(patch){
        	doPatch(dom, patch);
        }
    }
    复制代码

*  打补丁的实现过程
    
     *  属性
    
        // 遍历属性
        // key 就是 class或者value（这个value是属性）
        // value 就是 类名或者是值
        for (key in p.attr) {
            let value = p.attr[key];
            // 如果有值（其实就是上一篇虚拟DOM中的设置属性）
            if(value){
                if(key === "value"){
        	    if(node.type.toUpperCase() === "INPUT" || node.type.toUpperCase() === "TEXTAREA"){
        	        node.value = value;
        	    }
        	}else {
        		node.setAttribute(key, value);
        	}
        	// 没有值，就是删除属性
            }else {
                node.removeAttribute(key);
            }
        }
        复制代码
    
     *  文本
    
        // 替换文本节点
        node.textContent = p.text;
        复制代码
    
     *  删除
    
        // 删除自己
        node.parentNode.removeChild(node);
        复制代码
    
     *  替换
    
        let { newNode } = p;
        // 如果是元素就创建元素否则就是文本
        newNode = (newNode instanceof Element) ?  createDom(newNode): document.createTextNode(newNode);
        // 用新节点替换旧结点
        newNode.parentNode.replaceChild(newNode, node);
        复制代码

整体代码

未打补丁的DOM树

打完补丁的DOM树我们用一个相对复杂一点的例子来验证

let vDom1 = createElement("div", {class: "div"}, [
                	createElement("div", {class: "div"}, ["a"]),
                	createElement("div", {}, ["b"]),
                	createElement("div", {class: "div"}, [
            		    createElement("div", {class: "div"}, ["c"]),
            		    createElement("div", {class: "div"}, ["d"])
                	])
                ]);
    let vDom2 = createElement("div", {class: "div1"}, [
        	        createElement("div", {class: "div2"}, ["1"]),
        	        createElement("div", {class: "div3"}, ["2"]),
        	        createElement("div", {}, [
        	            createElement("div", {class: "div5"}, ["3"]),
        		        createElement("div", {class: "div6"}, ["4"])
        	        ])
                ]);
    复制代码

打补丁以前的DOM树

打补丁之后的DOM树

*  **总结**
    
     *  其实我只是实现了一个很简单的diff算法，还有好多情况没有考虑和实现。比如新增还有两个节点交换了位置，以及不是同级的比较。
     *  其实我觉得这就是一种思想，重点在于我们不仅会使用它还有学会了解他并慢慢的掌握它。
     *  上边的属性，其实没有包含style的实现。

转载于:https://juejin.im/post/5cf7624d5188252f325d677e

[DOM]: https://juejin.im/post/5cf3c75de51d45572c05fff3