vue2.x之diff算法详解
江北 5月24日 32 2 2 32 2 2

创建虚拟节点,并渲染到我们的页面上

我们以对象的形式表示一个个dom元素,然后每次更新的时候通过对比,在一定程度上可以复用而并非新建

假设我们的html如下


<div id="app"></div>

//用来创建虚拟dom节点
function h(tag,key,...children){
    children = children.map(child=>{
        if(typeof child === 'object'){
            return  child
        }else{
            return {
                undefined,undefined,undefined,text:child
            }
        }
    })
    return {
        tag,
        key,
        children
    }
}

//把虚拟dom转化为真是节点

function createElement(vnode){
    const { tag ,children,text} = vnode;
    if(typeof tag === 'string'){
        vnode.el = document.createElement(tag);
        children &&  children.forEach(child=>{
            render(child,vnode.el)
        })
    }else{
        vnode.el = document.createTextNode(text)
    }

    return vnode.el;
}

//创建render函数

function render(vnode,container){
    const el = createElement(vnode);
    container.appendChild(el);
}

//创建一个包含子节点的虚拟节点

var vnode = h("div",1,
            h("div","a","a"),
            h("div","b","b"),
            h("div","c","c"),
            h("div","d","d"),
        )

//执行我们的渲染函数

render(vnode,app)

通过diff算法优化更新

分析:我们可以在每次拿旧的节点去比较新节点,如果节点的类型和key一样,我们就认为他们是一样的元素,直接复用旧的节点


//工具方法,判断是否是同一个dom

function sameVnode(oldVnode,newVnode){
    return oldVnode.tag === newVnode.tag && oldVnode.key === newVnode.key
}

//patch方法,拿新的节点比较旧的节点

function patch(oldVnode,newVnode){
    //假设两个元素的节点类型不同,直接拿新节点替换老节点 
    if(newVnode.tag !== oldVnode.tag){
        let el = createElement(newVnode);
        oldVnode.el.parentNode.replaceChild(el,oldVnode.el);
        return el;
    }
    //假设两个节点都是文字节点 ,如果节点不一样,直接拿新的文字替换老的文字 
    if(!oldVnode.tag){
        if (oldVnode.text !== newVnode.text) {
            oldVnode.el.textContent = newVnode.text
        }
        return oldVnode.el;
    }
    // 假设两个节点类型相同,我们直接拿旧节点赋给新节点
    let el = newVnode.el = oldVnode.el;
    let oldChildren = oldVnode.children || [];
    let newChildren = newVnode.children || [];
    // 子元素对比
    if(newChildren.length>0 && newChildren.length>0){
        //如果新旧节点都有子节点,那么我们去对比子节点
        updateChildren(el,oldChildren,newChildren)
    }else if(newChildren.length>0){
        //如果新节点 有子元素,而旧节点没有,我们 直接把新的子节点放入父元素中
        for (let i = 0; i < newChildren.length; i++) {
            let child = newChildren[i];
            el.appendChild(createElement(child))
        }
    }else if(oldChildren>0){
        //假设老节点 有子元素,而新节点没有,那么我们直接把元素的内容清空即可
        el.innerHTML = ''
    }
    return el;
}

以上:更新子节点时,后面两种情况都很好理解,我们主要关注新旧节点都有的情况下时如何做对比的。请看下面代码

对比更新子节点

优化层面的对比

说明:我们在操作dom时,一般会有几种操作

1,尾部插入元素。

例:

//老节点
a,b,c,d
//新节点
a,b,c,d,e

function updateChildren(parentElm, oldCh, newCh){
    //双指针对比 
    let oldStartIndex = 0;
    let oldEndIndex = oldCh.length-1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIndex];

    let newStartIndex = 0;
    let newEndIndex = newCh.length-1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIndex];

    while(oldStartIndex<=oldEndIndex && newStartIndex<=newEndIndex){
        //假设新节点的首个元素和旧节点的首个元素相同,那我们直接把复用老节点,并且新旧节点的头部指针都向后移位
        if(sameVnode(oldStartVnode,newStartVnode)){
            patch(oldStartVnode,newStartVnode)
            oldStartVnode = oldCh[++oldStartIndex];
            newStartVnode = newCh[++newStartIndex];
        }
    }
    //此时新节点的头部指针和新节点的尾部指针重合
    if(newStartIndex<=newEndIndex){
        for(let i=newStartIndex;i<=newEndIndex;i++){
            let el = newCh[newEndIndex+1] == null ? null : newCh[newEndIndex+1].el;
            //此时el为null,因此下方的操作 等同于 parentElm.appendChild(createElement(newCh[i]))
            parentElm.insertBefore(createElement(newCh[i]),el)
        }
    }
}

