Virtual DOM and Diff Algorithm Principles

Description
Virtual DOM (Virtual DOM) is a programming concept that uses JavaScript objects to describe the structure of the real DOM. When the application state changes, the framework creates a new virtual DOM tree, then uses the Diff algorithm to compare the differences between the old and new virtual DOM trees, and finally updates only the changed parts to the real DOM, thereby improving rendering efficiency.

Problem-Solving Process

1. Why is Virtual DOM Needed?

   • Real DOM operations are very expensive: Direct DOM manipulation triggers reflow and repaint, and frequent operations cause performance issues.
   • Virtual DOM is a lightweight JavaScript object, and its operation cost is much lower than that of the real DOM.
   • Optimizes performance through batch updates and minimizing DOM operations.

2. Basic Representation of Virtual DOM

   // Basic structure of a virtual DOM node
   const vnode = {
     tag: 'div',        // Tag name
     props: {           // Properties object
       id: 'app',
       className: 'container'
     },
     children: [        // Array of child nodes
       {
         tag: 'span',
         props: { style: { color: 'red' } },
         children: ['Hello World']
       }
     ]
   }
   

3. Core Idea of the Diff Algorithm

   • Same-Level Comparison: Only compares nodes at the same level; does not compare across levels.
   • Role of Key: Uses a key to identify the uniqueness of a node, improving reuse efficiency.
   • Type Differences: If the node type changes, the entire node is replaced directly.

4. Specific Steps of the Diff Algorithm

   Step 1: Node Type Comparison

   • If the tag types of the old and new nodes differ (e.g., div changes to p), replace the entire node directly.
   • If the types are the same, proceed to the property comparison stage.

   Step 2: Property Updates

   // Compare property differences between old and new nodes
   function updateProps(oldVnode, newVnode) {
     const oldProps = oldVnode.props || {}
     const newProps = newVnode.props || {}
   
     // Remove old properties
     for (let key in oldProps) {
       if (!(key in newProps)) {
         // Remove the property from the DOM
         domNode.removeAttribute(key)
       }
     }
   
     // Update/Add new properties
     for (let key in newProps) {
       if (oldProps[key] !== newProps[key]) {
         // Set the new property value
         domNode.setAttribute(key, newProps[key])
       }
     }
   }
   

   Step 3: Child Node Comparison (Core Difficulty)

   • Uses a double-pointer strategy for efficient comparison.
   • Four comparison scenarios:

     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) {
         // Scenario 1: Head-to-head comparison
         if (isSameVnode(oldChildren[oldStartIdx], newChildren[newStartIdx])) {
           patchVnode(oldChildren[oldStartIdx], newChildren[newStartIdx])
           oldStartIdx++; newStartIdx++
         }
         // Scenario 2: Tail-to-tail comparison
         else if (isSameVnode(oldChildren[oldEndIdx], newChildren[newEndIdx])) {
           patchVnode(oldChildren[oldEndIdx], newChildren[newEndIdx])
           oldEndIdx--; newEndIdx--
         }
         // Scenario 3: Head-to-tail comparison (node position movement)
         else if (isSameVnode(oldChildren[oldStartIdx], newChildren[newEndIdx])) {
           // Move the old head node to the end
           parentEl.insertBefore(oldChildren[oldStartIdx].el, 
                               oldChildren[oldEndIdx].el.nextSibling)
           oldStartIdx++; newEndIdx--
         }
         // Scenario 4: Tail-to-head comparison (node position movement)
         else if (isSameVnode(oldChildren[oldEndIdx], newChildren[newStartIdx])) {
           // Move the old tail node to the beginning
           parentEl.insertBefore(oldChildren[oldEndIdx].el, 
                               oldChildren[oldStartIdx].el)
           oldEndIdx--; newStartIdx++
         }
         // Scenario 5: Key mapping lookup
         else {
           // Create a mapping table via keys to find reusable nodes
           const keyIndex = createKeyToIdxMap(newChildren, newStartIdx, newEndIdx)
           const oldKey = getKey(oldChildren[oldStartIdx])
     
           if (keyIndex.has(oldKey)) {
             const idxInNew = keyIndex.get(oldKey)
             const vnodeToMove = oldChildren[oldStartIdx]
     
             // Move the node to the correct position
             parentEl.insertBefore(vnodeToMove.el, oldChildren[oldStartIdx].el)
             patchVnode(vnodeToMove, newChildren[idxInNew])
           } else {
             // Create a new node
             createEl(newChildren[newStartIdx], parentEl, oldChildren[oldStartIdx].el)
           }
           oldStartIdx++; newStartIdx++
         }
       }
     
       // Handle remaining nodes
       if (oldStartIdx > oldEndIdx) {
         // Add new nodes
         for (let i = newStartIdx; i <= newEndIdx; i++) {
           createEl(newChildren[i], parentEl)
         }
       } else if (newStartIdx > newEndIdx) {
         // Remove old nodes
         for (let i = oldStartIdx; i <= oldEndIdx; i++) {
           parentEl.removeChild(oldChildren[i].el)
         }
       }
     }
     

5. Performance Optimization Strategies

   • Importance of Key: Correct keys help the algorithm accurately identify node identity, avoiding unnecessary re-renders.
   • Batch Updates: Consolidate multiple DOM operations into one, reducing reflow and repaint.
   • Component-Level Optimization: Use shouldComponentUpdate or memo to avoid unnecessary virtual DOM calculations.

Through this fine-grained difference comparison strategy, the Virtual DOM Diff algorithm can update nodes with a time complexity close to O(n), significantly improving performance in large-scale DOM operation scenarios.