date
type
status
slug
summary
tags
category
password
icon
双端diff算法
在上述例子中，使用简单diff算法真实 DOM 节点会
移动两次
，但是实际上通过简单的观察可以发现只需要移动一次p-3就可以。
所以得出结论：简单diff算法的性能在某些场景下并不是最好的。对于上述的例子，使用双端diff算法的性能会更高。
双端diff算法比较原理
双端diff是一种对新旧两组子节点的端点进行比较的算法。
在双端比较中，每一轮比较都分为四个步骤。
- 第一步：比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的第一个子节点 p-4，看它们是否相同。这里不相同，什么都不做。
- 第二步：比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的最后一个子节点 p-3，看它们是否相同。这里不相同，什么都不做。
- 第三步：比较旧的一组子节点中的第一个子节点 p-1 与新的一组子节点中的最后一个子节点 p-3，看它们是否相同。这里不相同，什么都不做。
- 第四步：比较旧的一组子节点中的最后一个子节点 p-4 与新的一组子节点中的第一个子节点 p-4。由于它们key相同，所以可以进行 DOM 复用。
思考下，p-4节点所对应的真实 DOM 此时应该如何移动？代码如何实现？
非理想状况的处理方式
在进行双端比较中，可能会出现第一轮比较时，无法找到可以复用的节点。
在这种情况下，需要尝试非头部，尾部的节点能否复用。可以用新的一组子节点去旧的一组子节点去寻找。
这里拿新的一组子节点的头部节点p-2去旧的一组子节点中查找时，会在索引为1的位置找到可复用的节点。说明p-2旧子节点对应的真实 DOM 需要移动到旧子节点 p-1 所对应的真实 DOM 之前。
已经处理过的旧子节点后续不用继续比较，这里设置为undefined。然后开始进行双端比较。在这一轮的比较第四步，找到了可复用的节点。所以将真实 DOM 中的p-4移动到p-1的前面，并且更新对应指针。
在这一轮比较的第一步就找到了可复用的节点，不需要移动 DOM 节点，并更新指针。
在这一轮比较中发现旧子节点中头部节点为undefined。不用比较，直接跳过。
继续进行比较，发现第一轮比较就可以找到复用节点。不需要移动 DOM，更新指针。这时满足循环停止条件，双端比较结束。
- 作者:NotionNext
- 链接:https://tangly1024.com/article/803eda4a-8f59-4c46-a8a4-e63c0c4bb020
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。