The diff algorithm
Before we talk about the Diff algorithm, let’s create some data that we need to test
// the h function to create the virtual DOM
function h(type, props, children, key) {
return {
type,
props,
children,
key,
};
}
// Test data
// Old child node
const v1 = [
h("div".null["a"]),
h("div".null["b"]),
h("div".null["c"]),
h("div".null["d"]]),// New child node
const v2 = [
h("div".null["d"]),
h("div".null["a"]),
h("div".null["b"]),
h("div".null["c"]),
h("div".null["e"]]),Copy the codeDiff algorithm without adding keys
- Here I made some modifications to the vue source code, deleted some parameters, and changed some operations to print, which is easy to understand.
// This method is used for diff when there is no key
const patchUnkeyedChildren = (c1, c2) = > {
// c1 old node array, c1 new node array
c1 = c1 || []
c2 = c2 || []
const oldLength = c1.length
const newLength = c2.length
// Get two values of smaller array lengths as end-of-loop conditions
const commonLength = Math.min(oldLength, newLength)
let i;
for (i = 0; i < commonLength; i++) {
// patch the old and new arrays with the same subscript
console.log(`patch The ${JSON.stringify(c1[i]) + "" + JSON.stringify(c2[i])}`)}if (oldLength > newLength) {
// The old array is longer
// Remove the element after the old array
console.log(`ummount The ${JSON.stringify(c1.slice(i))}`)}else {
// The new array is longer
console.log(`mountChildren The ${JSON.stringify(c2.slice(i))}`)}}// Use patchUnkeyedChildren to test the method
patchUnkeyedChildren(v1, v2)
// Print the result
patch {"type":"div"."props":null."children": ["a"]} {"type":"div"."props":null."children": ["d"]}
patch {"type":"div"."props":null."children": ["b"]} {"type":"div"."props":null."children": ["a"]}
patch {"type":"div"."props":null."children": ["c"]} {"type":"div"."props":null."children": ["b"]}
patch {"type":"div"."props":null."children": ["d"]} {"type":"div"."props":null."children": ["c"]}
mountChildren [{"type":"div"."props":null."children": ["e"]}]
Copy the code- It can be seen that when key is not used, diff algorithm will only patch the old and new nodes with the same subscripts. If the element is added or deleted at the back of the array, there is no problem. However, if the location of the child nodes is moved, the patch of the same node cannot be made, and the efficiency is low.
Diff algorithm with a key
- Similarly, I’ve simplified the diff algorithm for keys
// The diff algorithm is used to determine whether two nodes satisfy the SameVNodeType
Return true if the type and key of the node are the same, false otherwise
function isSameVNodeType(n1, n2) {
return n1.type === n2.type && n1.key === n2.key;
}
const patchKeyedChildren = (c1, c2) = > {
let i = 0;
const l2 = c2.length; // The length of the new node array
let e1 = c1.length - 1; // The last element of the old node
let e2 = l2 - 1; // The last element of the new node
// 1. The preceding nodes are the same
// for example :(a b) c becomes (a b) d e
while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = c2[i];
if (isSameVNodeType(n1, n2)) {
// If the type and key of the new and old nodes are the same, patch the two nodes
console.log(`patch The ${JSON.stringify(n1) + "" + JSON.stringify(n2)}`);
} else {
// If either type or key is different, break the while loop
break;
}
// Change I
i++;
}
// 2. The following nodes are the same
// For example a (b c) becomes d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = c2[e2];
if (isSameVNodeType(n1, n2)) {
// If the type and key of the new and old nodes are the same, patch the two nodes
console.log(`patch The ${JSON.stringify(n1) + JSON.stringify(n2)}`);
} else {
// If either type or key is different, break the while loop
break;
}
// Make the subscript of the last element of the old node array and new node array --
e1--;
e2--;
}
if (i > e1) {
if (i <= e2) {
// If you just add the node at the end, it will come here, just mount the new node
while (i <= e2) {
console.log(`mount The ${JSON.stringify(c2[i])}`); i++; }}}else if (i > e2) {
// If you just delete the following nodes, you will get here, just uninstall the unnecessary nodes.
while (i <= e1) {
console.log(`unmount The ${JSON.stringify(c1[i])}`); i++; }}// If it is a complex change
For example from a b [c d e] f g to a b [e d c h] f g
Diff = diff = diff = diff
else {
const s1 = i; // The first node index of the old node array that has not been processed
const s2 = i; // The first node index of the new node array that has not yet been processed
// Create a map of the keys and indexes of the nodes in the new array that have not yet been processed
const keyToNewIndexMap = new Map(a);for (i = s2; i <= e2; i++) {
// Loop through the new array, saving the mapping between key and index to the keyToNewIndexMap
const nextChild = c2[i];
if(nextChild.key ! =null) { keyToNewIndexMap.set(nextChild.key, i); }}let j;
let patched = 0; // Number of nodes patched
const toBePatched = e2 - s2 + 1; // How many nodes are left to be patched
let moved = false; // Record whether the node position needs to be moved, default is not required.
// maxNewIndexSoFar is used to trace whether move is needed
let maxNewIndexSoFar = 0;
// Create an array whose length is the number of times it needs to be patched. This array holds the relationship between the new node and the old node
// The index of the array represents the index of the unprocessed node in the new array minus s2, that is, the index of the unprocessed node starts at 0
// The value of this array is the subscript of the node in the old array that has not been processed by 1. Note: 0 is not in the old array
const newIndexToOldIndexMap = new Array(toBePatched);
// Start by setting all items of newIndexToOldIndexMap to 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;
// Traverses the old array through nodes that have not yet been processed
for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
if (patched >= toBePatched) {
// All new nodes are patched, unmount them directly
console.log(`unmount The ${JSON.stringify(prevChild)}`);
continue;
}
let newIndex;
if(prevChild.key ! =null) {
// The current node has a key
// Obtain the subscript of the node corresponding to the key from the map table according to the key in the new array, save to the newIndex
newIndex = keyToNewIndexMap.get(prevChild.key);
} else {
// The current node does not have a key
// 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])
) {
newIndex = j;
break; }}}if (newIndex === undefined) {
// If newIndex is undefined, that is, there is no node corresponding to the key in the new array, then simply unmount the node.
console.log(`unmount The ${JSON.stringify(prevChild)}`);
} else {// The new array has the node corresponding to the key
// Modify the values in the newIndexToOldIndexMap array
newIndexToOldIndexMap[newIndex - s2] = i + 1;
if (newIndex >= maxNewIndexSoFar) {
// If newIndex is greater than maxNewIndexSoFar, the node does not need to be moved
// Because maxNewIndexSoFar stores the maximum index that appears in the new array during traversal.
// If newIndex is always larger than maxNewIndexSoFar, the order of the nodes remains the same. Other nodes may be inserted, but the overall order remains the same
// Assign newIndex to maxNewIndexSoFar
maxNewIndexSoFar = newIndex;
} else {
// If newIndex > maxNewIndexSoFar, then the position of the node in the old array needs to be moved in the new array
// Change the moved variable to true
moved = true;
}
// Patch the two nodes with the same key
console.log(
`patch The ${JSON.stringify(prevChild) + "" + JSON.stringify(c2[newIndex])
}`); patched++; }}// After traversing the old array, you just need to move and mount the nodes of the new array
// If you need to move, that is, moved is true
// Then the longest increasing subsequence of the newIndexToOldIndexMap array
// Find the longest increasing subsequence and move based on that sequence
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: [];
// j holds the longest increasing subsequence of length -1
j = increasingNewIndexSequence.length - 1;
for (i = toBePatched - 1; i >= 0; i--) {
// The new array has not been processed by the end of the patch section
const nextIndex = s2 + i;
const nextChild = c2[nextIndex];
if (newIndexToOldIndexMap[i] === 0) {
// If the node does not exist in the old array, mount it
console.log(`mount The ${JSON.stringify(nextChild)}`);
} else if (moved) {
/ / version to true
/ / if j < 0 or I is not equal to increasingNewIndexSequence [j], you need to move
if (j < 0|| i ! == increasingNewIndexSequence[j]) {console.log(`move The ${JSON.stringify(nextChild)}`);
} else {
// j--j--; }}}}};Copy the code// Test the diff algorithm with key
/ / data
const v1 = [
h("div".null["a"].'a'),
h("div".null["b"].'b'),
h("div".null["c"].'c'),
h("div".null["d"].'d'),
h("div".null["e"].'e'),
h("div".null["f"].'f'),
h("div".null["g"].'g')];const v2 = [
h("div".null["a"].'a'),
h("div".null["b"].'b'),
h("div".null["e"].'e'),
h("div".null["d"].'d'),
h("div".null["c"].'h'),
h("div".null["f"].'f'),
h("div".null["g"].'g')]; patchKeyedChildren(v1, v2)// Print the result
patch {"type":"div"."props":null."children": ["a"]."key":"a"} {"type":"div"."props":null."children": ["a"]."key":"a"}
patch {"type":"div"."props":null."children": ["b"]."key":"b"} {"type":"div"."props":null."children": ["b"]."key":"b"}
patch {"type":"div"."props":null."children": ["g"]."key":"g"} {"type":"div"."props":null."children": ["g"]."key":"g"}
patch {"type":"div"."props":null."children": ["f"]."key":"f"} {"type":"div"."props":null."children": ["f"]."key":"f"}
unmount {"type":"div"."props":null."children": ["c"]."key":"c"}
patch {"type":"div"."props":null."children": ["d"]."key":"d"} {"type":"div"."props":null."children": ["d"]."key":"d"}
patch {"type":"div"."props":null."children": ["e"]."key":"e"} {"type":"div"."props":null."children": ["e"]."key":"e"}
mount {"type":"div"."props":null."children": ["c"]."key":"h"}
move {"type":"div"."props":null."children": ["e"]."key":"e"}
Copy the codeNow that you know the general idea of the diff algorithm, you can see why index is not recommended
- Using index as the key, since index is changeable, as long as the index is the same, then the key is the same, because no matter what the length of the old and new array is the same index, that is, the key is the same, so that the effect of adding key and not adding key is the same.