Vue的diff算法原理你真的了解嗎

更新時(shí)間：2022年03月17日 16:45:57 作者：darabiuz

這篇文章主要為大家詳細(xì)介紹了Vue的diff算法原理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

思維導(dǎo)圖

在這里插入圖片描述

0. 從常見(jiàn)問(wèn)題引入

虛擬dom是什么?
如何創(chuàng)建虛擬dom?
虛擬dom如何渲染成真是dom?
虛擬dom如何patch（patch）
虛擬DOM的優(yōu)勢(shì)?（性能）
Vue中的key到底有什么用，為什么不能用index?
Vue中的diff算法實(shí)現(xiàn)
diff算法是深度還是廣度優(yōu)先遍歷

1. 生成虛擬dom

1. h方法實(shí)現(xiàn)

virtual dom ，也就是虛擬節(jié)點(diǎn)

1.它通過(guò)js的Object對(duì)象模擬dom中的節(jié)點(diǎn)

2.再通過(guò)特定的render方法將其渲染成真實(shí)的dom節(jié)點(diǎn)

eg：

<div id="wrapper" class="1">
    <span style="color:red">hello</span>
    world
</div>

如果利用h方法生成虛擬dom的話(huà)：

h('div', { id: 'wrapper', class: '1' }, h('span', { style: { color: 'red' } }, 'hello'), 'world');

對(duì)應(yīng)的js對(duì)象如下：

let vd = {
    type: 'div',
    props: { id: 'wrapper', class: '1' },
    children: [
        {
            type: 'span',
            props: { color: 'red' },
            children: [{}]
        },
        {
            type: '',
            props: '',
            text: 'world'
        }
    ]
}

自己實(shí)現(xiàn)一個(gè)h方法

 function createElement(type, props = {}, ...children) {
    // 防止沒(méi)有傳值的話(huà)就賦值一個(gè)初始值
    let key;
    if (props.key) {
        key = props.key
        delete props.key
    }
    // 如果孩子節(jié)點(diǎn)有字符串類(lèi)型的，也需要轉(zhuǎn)化為虛擬節(jié)點(diǎn)
    children = children.map(child => {
        if (typeof child === 'string') {
            // 把不是節(jié)點(diǎn)類(lèi)型的子節(jié)點(diǎn)包裝為虛擬節(jié)點(diǎn)
            return vNode(undefined, undefined, undefined, undefined, child)
        } else {
            return child
        }
    })
    return vNode(type, props, key, children)
}
function vNode(type, props, key, children, text = undefined) {
    return {
        type,
        props,
        key,
        children,
        text
    }
}

2. render方法實(shí)現(xiàn)

render的作用：把虛擬dom轉(zhuǎn)化為真實(shí)dom渲染到container容器中去

export function render(vnode, container) {
    let ele = createDomElementFrom(vnode) //通過(guò)這個(gè)方法轉(zhuǎn)換真實(shí)節(jié)點(diǎn)
    if (ele) container.appendChild(ele)
}

把虛擬dom轉(zhuǎn)化為真實(shí)dom，插入到容器中，如果虛擬dom對(duì)象包含type值，說(shuō)明為元素（createElement），否則為節(jié)點(diǎn)類(lèi)型(createTextnode),并把真實(shí)節(jié)點(diǎn)賦值給虛擬節(jié)點(diǎn)，建立起兩者之間的關(guān)系

function createDomElementFrom(vnode) {
    let { type, key, props, children, text } = vnode
    if (type) {//說(shuō)明是一個(gè)標(biāo)簽
        // 1. 給虛擬元素加上一個(gè)domElemnt屬性，建立真實(shí)和虛擬dom的聯(lián)系，后面可以用來(lái)跟新真實(shí)dom
        vnode.domElement = document.createElement(type)
        // 2. 根據(jù)當(dāng)前虛擬節(jié)點(diǎn)的屬性，去跟新真實(shí)dom的值
        updateProperties(vnode)
        // 3. children中方的也是一個(gè)個(gè)的虛擬節(jié)點(diǎn)(就是遞歸把兒子追加到當(dāng)前元素里)
        children.forEach(childVnode => render(childVnode, vnode.domElement))
    } else {//說(shuō)明是一個(gè)文本
    }
    return vnode.domElement

}

