SlhwSR

1. What is it#

Consistent with Vue, React introduces the concept of Virtual DOM to greatly avoid unnecessary DOM operations, which greatly improves the efficiency of building our pages.

And the diff algorithm is to more efficiently find the real DOM changes by comparing the new and old Virtual DOM.

Traditional diff algorithms compare nodes one by one through loop recursion, which is inefficient and has a complexity of O(n^3). React optimizes the algorithm and reduces the complexity to O(n), as shown in the following figure:

2. Principle#

The diff algorithm in React mainly follows three levels of strategies:

• Tree level

• Component level

• Element level

Tree level#

Operations that involve crossing levels of DOM nodes are not optimized, and only nodes at the same level are compared.

There are only deletion and creation operations, and no movement operations, as shown in the following figure:

React finds that there is no A under the R node in the new tree, so it directly deletes A and creates A and its subordinate nodes under the D node.

In the above operations, only deletion and creation operations are performed.

Component level#

If it is the same class of component, the diff operation will continue recursively. If it is not the same class of component, the component and all its child nodes will be deleted and recreated.

When component D is replaced with component G, even if the structures of the two are very similar, D will be deleted and G will be recreated.

Element level#

For nodes at the same level, each node is identified by a unique key at the corresponding level.

Three types of node operations are provided: INSERT_MARKUP, MOVE_EXISTING, and REMOVE_NODE.

In the following scenario:

Through the key, the nodes in the new and old collections can be accurately identified as the same nodes, so there is no need to delete and create nodes, only the positions of nodes in the old collection need to be moved to the positions of nodes in the new collection.

The process is shown in the following table:

• index: The traversal index of the new collection.
• oldIndex: The index of the current node in the old collection.
• maxIndex: The maximum index in the old collection among the nodes visited in the new collection.

If the position of the current node in the new collection is earlier than that in the old collection, it will not affect the subsequent node operations, so the node does not need to be moved.

During the operation, only oldIndex and maxIndex are compared, and the rules are as follows:

• When oldIndex > maxIndex, assign the value of oldIndex to maxIndex.
• When oldIndex = maxIndex, no operation is performed.
• When oldIndex < maxIndex, move the current node to the position of index.

The diff process is as follows:

• Node B: At this time, maxIndex = 0 and oldIndex = 1; maxIndex < oldIndex is satisfied, so the B node remains unchanged, and maxIndex = Math.max(oldIndex, maxIndex), which is 1.
• Node A: At this time, maxIndex = 1 and oldIndex = 0; maxIndex < oldIndex is not satisfied, so the A node is moved, and maxIndex = Math.max(oldIndex, maxIndex), which is still 1.
• Node D: At this time, maxIndex = 1 and oldIndex = 3; maxIndex < oldIndex is satisfied, so the D node remains unchanged, and maxIndex = Math.max(oldIndex, maxIndex), which is 3.
• Node C: At this time, maxIndex = 3 and oldIndex = 2; maxIndex < oldIndex is not satisfied, so the C node is moved, and the comparison is complete.

After the comparison of ABCD nodes is completed, the diff process is not over yet. The old collection will be traversed as a whole to see if there are any unused nodes, and if so, they will be deleted.

3. Notes#

For simple list rendering, not using key performs better than using key. For example:

Rendering [1,2,3,4,5] as follows:

<div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>

Changing it to [1,3,2,5,4] later, the effects of using key and not using key are as follows:

1. With key
<div key='1'>1</div>             <div key='1'>1</div>     
<div key='2'>2</div>             <div key='3'>3</div>  
<div key='3'>3</div>  ========>  <div key='2'>2</div>  
<div key='4'>4</div>             <div key='5'>5</div>  
<div key='5'>5</div>             <div key='4'>4</div>  
Operation: Node 2 is moved to index 2, and node 4 is moved to index 4.

2. Without key
<div>1</div>             <div>1</div>     
<div>2</div>             <div>3</div>  
<div>3</div>  ========>  <div>2</div>  
<div>4</div>             <div>5</div>  
<div>5</div>             <div>4</div>  
Operation: Modify the innerText of the 1st to 5th nodes.

If we perform add and delete operations on this collection and change it to [1,3,2,5,6]

1. With key
<div key='1'>1</div>             <div key='1'>1</div>     
<div key='2'>2</div>             <div key='3'>3</div>  
<div key='3'>3</div>  ========>  <div key='2'>2</div>  
<div key='4'>4</div>             <div key='5'>5</div>  
<div key='5'>5</div>             <div key='6'>6</div>  
Operation: Node 2 is moved to index 2, node 6 is added to index 4, and node 4 is deleted.

2. Without key
<div>1</div>             <div>1</div>     
<div>2</div>             <div>3</div>  
<div>3</div>  ========>  <div>2</div>  
<div>4</div>             <div>5</div>  
<div>5</div>             <div>6</div> 
Operation: Modify the innerText of the 1st to 5th nodes.

Since the cost of moving dom nodes is relatively high, the performance without key is better than that with key.