React实现核心Diff算法的示例代码.docx
第
React实现核心Diff算法的示例代码
目录Diff算法的设计思路Demo介绍Diff算法实现遍历前的准备工作遍历after遍历后的收尾工作总结
Diff算法的设计思路
试想，Diff算法需要考虑多少种情况呢？大体分三种，分别是：
节点属性变化，比如：
//更新前
likey=0className=before0/li
likey=11/li
/ul
//更新后
likey=0className=after0/li
likey=11/li
/ul
节点增删，比如：
//更新前
likey=00/li
likey=11/li
likey=22/li
/ul
//更新后情况1——新增节点
likey=00/li
likey=11/li
likey=22/li
likey=33/li
/ul
//更新后情况2——删除节点
likey=00/li
likey=11/li
/ul
节点移动，比如：
//更新前
likey=00/li
likey=11/li
/ul
//更新后
likey=11/li
likey=00/li
/ul
该如何设计Diff算法呢？考虑到只有以上三种情况，一种常见的设计思路是：
首先判断当前节点属于哪种情况如果是增删，执行增删逻辑如果是属性变化，执行属性变化逻辑如果是移动，执行移动逻辑
按这个方案，其实有个隐含的前提不同操作的优先级是相同的。但在日常开发中，节点移动发生较少，所以Diff算法会优先判断其他情况。
基于这个理念，主流框架（React、Vue）的Diff算法都会经历多轮遍历，先处理常见情况，后处理不常见情况。
所以，这就要求处理不常见情况的算法需要能给各种边界case兜底。
换句话说，完全可以仅使用处理不常见情况的算法完成Diff操作。主流框架之所以没这么做是为了性能考虑。
本文会砍掉处理常见情况的算法，保留处理不常见情况的算法。
这样，只需要40行代码就能实现Diff的核心逻辑。
Demo介绍
首先，我们定义虚拟DOM节点的数据结构：
typeFlag=Placement|Deletion;
interfaceNode{
key:string;
flag:Flag;
index:number;
}
key是node的唯一标识，用于将节点在变化前、变化后关联上。
flag代表node经过Diff后，需要对相应的真实DOM执行的操作，其中：
Placement对于新生成的node，代表对应DOM需要插入到页面中。对于已有的node，代表对应DOM需要在页面中移动Deletion代表node对应DOM需要从页面中删除
index代表该node在同级node中的索引位置
注：本Demo仅实现为node标记flag，没有实现根据flag执行DOM操作。
我们希望实现的diff方法，接收更新前与更新后的NodeList，为他们标记flag：
typeNodeList=Node[];
functiondiff(before:NodeList,after:NodeList):NodeList{
//...代码
}
比如对于：
//更新前
constbefore=[
{key:a}
//更新后
constafter=[
{key:d}
//diff(before,after)输出
{key:d,flag:Placement},
{key:a,flag:Deletion}
]
{key:d,flag:Placement}代表d对应DOM需要插入页面。
{key:a,flag:Deletion}代表a对应DOM需要被删除。
执行后的结果就是：页面中的a变为d。
再比如：
//更新前
constbefore=[
{key:a},
{key:b},
{key:c},
//更新后
constafter=[
{key:c},
{key:b},
{key:a}
//diff(before,after)