function updateProperties(newVnode, oldProps = {}) {
    let domElement = newVnode.domElement //真實(shí)dom，
    let newProps = newVnode.props; //當(dāng)前虛擬節(jié)點(diǎn)中的屬性
    // 如果老的里面有，新的里面沒(méi)有，說(shuō)明這個(gè)屬性被移出了
    for (let oldPropName in oldProps) {
        if (!newProps[oldPropName]) {
            delete domElement[oldPropName] //新的沒(méi)有，為了復(fù)用這個(gè)dom，直接刪除
        }
    }
    // 如果新的里面有style，老的里面也有style，style可能還不一樣
    let newStyleObj = newProps.style || {}
    let oldStyleObj = oldProps.style || {}
    for (let propName in oldStyleObj) {
        if (!newStyleObj[propName]) {
            domElement.style[propName] = ''
        }
    }
    // 老的里面沒(méi)有，新的里面有
    for (let newPropsName in newProps) {
        // 直接用新節(jié)點(diǎn)的屬性覆蓋老節(jié)點(diǎn)的屬性
        if (newPropsName === 'style') {
            let styleObj = newProps.style;
            for (let s in styleObj) {
                domElement.style[s] = styleObj[s]
            }
        } else {
            domElement[newPropsName] = newProps[newPropsName]
        }
    }

}

根據(jù)當(dāng)前虛擬節(jié)點(diǎn)的屬性，去更新真實(shí)dom的值
由于還有子節(jié)點(diǎn)，所以還需要遞歸，生成子節(jié)點(diǎn)虛擬dom的真實(shí)節(jié)點(diǎn)，插入當(dāng)前的真實(shí)節(jié)點(diǎn)里去

在這里插入圖片描述

3. 再次渲染

剛剛可能會(huì)有點(diǎn)不解，為什么要把新的節(jié)點(diǎn)和老的節(jié)點(diǎn)屬性進(jìn)行比對(duì)，因?yàn)閯倓偸鞘状武秩?，現(xiàn)在講一下二次渲染

比如說(shuō)現(xiàn)在構(gòu)建了一個(gè)新節(jié)點(diǎn)newNode,我們需要和老節(jié)點(diǎn)進(jìn)行對(duì)比，然而并不是簡(jiǎn)單的替換，而是需要盡可能多地進(jìn)行復(fù)用

首先判斷父親節(jié)點(diǎn)的類(lèi)型，如果不一樣就直接替換

如果一樣

1.文本類(lèi)型，直接替換文本值即可

2.元素類(lèi)型，需要根據(jù)屬性來(lái)替換

這就證明了render方法里我們的oldProps的必要性，所以這里把新節(jié)點(diǎn)的真實(shí)dom賦值為舊節(jié)點(diǎn)的真實(shí)dom，先復(fù)用一波，待會(huì)再慢慢修改

updateProperties(newVnode, oldVNode.props)

export function patch(oldVNode, newVnode) {
    // //判斷類(lèi)型是否一樣,不一樣直接用新虛擬節(jié)點(diǎn)替換老的
    if (oldVNode.type !== newVnode.type) {
        return oldVNode.domElement.parentNode.replaceChild(
            createDomElementFrom(newVnode), oldVNode.domElement
        )
    }
    // 類(lèi)型相同，且是文本
    if (oldVNode.text) {
        return oldVNode.document.textContent = newVnode.text
    }
    // 類(lèi)型一樣，不是文本，是標(biāo)簽，需要根據(jù)新節(jié)點(diǎn)的屬性更新老節(jié)點(diǎn)的屬性
    // 1. 復(fù)用老節(jié)點(diǎn)的真實(shí)dom
    let domElement = newVnode.domElement = oldVNode.domElement
    // 2. 根據(jù)最新的虛擬節(jié)點(diǎn)來(lái)更新屬性
    updateProperties(newVnode, oldVNode.props)
    // 比較兒子
    let oldChildren = oldVNode.children
    let newChildren = newVnode.children
    // 1. 老的有兒子，新的有兒子
    if (oldChildren.length > 0 && newChildren.length > 0) {
        // 對(duì)比兩個(gè)兒子(很復(fù)雜)
    } else if (oldChildren.length > 0) {
        // 2. 老的有兒子，新的沒(méi)兒子
        domElement.innerHTML = ''
    } else if (newChildren.length > 0) {
        // 3. 新增了兒子
        for (let i = 0; i < newChildren.length; i++) {
            // 把每個(gè)兒子加入元素里
            let ele = createDomElementFrom(newChildren[i])
            domElement.appendChild(ele)
        }
    }


}

