Diff 算法是用于比较两个虚拟 DOM 树的差异，并以最小的操作代价将旧的 DOM 树更新为新的 DOM 树的一种算法。
Diff 算法的高效实现对于提高前端应用的性能和用户体验至关重要，尤其是在频繁更新组件状态导致 DOM 频繁更新的情况下。
1. 原理
1.1 树层级比较
首先，比较新旧两棵树的根节点。如果根节点的类型不同，直接替换整个旧根节点及其子树。
1.2 节点类型相同的比较
比较节点的属性（如 id、class 等），如果属性有变化，更新相应的属性。
1.3 子节点列表比较
对新旧节点的子节点列表进行比较。
常见的策略有双指针比较、key 值比较等。
双指针比较：从新旧子节点列表的头部和尾部同时开始比较。
key 值比较：如果子节点设置了 key 属性，通过 key 来快速找到对应的节点进行比较和更新。
1.4 处理新增和删除
如果新节点列表中有新增的节点，将其添加到适当的位置。
如果旧节点列表中有不再存在于新列表中的节点，将其删除。
1.5 最小化操作
算法的目标是尽量减少 DOM 操作，例如尽量通过修改节点属性而不是删除和重新创建节点来更新 DOM。
2. 实现
通过 js 实现一个简单的 diff 算法
function diff(oldArray, newArray) {
let inserts = [];
let deletes = [];
let oldIndex = 0;
let newIndex = 0;
while (oldIndex < oldArray.length && newIndex < newArray.length) {
if (oldArray[oldIndex] !== newArray[newIndex]) {
if (oldArray[oldIndex] === undefined) {
inserts.push(newArray[newIndex]);
newIndex++;
} else {
deletes.push(oldArray[oldIndex]);
oldIndex++;
}
} else {
oldIndex++;
newIndex++;
}
}
while (oldIndex < oldArray.length) {
deletes.push(oldArray[oldIndex++]);
}
while (newIndex < newArray.length) {
inserts.push(newArray[newIndex++]);
}
return { inserts, deletes };
}
let oldArray = [1, 2, 3, 4, 5];
let newArray = [1, 3, 5, 6, 7];
console.log(diff(oldArray, newArray));
// {
// deletes: (2)[(2, 4)];
// inserts: (2)[(6, 7)];
// }
