带你简单理解diff算法

关于virtual dom

我们知道不管是vue还是react当中，都是利用virtual dom(下面简称vd)来表示真实的dom，因为操作真实的dom的代价是昂贵的，即使是查找dom节点的操作都是昂贵的，所以在优化的方法当中，就有缓存dom的查找结果的一个优化，那么既然真实dom的操作是昂贵的，所以如果我们在使用diff算法来比较两个dom之间的差异的时候，就要遍历所有的dom来进行对比，如果是按照真实的dom来进行diff算法的比较的话，那么就相当消耗性能了，因此vd应运而生。那么怎么将真实的dom和vd对应起来呢？我们知道，dom不外乎三个特性：
1、标签名
2、各种属性
3、孩子节点
因此，如果要用vd来表示dom的话我们就可以这样定义。

class VNode {
    constructor(tagName, attributes, children) {
        this.tagName = tagName
        this.attributes = attributes
        this.children = children
    }
}

比如有这样的dom

<div id="div" class="classVal">
    <span>child</span>
</div>

那么vd就是这样的

{
    tagName: 'div',
    attributes: {
        'id': 'div',
        'class': 'classVal'
    },
    children: [{
        tagName: 'span',
        attributes: null,
        children: ['child']
    }]
}

当然，这里vd的定义少了TEXT节点，所以我们加上TEXT节点，TEXT节点直接返回里面的innerText/textContent，就像上面的children: ['child']，我们定义一个叫h的函数，用来创建vd，包括TEXT节点，它接受四个参数，分别如下:

tagName: 标签名  
text: 如果是TEXT节点，那么就是TEXT的内容，即innerText/textContent
attributes: dom属性的价值对  
children: dom的孩子vd

function h(tagName, text, attributes, children) {
    // 判断到是TEXT节点，直接返回TEXT里面的内容
    if(text) {
        return text
    }
    return new VNode(tagName, attributes, children)
}

好了，VD大概就是这样子表示，那么我们如果根据vd还原成真实的dom呢，其实很简单，就是根据一一对应关系还原呗:

function createElement(vnode) {
    var el = null;
    // 文本元素
    if(typeof vnode === "string") {
        el = document.createTextNode(vnode);
        return el;
    }
    // 还原dom
    el = document.createElement(vnode.tagName);
    // 还原attribute
    for(var key in attributes) {
        el.setAttribute(key, attributes[key]);
    }
    // 还原孩子节点
    var children = vnode.children.map(createElement);
    children.forEach(function(child) {
        el.appendChild(child);
    });
    return el;
}

关于vd的理解差不多就这样，如果有需要补充的或者指正的，望不吝赐教。

diff算法

有了vd后，我们要怎么比较两个dom树之间的不同呢，当然不能无脑的使用innerHTML对整块树更新（backbone就是这样），而是针对更改的地方进行更新或者替换，那么我们就需要依赖diff来找出两棵树之间的不同。
传统的diff算法，是需要跨级对比两个树之间的不同，时间复杂度为O(n^3)，这样的对比是无法接受的，所以react提出了一个简单粗暴的diff算法，只对比同级元素，这样算法复杂度就变成了O(n)了，虽然不能做到最优的更新，但是时间复杂度大大减少，是一种平衡的算法，下面会提到。

那么怎么理解它是只对比同级和具体它是怎么对比的呢？
基于diff算法的同级对比，我们先讲下对比的过程中，它主要分为四种类型的对比，分别为:
1、新建create： 新的vd中有这个节点，旧的没有
2、删除remove： 新的vd中没有这个节点，旧的有
3、替换replace： 新的vd的tagName和旧的tagName不同
4、更新update： 除了上面三点外的不同，具体是比较attributes先，然后再比较children
写成代码就是这样:

diff(newVnode, oldVNode) {

    if(!newVNode) {
        // 新节点中没有，说明是删除旧节点的
        return {
            type: 'remove'
        }
    } else if(!oldVNode) {
        // 新节点中有旧节点没有的，说明是删除
        return {
            type: 'create',
            newVNode
        }
    } else if(isDiff(newVNode, oldVNode)) {
        // 只要对比出两个节点的tagName不同，说明是替换
        return {
            type: 'replace',
            newVNode
        }
    } else {
        // 其他情况是更新节点，要对比两个节点的attributes和孩子节点
        return {
            type: 'update',
            attributes: diffAttributes(newVNode, oldVNode),
            children: diffChildren(newVNode, oldVNode)
        }
    }
}

// 对比孩子节点，其实就是遍历所有的孩子节点，然后调用diff对比
function diffChildren(newVnode, oldVNode) {
    var patches = []
    // 这里要获取两个节点中的最大孩子数，然后再进行对比 
    var len = Math.max(newVnode.children.length, oldVNode.children.length);
    for(let i = 0; i <len; i++) {
        patches[i] = diff(newVnode.children[i], oldVnode.children[i])
    }
    return patches
}

// 对比attribute，只有两种情况，要不就是值改变/新建，要不就是删除值，对比dom只有setAttribute和removeAttribute就知道了
function diffAttributes(newVnode, oldVNode) {
    var patches = []
    // 获取新旧节点的所有attributes
    var attrs = Object.assign({}, oldVNode.attributes, newVNode.attributes)
    for(let key in attrs) {
        let value = attrs[key]
        // 只要新节点的属性值和久节点的属性值不同，就判断为新建，不管是更新和真正的新建都是调用setAttribute来更新
        if(oldVNode.attributes[key] !== value) {
            patches.push({
                type: 'create',
                key,
                value: newVnode.attributes[key]
            })
        } else if(!newVNode.attributes[key]) {
            patches.push({
                key,
                type: 'remove'
            })
        }
    }
    return patches
}

// 判断两个节点是否不同
function isDiff(newVNode, oldVNode) {
    // 正常情况下，只对比tagName，但是text节点对比没有tagName，所以要考虑text节点
    return (typeof newVNode === 'string' && newVNode !== oldVNode) 
    || (typeof oldVNode === 'string' && newVNode !== oldVNode) 
    || newVNode.tagName !== oldVNode.tagName
}

结合代码，大家对比下面的图，图里面remove没有列出来，remove和create差不多原因，相信大家知道什么情况下是remove。

上图，按传统的方法只是在span和p直接插入了一个div，但是diff算法不是这么来更新的，它只对比同一级别的，即会觉得旧节点的p和新节点的div才是同一级，他们的tagName不同，所以定义为replace，接着把旧节点的div看成和新节点的p是同一级，依旧是replace，最后旧节点没有div，所以create了。可以看到，其实这个更新代价还是比较大的，但是比对的过程却简单和快速，因此是一种相对平衡的算法。

完整的代码大家可以看下我的git地址：github.com/VikiLee/XLM…

总结

我们更新dom的时候，尽量不要整棵树进行更新，需要做到细颗粒的更新，要做到细颗粒地更新就必须知道两棵树直接的不同，所以需要使用diff算法来进行对比，但是传统的diff算法虽然能做到细颗粒准确地更新，但是它需要花销大量的时间来进行比对，所以有来react的改版的diff算法，只比较同一级的元素，这样可以做到快速的比对，为O(n)，即使这样，在对比两棵树的时候，我们还是需要遍历所有的节点，我们知道dom的操作是昂贵的，即使是查找，也是昂贵的一个过程，特别是在节点很多的donm树下，所以虚拟dom应运而生，虚拟dom避开了直接操作dom的缺点，而是直接对比内存中vd，使得对比速度进一步得到质地提升。

文章永久链接：https://tech.souyunku.com/42937