Consider the following questions
- What is the role of key in vUE?
- What is the difference between using key and not using key?
- Why would V-for use a unique key?
Let’s discuss the above questions one by one
Key is the unique ID of each Vnode, which is also an optimization strategy of the DIff algorithm. The corresponding VNode can be found more accurately and quickly according to the keyCopy the codeIf keys are not used, Vue uses an algorithm to minimize element movement and tries to modify/reuse elements of the same type in place as much as possible. When keys are used, it rearranges elements based on key order changes, and elements that use keys that no longer exist are removed/destroyed.Copy the codeChild elements that have the same parent element must have a unique key. Duplicate keys cause render errors.Copy the codeReading the above answers you may still have some doubts
- Key is an optimization strategy of diff algorithm, how to optimize?
- What’s the difference between a diff algorithm with and without a key?
- Why does V-for recommend using the unique ID returned as key instead of index?
He who knows does not know what he has. Here, hungry readers take a look at the Diff algorithm
To understand these questions we first need to know
The diff algorithm
Diff algorithm is the difference search algorithm.Copy the codeVue’s DIff policy
1. The traditional time complexity of calculating the difference between two trees is O(n^3), 2. In VUE, the nodes of the tree are compared at the same level, so the time complexity is O(n).Copy the codeWhat strategy is the Vue Diff algorithm based on
1. In Web UI, DOM node movement across hierarchies is rare and can be ignored (tree-diff) 2. Two components with the same class will generate similar tree structures, and two components with different classes will generate different tree nodes (Component diff) 3. For a group of children at the same level, they can be distinguished by unique ids (element-diff)Copy the codeThe reason and purpose of Vue Diff algorithm
1. It is used to calculate the minimum changes that need to be changed by comparing old and new nodes. 2. Core idea: reuse old nodes as much as possible (the cost of creating new DOM nodes and removing old DOM nodes and updating existing DOM nodes is definitely much higher than updating or moving existing DOM nodes)Copy the codeText (vue2 && vue3)
Vue2 diff process
New and old nodes are different
1. Create a new node and insert it into the DOM based on the existing node. 2Copy the codeThe new and old nodes are the same
1. If the two nodes are referenced in the same way, the text node is returned. 2. Only the new node has child nodes. Add contents of the old node in batches. 4. Both have child nodes and update child nodes differently by performing updateChildrenCopy the codeNext, focus on Update Dren
Before I can focus on updateChildren, I need to understand the sameVnode method, which determines whether two nodes are the same node
// see Vue2 source code core/vdom/patch.js
function sameVnode (a, b) {
return (
a.key === b.key && (
(
a.tag === b.tag &&
a.isComment === b.isComment &&
isDef(a.data) === isDef(b.data) &&
sameInputType(a, b)
) || (
isTrue(a.isAsyncPlaceholder) &&
a.asyncFactory === b.asyncFactory &&
isUndef(b.asyncFactory.error)
)
)
)
}
Copy the codeAccording to this method, we can know that the key is the first condition to determine whether two nodes are the same node. Note that if the new and old vNode keys are undefined, then both keys are undefined, and a.key === b.key is valid
In the updateChildren method, this method diff the old and new VNodes and use the result to update the real DOM
// see Vue2 source code core/vdom/patch.js
function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {...while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
if (isUndef(oldStartVnode)) {
...
} else if (isUndef(oldEndVnode)) {
...
} else if (sameVnode(oldStartVnode, newStartVnode)) {
...
} else if (sameVnode(oldEndVnode, newEndVnode)) {
...
} else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right. }else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left. }else {
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) { // New element
createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
oldCh[idxInOld] = undefined
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)
}
}
newStartVnode = newCh[++newStartIdx]
}
}
...
}
Copy the codeIn VUe2, update dren adopts a head-to-tail cross traversal comparison (head-to-head comparison, tail-to-tail comparison, and head-to-tail cross comparison) in a total of four cases. The following is the comparison process of one case. It’s worth noting that Vue updates the DOM while diff, unlike React
If none of those four things happen it goes into the else branch of the while loop
Olddvnode is found by comparing the oldCh array key with the newStartVnode key
Start by creating a map of oldCh using the createKeyToOldIdx method
if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
function createKeyToOldIdx (children, beginIdx, endIdx) {
let i, key
const map = {}
for (i = beginIdx; i <= endIdx; ++i) {
key = children[i].key
if (isDef(key)) map[key] = i
}
return map
}
Copy the codeThis map takes the index values of all oldvNodes that define keys in the array as key values, stores its keys as key names, and assigns them to oldKeyToIdx
idxInOld = isDef(newStartVnode.key) ? oldKeyToIdx[newStartVnode.key] :
findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
function findIdxInOld (node, oldCh, start, end) {
for (let i = start; i < end; i++) {
const c = oldCh[i]
if (isDef(c) && sameVnode(node, c)) return i
}
}
Copy the codeIf the key of newStartVnode exists, oldKeyToIdx can find the index of oldVnode corresponding to newStartVnode based on the key, and oldKeyToIdx can find the index of oldVnode corresponding to newStartVnode based on the index.
If newStartVnode does not have a key, findIdxInOld is used to traverse oldCh to obtain the oldVnode that is the sameVnode of newStartVnode, and the index of this oldVnode in oldCh array is returned
Here are the answers to the first and second questions
1. Key is an optimization strategy of DIFF algorithm. How to optimize it? 2. What is the difference between the diff algorithm with and without keys? When there is a key, we can quickly locate the corresponding oldVnod through map mapping and then patch. When there is no key value, we need to traverse this oldCh array and then compare one by one. By contrast, diff efficiency is definitely higher when there is a key.Copy the codeThen set thekeyThe value is bound to go updiffEfficiency?
// The answer is no
<div v-for="i in arr">{{ i }}</div>
// If our array looks like this
[1.2.3.4.5]
// It renders all keys like this: undefined
<div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>
// Scramble it
[4.1.3.5.2]
// The result is that only the text content of the DOM node is updated during the render
<div>4</div>
<div>1</div>
<div>3</div>
<div>5</div>
<div>2</div>
// If we set a unique key for each entry in the array
[{id: 'A'.value: 1}, {id: 'B'.value: 2}, {id: 'C'.value: 3}, {id: 'D'.value: 4}, {id: 'E'.value: 5}]
// It should render like this
<div>1</div> // key: A
<div>2</div> // key: B
<div>3</div> // key: C
<div>4</div> // key: D
<div>5</div> // key: E
// Scramble it
[{id: 'D'.value: 4}, {id: 'A'.value: 1}, {id: 'C'.value: 3}, {id: 'E'.value: 5}, {id: 'B'.value: 2}]
// The render result is that only DOM node movement occurs during this period
<div>4</div> // key: D
<div>1</div> // key: A
<div>3</div> // key: C
<div>5</div> // key: E
<div>2</div> // key: B
Copy the codeIn the simple template, this situation is special, because the key is not set, so it is undefined. According to the judgment conditions of sameVnode mentioned above, the new and old nodes have the same key, tag and other attributes. It has been determined to be the corresponding node (no more head-to-tail cross-comparison is performed) and then patchVnode is directly implemented without the others. The old node and the new node are corresponding each time in the cycle. DOM update can be completed only by updating the text content in the node, which is undoubtedly the most efficient in situ reuse.
When we set the key, we will execute the following if else according to the result of cross comparison between the head and tail. After judgment, we also need to execute insertBefore and other methods to move the location of real DOM nodes or add and delete DOM nodes. The cost of such lookup reuse is certainly higher than that of in-place reuse without key.
Vue3 diff process
New and old nodes are different
Destroy the old node. 2. Mount different nodes based on the type of the new nodeCopy the codeProcessing components
1. Determine whether the sub-component needs to be updated first; 2. If so, recursively execute the sub-render function of the sub-component to update; 3. Otherwise, just update some vNode properties and let child component instances keep references to component VNodesCopy the codeProcessing elements
There are three types of child nodes: plain text Vnode arrays and emptyCopy the codeThe old node is plain text:
The new node is also a simple replacement. The new node is empty and deleted. The new node is batch added to the Vnode arrayCopy the codeThe old node is empty:
If the new child node is plain text, add the new text node under the parent container of the old child node. If the new child is also empty, then nothing needs to be done. If the new child is a vNode array, just add multiple new children to the parent container of the old child.Copy the codeThe old child nodes are vNode arrays:
If the new child is plain text, delete the old child and add a new text node to the parent container of the old child. If the new child is empty, delete the old child. If the new child is also a VNode array, then you need to do a full diff of the old and new child, which is the most complicated case, Internal use of the core diff algorithmCopy the codeThe old child nodes are vNode arrays:
If the new child is plain text, delete the old child and add a new text node to the parent container of the old child. If the new child is empty, delete the old child. If the new child is also a VNode array, then you need to do a full diff of the old and new child, which is the most complicated case, Internal use of the core diff algorithmCopy the codeBoth old and new nodes are arrays
The comparison between the old and new arrays is accomplished by updating, deleting, adding and removing nodes. The core of the DIff algorithm is to reuse in place and solve the series of operations that generate the DOM of new child nodes. Process: 1. Synchronize the head node 2. Synchronize the tail node 3. Delete redundant nodes. 5. Process unknown subsequencesCopy the codeProcessing unknown subsequences
Sometimes we encounter complex unknown subsequence: for the operations of move, delete, add and update, the most complex is the move operation. The core of Vue for unknown subsequence is to find the minimum value that needs to be moved through the longest increasing subsequence.
Contrast old and new subsequence is needed in finding process, so we must traverse a sequence, if in the process of traversal sequence old need to determine whether a node in the new subsequence exist, this will require a double loop, and the complexity of the double loop is O (n2), in order to optimize this complexity, we can use a space in the thinking of time, index figure, Reduce the time complexity to O(n).
Build index map
2. Then create a mapping between the old and new subsequence indexes to determine the longest increasing subsequence 3. Then it traverses the old subsequence in positive order to see if it is in the index graph of the new subsequence. If it is no longer in the index, it will be deleted. If it is in the longest increasing subsequence, it does not need to move. Then, the new node is marked in the traversal process. For the identifier 0 that is not searched, the operation needs to be addedCopy the code// can be all-keyed or mixed
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
let i = 0
const l2 = c2.length
// Tail index of the old node
let e1 = c1.length - 1
// The tail index of the new node
let e2 = l2 - 1
// Start synchronization from the header
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
if (isSameVNodeType(n1, n2)) {
// If it is the same node, perform patch recursively to update the node
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// Otherwise, the loop is broken
break
}
i++
}
// Synchronize the tail nodes from the tail
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = (c2[e2] = optimized ? cloneIfMounted(c2[e2] as VNode) : normalizeVNode(c2[e2]))
if (isSameVNodeType(n1, n2)) {
// If it is the same node, perform patch recursively to update the node
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else {
// Otherwise, the loop is broken
break
}
e1--
e2--
}
// The new child node has new nodes left to add
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
// Old child nodes, with extra nodes to delete
}else if (i > e2) {
while (i <= e1) {
// Delete redundant nodes
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
// Unknown subsequences are complicated
}else {
// The old subsequence is indexed from I
const s1 = i
// the new subsequence starts indexing from I
const s2 = i
// Build the index graph of the new subsequence based on the key
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map(a)for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized ? cloneIfMounted(c2[i] as VNode) : normalizeVNode(c2[i]))
if(nextChild.key ! =null) {
if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {
warn(
`Duplicate keys found during update:`.JSON.stringify(nextChild.key),
`Make sure keys are unique.`)}// key corresponds to I
keyToNewIndexMap.set(nextChild.key, i)
}
}
// loop through the old subsequence patch
let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
// Is used to trace whether a node has moved
let maxNewIndexSoFar = 0
// This array is used to store the index of the elements in the new subsequence at the node of the old subsequence, which is used to determine the longest increment subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
/* * Initializes the array, each element is 0, 0 is a special value, if the traversal is still 0, the new node has no corresponding old node */
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// Loop over the old child node
for (i = s1; i <= e1; i++) {
// Each old subsequence node
const prevChild = c1[i]
// toBePatched indicates the length of a new subsequence
if (patched >= toBePatched) {
// All nodes of the new subsequence have been updated, and the remaining nodes of the old subsequence have been deleted
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if(prevChild.key ! =null) {
// Find the index of the node in the old subsequence in the new subsequence
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if ( newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j] as VNode)) {
newIndex = j
break}}}// Delete the node from the old subsequence if it is not found
if (newIndex === undefined) {
unmount(prevChild, parentComponent, parentSuspense, true)}else {
/* The index of the new subsequence is offset by 1 to avoid the special case where I is 0, which affects the solution of the longest increasing subsequence */
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar will always store the newIndex of the last evaluation
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// Update matched nodes in the old and new subsequences
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
// Loop over the old node
/* Moved to TRUE to calculate the longest incremented subsequence, which is the most complex algorithm newIndexToOldIndexMap: [5, 3, 4, 0] the value stored in the old subsequence index 5 is moved to the end of 4, 0 is occupied, If newIndexToOldIndexMap is [5, 3, 4, 0], then the longest incrementing subsequence [1,2] contains the index */
const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : EMPTY_ARR
j = increasingNewIndexSequence.length - 1
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else if (moved) {
if (j < 0|| i ! == increasingNewIndexSequence[j]) { move(nextChild, container, anchor, MoveType.REORDER) }else {
j--
}
}
}
}
}
Copy the codeCheck whether the node is the same
isSameVNodeType(n1: VNode, n2: VNode): boolean {
if (
__DEV__ &&
n2.shapeFlag & ShapeFlags.COMPONENT &&
hmrDirtyComponents.has(n2.type as ConcreteComponent)
) {
// HMR only: if the component has been hot-updated, force a reload.
return false
}
return n1.type === n2.type && n1.key === n2.key
}
Copy the codeconclusion
It can be seen from the code that key is a crucial factor in the method to determine whether it is the same node, no matter vue2’s updateChildren or Vue3’s patchKeyedChildren. Setting the key enables you to quickly and accurately find the oldVnode corresponding to newVnode, improving DIFF efficiency
Now for the third question: Why does V-for recommend using the unique ID returned as key instead of index?
Let’s look at this example
const carList = [
{ car:'BMW' },
{ car:'Benz' },
{ car:'Audi' },
{ car:'HongQi'},
{ car:'BYD' },
]
<div v-for="(item,index) in carList " :key="index">{{item.car}}</div> code generation5Div the key of each div is the corresponding index.0 car:BMW
div key:1 car:Benz
div key:2 car:Audi
div key:3 car:HongQi
div key:4Car :BYD if the data returned by the back end suddenly adds a line in the middle of the data like carList becomes carList = [{car:'BMW' },
{ car: 'Rolls-Royce'}
{ car:'Benz' },
{ car:'Audi' },
{ car:'HongQi'},
{ car:'BYD'},] If we use index as the key, the idea is that we should be able to reuse everything except the newly added element. This is also in line with the principle advocated by VUE to reuse as many existing elements as possible. You will find that except for the first key0As a result, the diff algorithm of the virtual DOM finds that the nodes with the same key value will be re-rendered if the content is inconsistent during comparison, thus losing the performance advantage of the virtual DOM. If the returned id is key, the carList becomes: carList = [{car:'BMW'The id:1 },
{ car:'Benz'Id:2 },
{ car:'Audi'Id:3 },
{ car:'HongQi'Id:4 },
{ car:'BYD'Id:5}] code generation5Div The key for each div is the corresponding ID:1 car:BMW
div key:2 car:Benz
div key:3 car:Audi
div key:4 car:HongQi
div key:5Car :BYD even if an insert such as carList is changed to carList = [{car:'BMW'The id:1 },
{ car: 'Rolls-Royce'The id:5}
{ car:'Benz'Id:2 },
{ car:'Audi'Id:3 },
{ car:'HongQi'Id:4 },
{ car:'BYD'Id:5}] Diff algorithm found that the original nodes with the same key had the same content and were completely reused, just rendering an inserted data, which also made use of the performance advantages of virtual DOMCopy the code