虚拟DOM与Diff算法原理

描述
虚拟DOM（Virtual DOM）是一种用JavaScript对象来描述真实DOM结构的编程概念。当应用状态变化时，框架会创建一个新的虚拟DOM树，然后通过Diff算法比较新旧两棵虚拟DOM树的区别，最后只将发生变化的部分更新到真实DOM上，以此提高渲染效率。

解题过程

1. 为什么需要虚拟DOM？

   • 真实DOM操作非常昂贵：直接操作DOM会引起重排和重绘，频繁操作会导致性能问题
   • 虚拟DOM是轻量级的JavaScript对象，操作成本远低于真实DOM
   • 通过批量更新和最小化DOM操作来优化性能

2. 虚拟DOM的基本表示

   // 虚拟DOM节点的基本结构
   const vnode = {
     tag: 'div',        // 标签名
     props: {           // 属性对象
       id: 'app',
       className: 'container'
     },
     children: [        // 子节点数组
       {
         tag: 'span',
         props: { style: { color: 'red' } },
         children: ['Hello World']
       }
     ]
   }
   

3. Diff算法的核心思想

   • 同级比较：只比较同一层级的节点，不跨层级比较
   • Key的作用：通过key标识节点的唯一性，提高复用效率
   • 类型差异：如果节点类型改变，直接替换整个节点

4. Diff算法的具体步骤

   步骤1：节点类型比较

   • 如果新旧节点标签类型不同（如div变为p），直接替换整个节点
   • 如果类型相同，进入属性比较阶段

   步骤2：属性更新

   // 比较新旧节点的属性差异
   function updateProps(oldVnode, newVnode) {
     const oldProps = oldVnode.props || {}
     const newProps = newVnode.props || {}
   
     // 移除旧属性
     for (let key in oldProps) {
       if (!(key in newProps)) {
         // 从DOM中移除该属性
         domNode.removeAttribute(key)
       }
     }
   
     // 更新/添加新属性
     for (let key in newProps) {
       if (oldProps[key] !== newProps[key]) {
         // 设置新的属性值
         domNode.setAttribute(key, newProps[key])
       }
     }
   }
   

   步骤3：子节点比较（核心难点）

   • 采用双指针策略进行高效比较
   • 四种比较情况：

     function updateChildren(parentEl, oldChildren, newChildren) {
       let oldStartIdx = 0, newStartIdx = 0
       let oldEndIdx = oldChildren.length - 1
       let newEndIdx = newChildren.length - 1
     
       while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
         // 情况1：头头比较
         if (isSameVnode(oldChildren[oldStartIdx], newChildren[newStartIdx])) {
           patchVnode(oldChildren[oldStartIdx], newChildren[newStartIdx])
           oldStartIdx++; newStartIdx++
         }
         // 情况2：尾尾比较
         else if (isSameVnode(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
           patchVnode(oldChildren[oldEndIdx], newChildren[newEndIdx])
           oldEndIdx--; newEndIdx--
         }
         // 情况3：头尾比较（节点位置移动）
         else if (isSameVnode(oldChildren[oldStartIdx], newChildren[newEndIdx])) {
           // 将旧头节点移动到末尾
           parentEl.insertBefore(oldChildren[oldStartIdx].el, 
                               oldChildren[oldEndIdx].el.nextSibling)
           oldStartIdx++; newEndIdx--
         }
         // 情况4：尾头比较（节点位置移动）
         else if (isSameVnode(oldChildren[oldEndIdx], newChildren[newStartIdx])) {
           // 将旧尾节点移动到开头
           parentEl.insertBefore(oldChildren[oldEndIdx].el, 
                               oldChildren[oldStartIdx].el)
           oldEndIdx--; newStartIdx++
         }
         // 情况5：key映射查找
         else {
           // 通过key建立映射表，查找可复用的节点
           const keyIndex = createKeyToIdxMap(newChildren, newStartIdx, newEndIdx)
           const oldKey = getKey(oldChildren[oldStartIdx])
     
           if (keyIndex.has(oldKey)) {
             const idxInNew = keyIndex.get(oldKey)
             const vnodeToMove = oldChildren[oldStartIdx]
     
             // 移动节点到正确位置
             parentEl.insertBefore(vnodeToMove.el, oldChildren[oldStartIdx].el)
             patchVnode(vnodeToMove, newChildren[idxInNew])
           } else {
             // 创建新节点
             createEl(newChildren[newStartIdx], parentEl, oldChildren[oldStartIdx].el)
           }
           oldStartIdx++; newStartIdx++
         }
       }
     
       // 处理剩余节点
       if (oldStartIdx > oldEndIdx) {
         // 添加新节点
         for (let i = newStartIdx; i <= newEndIdx; i++) {
           createEl(newChildren[i], parentEl)
         }
       } else if (newStartIdx > newEndIdx) {
         // 移除旧节点
         for (let i = oldStartIdx; i <= oldEndIdx; i++) {
           parentEl.removeChild(oldChildren[i].el)
         }
       }
     }
     

5. 性能优化策略

   • Key的重要性：正确的key可以帮助算法准确识别节点身份，避免不必要的重新渲染
   • 批量更新：将多次DOM操作合并为一次，减少重排重绘
   • 组件级别优化：通过shouldComponentUpdate或memo避免不必要的虚拟DOM计算

通过这种精细的差异比较策略，虚拟DOM Diff算法能够以接近O(n)的时间复杂度完成节点更新，在大规模DOM操作场景下显著提升性能。