2,往头部插入元素。


//老节点
a,b,c,d
//新节点
e,a,b,c,d

function updateChildren(parentElm, oldCh, newCh){
    //双指针对比 
    //同上

    while(oldStartIndex<=oldEndIndex && newStartIndex<=newEndIndex){

        //假设新节点的末尾元素和旧节点的末尾元素相同,我们依旧直接把复用老节点,并且新旧节点的尾部指针都前移
        if(sameVnode(oldEndVnode,newEndVnode)){
            patch(oldEndVnode,newEndVnode);
            //尾指针前移
            oldEndVnode = oldCh[--oldEndIndex];
            newEndVnode = newCh[--newEndIndex];
        }
    }
    //此时新节点的头部指针和新节点的尾部指针重合为0
    if(newStartIndex<=newEndIndex){
        for(let i=newStartIndex;i<=newEndIndex;i++){
            //此时newCh[newEndIndex+1]指向新节点a
            let el = newCh[newEndIndex+1] == null ? null : newCh[newEndIndex+1].el;
            //此时el为a,节点a的el复用了旧节点的el
            //因此我们直接创建节点e的真实节点 并直接插入在节点a前
            parentElm.insertBefore(createElement(newCh[i]),el)
        }
    }
}

3,交叉对比

尾移头或者头移尾

//1,头移尾
//老节点 
a,b,c,d
新节点
b,c,d,a

或者

//2.尾移头
//老节点 
a,b,c,d
新节点
d,a,b,c,

再或者

//3.反转
 //老节点 
 a,b,c,d
 新节点
 d,c,b,a

function updateChildren(parentElm, oldCh, newCh){
            /*
            ...
            */
        while(oldStartIndex<=oldEndIndex && newStartIndex<=newEndIndex){

            if(sameVnode(oldStartVnode,newStartVnode)){
                /*
                ...
                */
            }else if(sameVnode(oldEndVnode,newEndVnode)){
                /*
                ...
                */
            }else if(sameVnode(oldStartVnode,newEndVnode)){
                //头移尾
                //a,b,c,d => b,c,d,a
                patch(oldStartVnode,newEndVnode)
                //把头部元素添加到尾部元素的下一个元素之前
                parentElm.insertBefore(oldStartVnode.el,oldEndVnode.el.nextSibling)
                //旧节点头部指针向后移
                oldStartVnode = oldCh[++oldStartIndex];
                //新节点尾部指针向前移
                newEndVnode = newCh[--newEndIndex];
            }else if(sameVnode(oldEndVnode,newStartVnode)){
                //尾移头
                //a,b,c,d => d,a,b,c
                patch(oldEndVnode,newStartVnode)
                //把尾部元素移动到头部元素之前
                parentElm.insertBefore(oldEndVnode.el,oldStartVnode.el)
                //旧节点尾指针向前移
                oldEndVnode = oldCh[--oldEndIndex];
                //新节点头部指针向后移
                newStartVnode = newCh[++newStartIndex];
            }
        }

        if(newStartIndex<=newEndIndex){
            for(let i=newStartIndex;i<=newEndIndex;i++){
                let el = newCh[newEndIndex+1] == null ? null : newCh[newEndIndex+1].el;
                parentElm.insertBefore(createElement(newCh[i]),el)
            }
        }
    }

以上其实都是一些优化策略,那么如果是乱序呢?

乱序

老节点a,b,c,d

新节点e,a,f,c,g

头和头不同,尾和尾不同,头和尾,尾和头,都不同,此时我们可以把旧节点用key生成一个映射表,然后每次在表里去找新节点,请看最后一种情况


