虚拟DOM

解释

把页面中的真实DOM树映射到 js 对象树上，这个对象树就是虚拟DOM，我们可以在虚拟DOM上进行一系列操作：添加，比较修改和删除等。将最后修改好的DOM再一次性插入到真实DOM上。

作用

直接操作真实DOM，会不断引起浏览器重新解析，回流重绘等，大大降低了性能。而虚拟DOM，是存储在内存中的，把所有对DOM操作都放内存里的虚拟DOM上计算，只在最后才插入真实DOM，程序运行会更高效。

示例

真实DOM树

<div id="root" class="container">
  <h2>这是一颗dom树<h2>
  <img src="tree.jpg" alt="树" width="100">
</div>

虚拟DOM树

{
  tag: 'div',
  attrs: {
    id: 'root',
    class: 'container',
  },
  children: [
    {
      tag: 'h2',
      attrs: {},
      text: '这是一颗dom树',
    },
    {
      tag: 'img',
      attrs: {
        src: 'tree.jpg',
        alt: '树',
        width: 100,
      },
    },
  ],
}

Diff 算法

所谓的 diff 算法就是对两颗树结构进行比较算出不同之处。
传统的 diff 算法会把两棵树的所有节点一一比较，十分复杂并且计算很慢。
高效的 diff 算法有一套算法逻辑，根据算法逻辑可以大大提高速度和降低复杂度。

vue 和 react 的 diff 算法

vue 和 react 的 diff 算法都是对渲染前后两棵虚拟DOM树进行比较算出差异最后更新真实DOM。
当组件的状态state（数据data）发生变化，会通知组件进行更新，组件就会调用render函数生成新的虚拟DOM树vnode，而新虚拟DOM树和旧的虚拟DOM树oldVnode之间可能存在一些没有变动，或者可以复用的节点，此时对两棵树进行diff计算，算出差异。

vue的diff

逻辑判断步骤：

当拿到了vnode和oldVnode之后，会对两棵树进行判断：
1，vnode存在oldVnode不存在，则可认为是节点新建，直接根据vnode新建节点。
2，vnode不存在oldVnode存在，则可认为是节点删除，直接删除oldVnode节点。
3，vnode不存在oldVnode不存在，不会发生这样得情况。
4，vnode存在oldVnode存在，此时进一步比较两个节点是否相同（vue比较两个节点是否相同是判断两个节点的key，tag和input type等）
5，如果两个节点不同，则不会比较子节点，直接删除oldVnode节点再根据vnode新建节点。
6，如果两个节点相同，会再进行两个小判断，一个是看是否全等于，是的话就认为是同一个节点，直接返回结束。另一个是看新节点vnode是否是旧节点oldVnode的克隆，是的话就完全复制旧节点返回结束。
7，两个节点相同继续比较两个节点的子节点集合的存在性。
8，如果vnode的存在子节点，oldVnode不存在子节点，则直接按照vnode子节点全部创建，返回结束。
9，如果vnode不存在子节点，oldVnode存在子节点，则直接删除oldVnode的所有子节点，返回结束。
10，如果vnode不存在子节点，oldVnode不存在子节点，则直接返回结束。
11，如果vnode存在子节点，oldVnode存在子节点，判断vnode子节点是否文本节点，如是文本节点，则直接判断oldVnode子节点的文本是否与vnode相同，如果不同，直接更新节点文本返回结束。如果相同，也不需要更新了直接返回结束。
13，如果不是文本节点，则进行子节点的diff计算。
14，对vnode的子节点集合和oldVnode子节点集合各保持首尾指针（下标）然后循环判断，只要vnode的首指针（oldStartIdx）小于尾指针（newEndIdx）并且oldVnode的首指针（oldStartIdx）小于尾指针（oldEndIdx ）就一直持续循环判断。
15，具体判断就是：分别判断vnode的oldStartIdx子节点，newEndIdx子节点和oldVnode的oldStartIdx子节点，oldEndIdx 子节点的存在性以及两两是否相同，只要有其中一组相同就不再继续判断，进入下一次循环再去判断，对于命中不存在的指针前进一步，命中节点相同的，对应的新旧指针都向前或向后进一步，同时认为这个节点可以复用，然后对该节点进行打补丁。最后循环直到出现都不命中的情况。此时，进入最后一道查询：把oldStartIdx和oldEndIdx 之间的所有旧节点转换成 { key:节点 } 的对象，再在新子节点中从oldStartIdx节点开始查找，看新节点中是否有与上面key（旧节点的key）相同的，没有，就认为是新建节点，然后oldStartIdx向后进一步，重新循环。如果有，再判断对应的新旧子节点是否相同，如不同，也认为是新建节点。若相同，则认为老节点可以复用，则进行打补丁，并将旧子节点集合中的该节点置空（注意不是删除，否则会影旧节点集合长度进而影响指针），同时oldStartIdx向后进一步，重新循环。
16，按照上述循环直到新旧子节点集合其中一个的start指针大于end指针停止。
17，停止后，如果新旧子节点集合的start指针都大于end指针，则认为新旧子节点数目一样，无需再做其他操作。
18，如果新子节点集合的start指针大于end指针，则认为旧子节点集合的start到end之间的节点是需要删除的节点，直接删除。
19，如果旧子节点集合的start指针大于end指针，则认为新子节点集合的start到end之间的节点是新创建的节点，直接全部创建。
20，在对可复用节点（两个子节点相同）进行打补丁时，如果这些节点也有子节点，则打补丁时对它们的子节点也进行上述一样的diff计算（所以diff算法其实按照了深度优先的算法进行的），就是重复第6步开始往后。