2. diff算法

剛剛的渲染方法里，首先是對(duì)最外層元素進(jìn)行對(duì)比，對(duì)于兒子節(jié)點(diǎn)，分為三種情況

1.老的有兒子，新的沒(méi)兒子（那么直接把真實(shí)節(jié)點(diǎn)的innerHTML設(shè)置為空即可）

2.老的沒(méi)兒子，新的有兒子（那么遍歷新的虛擬節(jié)點(diǎn)的兒子列表，把每一個(gè)都利用createElementFrom方法轉(zhuǎn)化為真實(shí)dom，append到最外層真實(shí)dom即可）

3.老的有兒子，新的有兒子，這個(gè)情況非常復(fù)雜，也就是我們要提及的diff算法

1. 對(duì)常見(jiàn)的dom做優(yōu)化

前后追加元素
正序和倒序元素
中間插入元素

以最常見(jiàn)的ul列表為例子

舊的虛擬dom

let oldNode = h('div', {},
    h('li', { style: { background: 'red' }, key: 'A' }, 'A'),
    h('li', { style: { background: 'blue' }, key: 'B' }, 'A'),
    h('li', { style: { background: 'yellow' }, key: 'C' }, 'C'),
    h('li', { style: { background: 'green' }, key: 'D' }, 'D'),
);

情況1：末尾追加一個(gè)元素(頭和頭相同)

新的虛擬節(jié)點(diǎn)

在這里插入圖片描述

let newVnode = h('div', {},
    h('li', { style: { background: 'red' }, key: 'A' }, 'A'),
    h('li', { style: { background: 'blue' }, key: 'B' }, 'B'),
    h('li', { style: { background: 'yellow' }, key: 'C' }, 'C1'),
    h('li', { style: { background: 'green' }, key: 'D' }, 'D1'),
    h('li', { style: { background: 'black' }, key: 'D' }, 'E'),
);

eg：

// 比較是否同一個(gè)節(jié)點(diǎn)
function isSameVnode(oldVnode, newVnode) {
    return oldVnode.key == newVnode.key && oldVnode.type == newVnode.type
}
// diff
function updateChildren(parent, oldChildren, newChildren) {
    // 1. 創(chuàng)建舊節(jié)點(diǎn)開(kāi)頭指針和結(jié)尾
    let oldStartIndex = 0
    let oldStartVnode = oldChildren[oldStartIndex];
    let oldEndIndex = oldChildren.length - 1
    let oldEndVnode = oldChildren[oldEndIndex];
    // 2. 創(chuàng)建新節(jié)點(diǎn)的指針
    let newStartIndex = 0
    let newStartVnode = newChildren[newStartIndex];
    let newEndIndex = newChildren.length - 1
    let newEndVnode = newChildren[newEndIndex];
    // 1. 當(dāng)從后面插入節(jié)點(diǎn)的時(shí)候，希望判斷老的孩子和新的孩子 循環(huán)的時(shí)候，誰(shuí)先結(jié)束就停止循環(huán)
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        // 注意：比較對(duì)象是否相等，你不能用==，因?yàn)橹赶虻奈恢每赡懿灰粯?，可以用type和key
        if (isSameVnode(oldStartVnode, newStartVnode)) {
            //patch比對(duì)更新
            patch(oldStartVnode, newStartVnode)
            // 移動(dòng)指針
            oldStartVnode = oldChildren[++oldStartIndex]
            newStartVnode = newChildren[++newStartIndex]
        }
    }
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            parent.appendChild(createDomElementFrom(newChildren[i]))
        }
    }
}