function updateChildren(parentElm, oldCh, newCh){
    let oldStartIndex = 0;
    let oldEndIndex = oldCh.length-1;
    let oldStartVnode = oldCh[0];
    let oldEndVnode = oldCh[oldEndIndex];

    let newStartIndex = 0;
    let newEndIndex = newCh.length-1;
    let newStartVnode = newCh[0];
    let newEndVnode = newCh[newEndIndex];

    let map = createIndexByKey(oldCh)

    while(oldStartIndex<=oldEndIndex && newStartIndex<=newEndIndex){

        if(!oldStartVnode){
            oldStartVnode = oldCh[++oldStartIndex]
        }else if(!oldEndVnode){
            oldEndVnode = oldCh[--oldEndIndex]
        }else if(sameVnode(oldStartVnode,newStartVnode)){
            patch(oldStartVnode,newStartVnode)
            oldStartVnode = oldCh[++oldStartIndex];
            newStartVnode = newCh[++newStartIndex];
        }else if(sameVnode(oldEndVnode,newEndVnode)){
            patch(oldEndVnode,newEndVnode)
            oldEndVnode = oldCh[--oldEndIndex];
            newEndVnode = newCh[--newEndIndex];
        }else if(sameVnode(oldStartVnode,newEndVnode)){
            patch(oldStartVnode,newEndVnode)
            parentElm.insertBefore(oldStartVnode.el,oldEndVnode.el.nextSibling)
            oldStartVnode = oldCh[++oldStartIndex];
            newEndVnode = newCh[--newEndIndex];
        }else if(sameVnode(oldEndVnode,newStartVnode)){
            patch(oldEndVnode,newStartVnode)
            parentElm.insertBefore(oldEndVnode.el,oldStartVnode.el)
            oldEndVnode = oldCh[--oldEndIndex];
            newStartVnode = newCh[++newStartIndex];
        }else{
            //乱序
            //用旧的节点的key生成一个映射表,那新的节点的key再映射表里面寻找,找到就做移动操作,找不到就直接插入即可
            //debugger
            let  findedIndex = map[newStartVnode.key];
            if(findedIndex){
                let findVnode = oldCh[findedIndex];
                //防止数组塌陷,此处置为空
                oldCh[findedIndex] = undefined;
                //当旧节点重有这个key时,直接把找到的这个节点元素移动到开始节点的前面
                parentElm.insertBefore(findVnode.el,oldStartVnode.el)
                patch(findVnode,newStartVnode)
            }else{
                //如果找不到,直接创建新节点,移动旧的开始节点前
                parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.el)

            }
            //新节点头指针向后移动
            newStartVnode = newCh[++newStartIndex]
        }
    }

    if(newStartIndex<=newEndIndex){
        for(let i=newStartIndex;i<=newEndIndex;i++){
            let el = newCh[newEndIndex+1] == null ? null : newCh[newEndIndex+1].el;
            parentElm.insertBefore(createElement(newCh[i]),el)
        }
    }
    if(oldStartIndex <= oldEndIndex){
        for(let i=oldStartIndex;i<=oldEndIndex;i++){
            let child = oldCh[i];
            if(child){
                parentElm.removeChild(child.el)
            }
        }
    }
}

完整代码


function createIndexByKey(children){
        let map = {};
        children.forEach((item,index)=>{
            if(item.key){
                map[item.key] = index
            }
        })
        return map;
    }
    function sameVnode(oldVnode,newVnode){
        return oldVnode.tag === newVnode.tag && oldVnode.key === newVnode.key
    }
    function patch(oldVnode,newVnode){
        if(newVnode.tag !== oldVnode.tag){
            let el = createElement(newVnode);
            oldVnode.el.parentNode.replaceChild(el,oldVnode.el);
            return el;
        }
        if(!oldVnode.tag){
            if (oldVnode.text !== newVnode.text) {
                oldVnode.el.textContent = newVnode.text
            }
            return oldVnode.el;
        }

        let el = newVnode.el = oldVnode.el;
        let oldChildren = oldVnode.children || [];
        let newChildren = newVnode.children || [];

        if(newChildren.length>0 && newChildren.length>0){
            updateChildren(el,oldChildren,newChildren)
        }else if(newChildren.length>0){
            for (let i = 0; i < newChildren.length; i++) {
                let child = newChildren[i];
                el.appendChild(createElement(child))
            }
        }else if(oldChildren>0){
            el.innerHTML = ''
        }
        return el;
    }
    function updateChildren(parentElm, oldCh, newCh){
        let oldStartIndex = 0;
        let oldEndIndex = oldCh.length-1;
        let oldStartVnode = oldCh[0];
        let oldEndVnode = oldCh[oldEndIndex];

        let newStartIndex = 0;
        let newEndIndex = newCh.length-1;
        let newStartVnode = newCh[0];
        let newEndVnode = newCh[newEndIndex];

        let map = createIndexByKey(oldCh)

        while(oldStartIndex<=oldEndIndex && newStartIndex<=newEndIndex){

            if(!oldStartVnode){
                oldStartVnode = oldCh[++oldStartIndex]
            }else if(!oldEndVnode){
                oldEndVnode = oldCh[--oldEndIndex]
            }else if(sameVnode(oldStartVnode,newStartVnode)){
                patch(oldStartVnode,newStartVnode)
                oldStartVnode = oldCh[++oldStartIndex];
                newStartVnode = newCh[++newStartIndex];
            }else if(sameVnode(oldEndVnode,newEndVnode)){
                patch(oldEndVnode,newEndVnode)
                oldEndVnode = oldCh[--oldEndIndex];
                newEndVnode = newCh[--newEndIndex];
            }else if(sameVnode(oldStartVnode,newEndVnode)){
                patch(oldStartVnode,newEndVnode)
                parentElm.insertBefore(oldStartVnode.el,oldEndVnode.el.nextSibling)
                oldStartVnode = oldCh[++oldStartIndex];
                newEndVnode = newCh[--newEndIndex];
            }else if(sameVnode(oldEndVnode,newStartVnode)){
                patch(oldEndVnode,newStartVnode)
                parentElm.insertBefore(oldEndVnode.el,oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIndex];
                newStartVnode = newCh[++newStartIndex];
            }else{
                //乱序
                //用旧的节点的key生成一个映射表,那新的节点的key再映射表里面寻找,找到就做移动操作,找不到就直接插入即可
                //debugger
                let  findedIndex = map[newStartVnode.key];
                if(findedIndex){
                    let findVnode = oldCh[findedIndex];
                    oldCh[findedIndex] = undefined;
                    parentElm.insertBefore(findVnode.el,oldStartVnode.el)
                    patch(findVnode,newStartVnode)
                }else{
                    parentElm.insertBefore(createElement(newStartVnode),oldStartVnode.el)

                }
                newStartVnode = newCh[++newStartIndex]
            }
        }

        if(newStartIndex<=newEndIndex){
            for(let i=newStartIndex;i<=newEndIndex;i++){
                let el = newCh[newEndIndex+1] == null ? null : newCh[newEndIndex+1].el;
                parentElm.insertBefore(createElement(newCh[i]),el)
            }
        }
        if(oldStartIndex <= oldEndIndex){
            for(let i=oldStartIndex;i<=oldEndIndex;i++){
                let child = oldCh[i];
                if(child){
                    parentElm.removeChild(child.el)
                }
            }
        }
    }