流程图

vue-diff_01.png

vue-diff_02.png

vue-diff_03.png

代码逻辑

function patch(oldVnode, vnode, hydrating, removeOnly) {
    if (isUndef(vnode)) {
        if (isDef(oldVnode)) {
            // 对应第2点：vnode不存在oldVnode存在，则可认为是节点删除，直接删除oldVnode节点。
            invokeDestroyHook(oldVnode)
        }
        // else 对应第3点：vnode不存在oldVnode不存在，不会发生这样得情况。
        return
    }

    var isInitialPatch = false
    var insertedVnodeQueue = []

    if (isUndef(oldVnode)) {
        // empty mount (likely as component), create new root element
        isInitialPatch = true
        // 对应第1点：vnode存在oldVnode不存在，则可认为是节点新建，直接根据vnode新建节点
        createElm(vnode, insertedVnodeQueue)
    } else {
        // else 对应第4点：vnode存在oldVnode存在，此时进一步比较两个节点是否相同。
        // 元素是否是真实dom元素节点，不是自定义组件节点。
        var isRealElement = isDef(oldVnode.nodeType)
        // 对应第6点：如果两个节点相同，则patchVnode。
        if (!isRealElement && sameVnode(oldVnode, vnode)) {
            // patch existing root node
            patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
        } else {
            // 对应第5点：如果两个节点不同，则不会比较子节点，直接删除oldVnode节点再根据vnode新建节点。
            if (isRealElement) {
                // mounting to a real element
                // check if this is server-rendered content and if we can perform
                // a successful hydration.
                if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
                    oldVnode.removeAttribute(SSR_ATTR)
                    hydrating = true
                }
                if (isTrue(hydrating)) {
                    if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
                        invokeInsertHook(vnode, insertedVnodeQueue, true)
                        return oldVnode
                    } else {
                        warn(
                            'The client-side rendered virtual DOM tree is not matching ' +
                                'server-rendered content. This is likely caused by incorrect ' +
                                'HTML markup, for example nesting block-level elements inside ' +
                                '<p>, or missing <tbody>. Bailing hydration and performing ' +
                                'full client-side render.'
                        )
                    }
                }
                // either not server-rendered, or hydration failed.
                // create an empty node and replace it
                oldVnode = emptyNodeAt(oldVnode)
            }

            // replacing existing element
            var oldElm = oldVnode.elm
            var parentElm = nodeOps.parentNode(oldElm)

            // 创建新节点
            createElm(
                vnode,
                insertedVnodeQueue,
                // extremely rare edge case: do not insert if old element is in a
                // leaving transition. Only happens when combining transition +
                // keep-alive + HOCs. (#4590)
                oldElm._leaveCb ? null : parentElm,
                nodeOps.nextSibling(oldElm)
            )

            // update parent placeholder node element, recursively
            if (isDef(vnode.parent)) {
                var ancestor = vnode.parent
                var patchable = isPatchable(vnode)
                while (ancestor) {
                    for (var i = 0; i < cbs.destroy.length; ++i) {
                        cbs.destroy[i](ancestor)
                    }
                    ancestor.elm = vnode.elm
                    if (patchable) {
                        for (var i$1 = 0; i$1 < cbs.create.length; ++i$1) {
                            cbs.create[i$1](emptyNode, ancestor)
                        }
                        // #6513
                        // invoke insert hooks that may have been merged by create hooks.
                        // e.g. for directives that uses the "inserted" hook.
                        var insert = ancestor.data.hook.insert
                        if (insert.merged) {
                            // start at index 1 to avoid re-invoking component mounted hook
                            for (var i$2 = 1; i$2 < insert.fns.length; i$2++) {
                                insert.fns[i$2]()
                            }
                        }
                    } else {
                        registerRef(ancestor)
                    }
                    ancestor = ancestor.parent
                }
            }

            // destroy old node
            if (isDef(parentElm)) {
                removeVnodes([oldVnode], 0, 0)
            } else if (isDef(oldVnode.tag)) {
                invokeDestroyHook(oldVnode)
            }
        }
    }

    invokeInsertHook(vnode, insertedVnodeQueue, isInitialPatch)
    return vnode.elm
}