在這里插入圖片描述

情況2：隊(duì)首添加一個(gè)節(jié)點(diǎn)（尾和尾）

在這里插入圖片描述

頭和頭+尾和尾的處理方法:

我們通過(guò)parent.insertBefore(createDomElementFrom(newChildren[i]), beforeElement)使得末尾添加和頭部添加采用同一種處理方法

    // 如果是從前往后遍歷說(shuō)明末尾新增了節(jié)點(diǎn)，會(huì)比原來(lái)的兒子后面新增了幾個(gè)
    // 也可以時(shí)從后往前遍歷，說(shuō)明比原來(lái)的兒子前面新增了幾個(gè)
    if (newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            // 取得第一個(gè)值，null代表末尾
            let beforeElement = newChildren[newEndIndex + 1] == null ? null : newChildren[newEndIndex + 1].domElement   parent.insertBefore(createDomElementFrom(newChildren[i]), beforeElement)
        }
    }

圖解：

在這里插入圖片描述

MVVM=>數(shù)據(jù)一變，就調(diào)用patch

情況3：翻轉(zhuǎn)類(lèi)型(頭和尾)

在這里插入圖片描述

尾和頭就不畫(huà)圖了

else if (isSameVnode(oldStartVnode, newEndVnode)) {
                // 頭和尾巴都不一樣,拿老的頭和新的尾巴比較
                patch(oldStartVnode, newEndVnode)
                // 把舊節(jié)點(diǎn)的頭部插入到舊節(jié)點(diǎn)末尾指針指向的節(jié)點(diǎn)之后一個(gè)
                parent.insertBefore(oldStartVnode.domElement, oldEndVnode.domElement.nextSibling)
                // 移動(dòng)指針
                oldStartVnode = oldChildren[++oldStartIndex]
                newEndVnode = newChildren[--newEndIndex]
            } else if (isSameVnode(oldEndVnode, newStartVnode)) {
                // 頭和尾巴都不一樣,拿老的頭和新的尾巴比較
                patch(oldEndVnode, newStartVnode)
                // 把舊節(jié)點(diǎn)的頭部插入到舊節(jié)點(diǎn)末尾指針指向的節(jié)點(diǎn)之后一個(gè)
                parent.insertBefore(oldEndVnode.domElement, oldStartVnode.domElement)
                // 移動(dòng)指針
                oldEndVnode = oldChildren[--oldEndIndex]
                newStartVnode = newChildren[++newStartIndex]
            } else {

情況4: 暴力比對(duì)復(fù)用

在這里插入圖片描述

else {
                // 都不一樣，就暴力比對(duì)
                // 需要先拿到新的節(jié)點(diǎn)去老的節(jié)點(diǎn)查找是否存在相同的key，存在則復(fù)用，不存在就創(chuàng)建插入即可
                // 1. 先把老的哈希
                let index = map[newStartVnode.key]//看看新節(jié)點(diǎn)的key在不在這個(gè)map里
                console.log(index);
                if (index == null) {//沒(méi)有相同的key
                    // 直接創(chuàng)建一個(gè)，插入到老的前面即可
                    parent.insertBefore(createDomElementFrom(newStartVnode),
                        oldStartVnode.domElement)
                } else {//有，可以復(fù)用
                    let toMoveNode = oldChildren[index]
                    patch(toMoveNode, newStartVnode)//復(fù)用要先patch一下
                    parent.insertBefore(toMoveNode.domElement, oldStartVnode.domElement)
                    oldChildren[index] = undefined
                    // 移動(dòng)指正
                }
                newStartVnode = newChildren[++newStartIndex]
            }
// 寫(xiě)一個(gè)方法，做成一個(gè)哈希表{a:0,b:1,c:2}
function createMapToIndex(oldChildren) {
    let map = {}
    for (let i = 0; i < oldChildren.length; i++) {
        let current = oldChildren[i]
        if (current.key) {
            map[current.key] = i
        }
    }
    return map
}