function h(tag,key,...children){
        children = children.map(child=>{
            if(typeof child === 'object'){
                return  child
            }else{
                return {
                    undefined,undefined,undefined,text:child
                }
            }
        })
        return {
            tag,
            key,
            children
        }
    }
    var  app = document.getElementById("app");
    function createElement(vnode){
        const { tag ,children,text} = vnode;
        if(typeof tag === 'string'){
            vnode.el = document.createElement(tag);
            children &&  children.forEach(child=>{
                render(child,vnode.el)
            })
        }else{
            vnode.el = document.createTextNode(text)
        }

        return vnode.el;
    }
    function render(vnode,container){
        const el = createElement(vnode);
        container.appendChild(el);
    }
    var vnode = h("div",1,
            h("div","a","a"),
            h("div","b","b"),
            h("div","c","c"),
            h("div","d","d"),
        )
    render(vnode,app)
    var newVnode =  h("div",1,
            h("div","d","d"),
            h("div","a","a"),
            h("div","f","f"),
            h("div","c","c"),
            h("div","g","g"),
        )
    setTimeout(()=>{
        patch(vnode,newVnode)
    },2000)

当然,真实的情况肯定是更加的复杂,比如说同一个节点相同的key,我们在patch中肯定还是要更新新旧props style attr等,然而这些并不是本节的重点

关于key

带有key的优化

假如新旧节点如下

旧节点
<li key="a">a</li>
<li key="b">b</li>
<li key="c">c</li>
<li key="d">d</li>
新节点

<li key="d">d</li>
<li key="c">c</li>
<li key="b">b</li>
<li key="a">a</li>

如以上带有key,我们在比对的时候,直接移动复用就好了

假设没有key

旧节点
<li>a</li>
<li>b</li>
<li>c</li>
<li>d</li>
新节点

<li>d</li>
<li>c</li>
<li>b</li>
<li>a</li>

如上,没有key,那么我们需要更新四次,即依次更改每一个li里面的内容

为什么有时候不建议用index作为key

假设数据如下

list = [a,b,c,d]

循环后在html里

旧节点
<li key="0">a</li>
<li key="1">b</li>
<li key="2">c</li>
<li key="3">d</li>

新节点
<li key="0">d</li>
<li key="1">c</li>
<li key="2">b</li>
<li key="3">a</li>

如上:我们在对比时本来可以直接移动复用的,但是此时,根据上面对比,会得到首位元素是相同的,然后依次更新其内容及其它,这完全是不必要的

扫码分享到移动端
2 条评论
有趣LV4 评论于 5月24日 23:59

第二个代码块第九行,为啥有那么多 undefined,是打错了吗?

江北LV4 5月26日 17:44:

没啊  那证明这个节点就是文本节点  只是一个字符串

参与评论互动
登录即可参与评论互动哦