function patchVnode(oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
    // 对应第6点：是否全等于，是的话就认为是同一个节点，直接返回结束。
    if (oldVnode === vnode) {
        return
    }
    // 对应第6点：是否克隆节点，是的话就完全复制旧节点返回结束。
    if (isDef(vnode.elm) && isDef(ownerArray)) {
        // clone reused vnode
        vnode = ownerArray[index] = cloneVNode(vnode)
    }

    var elm = (vnode.elm = oldVnode.elm)

    if (isTrue(oldVnode.isAsyncPlaceholder)) {
        if (isDef(vnode.asyncFactory.resolved)) {
            hydrate(oldVnode.elm, vnode, insertedVnodeQueue)
        } else {
            vnode.isAsyncPlaceholder = true
        }
        return
    }

    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    if (
        isTrue(vnode.isStatic) &&
        isTrue(oldVnode.isStatic) &&
        vnode.key === oldVnode.key &&
        (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))
    ) {
        vnode.componentInstance = oldVnode.componentInstance
        return
    }

    var i
    var data = vnode.data
    if (isDef(data) && isDef((i = data.hook)) && isDef((i = i.prepatch))) {
        i(oldVnode, vnode)
    }
    // 对应第7点：两个节点相同继续比较两个节点的子节点集合的存在性。
    var oldCh = oldVnode.children
    var ch = vnode.children
    if (isDef(data) && isPatchable(vnode)) {
        for (i = 0; i < cbs.update.length; ++i) {
            cbs.update[i](oldVnode, vnode)
        }
        if (isDef((i = data.hook)) && isDef((i = i.update))) {
            i(oldVnode, vnode)
        }
    }
    // 对应第11点：先判断是否为文本节点
    if (isUndef(vnode.text)) {
        // 不是文本几点的情况：如果新旧子节点集合都存在子节点，并且集合不相等，开始比较子节点
        if (isDef(oldCh) && isDef(ch)) {
            if (oldCh !== ch) {
                // 对应第13点：子节点的diff计算
                updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
            }
        } else if (isDef(ch)) {
            {
                checkDuplicateKeys(ch)
            }
            if (isDef(oldVnode.text)) {
                nodeOps.setTextContent(elm, '')
            }
            // 对应第8点：如果vnode的存在子节点，oldVnode不存在子节点，则直接按照vnode子节点全部创建，返回结束。
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        } else if (isDef(oldCh)) {
            // 对应第9点：如果vnode不存在子节点，oldVnode存在子节点，则直接删除oldVnode的所有子节点，返回结束。
            removeVnodes(oldCh, 0, oldCh.length - 1)
        } else if (isDef(oldVnode.text)) {
            nodeOps.setTextContent(elm, '')
        }
    } else if (oldVnode.text !== vnode.text) {
        // 如果不是文本节点同时oldVnode文本也和vnode文本不一样，则直接更新文本
        nodeOps.setTextContent(elm, vnode.text)
    }
    if (isDef(data)) {
        if (isDef((i = data.hook)) && isDef((i = i.postpatch))) {
            i(oldVnode, vnode)
        }
    }
}

function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    var oldStartIdx = 0
    var newStartIdx = 0
    var oldEndIdx = oldCh.length - 1
    var oldStartVnode = oldCh[0]
    var oldEndVnode = oldCh[oldEndIdx]
    var newEndIdx = newCh.length - 1
    var newStartVnode = newCh[0]
    var newEndVnode = newCh[newEndIdx]
    var oldKeyToIdx, idxInOld, vnodeToMove, refElm

    // removeOnly is a special flag used only by <transition-group>
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    var canMove = !removeOnly

    {
        checkDuplicateKeys(newCh)
    }

    // 对应第14点：对vnode的子节点集合和oldVnode子节点集合各保持首尾指针（下标）然后循环判断，只要vnode的首指针（oldStartIdx）小于尾指针（newEndIdx）并且oldVnode的首指针（oldStartIdx）小于尾指针（oldEndIdx ）就一直持续循环判断。

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 对应第15点和第16点具体判断：
        // 如果oldVnode的第一个child不存在
        if (isUndef(oldStartVnode)) {
            // oldStartIdx索引右移，同时oldStartVnode右移
            oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left

            // 如果oldVnode的最后一个child不存在
        } else if (isUndef(oldEndVnode)) {
            // oldEndIdx索引左移，同时oldEndVnode左移
            oldEndVnode = oldCh[--oldEndIdx]

            // oldStartVnode和newStartVnode是相同节点
        } else if (sameVnode(oldStartVnode, newStartVnode)) {
            // 复用节点并递归patch oldStartVnode和newStartVnode， old和new索引和节点左移，继续循环
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
            // oldEndVnode和newEndVnode是相同节点
        } else if (sameVnode(oldEndVnode, newEndVnode)) {
            // 复用节点并递归patch oldEndVnode和newEndVnode， old和new索引和节点右移，继续循环
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]

            // oldStartVnode和newEndVnode是相同节点
        } else if (sameVnode(oldStartVnode, newEndVnode)) {
            // Vnode moved right
            // 复用节点并递归patch oldStartVnode和newEndVnode
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            // 将oldStartVnode对应dom移动到oldEndVnode的下一节点的前面（下一个节点不存在会直接追加在父节点后面）
            canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
            // old索引和节点右移，new索引和节点左移，继续循环
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldEndVnode, newStartVnode)) {
            // Vnode moved left
            // 复用节点并递归patch oldEndVnode和newStartVnode
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // 将oldEndVnode对应dom移动到此刻oldStartVnode对应dom前面
            canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
            // old索引和节点左移，new索引和节点右移，继续循环
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]

            // 如果都不匹配，开始查找
        } else {
            // 将oldVnode.children[oldStartIdx到oldEndIdx]之间的节点转换为{key:vnode}的映射oldKeyToIdx
            if (isUndef(oldKeyToIdx)) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
            }
            // 根据newStartVnode.key在映射里寻找
            idxInOld = isDef(newStartVnode.key)
                ? oldKeyToIdx[newStartVnode.key]
                : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
            // 如果未找到，说明newStartVnode是一个新的节点，新节点创建
            if (isUndef(idxInOld)) {
                // New element
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            } else {
                // 如果找到了和newStartVnodej具有相同的key的Vnode，叫vnodeToMove
                vnodeToMove = oldCh[idxInOld]
                // 比较两个具有相同的key的新节点是否是同一个节点
                // 不设key，newCh和oldCh只会进行头尾两端的相互比较，设key后，除了头尾两端的比较外，还会从用key生成的对象oldKeyToIdx中查找匹配的节点，所以为节点设置key可以更高效的利用dom。
                if (sameVnode(vnodeToMove, newStartVnode)) {
                    // 复用节点并递归patch vnodeToMove和newStartVnode
                    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                    // 清掉旧子节点集合中对应的节点（注意不是删除，否则会影旧节点集合长度进而影响指针）
                    oldCh[idxInOld] = undefined
                    // 将vnodeToMove对应dom移动到此刻oldStartVnode对应dom前面
                    canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                } else {
                    // 不相同，表示是新节点，直接创建
                    // same key but different element. treat as new element
                    createElm(
                        newStartVnode,
                        insertedVnodeQueue,
                        parentElm,
                        oldStartVnode.elm,
                        false,
                        newCh,
                        newStartIdx
                    )
                }
            }
            // 上述任何操作之后，概论循环结束，new的索引和节点右移，继续循环
            newStartVnode = newCh[++newStartIdx]
        }
    }
    if (oldStartIdx > oldEndIdx) {
        // 对应第19点：如果旧子节点集合的start指针大于end指针，则认为新子节点集合的start到end之间的节点是新创建的节点，直接全部创建。
        refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
        addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
        // 对应第18点：如果新子节点集合的start指针大于end指针，则认为旧子节点集合的start到end之间的节点是需要删除的节点，直接删除。
        removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
}

参考文章：https://blog.csdn.net/xiaolu567/article/details/126314478
参考文章：https://www.cnblogs.com/wind-lanyan/p/9061684.html

react的diff

逻辑判断步骤：

1，react的diff分为tree级，component级别和element级别。
2，tree级中，diff只在同层级比较，跨层不比较。
3，component级，react认为两个组件类新相同即为相同组件，否则为不同组件，不同组件不会再向下比较。
4，element级，react对同级元素比较会通过key来比较是否可以复用。
5，具体算法，请参阅下一章：React Diff